De Morgan's Laws

De Morgan's Laws are two very important laws in the fields of set theory and boolean algebra.

Statement

For any two mathematical statements $p$ and $q$ , $\neg(p\vee q) \Longleftrightarrow \neg p \wedge \neg q$ . The dual of this statement is also true, that is, $\neg(p\wedge q) \Longleftrightarrow \neg p \vee \neg q$ . Also, for any two sets $A$ and $B$ , $\overline{A\cup B} = \overline A \cap \overline B$ . Again, the dual is true, for $\overline{A\cap B} = \overline A \cup \overline B$ .

In fact, all dual operators will interchange upon negation. So we can also say that for any proposition P, $\neg\forall x \: P(x) \equiv \exists x \:\neg P(x)$ , because $\forall$ is dual with $\exists$ . Also, $\neg\exists x \:P(x) \equiv \forall x \:\neg P(x)$ .

Proof

Any two propositions $p$ and $q$ have four possible combinations of truth values. We can therefore prove that two propositions stated in terms of $p$ and $q$ are equivalent by proving that they hold the same value in each of the four cases.

In the following truth table, $\top$ indicates "true" and $\bot$ indicates "false".

$p$	$q$	$\neg p$	$\neg q$	$p \vee q$	$p \wedge q$	$\neg(p\vee q)$	$\neg p \wedge \neg q$	$\neg(p\wedge q)$	$\neg p \vee \neg q$
$\top$	$\top$	$\bot$	$\bot$	$\top$	$\top$	$\bot$	$\bot$	$\bot$	$\bot$
$\top$	$\bot$	$\bot$	$\top$	$\top$	$\bot$	$\bot$	$\bot$	$\top$	$\top$
$\bot$	$\top$	$\top$	$\bot$	$\top$	$\bot$	$\bot$	$\bot$	$\top$	$\top$
$\bot$	$\bot$	$\top$	$\top$	$\bot$	$\bot$	$\top$	$\top$	$\top$	$\top$