A pair of tautologies that capture an important relationship between
where
\[\begin{align*} & \lnot (P \land Q) \equiv \lnot P \lor \lnot Q \\ \qand & \lnot (P \lor Q) \equiv \lnot P \land \lnot Q. \end{align*} \]
Prove the laws true.
By definition of equivalence and implication,
\[\begin{align*} & \lnot (P \land Q) \equiv \lnot P \lor \lnot Q \\[1ex] & \quad \equiv ((\lnot (P \land Q) ) \implies (\lnot P \lor \lnot Q)) \land ((\lnot P \lor \lnot Q ) \implies (\lnot (P \land Q))) \\[1ex] & \quad \equiv (\lnot ( \lnot (P \land Q)) \lor (\lnot P \lor \lnot Q)) \land (\lnot (\lnot P \lor \lnot Q) \lor (\lnot (P \land Q))) \\[2ex] & \lnot (P \lor Q) \equiv \lnot P \land \lnot Q \\[1ex] & \quad \equiv ((\lnot (P \lor Q)) \implies (\lnot P \land \lnot Q)) \land ((\lnot P \land \lnot Q) \implies (\lnot (P \lor Q))) \\[1ex] & \quad \equiv (\lnot (\lnot (P \lor Q)) \lor (\lnot P \land \lnot Q)) \land (\lnot (\lnot P \land \lnot Q) \lor (\lnot (P \lor Q))), \end{align*} \]
and those are tautologies, per
<<scheme/tautology?>> (and (tautology? (lambda (p q) (and (or (not (not (and p q))) (or (not p) (not q))) (or (not (or (not p) (not q))) (not (and p q))))) 2) (tautology? (lambda (p q) (and (or (not (not (or p q))) (and (not p) (not q))) (or (not (and (not p) (not q))) (not (or p q))))) 2))
#t
so De Morgan’s laws are always ‘true’. \(\blacksquare\)