2

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 ?

Het
  • 333
  • There are infinite groups of universal logic gates are function complete, please check https://en.wikipedia.org/wiki/Functional_completeness . Even if we limit the size of the group to 1, we can still have Fredkin gate at airy of 3. – Mountain Jul 03 '20 at 11:22

1 Answers1

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'!

JMP
  • 21,771