Trivium: 24oct2008

Proof of de Morgan’s laws by rewriting due to Kai Cieliebak.

$\begin{align*} \neg A \vee \neg B &= [\neg(A \wedge B) \vee (A \wedge B)] \wedge (\neg A \vee \neg B)\\ &= [\neg(A \wedge B) \wedge (\neg A \vee \neg B)] \vee [A \wedge B \wedge \neg A] \vee [A \wedge B \wedge \neg B]\\ &= \neg(A \wedge B) \wedge [\neg A \vee \neg B \vee (A \wedge B)]\\ &= \neg(A \wedge B) \wedge [\neg A \vee \neg B \vee A] \wedge [\neg A \vee \neg B \vee B]\\ &= \neg(A \wedge B) \end{align*}$

(Update: Mistake in my transcription found by Gregory Brown and his girlfriend.)