Logical Equivalence and Quantifiers

Equivalences involving universal quantifier

Let’s sum up the simplest equivalence statements involving universal quantification. Assume a domain of discourse $D$ containing elements $e_1, e_2, e_3, \ldots, e_n$ and a generic predicate $P(x).$ We know that,

$$\forall x P(x) \equiv \bigwedge_{i=1}^n P(e_i).$$

This equivalence also shows us a connection between the propositional and predicate logic. We also know that for some generic predicate $P(x,y)$, the quantification order does not matter if we quantify both variables with the universal quantifier. That is,

$$\forall x \forall y P(x,y)\equiv \forall y \forall x P(x,y).$$

Further, we know that:

$$\neg \forall x P(x) \equiv \exists x \neg P(x).$$

Is the universal quantifier distributive?

We want to look at the following question. Does the universal quantifier distribute over conjunction and disjunction? Let’s look at conjunction first.

Assume generic domain $D$ and two predicates $P(x)$ and $Q(x)$. The question of distribution arises if the conjunction of both the predicates is universally quantified.

$$\forall x (P(x)\land Q(x)).$$

This statement says that every element of the domain has both the properties $P$ and $Q$. That is equivalent to saying that all the domain elements have the property $P$, and all the domain elements have the property $Q$. This means:

$$\left(\forall x P(x)) \land (\forall x Q(x)\right).$$

If $D$ contains elements $e_1, e_2, e_3, \ldots, e_n$, we can look at it as follows:

$$\forall x \left(P(x)\land Q(x)\right) \equiv \bigwedge_{i=1}^n \left(P(e_i)\land Q(e_i)\right).$$

We can write the following equivalence due to the commutativity and associativity of conjunction in our hand.

$$\bigwedge_{i=1}^n \left(P(e_i)\land Q(e_i)\right)\equiv \left (\bigwedge_{i=1}^n P(e_i)\right )\land \left (\bigwedge_{i=1}^n Q(e_i)\right ).$$

$$\left (\bigwedge_{i=1}^n P(e_i)\right )\land \left (\bigwedge_{i=1}^n Q(e_i)\right ) \equiv ( \forall x P(x)) \land (\forall x Q(x)).$$

Therefore, we conclude that the universal quantifier distributes over conjunction operation.

$$\forall x \left(P(x)\land Q(x)\right) \equiv \left(\forall x P(x)\right) \land \left(\forall x Q(x)\right).$$

Now, let’s look at the distribution over disjunction operation. Suppose we keep the assumption of the domain $D$ and two predicates $P(x)$ and $Q(x)$. In that case, the question of distribution arises if the disjunction of both predicates is universally quantified.

$$\forall x \left(P(x)\lor Q(x)\right).$$

This statement says that every element of the domain has either the property $P$ or $Q$ or both. That is not equivalent to saying that all the domain elements either have the property $P$ or all the domain elements have the property $Q$. This means:

$$\left(\forall x P(x)\right) \lor \left(\forall x Q(x)\right).$$

If $D$ contains elements $e_1, e_2, e_3, \ldots, e_n$, we can look at it as follows:

$$\forall x \left(P(x)\lor Q(x)\right) \equiv \bigwedge_{i=1}^n \left(P(e_i)\lor Q(e_i)\right).$$

The commutativity and associativity of conjunction are not helpful because of disjunction. Therefore, we conclude that the universal quantifier does not distribute over disjunction operation.

$$\forall x \left(P(x)\lor Q(x)\right) \not\equiv \left(\forall x P(x)\right) \lor \left(\forall x Q(x)\right).$$

Examples

Let’s have a look at an example.

---

Let’s consider the set of people taking the Basic Mathematical Logic course as the domain of discourse. We make the following two predicates:

• $P(x)$: $x$ has a laptop.
• $Q(x)$: $x$ has a smartphone.

---

Now, let’s examine the universal quantification for the conjunction of $P$ and $Q$.

• $c = \forall x (P(x)\land Q(x))$: Everybody taking Basic Mathematical Logic has both a laptop and a smartphone.

If we distribute the universal quantifier over the conjunction, it will follow.

• $d = \forall x P(x) \land \forall x Q(x)$: Everybody taking Basic Mathematical Logic has a laptop, and everybody taking Basic Mathematical Logic has a smartphone.

We note that the statements $c$ and $d$ are equivalent. The statement $c$ is true if everyone taking Basic Mathematical Logic has a laptop as well as a smartphone. In this scenario, $d$ will also be true. The statement $c$ will be false if at least one such person is taking Basic Mathematical Logic who does not have a laptop or does not have a smartphone, which is precisely the scenario when $d$ will be false.

Now, let’s see what happens when we distribute the universal quantifier over disjunction. Consider the statement $j$ that follows.

• $j=\forall x (P(x)\lor Q(x))$: Everybody taking Basic Mathematical Logic either has a laptop or a smartphone or both.

If we distribute the universal quantifier over the disjunction, we have the statement $k$.

• $k = \forall x P(x) \lor \forall x Q(x)$: Everybody taking Basic Mathematical Logic has a laptop, or everybody taking Basic Mathematical Logic has a smartphone.

The statements $j$ and $k$ are not equivalent. Assume a scenario that half of the people taking Basic Mathematical Logic have laptops only, and the rest of the people have only smartphones. In that case, the statement $j$ will be true, but the statement $k$ will be false.

Equivalences involving existential quantifier

Assume a domain of discourse $D$ containing elements $e_1, e_2, e_3, \ldots, e_n$ and a generic predicate $P(x).$ We know that,

$$\exists x P(x) \equiv \bigvee_{i=1}^n P(e_i).$$

We can see a connection between the propositional and predicate logic through this equivalence. We also know that for some generic predicate $P(x,y)$, the quantification order does not matter if we quantify both variables with the existential quantifier. That is,

$$\exists x \exists y P(x,y)\equiv \exists y \exists x P(x,y).$$

Further, we know that:

$$\neg \exists x P(x) \equiv \forall x \neg P(x).$$

Is the existential quantifier distributive?

We want to look at the following question. Does the existential quantifier distribute over conjunction and disjunction? Let’s look at them one by one.

Assume generic domain $D$ and two predicates $P(x)$ and $Q(x)$. The question of distribution arises if the conjunction of both the predicates is existentially quantified.

$$s=\exists x (P(x)\land Q(x)).$$

This statement says that at least one domain element has both the properties $P$ and $Q$. This is not equivalent to saying that at least one domain element has the property $P$, and at least one domain element has the property $Q$. This means

$$t=\left(\exists x P(x)) \land (\exists x Q(x)\right).$$

The statement $s$ asserts the existence of a domain element with properties $P$ and $Q$ simultaneously. In contrast, the statement $t$ asserts the presence of an element with property $P$ and an element (same or different) with property $Q$. Therefore, the statements $s$ and $t$ are not equivalent.

$$\exists x (P(x)\land Q(x))\not\equiv \left(\exists x P(x)\right) \land \left(\exists x Q(x)\right).$$

Now let’s look at the distribution of the existential quantifier over disjunction operation. Suppose we keep the assumption of the domain $D$ and two predicates $P(x)$ and $Q(x)$. In that case, the question of distribution arises if the disjunction of both the predicates is existentially quantified.

$$\exists x \left(P(x)\lor Q(x)\right).$$

This statement says that at least one domain element has the property $P$ or $Q$ (or both).

This is equivalent to saying that at least one domain element has the property $P$, or at least one domain element has the property $Q$. That means,

$$\left(\exists x P(x)\right) \lor \left(\exists x Q(x)\right).$$

If $D$ contains elements $e_1, e_2, e_3, \ldots, e_n$, we can look at it as follows.

$$\exists x \left(P(x)\lor Q(x)\right) \equiv \bigvee_{i=1}^n (P(e_i)\lor Q(e_i)).$$

We can write the following equivalence because the disjunction operation is commutative and associative.

$$\bigvee_{i=1}^n (P(e_i)\lor Q(e_i))\equiv \left (\bigvee_{i=1}^n P(e_i)\right )\lor \left (\bigvee_{i=1}^n Q(e_i)\right ).$$

$$\left (\bigvee_{i=1}^n P(e_i)\right )\lor \left (\bigvee_{i=1}^n Q(e_i)\right ) \equiv \left( \exists x P(x)\right) \lor \left(\exists x Q(x)\right).$$

Therefore, we conclude that the existential quantifier distributes over disjunction operation.

$$\exists x \left(P(x)\lor Q(x)\right) \equiv (\exists x P(x)) \lor (\exists x Q(x)).$$

Examples

Let’s look at an example.

---

Consider the set of people taking physics classes at Monash University as the domain set. As these people can take other classes as well, let’s define the following two predicates:

• $P(x)$: $x$ is taking chemistry classes.
• $Q(x)$: $x$ is taking astronomy classes.

---

Let’s existentially quantify the conjunction of $P$ and $Q$.

• $u = \exists x (P(x) \land Q(x))$: Someone is taking chemistry and astronomy classes.

If we distribute the existential quantifier, it becomes a different statement; let us call it $w$.

• $w = \left ( \exists x P(x) \right ) \land \left ( \exists x Q(x) \right )$: Someone is taking chemistry classes, and someone is taking astronomy classes.

Now assume that among the people taking physics classes at Monash University, no one is taking chemistry and astronomy classes. However, some are taking astronomy classes, and some are taking chemistry classes. In this case, the statement $u$ is false, but $w$ is true.

Now, let us existentially quantify the disjunction of $P$ and $Q$.

• $m = \exists x (P(x) \lor Q(x))$: Someone is taking chemistry or astronomy classes.

If we distribute the existential quantifier, it becomes,

• $k = \left ( \exists x P(x) \right ) \lor \left ( \exists x Q(x) \right )$: Someone is taking chemistry classes or someone is taking astronomy classes.

We can observe that both $m$ and $k$ are true or false simultaneously for any scenario.

Equivalences involving both quantifiers

We should be cautious about the order of quantifiers if they are not of the same kind. This means we can not change the order of universal and existential quantifiers. For the sake of completion, we state DeMorgan’s laws for the quantified statements here.

$$\neg\forall x \exists y P(x,y) \equiv \exists x \forall y \neg P(x,y).$$

$$\neg \exists x \forall y P(x,y) \equiv \forall x \exists y \neg P(x,y).$$