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.
Best Answer
$¬p\equiv¬(p ∧ p)$
$p ∧ q\equiv¬(¬(p ∧ q))$
$p∨q\equiv¬(¬p ∧ ¬q)$
$p→q\equiv¬p∨q$
Therefore nand is functionally complete.