Quantifier Equivalences

1. Commutativity §

2. Existential Quantifier Distributes Over Disjunction §

3. Universal Quantifier Distributes Over Conjunction §

4. Implication §

$$\exists x(F(x)\to G(x))\equiv (\forall xF(x))\to (\exists xG(x))$$

No Free Occurrences §

A free occurrence (or just reference) of a variable $x$ is simply any instance of the variable $x$ in a predicate, bounded or free.

If the quantifier is ranging over a variable that is simply not present in the predicate, it is much easier to simplify

Let $F$ be a predicate with at least one reference to $x$, and let $G$ be a predicate with no free occurrences.

1. Non-referencing Predicates Are Unchanged With Quantifiers §

$$\exists xG\equiv G$$

$$\forall xG\equiv G$$

2. Non-referencing predicates can be ‘pulled out’ §

$$\exists x(F(x)\wedge G)\equiv (\exists xF(x))\wedge G$$

$$\forall x(F(x)\vee G)\equiv (\forall xF(x))\vee G$$

$$\forall x(F(x)\to G)\equiv (\forall xF(x))\to G$$

$$\forall x(G\to F(x))\equiv G\to (\forall xF(x))$$