Predicate Calculus

It is not possible to express the fact that any two atomic statements have some features in common. In order to investigate questions of the nature, we introduce the concept of a predicate in an atomic statement. The logic based upon the analysis of predicates in any statement is called predicate logic.


1.5.1 Predicates

Consider two statements

1. 
   John is a bachelor
2. 
   Smith is a bachelor

The part ‘is a bachelor’ is called a predicate

Denote John by j and Smith by s, ‘is a bachelor’ by predicate letter B. The statements (1) and (2) may be written as B(j) and B(s).

In general "p is Q", where Q is predicate and p is the subject, can be denoted by Q(p). A statement, which is expressed by using a predicate letter must have atleast one name of an object associated with the predicate.

3. John is a bachelor, and this painting is red.

Let R denote the predicate "is red" and let p denote "this painting". Then the statement (3) can be written as B(j) Ù R(p). Other connectives can also be used to form statements such as B(j)®R(p), ùR(p), B(j)ÚR(p), etc.

Consider, now, statements involving the names of two objects, such as

4. James is taller than Jones

5. China is to the north of India

The predicates "is taller than" and "is to the north of" are 2-place predicates because names of two objects are needed to complete a statement involving these predicates. If the letter G symbolizes "is taller than", j₁ denotes "James", and j₂ denotes "Jones", then statement (4) can be translated as G(j₁, j₂). Note that the order in which the names appear in the statement as well as in the predicate is important. If N denotes the predicate "is to the north of", c : China, and i : India, then (5) is symbolized as N(c, i). N(c, i) is the statement "India is to the north of China".

6. Suji stands between Rani and Ravi.

7. Siva and Lazar played bridge against Jacob and Senthil.

If S is an n-place predicate letter and a₁,a₂,…,a_n are the names of objects, then S(a₁,a₂,…,a_n) is a statement.

Back to top

1.5.2 The Statement Function, Variables and Quantifiers

Let H be the predicate "is a mortal", a : the name "Mr.Suji", b : India" and c : "A Shirt".

Then H(a), H(b) and H(c) all denote statements. These statements have a common form.

If we write H(x) for "x is mortal", then H(a), H(b), H(c), and others having the same form can be obtained from H(x) by replacing x by an appropriate name. H(x) is not a statement but it results in a statement when x is replaced by the name of an object.

A simple statement function of one variable is defined to be an expression consisting of a predicate symbol and an individual variable. This statement function becomes statement when the variable is replaced by any object. The replacement is called a substitution instance of the statement function.

For example, if we let M(x) be "x is a man" and H(x) be "x is a mortal", then we can form compound statement functions such as

M(x)Ù H(x), M(x)® H(x), ùH(x), M(x)Ú ùH(x), etc.

Consider the statement function of two variables :

1. H(x, y) : x is taller than y.

If both x and y are replaced by the name of objects we get a statement. If i represents Ms. Indu and j Mr. Jeyaraj, then we have,

H(i, j) : Ms. Indu is taller than Mr. Jeyaraj and

H(j, i) : Mr. Jeyaraj is taller than Ms. Indu.



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

For example,

M(x) : x is a man

H(y): y is mortal.

Then we may write

M(x) Ù H(y) : x is a man and y is a mortal.

It is not possible to write every statement function of two variables using statement functions of one variable consider equation in elementary algebra.

1. x + 4 = 10.
2. x² + 2x + 5 = 0.
3. (x – 5) * ( x – ¼) = 0.
4. (x² – 1) = (x + 1) * (x – 1).

In algebra, it is conventional to assume that the variable x is to be replaced by numbers (real, complex, rational, integer, etc.). We state this idea by saying that the universe of the variable x is the set of real numbers or complex numbers or integers etc.

If x is replaced by a real number in (1), we get a statement. The resulting statement is true when 6 is substituted for x, while, for every other substitution, the resulting statement is false.

In (2) there is no real number which when substituted for x gives a true statement. In (3) if the universe of x is assumed to be integers, then there is only one number which produces a true statement when substituted. In (4), if any number is substituted for x, then the resulting statement is true.

Therefore we may say that

5. For a number x, x² – 1 = ( x – 1 ) * ( x + 1 ).

Here (5) is a statement and not a statement function even though the variable x appears in it. In (5) the variable x need not be replaced by any name to obtain a statement.

Consider the following statements. Each one is a statement about all individuals or objects belonging to a certain set.

6. All men are mortal.
7. Every apple is red.
8. Any integer is either positive or negative.

The above statements may be written as follows:

6a. For all x, if x is a man, then x is mortal.

7a. For all x, if x is an apple, then x is red.

8a. For all x, if x is an integer, then x is either positive or negative.


If we introduce a symbol to denote the phrase "for all x" by the symbol "(" x)" or by "(x)", then we may write as

M(x) : x is a man. H(x) : x is mortal.

A(x) : x is an apple. R(x) : x is red.

N(x) : x is an integer. P(x) : x is either positive or negative.

Using the above we write (6a), (7a) and (8a) as

6b. (x)(M(x)® H(x)) or (" x)(M(x)® H(x)).

7b. (x)(A(x)® R(x)) or (" x)(A(x)® R(x)).

8b. (x)(N(x)® P(x)) or (" x)(N(x)® P(x)).



The symbols (x) or (" x) are called universal quantifiers. It is possible to quantify any statement function of one variable to obtain a statement. (x)M(x) is a statement which can be translated as

9. For all x, x is a man.

9a. For every x, x is a man.

9b. Every thing is a man.


The statements remain unchanged if x is replaced by y through out.

Therefore the statements (x)(M(x)® H(x)) and (y)(M(y)® H(y)) are equivalent.


Consider an example of two universal quantifiers.

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

We can state that "For any x and any y, if x is taller than y, then y is not taller than x" or "For any x and y, if x is taller than y, then it is not true that y is taller than x".

This may be symbolized as

(x)(y)(H(x, y)® ùH(y, x))


Another quantifier ($ x) is used to translate the expression such as "for some", "there is atleast one", or "there exists some" ("some" is used in the sense of "atleast one").

Consider the following statements :

10. There exists a man.

11. Some men are clever.

12. Some real numbers are rational.


(10) can be written as

10a. There exists an x such that x is a man.

10b. There is atleast one x such that x is a man.

(11) can be written as

11a. There exists x such that x is a man and x is clever.

11b. There exists atleast one x such that x is a man and x is clever.


The phrase "there is atleast one x such that" or "there exists x such that" or "for some x" is represented by the symbol "$ x" called the existential quantifiers. Writing

M(x) : x is a man.

C(x) : x is clever.

R₁(x) : x is a real number.

R₂(x) : x is rational.

We can write (10) to (12) as

10c. ($ x) M(x)

11c. ($ x)(M(x)Ù C(x))

12c. ($ x)(R₁(x)Ù R₂(x))

Back to top

1.5.3 Predicate Formulas

Consider n-place predicate formulas P(x₁,x₂,…,x_n)

The letter P is an n-place predicate and x₁,x₂, … , x_n are individual variables. In general P(x₁,x₂,…,x_n) is called an atomic formula of predicate calculus. Some examples of atomic formulas:

P, Q(x), R(x, y), A(x, y, z), B(a, y), C(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 wff, then ù A is a wff.
3. If A and B are wffs, then (AÙ B), (AÚ B), (A® B), and (A B) are also wffs.
4. If A is a wff and x is any variable, then (x)A and ($ x)A are wffs.
5. Only those formulas obtained by using rules (1) to (4) are wffs.

Back to top

1.5.4 Free and Bound Variables
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 in an x-bound part of a formula is called a bound occurrence of x, while any occurrence of x, or of any variable, that is not bound is called a free occurrence.
The formula P(x) either in (x) P(x) or in ($ x)P(x) is described as the scope of the quantifier. If the scope is an atomic formula, then no parentheses are used to enclose the formula.

Consider the following formulas as examples :

1. (x)P(x, y).
2. (x) (P(x)® Q(x)).
3. (x)(P(x)® ($y)R(x, y)).
4. (x)(P(x)® R(x)) Ú (x)(P(x)® Q(x)).
5. ($x)(P(x)Ù Q(x)).
6. ($x)P(x) Ù Q(x).

In (1), P(x, y) is the scope of the quantifiers, and both occurrences 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 occurrences. 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 occurrences of x are bound occurrences. In (5), the scope of ($x) is P(x)ÙQ(x). In (6), the scope of ($x) is P(x), and the last occurrence of x in Q(x) is free.

We may write (x)P(x, y) as (z)P(z, y). The bound occurrence of a variable can not be substituted by a constant. Only a free occurrence of a variable can be substituted by a constant.

For example, (x)P(x)ÙQ(a) is a substitution instance of (x)P(x)ÙQ(y). (x)P(x)ÙQ(a) can be expressed in English as "Every x has the property P, and ‘a’ has the property Q". A change of variables in the bound occurrence is not a substitution instance. In (6), it is better to write (y)P(y)ÙQ(x) instead of (x)P(x)ÙQ(x), so as to separate the free and bound occurrences of variables. It may be mentioned that in a statement every occurrence of a variable must be bound, and no variable should have a free occurrence.


Example 1:

Let P(x) : x is 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. That is we want to say that x is the father of z and z the 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:

It means that everybody loves a lover.

Let P(x): x is 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))).

Back to top

1.5.5 The Universe Of Discourse

When we symbolize a statement some simplification can be introduced by limiting the class of individuals or objects. The limitation means that 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 it refers to human beings only, then the universe of discourse is the class of human beings.

Example 1:

Symbolize the statement "All men are giants".

Solution:

Using G(x) : x is a giant.

M(x) : x is a man.

The given statement can be symbolized as (x)(M(x)® G(x)).

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 integer as the universe of discourse.

Solution:

Let the variables x and y be restricted to the set of positive integers.

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 write P(x) for "x is a positive integer" then we can symbolize the given statement as (x)(P(x)®($y)(P(y)ÙG(y, x))).

If the correct connectives are not used, then the meaning changes.


Examples:

1. All cats are animals.

This is true for any universe of discourse. In particular let the universe of discourse E be {Cuddle,Ginger,0,1}, where the first two elements are the names of cats.

The statement (1) is true over E.

Now consider the statements

(x)(C(x)® A(x)) and (x)(C(x) Ù A(x))

where, C(x) : x is a cat.

A(x) : x is an animal.

In (x)(C(x)®A(x)), if x is replaced by any of the elements of E, then we get a true statement; hence (x)(C(x)®A(x)) is true over E.

When x is replaced by 0 or 1 (x)(C(x)ÙA(x)) becomes false over E because C(x)ÙA(x) assumes false. Therefore, the statement (1) can not be symbolized as (x)(C(x)ÙA(x))

Now consider the statement

2. Some cats are black.

Let E be as above and assume both Cuddle and Ginger are white cats, and let B(x) : x is black.

In this case there is no black cat in the universe E, and (2) is false.

The statement ($ x)(C(x)Ù B(x)) is also false over E because there is no black cat in E.


On the other hand, ($ x)(C(x)® B(x)) is true because C(x)® B(x) is true when x is replaced by 0 or 1. Therefore the conditional is not the correct connective to use in this case.