Predicates And Quantifiers

PREDICATES AND QUANTIFIERS: Assertions which are formed using variables in a “template” that expresses the property of an object or a relationship between objects are called “Predicates”.

Example:

(i) “He is dark and ugly” is written as

“x is dark and ugly”.

(ii) “Naveena lives in Maryland and

Menon Lakshmi lives in Texas” is written as

“x lives in Maryland and

y lives in Texas”.

Predicates are used in Control Statements in high level languages.

Predicates may be either “constants” or “variables”. Values of the individual variables are drawn from a set of values called “Universe of discourse”.

In order to change a predicate into a proposition, each individual variable of the predicate should be “bound”. There are two ways of doing it.

(i) The first way to bind an individual variable is by assigning a value to it.

Example:P = “a b = 6”. which is denoted by P(x, y).

If a = 2, and b = 3, then P(2, 3) is false.

(ii) The second way to bind an individual variable is by “quantification” of the variable.

It can be done either by “universal” or “extential”.

“For all values of x, the assertion P(x) is true.”

“For all x, P(x)” is written as “∀x P(x)”, where ∀is a “Universal Quantifier”.

“There exists a value of x for which the assertion P(x) is true”. This statement is written as “ÁxP(x)” whereÁ is called “External Quantifier”.

The proposition ∀x P(x) is equivalent to the conjunction

P(1)Ù P(2) Ù P(3) Ù P(4)

for the universal consisting of integers 1, 2, 3, and 4.

The proposition ÁxP(x) is equivalent to the disjunction

P(1) Ú P(2) Ú P(3) Ú P(4)

The proposition Á!xP(x) is equivalent to the proposition

Note that the sequence Ú Ú x y can always be replaced by ∀y  ∀x , and the sequence Á Á x y can always be replaced by Á Á y x , though the order in which individual variables are bound cannot always be changed without affecting the meaning of an assertion.

Example 1: Let S(x, y, z) denote the predicate “x y = z”. P(x, y, z) denote “x × y = z” and L(x, y) denote “x < y”. Let the universe of discourse be the natural numbers N. Using the above predicates, express the following assertions. The phrase “there is an x” does not imply that x has a unique value.

1. For every x and y, there is a z such that x y = z.
2. No x is less than 0.
3. For all x, x 0 = x.
4. For all x, x – y = y for all y.
5. There is an x such that x × y = y for all y.

Solution: