Universality of NOT and CNOT
Edit: This is a proof for the non-quantum version.

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.