De Morgan’s laws

Define

A pair of tautologies that capture an important relationship between

where

\[\begin{align*}
  & \lnot (P \land Q) \iff \lnot P \lor \lnot Q \\
  \qand & \lnot (P \lor Q) \iff \lnot P \land \lnot Q.
\end{align*}
\]

Explore

Prove the laws true.

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\)