Mathematical Logic – Predicate Calculus

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.

 

Rate this post

Leave a Reply