77
votes
Accepted
Why do logic gates behave the way they do?
As stated by user120366, 16 possible 2-input logic gates exist, I've tabulated them for you here:
...
- 690
37
votes
Is it possible to write an AND gate using XOR gates?
You cant.
Since $XOR$ is associative, i.e. $(x_1\oplus x_2)\oplus x_3=x_1\oplus(x_2\oplus x_3)$, you can only implement functions of the form $x_{i_1}\oplus...\oplus x_{i_k}$ where $x_{i_j}\in\{x_1,...
- 13.3k
25
votes
Why do logic gates behave the way they do?
It's easiest to think of $1$ representing a true statement and $0$ representing a false statement. The logic gates then act as truth functions.
Say you put two statements, $p,q$, together to form a ...
- 351
23
votes
Why do logic gates behave the way they do?
I think the questioner has it backwards. If we have a logical function such that
...
- 231
19
votes
Is it possible to write an AND gate using XOR gates?
Hmmm. It can't be done with boolean algebra that's for sure, but I could wire one up physically. The trick is wiring one of the inputs to a power lead of an XOR gate.
...
- 382
17
votes
Accepted
Boolean absorption
Here is one way to prove the first identity:
$$
A \land (A \lor C) = (A \lor 0) \land (A \lor C) = A \lor (0 \land C) = A \lor 0 = A.
$$
The second identity has a similar proof. Alternatively, you ...
- 274k
10
votes
10
votes
Accepted
Boolean algebraic expression vs Propositional logic expression
They are not the same, but I don't blame you for thinking that they are. The reason why it doesn't seem clear that they are the same is that you've only seen one example of each.
So let's step back, ...
- 21.3k
10
votes
Accepted
Absorption Law Proof by Algebra
First of all, this is a math question.
I think you are confused on how brackets are used. They indicate precedence of operations, and can be used anywhere, even in places where such indication is not ...
- 29.9k
9
votes
Why do logic gates behave the way they do?
The why of it actually comes from the development of logic, which is a philosophical study of what is true and what is not true. Logic was originally a study of human language with the assumption that ...
- 669
9
votes
Accepted
Why can't 3-SAT be solved efficiently if you convert all clauses (x ∨ y ∨ z) into (u ∨ z) by introducing a variable?
$u = (a \vee b) \iff
(u \vee \bar{a}) \wedge (u \vee \bar{b}) \wedge (\bar{u} \vee a) \wedge (\bar{u} \vee b) =1 $
Unfortunately, the equivalence above does not hold.
Let $a=\text{false}$, $b=\text{...
- 38.5k
8
votes
Accepted
Proving that $A \vee (\neg A \wedge B) \equiv A \vee B$
Note that
$\qquad A \lor (B \land C) \equiv (A \lor B) \land (A \lor C)$;
you can "multiply out". Add in
$\qquad (A \lor \lnot A) \land B \equiv B$
and you are done.
- 71.9k
8
votes
Accepted
A universal operator necessarily generates $\neg x$ for input $x,…,x$
There are two ways to define a universal operator: when constants are allowed, and when they are not allowed. If constants are allowed, then one can define a universal operator which doesn't satisfy ...
- 274k
7
votes
Accepted
Measuring Complexity of Boolean Satisfiability Problem
The boolean satisfiability problem (SAT) involves finding a satisfying truth assignment for a set of clauses $C$ over the boolean variables $V=\{v_1, v_2, ..., v_n\}$ so that each clause in $C$ ...
- 3,634
7
votes
Accepted
Why are there two not operators in lambda calculus?
The lambda-calculus is confluent. All the terms involved are strongly normalizing (these boolean encodings only work on booleans; they could do anything if applied to a lambda-term that doesn't reduce ...
6
votes
Proving that $A \vee (\neg A \wedge B) \equiv A \vee B$
I'll write your expression as $A\lor(\neg A\land B)$. Then
$$\begin{align}
A\lor B &= A\lor((A\lor\neg A)\land B) &\text{identity}\\
&=A\lor (A\land B)\lor(\neg A\land B) &\text{...
- 14.8k
6
votes
Boolean absorption
Here's one way of thinking how these identities "work". Of the first one, when A is false, A and anything is false; when A is true, A or C is true, and the whole thing is true too; therefore being ...
6
votes
Why is SAT based on the CNF?
Conjunctive normal form first appears, in this context, in Davis and Putnam's A computing procedure for quantification theory, in which they describe a primitive form of the DPLL algorithm (which ...
- 274k
6
votes
Accepted
Prove HAKMEM Item 23: connection between arithmetic operations and bitwise operations on integers
Bitlength and bound needed for two's complement
Prove that for $A, B \in \mathbb{Z}$, $A + B$ $= (A\operatorname{\&}B) + (A \mid B)$ $= (A \oplus B) + 2(A\operatorname{\&}B)$ where $\...
- 38.5k
5
votes
Accepted
Are there any techniques for checking whether a clause is subsumed by another clause when adding it to a cnf formula?
There is a preprocessing method called vivification$^1$ that can be used to detect subsumed clauses. It relies on unit propagation to work.
To vivify a clause, make a partial variable assignment ...
- 8,011
5
votes
Why is Boolean satisfiability such a rare case?
Your trick doesn't really work. There are several issues.
First, your trick shows that for every unsatisfiable circuit of size $n$, there exists a satisfiable circuit of size $n+1$. But that doesn'...
D.W.♦
- 154k
5
votes
Prove HAKMEM Item 23: connection between arithmetic operations and bitwise operations on integers
This answer isn't rigorous or starting from first principles, but I thought this was elegant so here it is anyway.
Given that addition is commutative and associative and bit-shifting all summands left ...
- 1,685
4
votes
Accepted
Classical Computation without NOT
You're confusing classical and quantum computation, so let me ignore the quantum aspects for now. If you forbid the unary NOT gate then you can use a binary NOT gate, say $g(a,b) = \lnot a$. You can ...
- 274k
4
votes
Accepted
What is the XNOR of 3 or more inputs?
There is no standard definition for the XNOR of more than two inputs (indeed, nor is there a standard definition for less than two inputs). Since XNOR is associative, one possible definition is
$$
A_1 ...
- 274k
4
votes
Accepted
What happens to uninterpreted predicates in Ackermann's reduction?
Essentially, you can treat uninterpreted predicates as boolean-valued functions (adding a new boolean sort if necessary) and replace them with boolean variables as you would other functions. For the ...
- 2,178
4
votes
Accepted
Algorithm for simplifying ANF or polynomials?
The algebraic normal form (ANF) is unique. You can't "simplify" the ANF; each formula has a single, unique ANF, and there's only one. Once you've found it, that's it; there's no other, "simpler" ANF ...
D.W.♦
- 154k
4
votes
Measuring Complexity of Boolean Satisfiability Problem
I think you have a misconception. SAT by definition accepts formulas in CNF form, and only in CNF form. Moreover, in practice, SAT solvers all use CNF form.
(You might find some tools that have a ...
D.W.♦
- 154k
4
votes
Relation between Lattice and Boolean Algebra
I would hardly describe a lattice as a generalized form of boolean algebra, since there are many more things that a lattice can describe.
A better description would be to say that boolean algebra ...
- 29.6k
4
votes
How does the following truth table show Y's behaviour?
Giving an example of what Eugene has said, but letting you do your own homework. Let's look at another Truth Table:
$
\begin{array}{|c|c|c|c|}
\hline
a& b & c & \varphi \\ \hline
1 & ...
- 1,483
Only top scored, non community-wiki answers of a minimum length are eligible