# De Morgan's Laws

Jump to navigation
Jump to search

## 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**