Disprove universal gate of the following function: $F(x,y)=(x+y')'$

Question

Prove that the following function:

$F(x,y)=(x+y')'$

can not be a universal gate.

I believe that 'Not' can not be represented using this function (by trying many combinations).

How can I show it?

Any help would be appreciated.

Answer 1

The question is if the function would still be a "universal gate" if using constants (0 or 1) as function arguments is required, just like this:

$\overline{x+y} = F(x,F(y,1))$

In electronic circuit development this would not be a reason not to call a circuit showing such a behavior a "universal gate"; however in your case it seems not to be allowed.

(Otherwise $F$ would be a "universal gate" because the NOR gate can be created of two of such gates.)

However if using constants as additional inputs is not allowed, the proof is quite easy:

(Sorry for using engineering language instead of mathematics language here:)

If both inputs ($x$ and $y$) of the gate $F(x,y)$ are zero, the output of the gate is also zero.

This however means that larger gates/circuits built of gates of this type will always output zero if all inputs are zero.

You cannot build a NOR gate, for example, because a NOR gate will output a one if all inputs are zero.