# Is [F(a, b, c) = a' + b] functionally or logically complete?

I'm having a problem determining whether [F(a, b, c) = a' + b] is functionally(logically) complete or not.
I would really appreciate it if you could help me.
P.S: I can't have 1 or 0 as input.

• you can derive 1 by F(a,a,a) and ~a by F(a,1,a). Then proceed to prove any of the universal gate equivalents. Mar 12, 2022 at 9:40
• @RinkeshP Unfortunately $F(a,1,a)=1$. You cannot implement a NOT gate using $F$ (and without the constant 0) since otherwise you'd be able to generate $0$, and ultimately implement a NAND gate. This can't be possible since $F$ (without the constant 0) is not universal. Mar 12, 2022 at 10:40
• @Steven Oops, yeah. My bad. Mar 12, 2022 at 11:07

If you are not allowed to have the constant $$0$$ as input then you cannot implement the constant function $$0$$ using only $$F$$.
To see this, let $$C$$ be a minimum (w.r.t. the number of gates) circuit that uses only $$F$$ gates and that computes $$C(x) = 0$$. We will show that this leads to a contradiction. Since $$C$$ must contain at least one gate (otherwise $$C(1)=1$$), we can consider the last gate $$F(a,b,c)$$ of $$C$$. In order for such a gate to return $$0$$ we must have that $$b=0$$. But then there must be a smaller circuit that computes $$0$$.
If you are allowed to use $$0$$, then the gate $$F$$ is universal. Indeed $$1 = F(0,0,0)$$ and we can simulate a NAND gate, which is universal: $$a \text{ NAND } b = \overline{a \cdot b} = \overline{a} + \overline{b} = \overline{a} + (\overline{b} +0) = F(a, F(b,0,0),0).$$
• in general if it was asked is $f(a,b,c) = a' + b$ functionally complete? then can I take inputs a, b or c to be 0, 1 without deriving $f(a,b,c) = 0 (or) 1$? to prove $f$ is functionally complete? Jan 19 at 18:14