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 ...


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.


11

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)$. ...


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

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) = !((!(!(...


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

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

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 ...


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 ...


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

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 ...


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 ...


4

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 forms an extremely simple lattice. It has two elements, $\top$ and $\bot$, with $\bot \sqsubset \top$. The meet corresponds to conjunction (AND), and the join ...


4

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& 1& 1\\ \hline 1 & 1 & 0 & 1 \\ \hline 1 & 0 & 1 & 0 \\ \hline 1 & 0 & 0 & 1 \\ \hline 0 & 1 & 1 & 0 \\...


4

I presume you are looking for a way to prove the identity using a calculus. So far you have used distributivity an idempotency. Recall that A = A1 so you get A1+AB and you can use distributivity again, this time in the other direction. Then two obvious steps.


4

$\exists x\forall y \hspace{1mm}\varphi$ is not equivalent to $\forall y \exists x \hspace{1mm} \varphi$. Consider for example the formula "for all $x$ there exists $y$ such that $y=x^2$". When evaluated over the reals, this is true (every real number has a square). However, if you switch the quantifiers you get the statement "there exists $y$ such that for ...


4

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 such that all the proposed clause's literals are false. E.g. if your proposed clause is $x_1 \lor \lnot{x_2} \lor x_3 \lor \lnot{x_4}$, assign $x_1$ = FALSE, $x_2$...


4

Suppose that $f,g$ were functions satisfying $f(A) g(A) = 1$ and $f(A) g(B) = 0$ if $A \neq B$. Take any $A \neq B$. Then $f(A) g(B) = 0$, and so either $f(A) = 0$ or $g(B) = 0$. If $f(A) = 0$ then $f(A) g(A) = 0$, and if $g(B) = 0$ then $f(B) g(B) = 0$. So no such functions exist.


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