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$

Hence $\neg(p\vee q) \Longleftrightarrow \neg p \wedge \neg q$ and $\neg(p\wedge q) \Longleftrightarrow \neg p \vee \neg q$.

This article is a stub. Help us out by expanding it. ._.