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)$ .

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

Page

Toolbox

Search

De Morgan's Laws

Statement