5
$\begingroup$

Can anyone explain to me how to

Prove that nand is functionally complete.

(To wit: if we let $p ∗ q$ mean $¬(p ∧ q)$, show that the other connectives, $∧$, $∨$, $¬$ and $→$ are expressible in terms of $∗$.)

I understand that logical function on a fixed set of inputs has a finite number of cases, but unsure how to put that into context.

$\endgroup$

2 Answers 2

Reset to default
9
$\begingroup$

$¬p\equiv¬(p ∧ p)$

$p ∧ q\equiv¬(¬(p ∧ q))$

$p∨q\equiv¬(¬p ∧ ¬q)$

$p→q\equiv¬p∨q$

Therefore nand is functionally complete.

$\endgroup$
5
  • 1
    $\begingroup$ Forgive me for being pedantic but shouldn't those equality signs be equivalence signs (ie. $\equiv$ ) instead? $\endgroup$
    – Constantly confused
    Aug 2, 2018 at 6:18
  • 1
    $\begingroup$ @DanielMak OK, I edited my post. Thanks! $\endgroup$
    – user529760
    Aug 2, 2018 at 6:31
  • 2
    $\begingroup$ @DanielMak: That depends on context. In logic one usually keeps the $=$ sign reserved for equality between terms such that there won't be any confusion when we get to predicate logic -- but if one is doing Boolean algebra (or digital circuits or whatever) there's nothing wrong with using $=$ to assert equality between truth values as well. $\endgroup$
    – hmakholm left over Monica
    Aug 2, 2018 at 8:38
  • 5
    $\begingroup$ However, I would point out that this answer tacitly assumes that we already know $\{{\neg},{\land},{\lor},{\to}\}$ to be a functionally complete set. Hopefully the OP does already know that in his context. $\endgroup$
    – hmakholm left over Monica
    Aug 2, 2018 at 8:41
  • $\begingroup$ Functional completeness means that you can implement all truth tables. You only show a reduction but not functional completeness. $\endgroup$
    – Thorsten Altenkirch
    Oct 28, 2019 at 9:28
1
$\begingroup$

Two well-known basic facts:

Lemma 1: Every boolean function can be represented as a DNF.

Lemma 2: If $A = \{f_1, ... f_n\}$ if complete and every its function can be expressed in terms of functions from $B = \{g_1, ... g_m\}$, then $B$ is complete.

Lemma 1 $\implies \{\lnot, \lor, \land\}$ is complete. The following formulas

$¬p\equiv¬(p ∧ p)$

$p ∧ q\equiv¬(¬(p ∧ q))$

$p∨q\equiv¬(¬p ∧ ¬q)$

together with Lemma 2 imply that $\{NAND\}$ is complete.

$\endgroup$
3
  • $\begingroup$ I do not follow. you have shown that $ \{ \neg$, NAND } expresses functions, which set is complete. but why NAND alone is enough $\endgroup$
    – dEmigOd
    Jul 13 at 10:50
  • $\begingroup$ or you say, that you use $\neg$ after implementing it as NAND? $\endgroup$
    – dEmigOd
    Jul 13 at 10:58
  • $\begingroup$ @dEmigOd yes, take a look at the very first formula $\endgroup$
    – Sgg8
    Jul 13 at 10:59

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .