Prove that NAND and NOR are the only Universal Logic Gates.

Question

I was watching this lecture: link

H(x,y) is a boolean function.

He's says that H(x,y) is a Universal logic gate if and only if H(x,x) is 1 - x.

I didn't get this part.

So how to prove that NAND and NOR are the only Universal Logic Gates ?

Answer 1

If $H(x,x)\ne 1-x$, then constructing the single input NOT gate is impossible.

As for the 'iff' part, this means the only two gates left are the double input NOT gates, and so 'game over'!