77

As stated by user120366, 16 possible 2-input logic gates exist, I've tabulated them for you here: A|B||0|1|2|3|4|5|6|7|8|9|a|b|c|d|e|f -+-++-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- 0|0||0|0|0|0|0|0|0|0|1|1|1|1|1|1|1|1 0|1||0|0|0|0|1|1|1|1|0|0|0|0|1|1|1|1 1|0||0|0|1|1|0|0|1|1|0|0|1|1|0|0|1|1 1|1||0|1|0|1|0|1|0|1|0|1|0|1|0|1|0|1 A and B are the inputs, 0 through f ...


36

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,x_2\}$. This is equivalent to (depending on the parity of the number of instances of $x_1$ and $x_2$) either 0, $x_1$, $x_2$, or $x_1\oplus x_2$, which are not ...


25

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 new statement, $r$. In the case of and (logical conjunction), both $p$ and $q$ must be true for $r$ to be true. In the case of or (logical disjunction), $r$ ...


23

I think the questioner has it backwards. If we have a logical function such that A | B | result ---+---+------- 0 | 0 | 0 0 | 1 | 0 1 | 0 | 0 1 | 1 | 1 then we decide to call that function and because it is obvious that the result is 1 only when A and B are both 1. Similarly for or, exclusive-or, etc. There are 16 ...


19

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. I2 | 0 I1 | | | | \| |/ | |\ / | | .|---| \ / |--------/ \ V / \ / ...


17

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 could use duality to deduce it from the first identity.


14

From that formula? It can be done. But it's easier to start with this one: (using a different notation here) a ^ b = ~(a & b) & (a | b) Ok, now what? Eventually we should derive ~(~(~(a & b) & a) & ~(~(a & b) & b)) (which looks like it has 5 NANDs, but just like the circuit diagram it has a sub-expression which is used twice). ...


9

As Pål GD mentions in his comment, the proof is actually very simple: there are $2^{2^n}$ functions, but only $C_S = S^{O(S)}$ circuits of size at most $S \geq n$. The exact constant in the exponent depends on the exact definition of a circuit. Getting the best exponent requires some rather intricate arguments, together with the assumption $S = \omega(n)$. ...


9

I think you are asking for this proof: A^B = (!A)B + A(!B) = !!((!A)B) + !!(A(!B)) = !(!!A + !B) + !(!A + !!B) = !(A + !B) + !(!A + B) = !((A + !B)(!A + B)) = !(A(!A) + AB + (!A)(!B) + B(!B)) = !(AB + (!A)(!B)) = !(AB)(!(!A)(!B)) = !(AB)(!!A + !!B) = !(AB)(A+B) = !(AB)A + !(AB)B = !!(!(AB)A + !(AB)B) = !((!(!(...


9

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 if you can reason about how human language works you can maybe reason about how reason works. Since the language I'm answering you in English let's use ...


8

Informally, a (programming) language is Turing complete if every computable function has a representation. A general computable function accepts an input of arbitrary size. Boolean functions, on the other hand, accept an input of a fixed size. Hence Boolean functions don't even qualify as potentially Turing-complete. The relevant notion of completeness here ...


8

One way of looking at this is as a consequence of distributivity, where $P+QR\equiv (P+Q)(P+R)$. Then you'll have $$\begin{align} X+(X'Y) &\equiv (X+X')(X+Y)&\text{distributivity}\\ &\equiv T(X+Y)&\text{inverse}\\ &\equiv X+Y&\text{domination} \end{align}$$


8

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.


7

The clauses are not intended to be equivalent, so you shouldn't call it an "equivalent representation in 3-literal clauses." All the reduction requires is that the original formula has at least one satisfying assignment if, and only if, the new formula does. In this case, we have this property: if the original formula was satisfiable, we can choose at least ...


7

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 the claim, as follows: $$ T(x,y,z) = \overline{x \land y} \land z. $$ This is universal since $T(x,y,1)$ is the NAND operator, but $T(0,0,0) = 0$. Now suppose ...


6

The classical example is $$(x_1 \lor y_1) \land (x_2 \lor y_2) \land \cdots \land (x_n \lor y_n)$$ which blows up to $2^n$ terms when converted to a DNF. Most functions have CNF and DNF complexity very large – $\Theta(2^n/n)$ if I remember correctly – and so for random functions there is no blow-up for trivial reasons. Miltersen, Radhakrishnan and Wegener ...


6

Since you already have the diagram answer, easily awailable from wikipedia by typing you question title in Google, as a .png diagram identical to yours, it should be easy for you to find the formula by extracting it from that diagram. Given the definition NAND as $\text{NAND}(A,B)=\overline{AB}\;$: The leftmost gate gives $C=\overline{AB}$; The top gate ...


6

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, define them separately, and then look at some interesting examples. Propositional logic is a branch of mathematics that studies propositions, their truth or ...


6

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{distributive}\\ &=(A\lor (A\land B))\lor(\neg A\land B)\\ &= A\lor(\neg A\land B) &\text{absorption} \end{align}$$


6

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 equal A in both cases. Similarly, the second, when A is true, then A or anything is true; when A is false, A and C is false, and the whole expression is also false....


6

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 necessary. For example, $$3 \times 5 + 8$$ and $$(3 \times 5) + 8$$ are both legitimate expressions and they mean exactly the same thing. Your expression $$(x ...


5

Let's start with some definitions: A literal is either a variable (a positive literal) or the negation of a variable (a negative literal). A clause is a formula which is equivalent to a disjunction of literals. A Horn clause is a formula which is equivalent to a disjunction of literals, at most one of which is positive. Your formula $(P \to Q) \to W$ is ...


5

strictly speaking as YF has answered, finite circuits cannot be Turing complete. however its worth mentioning a lead in response to this question (and maybe what youre looking for) a closely related concept used quite widely in theory where circuits are used to compute functions in a way that is stronger than Turing complete. namely, circuit families. a ...


5

No. It's not possible. Any function that can be computed using just XOR's is affine over $GF(2)$. However, the Euclidean distance is not affine over $GF(2)$, so there is no hope of representing it with just XOR's. Recall that $GF(2)$ denotes the finite field with two elements; you might also see it indicated by $\mathbb{F}_2$, and it is the field $(\{0,1\...


5

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$ contains at least one true literal. Since $V$ contains $n$ variables and each of these variables can only have $2$ different values (i.e., true or false), the total ...


5

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't tell you anything about the relationship between the number of unsatisfiable circuits of size $n$ vs the number of satisfiable circuits of size $n$. And, in ...


4

2 does not hold as stated. All you know is that if you flip the all bits in a given block $B_i$, the output flips. Without additional conditions, I don't think you're guaranteed anything about flipping any individual bit within $B_i$. EDIT: In fact, if $B_1, B_2, \ldots, B_i, \ldots$ represents a maximal set of blocks, then for any $B_i$, there cannot be ...


4

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 also simulate NOT using natural gates: $XOR(a,1) = \lnot a$ (and this gate can even be made reversible!). So this kind of restriction is not really meaningful. ...


4

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 \text{ XNOR } A_2 \text{ XNOR } \cdots \text{ XNOR } A_n = A_1 \text{ XNOR } (A_2 \text{ XNOR } (A_3 \cdots )\cdots). $$ Another reasonable definition defines ...


4

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 given example: Getting rid of $F$ and $G$ first: $$\begin{align*} p(z,f_1)&\wedge f_2=g_1\to p(x_1,y)\wedge x_1=f_1\to f_1=f_2\\ &\wedge x_1=x_2\to ...


Only top voted, non community-wiki answers of a minimum length are eligible