De Morgan's Laws (Predicate Logic)

This proof is about De Morgan's Laws in the context of Predicate Logic. For other uses, see De Morgan's Laws.

Theorem

These are extensions of De Morgan's laws of propositional logic.

They are used to connect the universal quantifier $\forall$ with the existential quantifier $\exists$.

They can be stated as:

Assertion of Universality

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

If everything is, there exists nothing that is not.

Denial of Existence

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

If everything is not, there exists nothing that is.

Denial of Universality

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

Assertion of Existence

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

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.

Also see

• De Morgan's Laws as they arise in propositional logic
• De Morgan's Laws as they are applied in set theory

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.