1
$\begingroup$

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.

$\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 P
    Mar 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$
    – Steven
    Mar 12, 2022 at 10:40
  • $\begingroup$ @Steven Oops, yeah. My bad. $\endgroup$
    – Rinkesh P
    Mar 12, 2022 at 11:07

1 Answer 1

2
$\begingroup$

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).$$

$\endgroup$
1
  • $\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, 2023 at 18:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.