2

I want to see how to prove the functional completeness of NAND gate, but all the materials in the web I have reached just relies on the fact that the set $\{AND,NOT\}$ is complete and shows how to simulate those gates only using NAND gate. I want to see the proof or some list of references which contains the proof.

Thanks in advance.

Guldam
  • 934
  • I am not sure what more you want. The proof that ${\land, \lnot}$ is complete? – Tunococ Feb 06 '16 at 02:22
  • @Tunococ I think so. – BrianO Feb 06 '16 at 02:33
  • (i) Maybe you need to show that $\lnot$, $\land$, and $\lor$ together form a complete set. Or maybe that has already been done. (ii) Show that $\lor$ can be done with $\lnot$ and $\land$. – André Nicolas Feb 06 '16 at 02:34
  • @Tunococ Yes, exactly – Guldam Feb 06 '16 at 02:47
  • @André Nicolas I have done (ii) but have no idea as to (i). – Guldam Feb 06 '16 at 02:47
  • prove it by induction on the number of variables. $f(x_1,x_2,\ldots,x_n) = (x_n \land f(x_1,x_2,\ldots,1)) \lor (\lnot x_n \land f(x_1,x_2,\ldots,0))$ – reuns Feb 06 '16 at 02:55
  • Look at a "truth table" for our function $f$. If always $0$, easy. If not always $0$, look at all values of $(x_1,\dots,x_n)$ for which the function is $1$. For each such $(a_1,\dots,a_n)$, form the conjunction $A_j$ of $\lnot x_i$ where $a_i=0$ and $x_i$ if $a_i=1$. Then form the disjunction of all the $A_j$. We have obtained the important disjunctive normal form (DNF). – André Nicolas Feb 06 '16 at 03:12

1 Answers1

3

As confirmed by the OP, I'll simply write down the proof that $\{\land, \lnot\}$ is complete.

There are four possible choices for a pair of truth values (00, 01, 10, 11). There are $2^4 = 16$ possible functions from $\{00, 01, 10, 11\}$ to $\{0, 1\}$. For simplicity, I will represent a function by a sequence of its values on $00, 01, 10, 11$ respectively. For example, $0001$ is the AND function. $0111$ is the OR function.

Here is one way to construct 8 out of 16 binary functions using only $\land$ and $\lnot$: $$ \begin{array}{rl} 0000: & (p, q) \mapsto p \land \lnot p \\ 0001: & (p, q) \mapsto p \land q \\ 0010: & (p, q) \mapsto p \land \lnot q \\ 0011: & (p, q) \mapsto p \\ 0100: & (p, q) \mapsto \lnot p \land q \\ 0101: & (p, q) \mapsto q \\ 0110: & (p, q) \mapsto \lnot (p \land q) \land \lnot(\lnot p \land \lnot q) \\ 0111: & (p, q) \mapsto \lnot (\lnot p \land \lnot q) \end{array} $$ Now observe that if we negate each of these functions, we obtain all the remaining 8 functions.

Tunococ
  • 10,303
  • 1
    It seems you are implicitly assuming that only considering Boolean functions form of $f:B^2 \to B$ is enough, but I am afraid this implicit fact seems nontrivial to me.. – Guldam Feb 06 '16 at 02:59
  • 2
    @Guldam because this is enough to prove the $B^n \to B$ case by induction on $n$ : $f(x_1,x_2,\ldots,x_n) = (x_n \land f(x_1,x_2,\ldots,1)) \lor (\lnot x_n \land f(x_1,x_2,\ldots,0))$ where the latter are functions $B^{n-1} \to B$ – reuns Feb 06 '16 at 03:00
  • 1
    @user1952009 I see. All of my problems are resolved now. Thanks everyone! – Guldam Feb 06 '16 at 03:15