Predicates and Quantifiers

PREDICATES AND QUANTIFIERS

Predicates

Statements involving variables, such as "x > 4", "x = y+4", and "x + y  = z", are often found in mathematical assertions and in computer programs.

These statements are neither true nor false when the values of the variables are not specified.

The statement "x is greater than 4" has two parts. The first part, the variable x, is the subject of the statement.

The second part- the predictate, "is greater than 4" - refers to a property that the subject of the statement can have.

We can denote the statement "x is greater than 4" by P(x), here P denote the predicate "is greater than 4" and x is the variable.

The statement P(x) is also said to be the value of the propositional function P at x. Once a value has been assigned to the variable x, the statement P(x) becomes a proposition and has a truth value.

When all the variables in a propositional function are assigned values, the resulting statement becomes a proposition with a certain truth value. However, there is another important way, called quantification, to create a proposition from a propositional function. Two types of quantification will be discussed here, namely, universal quantification and existential quantification. The area of logic that deals with predicates and quantifiers is called the predicate calculus.

Place of variables

Definition: A predicate refers to a property that the subject of the statement can have. A predicate is a sentence that contains a finite number specific values are substituted for the variables.

The domain of a predicate variable is the set of all values that may be substituted place of variable.

In the statement "Ravi is a painter" the part. "is a painter" is called a predicate. If it is denoted by the symbol P and 'Ravi' is denoted by the letter r, the above statement is denoted by P (r).

In the statement, "Ram is a shorter than Deivani", if "is shorter than" is denoted by s and Ram and Deivani are denoted by r and n, then this statement is denoted by S (r, n). Hence S is a 2 place predicate as two objects are needed to complete this statement. Likewise, we can have n-place predicate.

Example 1: Let p (x) denote the statement "x > 4". What are the truth values of P(5) and P(2) ?

Solution: We obtain the statement P(5), by setting x = 5 in the statement "x > 4". Hence P(5), which is the statement "5 > 4" is true. However, P(2), which is the statement "2 > 4" is false.

Example 2: Let Q (x, y) denote the statement "x = y+2", what are the truth values of the prepositions Q (1, 2) and Q (2, 0).

Solution: To obtain Q (1, 2). Set x=1 and y = 2 in the statement Q (x, y).

Hence, Q (1, 2) is the statement "1 = 2+2", which is false.

The statement Q (2, 0) is the proposition "2 = 0+2", which is true.

Example 3: What are the truth values of the propositions R (1, 2, 3) and R (0, 0, 1) ?

Solution: The proposition R (1, 2, 3) is obtained by setting x = 1, y = 2 and z

= 3 in the statement R (x, y, z). We see that R (1, 2, 3) is the statement "1 + 2 =

3", which is true. Also note that R (0, 0, 1), which is the statement "0 + 0 = 1" is false.

Note: In general, a statement involving the n variables x₁, x₂... x_n can be denoted by P (x₁, x₂, ... X_n). A statement of the form P (x₁, x₂, … n) is the value of the propositional function p at the n-tuple (x₁, x₂, …X_n), and p is also called a predicate.

Definition: A simple statement function :

A simple statement function of one variable is defined to be an expression consisting of a predicate symbol and an individual variable. Such a statement function becomes a statement when the variable is replaced by the name of any object.

Example: If "X is a teacher" is denoted by T (x), it is a statement function. If X is replaced by John, then "John is a teacher" is a statement.

Definition: Compound statement function :

A compound statement function is obtained by combining one or more simple statement functions by logical connectives.

Example :

M. (x) Ʌ H (x)

M (x) → H (x)

M (x) v ┐H (x)

An extension of this idea to the statement functions of two or more variables is straight forward.

Example :

G (x, y): x is taller than y.

If both x and y are replaced by the names of objects, we get a statement. If m represents Mr.Ram and f Mr. Raj, then we have

G (m, f): Mr. Ram is taller than Mr. Raj

and G (f, m): Mr. Raj is taller than Mr. Ram

It is possible to firm statement functions of two variables by using statement functions of one variable.

Example :

M (x) x is a man

H (y) y is a mortal

then we may write M (x) Ʌ H (v): x is a man and y is a mortal.

Note: It is not possible, however, to write every statement function of two variables using statement functions of one variable.

Quantifiers :

Certain declarative sentences involve words that indicate quantity such as "all, some, none or one". These words help determine the answer to the question "How many?". Since such words indicate quantity they are called quantifiers.

Consider the following statements.

1. All isosceles triangles are equiangular.

2. Some birds cannot fly.

3. Not all vegetarians are healthy persons.

4. There is one and only one even prime integer.

5. Each rectangle is a parallelogram.

After some thought, we realize that there are two main quantifiers : all and some, where some is interpreted to mean atleast one.

The quantifier "all" is called the universal quantifier, and we shall denote it by ∀x, which is an inverted. A followed bythe variable x. It represents each of the following phrases, since they all have essentially the same meaning.

For all x, all x are such that

For every x, every x is such that

For each x, each x is such that

Remark: It is best to avoid using "for any x" since it is often ambiguous as to whether "any" means "every" or "some". In some cases, "any" is un ambiguous, such as when it is used in negatives.

Example: Let P (x) be the statement "x + 1 > x". "What is the truth value of the quantification ∀ xp(x), where the universe of discourse consists of all real numbers ?

Solution: Since P (x) is true for all real numbers x, the quantification ∀xp (x) is true.

The quantifier "some" is the existential quantifier and we shall denote it by Ǝx, which is a reversed E followed by x. It represents each of the following phrases:

There exists an x such that …..

There is an x such that ……

For some x ….

There is at least one x such that...

Some x is such that ...

Example 1: Something is Green.

It can be denoted by (Ǝx) (G(x))

Example 2: Something is nor green.

It can be denoted by (Ǝx) (┐G(x))

Predicate Formulas

Let p (x₁, x₂, ... X_n) denote as n-place predicate formula in which the letter p is an n-place predicate and x₁, x₂ …. X_n are individual variables.

In general, p(x₁, x₂, ... X_n) will be called an atomic formula of the statement calculus. It may be noted that our symbolism includes the atomic formulas of the statement calculus as special cases (n = 0).

The following are some examples of atomic formulas R Q (x), P(x, y) A (x, y, z) P (a, y) and A (x, a, z).

A well-formed formula of predicate calculus is obtained by using the following rules.

1. An atomic formula is a well-formed formula.

2. If A is a well-formed formula, then ┐A is a well-formed formula.

3. If A and B are well-formed formulas, then (A Ʌ B), (A V B), (A→B) and (A↔ B) are also well-formed formulas.

4. If A is a well-formed formula and x is any variable, then (x) A and (Ǝx) are well-formed formulas.

5. Only those formulas obtained by using rules (1) to (4) are well- formed formulas.

Free and Bound variables

When a quantifier is used on the variable x or when we assign a value to this variable, we say that this occurrence of the variable is bound. An occurrence of a variable that is not bound by a quantifier or set equal to a particular value is said to be free.

All the variables can be done using a combination of universal quantifiers, existential quantifiers, and value assignments.

Given a formula containing a part of the form (x) p (x) or (Ǝx) P (x), such a part is called an x-bound part of the formula. Any occurrence of x is an x-bound part of a formula is bound occurrence of x while any occurrence of x or of any variable that is not a bound occurrence is called a free occurence.

Further, the formula P (x) either in (x) P (x) or in (x) P (x) is described as the scope of the quantifier. In other words, the scope of a quantifier is the formula immediately following the quantifier. If the scope is an atomic formula, then no parenthesis are used to enclose the formula, otherwise parenthesis are needed. As illustrations, consider the following formulas.

(x) P(x, y) ……. (1)

(x) P(x) → Q(x) …….  (2)

(x) P(x) → (Ǝy) R(x, y) ……. (3)

(x) (P(x) → R(x)) V (x) (P(x) → Q(x)) …… (4)

(Ǝx) (P(x) Ʌ Q(x)) …… (5)

(Ǝx) P(x) Ʌ Q(x) …….. (6)

In (1), P (x, y) is the scope of the quantifier, and both occurrence of x are bound occurrences, while the occurrence of y is a free Occurrence.

In (2), the scope of the universal quantifier Is P(x) → Q(x), and all occurrences of x are bound. In (3), the scope of (x) is P(x) → (Ǝy) R(x, y), while the scope of (Ǝy) is R(x, y).

All occurrences of both x and y are bound occcurrences.

In (4), the scope of the first quantifier is P(x) R(x), and the scope of the second is P(x) → Q(x).

All occurrence of x are bound occurrences.

In (5), the scope of (Ǝx) is P(x) Ʌ Q(x). However, in (6) the scope of (Ǝx) is P (x), and the last occurrence of x in Q(x) is free.

Example 1:

Let P (x) : x is a person

F(x, y) : x is the father of y

M (x, y) : x is the mother of y

write the predicate "x is the father of the mother of y".

Solution: In order to symbolize the predicate we name a person called z as the mother of y. Obviously we want to say that x is the father of z and z and mother of y.

It is assumed that such a person z exists. We symbolize the predicate as

(Ǝz) P (z) ^ F (x, z) ^ M (z, y)

Example 2: Symbolize the expression "All the world loves a lover".

Solution: First note that the quotation really means that everybody loves a lover. Now let

P(x) : x is a person

L(x): x is a lover

R (x, y) : x loves y

The required expression is

(x) (P (x) → (y) (P (y) ^ L (y) → R (x, y))

Universe of Discourse :

Definition : The variables which are quantified stand for only those objects which are members of a particular set or class. Such a restricted class is called the universe of discourse or the domain of individuals or simply the universe.

If the discussion refers to the human beings only, then the universe of discourse is the class of human begins. In elementary algebra or member theory, the universe of discourse could be numbers (real, complex, rational, etc)

Many mathematical statements asserts that a property for all values of a variable in a particular domain called the universe of discourse.

Such a statement is expressed using a universal quantification.

The universal quantification of P (x) is the proposition P (x) is true for all values of x in the universe discourse.

Example 1: Symbolize the statement "All men are gaints".

Solution Using

G (x) : x is a gaint

M (x) : x is man

The given statement can be symbolized as (x) (M (x)) → G (x). However, if we restrict the variable x to the universe which is the class of men, then the statement is (x) G (x)

Example 2: Consider the statement "Given any positive integer, there is a greater positive integer". Symbolize this statement with and without using the set of positive integers as the universe of discourse. [A.U A/M 2005]

Solution: Let the variable x and y be restricted to the set of positive integers. Then the above statement can be paraphrased as follows:

For all x, there exists a y such that y is greater than x. If G (x, y) is "x is greater than y", then the given statement is (x) (Ǝy) G (y, x).

If we do not impose the restriction on the universe of discourse and if we writer P (x) for "x is a positive integer", then we can symbolize the given statement is

(x) (P (x) (Ǝy) → (P (y) Ʌ G (y, x))).

Note :

The universe of discourse if any, must be explicitly stated, because the truth value of a statement depends upon it.

For instance, consider the Q (x): x is less than 5 and the statements (x) Q (x) and (Ǝx) Q (x). If the universe of discourse is given by the sets.

1. {-1, 0, 1, 2, 4}

2. {3, -2, 7, 8, -2}

3. {15, 20, 24}

then (X) Q (x) true for the universe of discourse (1) and false for (2) and (3).

The statement (Ǝx) Q (x) is true for both (1) and (2) but false for (3).

Definition: The universal quantification of P(x) is the proposition.

"P(x) is true for all values of x in the universe of discourse".

The notation ∀x P(x) denotes the universal quantification of P(x). Here V is called the universal quantifier.

Definition: The existential quantification of P (x) is the proposition.

"Thereexists an element x in the universe of discourse such that P (x) is true".

We use the notation Ǝx P (x) for the existential quantification of P (x). Here Ǝ is called the existential quantifier.

Example 1 : Let Q (x) be the statement "x < 2". What is the truth value of the quantification ∀ x Q (x) where the universe of discourse consists of all real numbers ?

Solution: Q(x) is not true for every real number x, since for instance, Q(3) is false. Thus ∀ x Q(x) is false. When all the elements in the universe of discourse can be listed say, x₁, x₂, ... X_n - it follows that the universal quantification ∀ x P(x) is the same as the conjunction P (x₁) Ʌ P (x₂) Ʌ…. Ʌ P (x_n).

Since this conjunction is true if and only if P(x₁), P(x₂) ... P(x_n) are all true.

Example 2: What is the truth value of ∀x P (x), where P (x) is the statement "x² < 10" and the universe of discourse consists of the positive integers not exceeding 4 ?

Solution: The statement ∀x P (x) is the same as the conjunction

P(1) Ʌ P(2) Ʌ P(3) Ʌ P(4).

Since the universe of discourse consists of the integers 1, 2, 3 and 4. Since P (4), which is the statement "4² < 10" is false, it follows that ∀x P (x) is false.

Example 3 : What does the statement ∀x T (x) mean if T (x) is ''x has two parents" and the universe of discourse consists of all people?

Solution: The statement ∀x T (x) means that for every person x, person has two that parents. This statement can be expressed in English as "Every person has two parents". This statements is true.

Example 4: What is the truth value of ∀x (x² ≥ x) if the universe of discourse consists of all real numbers and what is its truth value if the universe of discourse consists of all integers ?

Solution: Note that x² ≥ x if and only if x² - x = x(x − 1) ≥ 0. Consequently, x²x if and only if x ≤ 0 or x ≥ 1. It follows that ∀x (x²x) is false if the universe of discourse consists of all real numbers (since the inequality is false for all real numbers x with 0 < x < 1). However, if the universe of discourse consists of the integers,

∀x (x² ≥ x) is true. Since there are no integers x with 0 < x < 1.

Example 5: Suppose that P (x) is "x²>0". To show the statement

∀x P(x) is false where the universe of discourse consists of all integers, we give a counter example. We see that x = 0 is a counter example since x² = 0 when x = 0 so that x² is not greater than when x = 0.

Example 6 : Let P(x) denote the statement "x > 3". What is the truth value of quantification Ǝx P(x), where the universe of discourse consists of all real numbers ?

Solution Since "x > 3" is true for instance, when x = 4 - the existential quantification of P (x), which is Ǝx P(x), is true.

Example 7: Let Q (x) denote the statement "x = x+1". What is the truth value of the quantification Ǝx Q(x), where the universe of discourse consists of all real numbers ?

Solution: Since Q (x) is false for every real number x, the existential quantification of Q (x), which is Ǝx Q(x) is false.

Example 8: What is the truth value of Ǝx P (x) where P (x) is the statement "x²> 10" and the universe of discourse consists of the positive integers not exceeding 4 ?

Solution : Since the universe of discourse is {1, 2, 3, 4}, the proposition Ex P(x) is the same as the disjunction P(1) V P(2) V P(3) V P(4) since the P (4), which is the statement "4² > 10" is true, it follows that Ǝx P (x) is true.

Table 1

Table 2 Four types of equivalences

Table 3:

From this chart we observe more proof techniques.

1. Proof by example: To show Ǝx, P (x) is true, it is sufficient to show P (c) is true for some c in the universe. This type is the only situation where an example proves anything.

2. Proof by exhaustion : A statement of the form, ∀x, [┐P(x)], that P(x) is false for all x (all fasle) or, equivalently, that there are no values x for which P(x) is true (none true) will have been proven after all the objects in the universe have been examined and none found with property P(x).

3. Proof by counter example: To show that ∀x, P (x) is false, it is sufficient to exhibit a specific example c in the universe such that P (c) is false. This one value c is called a counter example to the assertion ∀x, P (x). In actual fact, a counter example disproves the statement ∀x, P (x).

Example 8: Symbolise : For every x, there exists a y such that x²+ y² ≥ 100.

[A.U. A/M, 2003]

Solution: (∀x) (Ǝy) (x² + y² ≥ 100)       

Example 9: Give the symbolic form of the statement "every book with a blue cover is a mathematics book".

[A.U. N/D 2005]

Solution :

∀x (S (x)) → P (x)

where

S(x) = x is every book with a blue cover

P(x) = Mathematics book

Example 10 : Express the statement "Every student in this class has studied calculus" as a universe qualification.

Solution : Let P (x): x has studied calculus then the statement "Every student in this class has studied calculus" can be written as ∀x P(x), where the universe of discourse consists of the students in the class.

This statement can also be expressed as ∀x (S(x) → P(x)) where S(x) is the statement "x is in this class" P (x) is as before and the universe of discourse is the set of all students.

Example 11: (I) Write each of the following in symbolic form.

(a) All men are good

(b) No men are good

(c) Some men are good

(d) Some men are not good

Solution: We assume that the universe consists of objects some of which are not men.

Let M (x) : x is a man and

G (x) : x is good

(a) means 'for all x, if x is a man, then x is good'.

So (a) is

(∀x [M (x) → G (x)]

(b) means "For all x, if x is a man, then x is not good' a

So (b) is

(∀x) [M (x) → ┐G (x)]

(c) means "there is an x, such that x is a man and x is good".

So (c) is

(Ǝx) (M (x) Ʌ G (x))

(d) means, "there is an x, such that x is a man and x is not good".

So (d) is (Ǝx) (M (x) Ʌ ┐G (x))

Example 12: Write the following sentences in the closed form or symbolic form.

(a) Some people who trust others one rewarded.

(b) If any one is good then John is good.

(c) He is ambitious or no one is ambitious.

(d) Some one is teasing.

(e) It is not true that all roads lead to Rome.

Solution: Let

P(x) : x is a person

T(x) : x trusts others

R(x) : x is rewarded

G(x) : x is good

A(x) : x is ambitious

Q(x) : x is teasing

S(x) : x is a road

L(x) : x lead to Rome

Then

(a) "Some people who trust others one rewarded" can be rephrased as "There is one x such that x is a person, x trusts others and x is rewarded".

Symbolic form: (Ǝx) [P(x) ^ T(x) ^ R(x)]

(b) If any one is good, then John is good' can be worded as "If there is one x such that x is a person and x is good, then John is good"

Symbolic form: (Ǝx) [P(x) Ʌ G(x)] → G (John).

 (c) 'He' represents a particular person. Let that person be y. So the statement is y is ambitious or for all x, if x is a person then x is not ambitious'.

So A (y) V ((∀x) [P(x) →┐A(x)]

(d) 'Some one is teasing' can be written as

'There is one x such that x is a person and x is teasing' and it is

(Ǝx) [P(x) Ʌ Q(x)]

(e) The statement can be written as

┐ (∀x) [S(x) → L(x)]

or (Ǝx) [S(x) Ʌ ┐L(x)]

Example 13: Express "√2 is an irrational number" using quantifiers.

Solution: Let P be the proposition "√2 is irrational". Suppose that P is true. Then √2 is rational. We will show that this leads to a contradiction. Under the assumption that √2 is rational, there exist integers a and b with √2 = a/b, where a and b have no common factors (so that the fraction a/b is in lowest terms). Since √2 = a/b,

Squaring on both sides we get

2 = a²/b²

Hence, 2b² = a²

This means that a² is even, implying that a is even. Further more, since a is even, a = 2c for some integer c. Thus,

2b² = 4c²

So, b² = 2c²

This means that b² is even. Hence, b must be even as well.

It has been shown that ┐P implies that √2 = a/b, where a and b have no common factors, and 2 divides a and b. This is a contradiction since we have shown that ┐P implies both r and ┐r, where r is the statement that a and b are integers with no common factors. Hence, ┐P is false, so that P : "√2 is irrational" is true.

Example 14: Let A = {1, 2, 3, 4, 5, 6}. Determine the truth value of each of the following:

(i) (Ǝx ϵ A) (x²> 25),

(ii) (Ǝx ϵ A) (x + 6 > 12)

(iii) (∀x ϵ A) (x² – x < 30)

Solution: (i) Since x = 6 ϵ A such that x² > 25.

(Ǝx ϵ A) (x²>25) is true.

(ii) Since for all x ϵ A, x+6 ≤ 12

(Ǝx ϵ A) (x+6> 12) is false.

(iii) Since, for x = 1, 2, 3, 4, 5

x² - x < 30 and for x = 6,

x² – x = 6² – 6 = 30

(∀x ϵ A) (x² − x < 30) is false.

Example 15 : Symbolise the following statements assuming the real numbers as the universe of discourse.

(a) For any value of x, x² is non-negative.

(b) For every value of x, there is same value of Ꭹ such that zy = 1

(c) There are positive values of x and y such that xy > 0

(d) There is a value of x such that if y is positive then x + y is negaive.

Solution :

(a) (∀x) (x2 ≥ 0)

(b) (∀) x (Ǝy) (xy = 1)

(c) (Ǝx) (Ǝy) (x > 0) ^ (v > 0) ^ (xy > 0)

(d) (Ǝx) (∀y) ((y > 0) → (x + y < 0)

Example 16 : Suppose the universe of discourse is the integers. Let P(x) be the predicate "x > 1" and let Q(x) be the predicate. "x < 6". Determine which of the following statements are true and which are false.

(a) (∀x) (P(x) V Q(x))

(b) (∀ x) (P(x) v (∀ x) Q(x))

(c) (Ǝx) (P(x) ^ Q(x))

(d) (Ǝx) P(x) ^ (Ǝx) Q(x)

Solution :

(a) True

(b) False

(c) True

(d) True

Example 17 : Write the following sentences in symbolic form.

"All lions are fierce"

"Somelions do not drink coffee"

"Some fierce creatures do not drink coffee".

Solution: Let

P(x) : x is a lion

Q(x) : x is fierce

R(x) : x drinks coffee

∀x (P(x) → Q(x))

Ǝx (P(x) ^  ┐R (x))

Ǝx ((x) ^  ┐R (x))

Example 18. Write the following sentences in symbolic form.

"All humming birds are richly colored".

"No large birds live on honey".

"Birds that do not live on honey are dull in color".

"Hummingbirds are small".

Solution :

Let P(x) : "x is a hummingbird"

Q(x) : "x is large".

R(x) : "x lives on honey".

S(x) : "x is richly colored."

we get

∀x (P(x) → S (x))

┐Ǝx (Q(x) ^ R (x))

∀x (┐R (x) →  ┐S(x))

∀x (P (x) →  ┐Q(x))

EXERCISE

1. Indicate the variables that are free and bound. Also show the scope of the quantifiers.

(a) (x) (P(x) Ʌ R(x)) → (x) P(x) Ʌ Q(x)

(b) (x) (P(x) ^ (Ǝx) Q(x)) v ((x) P(x) → Q(x)

(c) (x) (P(x) ↔ Q(x) ^ (Ǝx) R(x) ^ S(x)

2. Which of the following are statements ?

(a) (x) (P(x) v Q(x) Ʌ R

(b) (x) (P(x) ^ Q(x) ^ (Ǝx) S(x)

(c) (x) (P(x) Ʌ Q(x)) ^ S(x)

3. If the universe of discourse is the set {a, b, c} eliminate the quantifiers in the following formulas.

(a) (x) P(x)

(b) (x) R(x) Ʌ (x) S (x)

(c) (x) R(x) ^ (Ǝx) S(x)

(d) (x) (P(x) → Q (x)

(e) (x) ┐P(x) v (x) P(x)

4. Show that (Ǝz) (Q (z) Ʌ R(z)) is not implied by the formula (Ǝx) (P(x) Ʌ Q(x)) and (Ǝy) (P(y) Ʌ R(y)), by assuming a universe of discourse which has two elements.

5. Find the truth values of

(a) (x) (P (x) v Q(x)), where P(x): x = 1, Q(x): x = 2 and the universe of discourse is {1, 2}.

(b) (x) (P→ Q(x)) v R(a), where P: 2 > 1, Q(x) : x ≤3, R (x) : x> 5, and a : 5, with the universe being {-2, 3, 6}.

(c) (Ǝx) (P (x) → Q(x)) Ʌ T, where P(x):x > 2, Q(x):x = 0 and T is any tautology, with the universe of discourse as {1}.