Statements involving variables such as:
x > 5 i.e. “x is greater than 5”
are very common in Mathematics and in computer programs. Such a statement is neither ‘false’ nor ‘true’ unless the possible value for variable x is specified and hence it is not a proposition. Predicates and quantifiers provide an appropriate way of producing propositions out of such situations.
Predicates:
In the example above, the variable x is the subject of the statement while the part “is greater than 5” is a property of the subject. Such part of a mathematical statement which specifies certain property of the subject is called a Predicate. We denote the statement “x is greater than 5” by P(x) where P is the predicate “is greater than 5” while the x is the variable.
Universe of discourse:
Before we move further in understanding the quantification, it is important to know what the term “Universe of discourse” means. It can be defined as a domain/ set from which the variables of a propositional function can draw their values.
Quantifiers:
As stated above, when all the variables in a predicate function are assigned values, then the resulting statement has a truth value and hence becomes a proposition. Such a process of creating a proposition from a propositional function is called Quantification. Two types of quantification are discussed here:
1. Universal quantification:
The universal quantification of P(x) is the statement/ proposition:
“P(x) is true for all values of x in the universe of discourse”
This is denoted by:
∀xP(x)
In the example above, ∀P(x) is true whenever x ϵ A where A = {6, 7, 8, 9…}.
Here A is the universe of discourse.
Conversely, ∀P(x) is false whenever x ϵ B where B = {…-1, 0, 1, 2, 3, 4, 5}. The universe of discourse is now set B.
2. Existential quantification:
The existential quantification of P(x) is the statement:
“There exists and element x in the universe of discourse such that P(x) is true.”
This is denoted by:
∃xP(x)
In the same example above, ∃P(x) is true when x ϵ A where A = {…-1, 0, 1, 2 …}.
NEGATION:
The negation of the universal quantification of a proposition is the existential quantification of the negation of original proposition. This can be represented symbolically as below:
¬∀xP(x) ↔ ∃x (¬P(x))
This observation is really important in solving expressions involving quantifiers.
We present below a list of all other such important equivalences involving quantifiers:
1. ∃ is distributive over ∨:
∃x (P(x) ∨ Q(x)) ≡ ∃x P(x) ∨ ∃x Q(x)
∃x (P ∨ Q(x)) ≡ P ∨ (∃x Q(x))
2. ∀ is distributive over ∧:
∀x (P(x) ∧ Q(x)) ≡ ∀x P(x) ∧ ∀x Q(x)
∀x (P ∧ Q(x)) ≡ P ∧ (∀x Q(x))
3. ¬(∃x P(x)) ≡ ∀x ¬(P(x))
4. ¬(∀x P(x)) ≡ ∃x ¬(P(x))
5. ∃x (P ∧ Q(x)) ≡ P ∧ (∃x Q(x))
6. ∀x (P ∨ Q(x)) ≡ P ∨ (∀x Q(x))
7. ∀x P(x) → ∃x P(x)
8. ∀x P(x) ∨ ∀x Q(x) → ∀x (P(x) ∨ Q(x))
9. ∃x (P(x) ∧ Q(x)) → ∃x P(x) ∧ ∃x Q(x)
Example:
Which one of the following is NOT logically equivalent to: ¬∃x (∀y (α) ∧ ∀z (β))?
(GATE 2013)
(A) ∀x (∃z(¬β) → ∀y(α)) (B) ∀x (∀z(β) → ∃y(¬α))
(C) ∀x (∀y (α) → ∃z (¬β)) (D) ∀x (∃y (¬α) → ∃z (¬β))
Solution:
The above question actually has 2 possible answers, as explained below:
Let’s take the original predicate function:
1. ¬∃x (∀y (α) ∧ ∀z (β)) ≡ ∀x (¬ (∀y (α) ∧ ∀z (β)))
(∵ ¬(∃x P(x)) ≡ ∀x ¬(P(x))) Step 1
Let’s assume predicate A = ∀y (α)
AND B = ∀z (β)
Then the R.H.S. above can be written as:
≡ ∀x (¬ (A ∧ B)) Step 2
≡ ∀x (¬A ∨ ¬B) (By De-Morgan’s law) Step 3
≡ ∀x (A → ¬B) Step 4
OR, alternately ≡ ∀x (B → ¬A) Step 5
≡ ∀x (∀y (α) → ¬ (∀z (β))) (by replacing A, B in step 4) Step 6
≡ ∀x (∀y (α) → ∃z (¬β)) (same as in step 1) Step 7
OR, alternately ≡ ∀x (∀z (β) → ¬ (∀y (α))) (from step 5) Step 8
≡ ∀x (∀z (β) → ∃ y (¬α)) (Same as in step 7) Step 9
As can be seen both options (B) and (C) are appearing in steps 9 and 7 respectively.
The remaining options are the answer to the question. This can also be verified as below:
1. Option (A) is opposite to option (C):
Option (C) is: ∀x (∀y (α) → ∃z (¬β)) ≡ ∀x (P → Q)
Where P = ∀y (α), and Q = ∃z (¬β)
While option (A) is: ∀x (∃z (¬β) → ∀y (α)) ≡ ∀x (Q → P)
Where P and Q are same as above
Now, we’ve seen that option (C) is logically equivalent to the given predicate function. But if (C) is to hold then (A) cannot hold simultaneously because:
P → Q ≢ Q → P
And hence (A) cannot be logically equivalent to the given function.
2. Option (D) is opposite to option (C):
Again, Option (C) is: ∀x (∀y (α) → ∃z (¬β)) ≡ ∀x (P → Q)
Where P = ∀y (α), and Q = ∃z (¬β)
While option (D) is: ∀x(∃y(¬α) → ∃z(¬β)) ≡ ∀x (¬P → Q)
Where P and Q are same as above
Again, option (C) is equivalent to the given predicate function. But (D) is not logically equivalent to (C) as:
P → Q ≢ ¬P → Q
And hence (D) also cannot be logically equivalent to the given function.