Inference Theory of the Predicate Calculus

We use the concepts of equivalence and implication to formulas of the predicate calculus.

1.6.1 Valid Formulas and Equivalences

The formulas of the predicate calculus are assumed to contain statement variables, predicates, and object variables. The object variables are assumed to belong to a set called the universe of discourse or the domain of the object variable. Such a universe may be finite or infinite. The term 'variable' includes constants as a special case. In a predicate formula, when all the object variables are replaced by definite names of objects and the statement variables by statements, we obtain a statement which has a truth value T or F.

The formulas of predicate calculus as given here do not contain predicate variables. They contain predicates; i.e., every predicate letter is intended to be a definite predicate, and hence is not available for substitution.

Let A and B be any two predicate formulas defined over a common universe denoted by the symbol E. If, for every assignment of object names from the universe of discourse E to each of the variables appearing in A and B, the resulting statements have the same truth values, then the predicate formulas A and B are said to be equivalent to each other over E. This idea is symbolized by writing AÛB over E. If E is arbitrary, then we say that A and B are equivalent, that is AÛ B.

It is possible to determine by truth table methods whether a formula is valid in E, where E is a finite universe of discourse. This method may not be practical when the number of elements in E is large. It is impossible when the number of elements in E is infinite.

Formulas of the predicate calculus that involve quantifiers and no free variables are also formulas of the statement calculus. Therefore, substitution instances of all the tautologies by these formulas yield any number of special tautologies.

Consider the tautologies of the statement calculus given by PÚùP, P®Qù PÚQ and substitute the formulas (x)R(x) and
($ x)S(x) for P and Q respectively. It is assumed that (x)R(x) and ($x)S(x) do not contain any free variables. The following tautologies are obtained.

((x)R(x))Úù((x)R(x)).

((x)R(x))®(($x)S(x))ù((x)R(x))Ú(($x)S(x)).

Let A(x), B(x), and C(x, y) denote any prime formulas of the predicate calculus. Then the following are valid formulas of the predicate calculus

ù ùA(x)A(x).

C(x,y)ÙB(x)B(x)ÙC(x, y).

A(x)®B(x)ùA(x)ÚB(x).

Back to top

1.6.2 Some Valid Formulas Over Finite Universe

We denote predicate formulas by capital letters such as A,B, C,… followed by object variable x, y,… . Thus A(x), A(x, y), B(y) and C(x,y, z) are examples of predicate formulas. In the formula A(x), A is a predicate formula and x is one of the free variables. For example we may write B(x) for (y) P(y) Ú Q(x).

If in a formula A(x) we replace each free occurrence of the variable x by another variable y, then we say that y is substituted for x in the formula, and the resulting formula is denoted by A(y). For such a substitution, the formula A(x) must be free for y. A formula A(x) is said to be free for y if no free occurrence of x is in the scope of the quantifiers (y) or ($y). If A(x) is not free for y, then it is necessary to change the variable y, appearing as a bound variable, to another variable before substituting y for x. If y is substituted, then it is usually a good idea to make all the bound variables different from y. The following examples show what A(y) is for a given A(x).

A(x)	A(y)
P(x,y) Ù ( $ y)Q(y)	P(y,y) Ù ( $ y)Q(y) or P(y,y) Ù ( $ x)Q(z)
(S(x) Ù S(y))Ú(x)R(x)	(S(y) Ù S(y))Ú(x)R(x) or (S(y) Ù S(y))Ú(z)R(z)

The following formulas are not free for y P(x,y) Ù(y)Q(x,y) and (y)(S(y)®S(x)).

In order to substitute y in place of the variables x in these formulas it is necessary to first make them free for y as follows.

A(x)	A(y)
P(x,y) Ù(z)Q(x,z)	P(y,y)Ù(z)Q(y,z)
(z)(S(z)®S(x))	(z)(S(z)®S(y))

Let the universe of discourse be denoted by a finite sets given by S={a₁,a₂,…,a_n}.



From the meaning of the quantifiers and by simple enumeration of all the objects in S, it is easy to see that

(x)A(x)ÛA(a₁)ÙA(a₂)Ù…ÙA(a_n)…………(1)

($x)A(x)ÛA(a₁)ÚA(a₂)Ú…ÚA(a_n)…………(2)

De Morgan's laws are

ù((x)A(x)) Û ( $x)ùA(x)……………(3)

ù(($ x)A(x))Û(x)ùA(x)……………(4)

Back to top

1.6.3 Special Valid Formulas Involving Quantifiers

Let A(x) be a predicate formula where x is a particular object variable of interest.

Then, (x)A(x)ÞA(y)………(1)

where y is substituted for x in A(x) to obtain A(y).

In order to show (1), we assume that (x)A(x) is true. A(y) must also be true. Hence the implication (1) holds. In case (x)A(x) is false, nothing need to be proved.

This implication can be written as (x)A(x)ÞA(x)…………(2)

Implication (2) will be called the rule of universal specification and will be denoted by US in the theory of inference.

Consider A(x)Þ(x)A(x)…………(3)

This rule is called the rule of universal generalization and is denoted by UG. We also have two more rules which will permit us to remove or add the existential quantifiers during the course of derivation.

Consider another two rules

($x)A(x)ÞA(y)………………(4)

A(y)Þ($x)A(x)………………(5)

Implication (4) is known as existential specification, abbreviated here as ES while (5) is known as existential generalization or EG.

Consider the following tables for the derivation of a conclusion from a set of premises.

Table1.6.1

($x)(A(x)ÚB(x))Û($x)A(x)Ú($x)B(x)	E23
(x)(A(x)ÙB(x))Û(x)A(x)Ù(x)B(x)	E24
ù($x)A(x)Û(x)ùA(x)	E25
ù(x)A(x)Û($x)ùA(x)	E26
(x)A(x)Ú(x)B(x)Þ(x)(A(x)ÚB(x))	I15
($x)(A(x)ÙB(x))Þ($x)A(x)Ù($x)B(x)	I16

Table 1.6.2

(x)(AÚB(x))ÛAÚ(x)B(x)	E27
($x)(AÙB(x))ÛAÙ($x)B(x)	E28
(x)A(x)®BÛ($x)(A(x)® B)	E29
($x)A(x)®BÛ(x)(A(x)® B)	E30
A®(x)B(x)Û(x)(A®B(x))	E31
A®($x)B(x)Û($x)(A®B(x))	E32

Back to top

1.6.4 Theory of Inference for the Predicate Calculus

The method of derivation involving predicate formulas uses the rules of inference given for the statement calculus and also certain additional rules which are required to deal with the formulas involving quantifiers. Using of rules P and T remain the same. If the conclusion is given in the form of a conditional, we shall use the rule of conditional proof called CP. In order to use the equivalences and implications, we need some rules on how to eliminate quantifiers during the course of derivation. This elimination is done by the rules of specification, called rules US and ES. Once the quantifiers are eliminated and the conclusion is reached. It may happen that the desired conclusion is quantified. In this case we need rules of generalization called rules UG and EG which can be used to attach a quantifier.

Rule US (Universal Specification) :

From (x)A(x) one can conclude A(y).

Rule ES (Existential Specification) :

From ($x)A(x) one can conclude A(y) provided that y is not free in any given premise and also not free in any prior step of the derivation. These requirements can easily be met by choosing a new variable each time ES is used.

Rule EG (Existential Generalization) :

From A(x) one can conclude ($ y)A(y).

Rule UG (Universal Generalization) :

From A(x) one can conclude (y)A(y) provided that x is not free in any of the given premises and provided that if x is free in a prior step which resulted from use of ES, then no variables introduced by that use of ES appear free in A(x).

Example1:

Show that (x) (H(x)® M(x)) Ù H(s)Þ M(s).

This is a well - known argument known as the "Socrates argument" which is given by

All men are mortal.

Socrates is a man.

Therefore Socrates is mortal.

If we denote H(x) : x is a man, M(x) : x is a mortal and s : Socrates, we can put the argument in the above form.

Solution:

{1} (1) (x)(H(x)® M(x)) Rule P

{1} (2) H(s)® M(s) Rule US, (1)

{3} (3) H(s) Rule P

{1, 3} (4) M(s) Rule T, (2), (3), I₁₁



Example 2:

Show that (x)(P(x)® Q(x)) Ù (x)(Q(x)® R(x)) Þ (x)(P(x)® R(x)).

Solution:

{1} (1) (x)(P(x)® Q(x)) Rule P

{1} (2) P(y)® Q(y) Rule US, (1)

{3} (3) (x)(Q(x)® R(x)) Rule P

{4} (4) Q(y)® R(y) Rule US, (3)

{1,3} (5) P(y)® R(y) Rule T, (2), (4), I₁₃

{1, 3} (6) (x)(P(x)® R(x)) Rule UG, (5)



Example 3:

Show that ($ x)M(x) follows logically from the premises (x)(H(x)® M(x)) and ($ x)H(x).

Solution:

{1} (1) (x)(H(x)® M(x)) Rule P

{1} (2) H(y)® M(y) Rule US, (1)

{3} (3) ($ x)H(x) Rule P

{3} (4) H(y) Rule ES, (3)

{1, 3} (5) M(y) Rule T, (2), (4), I₁₁

{1, 3} (6) ($ x)M(x) Rule EG, (5)



Example 4:

Prove that ($ x)(P(x) Ù Q(x)) Þ ($ x)P(x) Ù ($ x)Q(x).

Solution:

{1} (1) ($ x)(P(x)Ù Q(x)) Rule P

{1} (2) P(y) Ù Q(y) Rule ES, (1), y fixed

{1} (3) P(y) Rule T, (2), I₁

{1} (4) Q(y) Rule T, (2), I₂

{1} (5) ($ x)P(x) Rule EG, (3)

{1} (6) ($ x)Q(x) Rule EG, (4)

{1} (7) ($ x)P(x) Ù ( $ x)Q(x) Rule T, (4), (5), I₉



Example 5:

Show that from

1. ($ x)(F(x) Ù S(x)) ® (y)(M(y)® W(y))
2. ($ y)(M(y) Ù ùW(y))

the conclusion (x)(F(X) ® ùS(x)) follows.

Solution:

{1} (1) ($ y)(M(y) Ù ùW(y)) Rule P

{1} (2) M(z) Ù ùW(z) Rule ES, (1)

{1} (3) ù(M(z)® W(z)) Rule T, (2), E₁₇

{1} (4) ($ y)ù(M(y)® W(y)) Rule EG, (3)

{1} (5) ù(y)(M(y)® W(y)) E₂₆, (4)

{6} (6) ($ x)(F(x) Ù S(x))® (y)(M(y)® W(y)) Rule P

{1, 6} (7) ù($ x)(F(x) Ù S(x)) Rule T, (5), (6), I₁₂

{1, 6} (8) (x)ù(F(x) Ù S(x)) Rule T,(7), E₂₅

{1, 6} (9) ù(F(x) Ù S(x)) Rule US, (8)

{1, 6} (10) F(x)® ùS(x) Rule T, (9), E₉, E₁₆, E₁₇

{1, 6} (11) (x)(F(x)® ùS(x)) Rule UG, (10)



Example 6:

Show that (x)(P(x) Ú Q(x)) Þ (x)P(x) Ú ($ x)Q(x).

Solution:

We shall use the indirect method of proof by assuming ù((x)P(x)Ú ($ x)Q(x)) as an additional premises.

{1} (1) ù((x)P(x)Ú( $ x)Q(x)) Rule P(assumed)

{1} (2) ù(x)P(x) Ù ù($ x)Q(x) Rule T, (1), E₉

{1} (3) ù(x)P(x) Rule T, (2), I₁

{1} (4) ($ x)ùP(x) Rule T, (3), E₂₆

{1} (5) ù($ x)Q(x) Rule T, (2), I₂

{1} (6) (x)ùQ(x) Rule T, (5), E₂₅

{1} (7) ùP(y) Rule ES, (4)

{1} (8) ùQ(y) Rule US, (6)

{1} (9) ùP(y) Ù ùQ(y) Rule T, (7), (8), I₉

{1} (10) ù(P(y)ÚQ(y)) Rule T, (9), E₉

{11} (11) (x)(P(x)ÚQ(x)) Rule P

{11} (12) ù(P(y)ÚQ(y)) Ù (P(y)Ú Q(y)) Rule T, (10), (12), I₉

Contradiction.

Back to top

Exercise:

1. Show that P(x) Ù (x)Q(x)Þ ( $ x)(P(x) Ù Q(x)).

2. Explain why the following steps in the derivations are not correct

(a) (1) (x)P(x)® Q(x)

(2) P(x)® Q(x) (1), Rule US

(b) (1) (x)P(x)® Q(x)

(2) P(y)® Q(x) (1), Rule US

(c) (1) (x)(P(x)ÚQ(x))

(2) P(a)ÚQ(b) (1), Rule US

(d) (1) (x)(P(x)Ú( $ x)(Q(x) Ù R(x)))

(2) P(a)Ú( $ x)(Q(x) Ù R(a)) (1), Rule US

3. What is wrong in the following steps of derivation?

(a) (1) P(x)® Q(x) Rule P

(2) ($ x)P(x)® Q(x) (1), Rule EG

(b) (1) P(a)® Q(b) Rule P

(2) ($ x)(P(x)® Q(x) (1), Rule EG

(c) (1) P(a) Ù ( $ x)(P(a) Ù Q(x)) Rule P

(2) ($ x)(P(x) Ù ( $ x)(P(x) Ù Q(x))) (1), Rule EG

4. Demonstrate the following implications.

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

5. There is a mistake in the following derivation. Find it. Is the conclusion valid? If so, obtain a correct
derivation.

{1} (1) (x)(P(x)® Q(x)) Rule P

{1} (2) P(y)® Q(y) Rule US, (1)

{3} (3) ($ x)P(x) Rule P

{3} (4) P(y) Rule ES, (3)

{1,3} (5) Q(y) Rule T, (2), (4), I₁₁

{1,3} (6) ($x)Q(x) Rule EG, (5)

6. Are the following conclusions validly derivable from the premises given?

(a) (x)(P(x)® Q(x)), ($ y)P(y) C : ( $ z)Q(z)

(b) ($ x)(P(x) Ù Q(x)) C : (x)P(x)

(c) ($ x)P(x), ($ x)Q(x) C : ( $ x)(P(x) Ù Q(x))

(d) (x)(P(x)® Q(x)), ùQ(a) C : (x)ùP(x)

7. Using CP or otherwise, show the following implications
(a) ($ x)P(x)® (x)Q(x)Þ (x)(P(x)® Q(x)).

(b) (x)(P(x)® Q(x)), (x)(R(x)® ùQ(x)) Þ (x)(R(x)® ùP(x)).

(c) (x)(P(x)® Q(x)) Þ (x)P(x)® (x)Q(x).

8. Show the following by constructing derivations

(a) ($ x)P(x)® (x)((P(x)Ú Q(x))® R(x)), ($ x)P(x),($ x)Q(x)Þ ($ x)( $ y)(R(x) Ù R(y)).

(b) (x)(P(x)® (Q(y) Ù R(x))), ($ x)P(x) Þ Q(y) Ù ( $ x)(P(x) Ù R(x)).