Could someone please explain to me how (p ∨ q) = (p NAND p) NAND (q NAND q) I can prove it all the way to: What is the proof for those two equaling? So far I have: (p ∨ q) = (p ^ p) ∨ (q ^ q) Negate it… ~((p ^ p) ∨ (q ^ q)) You get… ~(p ^ p) ^ ~(q ^ q) = (p NAND p) ^ (q NAND q) SO CLOSE! How do I continue from here?

For starters, do note that

$$\text{NAND} (p_1, p_2) = \
eg (p_1 \land p_2)$$

Hence $\text{NAND} (p, p) = \
eg (p \land p) \equiv \
eg p$ because $p \land p \equiv p$. Therefore,

$$ \text{NAND} (\text{NAND} (p, p), \text{NAND} (q, q)) = \text{NAND} (\
eg p, \
eg q) = \
eg (\
eg p \land \
eg q) \equiv \
eg\
eg p \lor \
eg\
eg q \equiv p \lor q$$

where I used one of De Morgan's laws and elimination of the double negation (i.e., $\
eg \
eg p \equiv p$).