# Is it possible to write an AND gate using XOR gates?

How could I express an AND gate using only XOR gates ?

• why you want to express and gates with xor and in what ?
– abc
Oct 28, 2015 at 20:38
• I am reading something about homomorphic encryption, namely this paper eprint.iacr.org/2013/094.pdf also known as LTV scheme. There it is stated that multiplication means AND, addition between two bits means XOR. So I ask if it is possible to rewrite the scheme using only XOR ? Maybe I should migrate the question to Cryptography beta? Oct 28, 2015 at 20:54
• Related: Functional completeness Oct 29, 2015 at 8:50
• Oct 29, 2015 at 15:37
• electronics.stackexchange.com/questions/140684/… Oct 29, 2015 at 17:38

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 equivalent to AND.

• You might want to allow 0 and 1 as inputs as well. You still will not get AND though, although you will get the negation of the above as well. Oct 29, 2015 at 8:40

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  /
\   /
\ /
V
|
AND OUTPUT


The XOR gate is wired up as a non inverting buffer. The trick involved is that if you wire VCC to GND (or by extension a logic ground), the output is a weak GND.

Disclaimer: this works on the silicon I have, but might not work on all silicon.

• Some explanation of how this works would make this a much better answer. Oct 29, 2015 at 8:59
• Isn't the first gate redundant in this case? Oct 29, 2015 at 13:35
• What are these .|, |>? Oct 29, 2015 at 14:17
• @Wojowu ground and Vcc, I presume. Oct 29, 2015 at 14:27
• "might not work on all silicon." ... yes, and might even damage some - applying an input to a physical gate with the power turned off, or even worse turning the power on afterwards, is out-of-spec for a lot of parts (re: CMOS latchup effect!). Also, the "true" output voltage of the first gate is lower than your supply voltage, and depending on how much lower it is, will shift interpretation of input levels at the second gate significantly. And it is not unlikely (protection diodes, complimentary output...) that I2 will be an effective short circuit to ground when lower gate is unpowered. Oct 29, 2015 at 15:48

No

Consider W the set of the functions that maps {0, 1}×{0, 1} to {0, 1}. For example, the AND gate (denoted by ^) and the XOR gate (denoted by ⊕) are elements of W.

Now, for f ∈ W, define Val(f) in that way:

Val(f) := f(0, 0) ⊕ f(0, 1) ⊕ f(1, 0) ⊕ f(1, 1)

Its possible to prove that Val(¬f) = Val(f) and that Val(f ⊕ g) = Val(f) ⊕ Val(g). Now, let A(x, y) = x and B(x, y) = y two of the elements of W, and note that Val(A) = Val(B) = 0, and that Val(^) = 1

To finish, suppose that ^ can be expressed using only A, B, ⊕ and negations, so we have something like

A ^ B = ¬((¬A) ⊕ ((¬B) ⊕ A)) ⊕ ... ⊕ ((¬A) ⊕ (¬(A ⊕ ¬(A ⊕ B))))

and applying Val in both sides, we have

Val(A ^ B) = Val(¬((¬A) ⊕ ((¬B) ⊕ A)) ⊕ ... ⊕ ((¬A) ⊕ (¬(A ⊕ ¬(A ⊕ B)))))

1 = ((Val(A)) ⊕ ((Val(B)) ⊕ Val(A))) ⊕ ... ⊕ (((Val(A))) ⊕ ((Val(A) ⊕ (Val(A) ⊕ Val(B)))))

1 = ((0) ⊕ ((0) ⊕ 0)) ⊕ ... ⊕ (((0)) ⊕ ((0 ⊕ (0 ⊕ 0))))

1 = 0