Quantifications
- Tags
- logic
Refers to propositions acting across sets.
| Name | LHS | RHS |
|---|---|---|
| Negation (De Morgans) | \( \neg \forall P(x) \) | \( \exists x \neg P(x) \) |
| \( \neg \exists P(x) \) | \( \forall x \neg P(x) \) | |
| Equivalences | \( \forall x (P(x) \land Q(x)) \) | \( (\forall x P(x)) \land (\forall Q(x)) \) |
| \( \exists x (P(x) \lor Q(x)) \) | \( (\exists x P(x)) \lor (\exists Q(x)) \) | |
| \( \forall x \forall y P(x, y) \) | \( \forall y \forall x P(x, y) \) | |
| \( \exists x \exists y P(x, y) \) | \( \exists y \exists x P(x, y) \) |
Note: In regards to tbl:quant-laws not all quantifications are [see page 1, equivalent]. The statement \( \forall x \exists y L(x, y) \) could be interpreted as for all people there exists a person that \( x \) loves. However if we reverse the order of the quantifications we get \( \exists y \forall x L(x, y) \) which means there exists a person who loves everyone else. These are two vastly different meanings.