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.
$\begingroup$
$\endgroup$
3
-
$\begingroup$ 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. $\endgroup$– Rinkesh PMar 12, 2022 at 9:40
-
$\begingroup$ @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. $\endgroup$– StevenMar 12, 2022 at 10:40
-
$\begingroup$ @Steven Oops, yeah. My bad. $\endgroup$– Rinkesh PMar 12, 2022 at 11:07
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
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).$$
-
$\begingroup$ 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? $\endgroup$ Jan 19 at 18:14