Disjunction in terms of NAND

From ProofWiki
Jump to navigation Jump to search

Theorem

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

where $\lor$ denotes logical disjunction and $\uparrow$ denotes logical NAND.


Proof

\(\ds p \lor q\) \(\dashv \vdash\) \(\ds \neg \paren {\neg p \land \neg q}\) De Morgan's Laws (Logic): Disjunction
\(\ds \) \(\dashv \vdash\) \(\ds \neg p \uparrow \neg q\) Definition of Logical NAND
\(\ds \) \(\dashv \vdash\) \(\ds \paren {p \uparrow p} \uparrow \paren {q \uparrow q}\) NAND with Equal Arguments

$\blacksquare$


Sources