# Universality of NOT and CNOT

I'm trying to figure out why NOT and CNOT gates are not sufficient to create all bijective functions in classical circuits. I have been struggling on this for hours, and just can't make sense of it.

I feel it has something to do with the Toffoli gate, as it contains an (implicit) AND operation, and I feel that's what missing in the NOT and CNOT gates. However I can't find a proper way to actually 'show' this.

• It would be helpful if you could explain that CNOT is the same as XOR. – Yuval Filmus Oct 17 '12 at 23:32
• does this question shed some light? – Ran G. Oct 18 '12 at 2:55
• Assuming CONT = XOR... A XOR A = NOT A, so basically this is the same as asking why XOR isn't sufficient. – Danny Varod Oct 18 '12 at 18:49

Suppose we want to compute $x \land y$ from $x,y,0,1$ using the operations NOT and CNOT (=XOR). Prove by induction that any such expression is equal to one of the following forms: $$0,1,x,y,\lnot x, \lnot y, x\oplus y, \lnot(x\oplus y).$$ It is more helpful to write it in the form $\alpha \oplus (\beta \land x) \oplus (\gamma \land y)$, where $\alpha,\beta,\gamma \in \{0,1\}$. Yet more helpful is to switch notation so that this expression is written $\alpha + \beta x + \gamma y$; this should be suggestive enough.