October 2008


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

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

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

Copyright © 2008–2017