Personal website

Proof

By the definitions of equivalence and implication,

\begin{align*} & \lnot (P \land Q) \iff \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) \iff \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\)