Construct an AND gate from XOR gates

Question

I was able to figure how to make a NOT gate easily enough, but I'm stumped trying to figure out how to make an AND gate. Is it even possible?

Answer 1

No. Due to the both complementary and symmetric nature of XOR's inputs and outputs there is no way to configure any number of them to generate an output that does not exhibit the same symmetry.

Answer 2

The XOR operation is bilinear: inverting either of the inputs always inverts the output.

This property is preserved even if you cascade multiple XOR gates (and, optionally, constant inputs and/or NOT gates) together: inverting any input always inverts the output. Of course, you can construct more complex circuits where a single input can be split and fed into multiple gates, but all such circuits can be expanded into an equivalent tree of XOR gates, possibly with the same input appearing multiple times. For each input, one of the following two cases will then hold:

• if the input value appears an odd number of times in the XOR tree, inverting that input inverts the output;

• if the input value appears an even number of times in the XOR tree, its effects on the output cancel out, and the output ends up being completely independent of that input.

In any case, the only kinds of functions you can construct by combining XOR gates are those where each input either never affects on the output, or will always invert the output when the input is inverted.

Now consider an AND gate: if the first input is 1, the output is equal to the second input, whereas if the first input is 0, the output will always be 0 regardless of the second input. This is impossible to implement with XOR gates: in any XOR-only circuit, toggling the second input should either always change the output or never change it.

All this can be expressed concisely in mathematical terms: XOR is a multilinear operator, and composition of multilinear operators is always multilinear. AND is not a multilinear operator, so it cannot be obtained by combining XOR operators.

Answer 3

Here's a proof that might be a bit easier to picture visually . . .

Since XOR is commutative (p XOR q = q XOR p) and associative (p XOR (q XOR r) = (p XOR q) XOR r), there is no interesting way to re-order or re-structure a formula where XOR is the only gate; something like p XOR ((t XOR (s XOR q)) XOR r) is equivalent to p XOR q XOR r XOR s XOR t.

So if you only have two variables p and q, and the only gate you have is XOR, then your formula can be simplified to the form (p XOR p XOR ... XOR p) XOR (q XOR q XOR ... XOR q). We can simplify p XOR p XOR ... XOR p like so:

# of p's       full version     simplification
   0               FALSE             FALSE
   1                 p                 p
   2              p XOR p            FALSE
   3           p XOR p XOR p           p
   4        p XOR p XOR p XOR p      FALSE
   5     p XOR p XOR p XOR p XOR p     p
   .                 .                 .
   .                 .                 .
   .                 .                 .

. . . and similarly with q XOR q XOR ... XOR q. So there are only four functions that you can compute:

FALSE XOR FALSE          FALSE
FALSE XOR   q              q
  p   XOR FALSE            p
  p   XOR   q           p XOR q

Since you say that you managed to construct a NOT gate, I suppose that you're also allowing yourself to provide a constant input; but as you can see, adding FALSEs will not change the result, adding an even number of TRUEs will not change the result, and adding an odd number of TRUEs will merely invert the result (giving TRUE, NOT p, NOT q, or p XNOR q). None of these possibilities is equivalent to AND.

Answer 4

Any purely combinatorial circuit which consists entirely of XOR gates will, from a combinatorial point of view, compute either the even or odd the parity function for some combination of its inputs and ignore the rest. This may be shown by induction if one observes that each input will be the odd parity function of itself, and the xor of two parity functions will be a parity function of their disjoint inputs (inputs terms which are used in both will cancel). The xor of two even or two odd parity functions will be an even parity function; the xor of an even with an odd (or vice versa) will be an odd parity function.

Even if one does not limit oneself to combinatorial circuits and is willing to assume deterministic propagation delays through gates, that won't help unless the propagation delays through an XOR gate vary depending upon the type of signal being passed through. Otherwise, if one of the inputs to a circuit changes, each node will either never be affected, or will always experience the same state transitions at the same times relative to the change, regardless of the state of any other nodes. Since an AND gate requires that a change on one of the inputs should only change the output if the other input is low, an XOR gate would have no way of simulating such conditional behavior.