De Morgan's Laws

Theorem

De Morgan's Laws are a suite of theorems in logic, which are also applied in set theory, as follows:

Propositional Logic

$\neg p \lor \neg q \dashv \vdash \neg \paren {p \land q}$

$\neg p \land \neg q \dashv \vdash \neg \paren {p \lor q}$

$p \land q \dashv \vdash \neg \paren {\neg p \lor \neg q}$

$p \lor q \dashv \vdash \neg \paren {\neg p \land \neg q}$

Predicate Logic

$\forall x: \map P x \dashv \vdash \neg \paren {\exists x: \neg \map P x}$

If everything is, there exists nothing that is not.

$\forall x: \neg \map P x \dashv \vdash \neg \paren {\exists x: \map P x}$

If everything is not, there exists nothing that is.

$\neg \paren {\forall x: \map P x} \dashv \vdash \exists x: \neg \map P x$

If not everything is, there exists something that is not.

$\neg \paren {\forall x: \neg \map P x} \dashv \vdash \exists x: \map P x$

If not everything is not, there exists something that is.

Set Theory

$S \setminus \paren {T_1 \cap T_2} = \paren {S \setminus T_1} \cup \paren {S \setminus T_2}$

$S \setminus \paren {T_1 \cup T_2} = \paren {S \setminus T_1} \cap \paren {S \setminus T_2}$

Boolean Algebras

$\neg \paren {a \vee b} = \neg a \wedge \neg b$

$\neg \paren {a \wedge b} = \neg a \vee \neg b$

Also known as

De Morgan's Laws are also known as the De Morgan formulas.

Some sources, whose context is that of logic, refer to them as the laws of negation.

Some sources refer to them as the duality principle.

Source of Name

This entry was named for Augustus De Morgan.

Historical Note

Augustus De Morgan proposed what are now known as De Morgan's laws in $1847$, in the context of logic.

They were subsequently applied to the union and intersection of sets, and in the context of set theory the name De Morgan's laws has been carried over.

Sources

• 1998: David Nelson: The Penguin Dictionary of Mathematics (2nd ed.) ... (previous) ... (next): De Morgan's Laws
• 2008: David Nelson: The Penguin Dictionary of Mathematics (4th ed.) ... (previous) ... (next): De Morgan's Laws