Functionally Complete Logical Connectives/NAND

From ProofWiki
Jump to navigation Jump to search

Theorem

The singleton set containing the following logical connective:

$\set {\uparrow}$: NAND

is functionally complete.


Proof

From Functionally Complete Logical Connectives: Negation and Conjunction, any boolean expression can be expressed in terms of $\land$ and $\neg$.


From NAND with Equal Arguments:

$\neg p \dashv \vdash p \uparrow p$


From Conjunction in terms of NAND:

$p \land q \dashv \vdash \paren {p \uparrow q} \uparrow \paren {p \uparrow q}$

demonstrating that $p \land q$ is expressed solely in terms of $\uparrow$.


Thus any boolean expression can be represented solely in terms of $\uparrow$.

That is, $\set {\uparrow}$ is functionally complete.

$\blacksquare$


Also see


Sources