De Morgan's Laws (Predicate Logic)

From ProofWiki
Jump to: navigation, search

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 \exists x: \neg \map P x$
If everything is, there exists nothing that is not.


Denial of Existence

$\forall x: \neg P \paren x \dashv \vdash \neg \exists x: P \paren x$
If everything is not, there exists nothing that is.


Denial of Universality

$\neg \forall x: P \paren x \dashv \vdash \exists x: \neg P \paren x$
If not everything is, there exists something that is not.


Assertion of Existence

$\neg \forall x: \neg P \left({x}\right) \dashv \vdash \exists x: P \left({x}\right)$
If not everything is not, there exists something that is.


Source of Name

This entry was named for Augustus De Morgan.