II

Module Two

2 Predicate Calculus . . . . . . . . . . . . . . . . . 101

2.1 Mathematical Logic
2.2 Propositions
2.3 Connectives
2.4 Order of Precedence for Logical Connectives
2.5 Conditional and Biconditional Propositions
2.6 Normal Forms
2.7 Theory of Inference
2.8 Predicate Calculus or Predicate Logic
 2. Predicate Calculus

2.1 Mathematical Logic

Logic is the discipline that deals with the methods of reasoning. One of the aims of logic is to
provide rules by which we can determine whether a particular reasoning or argument is valid.
Logical reasoning is used in many disciplines to establish valid results. Rules of logic are used to
provide proofs of theorems in mathematics, to verify the correctness of computer programs and to
draw conclusions from scientific experiments. In this chapter, we shall introduce certain logical
symbols using which we shall state and apply rules of valid inference and hence understand how to
construct correct mathematical arguments.

2.2 Propositions
A declarative sentence (or assertion) which is true or false, but not both, is called a proposition
(or statement). Sentences which are exclamatory, interrogative or imperative in nature are not
propositions. Lower case letters such as p, q, r · · · are used to denote propositions. For example, we
consider the following sentences:
(a) New Delhi is the capital city of India.
(b) How beautiful is Rose?
(c) 2 + 2 = 3
(d) What time is it?
(e) x + y = z
(f) Take a cup of coffee.
In the given statements, (b), (d) and (f) are obviously not propositions as they are not declarative in
nature. (a) and (c) are propositions, but (e) is not, since (a) is true, (c) is false and (e) is neither true
nor false as the values of x, y and z are not assigned.
If a proposition is true, we say that the truth value of that proposition is true, denoted by T or 1.
If a proposition is false, the truth value is said to be false, denoted by F or 0.
Propositions which do not contain any of the logical operators or connectives (to be introduced
in the next section) are called atomic (primary or primitive) propositions. Many mathematical
 102 Chapter 2. Predicate Calculus

statements which can be constructed by combining one or more atomic statements using connectives
are called molecular or compound propositions.
The truth value of a compound proposition depends on those of sub- propositions and the way
in which they are combined using connectives.
The area of logic that deals with propositions is called propositional logic or propositional
calculus.

2.3 Connectives
Definition 2.3.1 — Conjunction. When p and q are any two propositions, the proposition
“p and q′′ denoted by p ∧ q and called the conjunction of p and q is defined as the compound
proposition that is true when both p and q are true and is false otherwise. (∧ is the connective
used) A truth table is a table that displays the relationships between the truth values of sub-
propositions and that of compound proposition constructed from them.
Table 2.1 is the truth table for the conjunction of two propositions p and q viz., “p and q′′ .

p q p∧q
T T T
T F F
F T F
F F F

Table 2.1

Definition 2.3.2 — Disjunction. When p and q are any two propositions, the propositions
“p or q′′ denoted by p ∨ q′′ and called the disjunction of p and q is defined as the compound
proposition that is false when both p and q are false and is true otherwise. (∨ is the connective
used).
Table 2.2 is the truth table for the disjunction of two propositions p and q, viz., “p ∨ q′′ .

p q p∨q
T T T
T F T
F T T
F F F

Table 2.2

Definition 2.3.3 — Negation. Given any proposition p, another proposition formed by writing
“It is not the case that” or “It is false that” before p or by inserting the word ‘not’ suitably in p is
called the negation of p and denoted by ¬p (read as ‘not p’). ¬p is also denoted as p′ , p and
∼ p. It p is true, then ¬p is false and if p is false, then ¬p is true.

p ¬p
T F
F T

Table 2.3
 2.4 Order of Precedence for Logical Connectives 103

Table 2.3 is the truth table for the negation of p. For example, if p is the statement “New Delhi
is in India”, the ¬p is any one of the following statements.
(a) It is not the case that New Delhi is in India
(b) It is false that New Delhi is in India
(c) New Delhi is not in India
The truth value of p is T and that of p is F.

2.4 Order of Precedence for Logical Connectives

We will generally use parentheses to specify the order in which logical operators in a compound
proposition are to be applied. For example, (p ∨ q) ∧ (¬r) is the conjunction of p ∨ q and ¬r.
However to avoid the use of an excessive number of parentheses, we adopt an order of precedence
for the logical operators, given as follows:
1. The negation operator has precedence over all other logical operators. Thus ¬p ∧ q means
(¬p) ∧ q, not ¬(p ∧ q).
2. The conjunction operator has precedence over the disjunction operator. Thus p ∧ q ∨ r means
(p ∧ q) ∨ r, but not p ∧ (q ∨ r).
3. The conditional and biconditional operators → and ↔ (to be introduced subsequently) have
lower precedence than other operators. Among them, → has precedence over ↔.

2.5 Conditional and Biconditional Propositions

Definition 2.5.1 If p and q are propositions, the compound proposition “if p, then q”, that is
denoted by p → q is called a conditional proposition, which is false when p is true and q is false
and true otherwise.
In this conditional proposition, p is called the hypothesis or premise and q is called the
conclusion or consequence. Some authors call p → q as an implication.

For example, let us consider the statement. “If I get up at 5 A.M., I will go for a walk”, which may
be represented as p → q and considered as a contract.
If p is true and q is also true, the contract is not violated and so ‘p → q′ is true.
If p is true and q is false (viz., I get up at 5 A.M., but I do not go for a walk), the contract is
violated and so ‘p → q′ is false.
If p is false and whether q is true or false (viz., when I have not got up at 5 A.M; I may or may
not go for a walk), the contract is not violated and so ‘p → q′ is true.
Accordingly, the truth table for the conditional proposition p → q will be as given in Table 2.4.
The alternative terminologies used to express p → q (if p, then q) are the following:

p q p→q
T T T
T F F
F T T
F F T

Table 2.4

(i) p implies q,
(ii) p only if q [“If p, then q” formulation emphasizes the hypothesis, whereas “p only if q”
formulation emphasizes the conclusion; the difference is only stylistic,
(iii) q if p or q when p,
(iv) q follows from p,
104 Chapter 2. Predicate Calculus

(v) p is sufficient for q or a sufficient condition for q is p and

(vi) q is necessary for p or a necessary conditions for p is q.
Definition 2.5.2 — Biconditional Proposition. If p and q are propositions, the compound
proposition “p if and only if q”, that is denoted by p ↔ q, is called a biconditional proposition,
which is true when p and q have the same truth values and is false otherwise.
It is easily verified that ‘p ↔ q’ is true when both the conditionals p → q and q → p are true.
This is the reason for the symbol ↔ which is a combination of → and ←.
Alternatively, ‘p ↔ q’ is also expressed as ‘p iff q’ and ‘p is necessary and sufficient for q’ .
The truth table for ‘p ↔ q’ is given in Table 2.5.

p q p↔q
T T T
T F F
F T F
F F T

Table 2.5

Definition 2.5.3 — Tautology and Contradiction. A compound proposition P = P(p1 , p2 , · · · , pn ),

where p1 , p2 , · · · , pn are variables (elemental propositions), is called a tautology, if it is true for
every truth assignment for p1 , p2 , · · · , pn .
P is called a contradiction, if it is false for every truth assignment for p1 , p2 , · · · , pn .

For example, p ∨ ¬p is a tautology, whereas p ∧ ¬p is a contradiction, as seen from the Table

2.6 given below.

p ¬p p ∨ ¬p p ∧ ¬p
T F T F
F T T F

Table 2.6

Note 2.5.1 1. The negation of a tautology is a contradiction and the negation of a contradiction
is a tautology.
2. If P(p1 , p2 , · · · , pn ) is a tautology, then P(q1 , q2 , · · · , qn ) is also a tautology, where q1 , q2 , · · · , qn
are any set of propositions. This is known as the principle of substitution. For example, since
p ∨ ¬p is a tautology, ((p ∨ q) ∧ r)v¬((p ∨ q) ∧ r) is also a tautology.
3. If a proposition is neither a tautology nor a contradiction, it is called a contingency.
Definition 2.5.4 — Equivalence of Propositions. Two compound propositions A(p1 , p2 , · · · , pn )
and B(p1 , p2 , · · · , pn ) are said to be logically equivalent or simply equivalent, if they have iden-
tical truth tables, viz. if the truth value of A is equal to the truth value of B for every one of the
2n possible sets of truth values assigned to p1 , p2 , · · · , pn .

The equivalence of two propositions A and B is denoted as A ⇔ B or A ≡ B (which is read as

‘A is equivalent to B’). ⇔ or ≡ is not a connective.
For example, let us consider the truth tables of ¬(p ∨ q) and ¬p ∧ ¬q (see Table 2.7). The final
columns in the truth tables for ¬(p ∨ q) and ¬p ∧ ¬q are identical. Hence ¬(p ∨ q) ≡ ¬p ∧ ¬q.
2.5 Conditional and Biconditional Propositions 105

p q p∨q ¬(p ∨ q) ¬p ¬q ¬p ∧ ¬q
T T T F F F F
T F T F F T F
F T T F T F F
F F F T T T T

Table 2.7

Note 2.5.2 We have already noted that the biconditional proposition A ↔ B is true whenever both
A and B have the same truth value, viz. A ↔ B is a tautology, when A and B are equivalent.
Conversely, A ≡ B, when A ↔ B is a tautology. For example, (p → q) ≡ (¬p ∨ q), since
(p → q) ↔ (¬p ∨ q) is a tautology, as seen from the truth Table 2.8 given below:

p q p→q ¬p ¬p ∨ q (p → q) ↔ (¬p ∨ q)
T T T F T T
T F F F F T
F T T T T T
F F T T T T

Table 2.8

Definition 2.5.5 — Duality of Compound Proposition. The dual of a compound proposition

that contains only the logical operators ∨, ∧ and ¬ is the proposition obtained by replacing
each ∨ by ∧, each ∧ by ∨, each T by F and each F by T , where T and F are special variables
representing compound propositions that are tautologies and contradictions respectively. The
dual of a proposition A is denoted by A∗ .

Theorem 2.5.1 — Duality Theorem. If A(p1 , p2 , · · · , pn ) ≡ B(p1 , p2 , · · · , pn ), where A and B

are compound propositions, then A∗ (p1 , p2 , · · · , pn ) ≡ B∗ (p1 , p2 , · · · , pn ).

Proof. In Table 2.7, we have proved that

(p ∨ q) ≡ ¬p ∧ ¬q or p ∨ q ≡ ¬(¬p ∧ ¬q) (2.1)

Similarly we can prove that

p ∧ q ≡ ¬(¬p ∨ ¬q) (2.2)

(2.1) and (2.2) are known as De Morgan’s laws. Using (2.1) and (2.2), we can show that

¬A(p1 , p2 , · · · , pn )¬A ∗ (¬p1 , ¬p2 , · · · , ¬pn ) (2.3)

Equation (2.3) means that the negation of a proposition is equivalent to its dual in which every
variable (primary proposition) is replaced by its negation. From Eq. (2.3), it follows that

A(p1 , p2 , · · · , pn ) ≡ ¬A∗ (¬p1 , ¬p2 , · · · , pn ) (2.4)

Now since A(p1 , p2 , · · · , pn ) ≡ B(p1 , p2 , · · · , pn ), we have A(p1 , p2 , · · · , pn ) ↔ B(p1 , p2 , · · · , pn ) is

tautology.

∴ A(¬p1 , p2 , · · · , pn ) ↔ B(p1 , p2 , · · · , pn ) (2.5)

106 Chapter 2. Predicate Calculus

is also a tautology.
Using (2.4) in (2.5), we get
A∗ (p1 , p2 , · · · , pn ) ↔ B∗ (p1 , p2 , · · · , pn )
is a tautology.
∴ A∗ ↔ B∗ is a tautology.
∴ A ≡ B∗
∗ ■

Definition 2.5.6 — Algebra Of Propositions. A proposition in a compound proposition can

be replaced by one that is equivalent to it without changing the truth value of the compound
proposition. By this way, we can construct new equivalences (or laws). For example, we have
proved that p → q ≡ ¬p ∨ q (Table 2.8). Using this equivalence, we get another equivalence
p → (q → r) ≡ p → (¬q ∨ r). Some of the basic equivalences (laws) and their duals which will
be of use later are given in Tables 2.9, 2.10 and 2.11. They can be easily established by using
truth tables.

Sl. No. Name of the law Primal form Dual form

1. Idempotent law p∨ p ≡ p p∧ p ≡ p
2. Identity law p∨F ≡ p p∧T ≡ p
3. Dominant law p∨T ≡ T p∧F ≡ F
4. Complement law p ∨ ¬p ≡ T p ∧ ¬p ≡ F
5. Commutative law p∨q ≡ q∨ p p∧q ≡ q∧ p
6. Associative law (p ∨ q) ∨ r ≡ p ∨ (q ∨ r) (p ∧ q) ∧ r ≡ p ∧ (q ∧ r)
7. Distributive law p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r) p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r)
8. Absorption law p ∨ (p ∧ q) ≡ p p ∧ (p ∨ q) ≡ p
9. De Morgan’s law ¬(p ∨ q) ≡ ¬p ∧ ¬q ¬(p ∧ q) ≡ ¬p ∨ ¬q

Table 2.9: Laws of Algebra of Propositions

Sl. No. Equivalences Conditionals

1 p → q ≡ ¬p ∨ q
2 p → q ≡ ¬q → ¬p
3 p ∨ q ≡ ¬p → q
4 p ∧ q ≡ ¬(p → ¬q)
5 ¬(p → q) ≡ p ∧ ¬q
6 (p → q) ∧ (p → r) ≡ p → (q ∧ r)
7 (p → r) ∧ (q → r) ≡ (p ∨ q) → r
8 (p → q) ∨ (p → r) ≡ p → (q ∨ r)
9 (p → r) ∨ (q → r) ≡ (p ∧ q) → r

Table 2.10: Equivalences Involving Conditionals

Sl. No. Equivalences Involving Biconditionals

1 p ↔ q ≡ (p → q) ∧ (q → p)
2 p ↔ q ≡ ¬p ↔ ¬q
3 p ↔ q ≡ (p ∧ q) ∨ (¬p ∧ ¬q)
4 ¬(p ↔ q) ≡ p ↔ ¬q

Table 2.11: Equivalences Involving Biconditionals

2.5 Conditional and Biconditional Propositions 107

Definition 2.5.7 — Tautological Implication. A compound proposition A(p1 , p2 , · · · , pn ) is

said to tautologically imply or simply imply the compound proposition B(p1 , p2 , · · · , pn ), if B is
true whenever A is true or equivalently if and only if A → B is a tautology. This is denoted by
A ⇒ B, read as “A implies B”.
Note 2.5.3 ⇒ is not a connective and A ⇒ B is not a proposition).
For example, p ⇒ p ∨ q, as seen from the following truth Table 2.12. We note that p ∨ q is
true, whenever p is true and that p → (p ∨ q) is a tautology.

p q p∨q p → (p ∨ q)
T T T T
T F T T
F T T T
F F F T

Table 2.12

Similarly we note that (p → q) ⇒ (¬q → ¬p) from the following truth Table 2.13.

p q ¬p ¬q p→q ¬q → ¬p (p → q) → (¬q → ¬p)

T T F F T T T
T F F T F F T
F T T F T T T
F F T T T T T

Table 2.13

Some important implications which can be proved by truth tables are given in Table 2.14.

Sl. No. Implications

1 p∧q ⇒ p
2 p∧q ⇒ q
3 p ⇒ p∨q
4 ¬p ⇒ p → q
5 q⇒ p→q
6 ¬(p → q) ⇒ p
7 ¬(p → q) ⇒ ¬q
8 p ∧ (p → q) ⇒ ¬p
9 ¬q ∧ (p ∨ q) ⇒ q
10 ¬p ∧ (p ∨ q) ⇒ q
11 (p → q) ∧ (q → r) ⇒ p → r
12 (p ∨ q) ∧ (p → r) ∧ (q → r) ⇒ r

Table 2.14: Implications

108 Chapter 2. Predicate Calculus

Note 2.5.4 We can easily verify that if A ⇒ B and B ≡ A, then A ≡ B. Hence to prove the
equivalence of two propositions, it is enough to prove that each implies the other.
Problem 2.1 Construct a truth table for each of the following compound propositions: (p ∨ q) →
(p ∧ q);

p q p∨q p∧q (p ∨ q) → (p ∧ q)
T T T T T
T F T F F
F T T F F
F F F F T

Table 2.15: Truth Table for (p ∨ q) → (p ∧ q)

Problem 2.2 Construct a truth table for each of the following compound propositions: (p → q) →
(q → p);

p q p→q q→ p (p → q) → (q → p)
T T T T T
T F F T T
F T T F F
F F T T T

Table 2.16: Truth Table for (p → q) → (q → p)

Problem 2.3 Construct a truth table for each of the following compound propositions: (q →
¬p) ↔ (p ↔ q);

p q ¬p q → ¬q p↔q (q → ¬p) ↔ (p ↔ q)
T T F F T F
T F F T F F
F T T T F F
F F T T T T

Table 2.17: Truth Table for (q → ¬p) ↔ (p ↔ q)

2.5 Conditional and Biconditional Propositions 109

Problem 2.4 Construct a truth table for each of the following compound propositions: (p ↔ q) ↔
((p ∧ q) ∨ (¬p ∧ ¬q));

p q ¬p ¬q p↔q p∧q ¬p ∧ ¬q (p ∧ q) ∨ (¬p ∧ ¬q) f

T T F F T T F T T
T F F T F F F F T
F T T F F F F F T
F F T T T T T T T

Table 2.18: Truth Table for (p ↔ q) ↔ ((p ∧ q) ∨ (¬p ∧ ¬q))

Problem 2.5 Construct a truth table for each of the following compound propositions: (¬p ↔
¬q) ↔ (p ↔ q).

p q ¬p ¬q ¬p ↔ ¬q p↔q (¬p ↔ ¬q) ↔ (p ↔ q)

T T F F T T T
T F F T F F T
F T T F F F T
F F T T T T T

Table 2.19: Truth Table for (¬p ↔ ¬q) ↔ (p ↔ q)

Note 2.5.5 Formulas given in 2.18 and 2.19 are tautologies.

Problem 2.6 Construct the truth table for each of the compound propositions given as follows:

((p → (q → r)) → ((p → q) → (p → r))

p q r p→q q→r p→r ((p → (q → r)) ((p → q) → (p → r)) a→b

≡a ≡b
T T T T T T T T T
T T F T F F F F T
T F T F T T T T T
T F F F T F T T T
F T T T T T T T T
F T F T F T T T T
F F T T T T T T T
F F F T T T T T T

Table 2.20: Truth Table for ((p → (q → r)) → ((p → q) → (p → r))

Proof. The given compound proposition is a tautology. ■

110 Chapter 2. Predicate Calculus

Problem 2.7 Construct the truth table for each of the compound propositions given as follows:
¬(p ∨ (q ∧ r)) ↔ ((p ∨ q) ∧ (p → r))

p q r q∧r p ∨ (q ∧ r) ¬a p∨q p→r (p ∨ q) ∧ (p → r) ¬a ↔ b

≡a ≡b
T T T T T F T T T F
T T F F T F T F F T
T F T F T F T T T F
T F F F T F T F F T
F T T T T F T T T F
F T F F F T T T T T
F F T F F T F T F F
F F F F F T F T F F

Table 2.21: Truth Table for ¬(p ∨ (q ∧ r)) ↔ ((pvq) ∧ (p → r))

Problem 2.8 Construct the truth table for each of the compound propositions given as follows:
(¬p ↔ ¬q) ↔ (q ↔ r)

p q r ¬p ¬q ¬p ↔ ¬q ≡ a q↔r≡b a↔b
T T T F F T T T
T T F F F T F F
T F T F T F F T
T F F F T F T F
F T T T F F T F
F T F T F F F T
F F T T T T F F
F F F T T T T T

Table 2.22: Truth Table for (¬p ↔ ¬q) ↔ (q ↔ r)

Problem 2.9 Construct the truth table for each of the compound propositions given as follows:

(i) (p → (q → s)) ∧ (¬r ∨ p) ∧ q

(ii) ((p → q) → r) → s
2.5 Conditional and Biconditional Propositions 111

p q r s q→s≡a p→a≡b ¬r ¬r ∨ p ≡ c b∧c b∧c∧q

T T T T T T F T T T
T T T F F F F T F F
T T F T T T T T T T
T T F F F F T T F F
T F T T T T F T T F
T F T F T T F T T F
T F F T T T T T T F
T F F F T T T T T F
F T T T T T F F F F
F T T F F T F F F F
F T F T T T T T T T
F T F F F T T T T T
F F T T T T F F F F
F F T F T T F F F F
F F F T T T T T T F
F F F F T T T T T F

Table 2.23: Truth Table for (p → (q → s)) ∧ (¬r ∨ p) ∧ q

p q r s p→q (p → q) → r ((p → q) → r) → s
T T T T T T T
T T T F T T F
T T F T T F T
T T F F T F T
T F T T F T T
T F T F F T F
T F F T F T T
T F F F F T F
F T T T T T T
F T T F T T F
F T F T T F T
F T F F T F T
F F T T T T T
F F T F T T F
F F F T T F T
F F F F T F T

Table 2.24: Truth Table for ((p → q) → r) → s

Proof. ■
112 Chapter 2. Predicate Calculus

Problem 2.10 Determine which of the following compound propositions are tautologies and which
of them are contradictions, using truth tables:
(i) ¬q ∧ (p → q) → p
(ii) ((p → q) ∧ (q → r)) → (p → r)
(iii) ¬(q ∨ r) ∧ r ∧ (p → q)
(iv) ((p ∨ q) ∧ (p → r) ∧ (q → r)) → r.

p q ¬p ¬q p→q ¬q ∧ (p → q) (¬q ∧ (p → q)) → p

T T F F T F T
T F F T F F T
F T T F T F T
F F T T T T T

Table 2.25: Truth Table for (¬q ∧ (p → q)) → p

Proof. From Table 2.25, since the truth value of the given compound proposition is T for all
combinations of p and q, it is a tautology.

p q r p→q p→r q→r (p → q) ∧ (q → r) ((p → q) ∧ (q → r)) → (p → r)

T T T T T T T T
T T F T F F F T
T F T F T T F T
T F F F F T F T
F T T T T T T T
F T F T T F F T
F F T T T T T T
F F F T T T T T

Table 2.26: Truth Table for ((p → q) ∧ (q → r)) → (p → r)

From Table 2.26, since the truth value of the given statement is T for all combinations of truth
values of p, q and r, it is a tautology.

p q r p→q q→r ¬(q → r) (q → r) ∧ r ¬(q → r) ∧ r ∧ (p → q)

T T T T T F F F
T T F T F T F F
T F T F T F F F
T F F F T F F F
F T T T T F F F
F T F T F T F F
F F T T T F F F
F F F T T F F F

Table 2.27: Truth Tables for ¬(q ∨ r) ∧ r ∧ (p → q)

From Table 2.27, the last column contains only F as the truth values of the given statement.
Hence it is a contradiction.
2.5 Conditional and Biconditional Propositions 113

p q r p∨q ≡ a p→r≡b a∧b q→r≡c a∧b∧c (a ∧ b ∧ c) → r

T T T T T T T T T
T T F T F F F F T
T F T T T T T T T
T F F T F F T F T
F T T T T T T T T
F T F T T T F F T
F F T F T F T F T
F F F F T F T F T

Table 2.28: Truth Table for ((p ∨ q) ∧ (p → r) ∧ (q → r)) → r

From Table 2.28, since all the entries in the last column are T ’s, the given statement is a
tautology. ■

Problem 2.11 Without using truth tables, prove the following:

(i) (¬p ∨ q) ∧ (p ∧ (p ∧ q) ≡ p ∧ q
(ii) p → (q → p) ≡ ¬p → (p → q)
(iii) (p ↔ q) ≡ (p ∨ q) ∧ ¬(p ∨ q) ≡ (¬p ∧ ¬q) ∨ (¬p ∧ q)

Proof. (i)

(¬p ∨ q) ∧ (p ∧ (p ∧ q)) ≡ (¬p ∨ q) ∧ (p ∧ p) ∧ q, Associative Law

≡ (¬p ∨ q) ∧ (p ∧ q), Idempotent Law
≡ (p ∧ q) ∧ (¬p ∨ q), Commutative Law
≡ ((p ∧ q) ∧ ¬p) ∨ ((p ∧ q) ∧ q), Distributive Law
≡ (¬p ∧ (p ∧ q)) ∨ ((p ∧ q) ∧ q), Commutative Law
≡ ((¬p ∧ p) ∧ q) ∨ (p ∧ (q ∧ q)), Associative Law
≡ (F ∧ q) ∨ (p ∧ (q ∧ q)), Complement Law
≡ (F ∧ q) ∨ (p ∧ q), Idempotent Law
≡ F ∨ (p ∧ q), Dominant Law
≡ p ∧ q, Identity Law.

(ii)

p → (q → p) ≡ ¬p ∨ (q → p) [Refer to Table 2.10]

≡ ¬p ∨ (¬q ∨ p) [Refer to Table 2.10]
≡ ¬q ∨ (p ∨ ¬p), Commutative and Associative Laws
≡ ¬p ∨ T, Complement Law
≡ T, Dominant Law (2.6)
¬p → (p → q) ≡ p ∨ (p → q), by (2.6) of Table 2.10
≡ p ∨ (¬p ∨ q), by (2.6) of Table 1.10
≡ (p ∨ ¬p) ∨ q, Associative Law
≡ T ∨ q, Complement Law
≡ T, Dominant Law, (2.7)

From (2.6) and (2.7), the result follows.

114 Chapter 2. Predicate Calculus

(iii)
¬(p ↔ q) ≡ ¬((p → q) ∧ (q → p)), from Table 2.11
≡ ¬((¬p ∨ q) ∧ (¬q ∨ q)), from Table 2.10
≡ ¬[((¬p ∨ q) ∧ ¬q) ∨ ((¬p ∨ q) ∧ p], Distributive Law
≡ ¬[((¬p ∧ ¬q) ∨ (q ∧ ¬q)) ∨ ((¬p ∧ p)) ∨ (q ∧ p))], Distributive Law
≡ ¬[((¬p ∧ ¬q) ∨ F) ∨ ((F ∨ (q ∧ p))], Complement Law
≡ ¬[(¬p ∧ ¬q) ∨ (q ∧ p)], Identity Law
≡ ¬[(¬p ∨ q) ∨ (q ∧ p)], De Morgan’s Law
≡ (p ∨ q) ∧ ¬(q ∧ p), De Morgan’s Law (2.8)

¬(p ↔ q) ≡ (p ∨ q) ∧ (¬q ∨ ¬p), De Morgan’s Law

≡ ((p ∨ q) ∧ ¬q)) ∨ ((p ∨ q) ∧ ¬p)), Distributive Law
≡ ((p ∧ ¬q) ∨ (q ∧ ¬q)) ∨ ((p ∧ ¬p) ∨ (q ∧ ¬p)), Distributive Law
≡ ((p ∧ ¬q) ∨ F) ∨ ((F ∨ (q ∧ ¬p)), Complement Law
≡ (p ∧ ¬q) ∨ (q ∧ ¬p), Identity Law
≡ (p ∧ ¬q) ∨ (¬p ∧ q), Commutative Law (2.9)
From (2.8) and (2.9), the result follows. ■
Problem 2.12 Without constructing the truth tables, prove the following:
(i) p ∧ (q ∧ r) ≡ q ∧ (p ∨ r)
(ii) p ∧ (q ∧ r) ≡ p ∧ (q ∨ r) ≡ (p ∧ q) ∧ r
(iii) ((p ∨ q) ∧ (p ∧ (q ∨ r))) ∨ (p ∧ q) ∨ (p ∧ r) is a tautology.
Proof. (i)
¬p → (q → r) ≡ p ∨ (q → r), from Table 2.10
≡ p ∨ (¬q ∨ r), from Table 2.10
≡ (pv¬q) ∨ r, Associative Law
≡ (¬q ∨ p) ∨ r, Commutative Law
≡ ¬q ∨ (p ∨ r), Associative Law
≡ q → (p ∨ r), from Table 2.10
(ii)
p → (q → r) ≡ p → (¬q ∨ r), from Table 2.10
Now p → (¬q ∨ r) ≡ ¬p ∨ (¬q ∨ r), from Table 2.10
≡ ¬(¬p ∨ q) ∨ r, Associative Law
≡ ¬(p ∧ q) ∨ r, De Morgan’s Law
≡ (p ∧ q) → r
(iii)
((p ∨ q) ∧ ¬(¬p ∧ (¬q ∨ ¬r))) ∨ (¬p ∧ ¬q) ∨ (¬p ∧ ¬r)
≡ ((p ∨ q) ∧ ¬(¬p ∨ ¬(q ∧ r))) ∨ ¬(p ∨ q) ∨ ¬(p ∨ r), De Morgan’s Law
≡ ((p ∨ q) ∧ [(p ∨ q) ∧ (p ∨ r)]) ∨ [¬(p ∨ q) ∨ ¬(p ∨ r)], Distributive Law
≡ ((p ∨ q) ∧ (p ∨ r)) ∨ [¬(p ∨ q) ∨ ¬(p ∨ r)], Idempotent Law
≡ [(p ∨ q) ∧ (p ∨ r)] ∨ ¬[(p ∨ q) ∧ (p ∨ r)], De Morgan’s laws
2.5 Conditional and Biconditional Propositions 115

The final statement is in the form of p ∨ ¬p.

∴ L.H.S. ≡ T
Hence the given statement is tautology. ■

Problem 2.13 Prove the following equivalences by proving the equivalences of the duals:
(i) ¬((¬p ∧ q) ∨ (¬p ∧ ¬q)) ∨ (p ∧ q) ≡ p
(ii) (p ∨ q) → r ≡ (p → r) ∧ (q ∧ r)
(iii) (p ∧ (p ↔ q)) → q ≡ T

Proof. (i) The dual of the given equivalence is

¬((¬p ∨ q) ∧ (¬p ∨ ¬q)) ∧ (p ∨ q) ≡ p

Let us now prove the dual equivalence.

L.H.S. ≡ ¬(¬p ∨ (q ∧ ¬q)) ∧ (p ∨ q), Distribution Law

≡ ¬(¬p ∨ F) ∧ (p ∨ q), Complement Law
≡ ¬(¬p) ∧ (p ∨ q), Identity Law
≡ p ∧ (p ∨ q)
≡ p, Absorption Law

(ii)

(p ∨ q) → r ≡ (p → r) ∧ (q → r)
i.e., ¬(p ∨ q) ∨ r ≡ (¬p ∨ r) ∧ (¬q ∨ r)

Dual of this equivalence is

¬(p ∧ q) ∧ r ≡ (¬p ∧ r) ∨ (¬q ∧ r)

L.H.S ≡ (¬p ∨ q) ∧ r, De Morgan’s law

≡ (¬p ∧ r) ∨ (¬q ∧ r), Distributive Law
≡ R.H.S.

(iii)

(p ∧ (p ↔ q)) → q ≡ T
i.e. p ∧ ((p → q) ∧ (q → p)) → q ≡ T, from Table 2.11
i.e. p ∧ ((¬p ∨ q) ∧ (¬q ∨ p)) → q ≡ T
i.e. ¬(p ∧ ((¬p ∨ q) ∧ (¬q ∨ p))) ∨ q ≡ T

Dual of this equivalence is

(p ∨ ((¬p ∧ q) ∨ (¬q ∧ p))) ∧ q ≡ F

116 Chapter 2. Predicate Calculus

L.H.S. ≡ ¬[(p ∨ (¬p ∧ q)) ∨ (¬q ∧ p)] ∧ q, Associative Law

≡ ¬[(T ∧ (p ∨ q)) ∨ (¬q ∧ p)] ∧ q, Distributive and Complement Laws
≡ ¬[(pvq) ∨ (¬q ∧ p)] ∧ q, Identity Law
≡ ¬[((p ∨ q) ∨ ¬q) ∧ ((p ∨ q) ∨ p)] ∧ q, Distributive Law
≡ ¬[(p ∨ T ) ∧ (p ∨ q)] ∧ q, Idempotent and Complement Laws.
≡ ¬[T ∧ (p ∨ q)] ∧ q, Dominant Law
≡ ¬[p ∨ q] ∧ q, Identity Law
≡ (¬p ∧ ¬q) ∧ q, De Morgan’s Law
≡ (¬p ∧ F), Complement Law
≡ F, Dominant Law.

Problem 2.14 Prove the following implications by using truth tables: p → ((q → r) ⇒ (p → q) →
(p → r)

Solution. We have defined that A → B, if and only if A → B is a tautology

p q r p→q q→r p→r p→b a→c d→e

(a) (b) (c) (d) (e)
T T T T T T T T T
T T F T F F F F T
T F T F T T T T T
T F F F T F T T T
F T T T T T T T T
F T F T F T T T T
F F T T T T T T T
F F F T T T T T T

Table 2.29

Since d → e, viz., [p → (q → r)] → [(p → q) → (p → r)] is a tautology, the required implication

follows. ■

Problem 2.15 Prove the following implications by using truth tables:

(p → (q → s)) ∧ (¬r ∨ p) ∧ q ⇒ r → s

Solution.
2.5 Conditional and Biconditional Propositions 117

p q r s q→s p→a ¬r ¬r ∨ p b∧c d ∧q r→s e→ f

(a) (b) (c) (d) (e) (f)
T T T T T T F T T T T T
T T T F F F F T F F F T
T T F T T T T T T T T T
T T F F F F T T F F T T
T F T T T T F T T F T T
T F T F T T F T T F F T
T F F T T T T T T F T T
T F F F T T T T T F T T
F T T T T T F F F F T T
F T T F F T F F F F F T
F T F T T T T T T T T T
F T F F F T T T T T T T
F F T T T T F F F F T T
F F T F T T F F F F F T
F F T F T T F F F F F T
F F F F T T T T T F T T

Since e → f is a tautology, e ⇒ f . ■

Problem 2.16 Prove the following implications without using truth tables:
(i) (p ∨ q) ∧ (p → r) ∧ (q → r) ⇒ r
(ii) ((p ∨ ¬p) → q) → ((p ∨ ¬p) → r) ⇒ q → r

Proof.

(i) [(p ∨ q) ∧ (p → r) ∧ (q → r)] → r ≡ (p ∨ q) ∧ ((p ∨ q) → r) → r, from Table 2.10

≡ (p ∨ q) ∧ (¬(p ∨ q) ∨ r) → r
≡ (F ∨ (p ∨ q) ∧ r) → r
≡ ((p ∨ q) ∧ r) → r
≡ ¬((p ∨ q) ∧ r) ∨ r
≡ ¬((p ∧ r) ∨ (q ∧ r)) ∨ r
≡ (¬(p ∧ r) ∧ ¬(q ∧ r)) ∨ r
≡ (¬(p ∧ r) ∨ r) ∧ (¬(q ∧ r) ∨ r)
≡ (¬p ∨ ¬r ∨ r) ∧ (¬q ∨ ¬r ∨ r)
≡ (¬p ∧ T ) ∧ (¬q ∧ T )
≡ T ∧T
≡T

(ii) [((p ∨ ¬p) → q) → ((p ∨ ¬p) → r)] → (q → r) ≡ [(T → q) → (T → r)] → (q → r)

≡ [(F ∨ q) → (F ∨ r)] → (q → r)
≡ (q → r) → (q → r)
≡T

■
 118 Chapter 2. Predicate Calculus

2.6 Normal Forms

To determine whether a given compound proposition A(p1 , p2 , · · · , pn ) is a tautology or a contra-
dictor or at least satisfiable and whether two given compound propositions A(p1 , p2 , · · · , pn ) and
B(p1 , p2 , · · · , pn ) are equivalent, we have to construct the truth tables and compare them.
Note 2.6.1 A(p1 , p2 , · · · , pn ) is said to be satisfiable, if it has the truth value T for at least one
combination of the truth values of p1 , p2 , · · · , pn .
Definition 2.6.1 — Normal Forms. Construction of truth tables may not be practical, when the
number of primary propositions (variables) p1 , p2 , · · · , pn increases. A better method is to reduce
A and B to some standard forms, called normal forms and use them for deciding the nature of A
or B and for comparing A and B. There are two types of normal form - disjunctive normal form
and conjunctive normal form. We shall use the word ‘product’ in place of ‘conjunction’ and
‘sum’ in place ‘disjunction’ hereafter in this section for convenience.

Definition 2.6.2 — Disjunctive and Conjunctive Normal Forms. A product of the variables
and their negations (a conjunction of primary statements and their negations) is called an
elementary product. Similarly, a sum of the variables and their negations is called an elementary
sum.
For example, p, ¬p, p ∧ ¬p, ¬p ∧ q, p ∧ ¬q and ¬p ∧ ¬q are some elementary products in 2
variables q, ¬q, p ∨ q, p ∨ ¬q and ¬p ∨ ¬q are some elementary sums is 2 variables.
A compound proposition (or a formula) which consists of a sum of elementary products
and which is equivalent to a given proposition is called a disjunctive normal form (DNF) of the
given proposition.
A formula which consists of a product of elementary sums and which is equivalent to a
given formula is called a conjunctive normal form (CNF) of the given formula.

2.6.1 Procedure to Obtain the DNF or CNF of a Given Formula

Step I If the connectives → and ↔ are present in the given formula they are replaced by ∧, ∨ and
¬ viz. p → q is replaced by ¬p ∨ q and p ↔ q is replaced by either (p ∧ q) ∨ (¬p ∧ ¬q) or
(¬p ∨ q) ∧ (¬q ∨ p).

p → q ≡ ¬p ∨ q
p ↔ q ≡ (p ∧ q) ∨ (¬p ∧ ¬q)
≡ (¬p ∨ q) ∧ (¬q ∨ p)

Step II If the negation is present before the given formula or a part of the given formula (not a
variable), De Morgan’s laws are applied so that the negation is brought before the variables
only.
Step II If necessary, the distributive law and the idempotent law are applied.
Step IV If there is an elementary product which is equivalent to the truth value F in the DNF, it is
omitted. Similarly if there is an elementary sum which is equivalent to the truth value T in
the CNF, it is omitted.
For example, the DNF of q → (q → p) is given by

q → (q → p) ≡ ¬q ∨ (q → p)
≡ ¬q ∨ (¬q ∨ p)
≡ (¬q ∨ ¬q) ∨ p [Associative Law]
≡ ¬q ∨ p ≡ p ∨ ¬q [Idempotent Law]
 2.6 Normal Forms 119

The CNF of ¬(p ∨ q) ↔ (p ∧ q) is given by

¬(p ∨ q) ↔ (p ∧ q) ≡ (¬(p ∨ q) ∧ (p ∧ q)) ∨ (¬(¬(p ∨ q)) ∧ ¬(p ∧ q))

≡ ((¬p ∧ ¬q) ∧ (p ∧ q)) ∨ (p ∨ q) ∧ (¬p ∨ ¬q)
≡ (p ∧ ¬p) ∧ (q ∧ ¬q) ∨ (p ∨ q) ∧ (¬ ∧ p ∨ ¬q)
≡ F ∧ F ∨ (p ∨ q) ∧ (¬p ∨ ¬q)
≡ (p ∨ q) ∧ (¬p ∨ ¬q)

2.6.2 Principal Disjunctive and Principal Conjunctive Normal Forms

Given a number of variables, the products (or conjunctions) in which each variable or its negation,
but not both, occurs only once are called the minterms. For two variable p and q, the possible
minterms are p ∧ q, p ∧ ¬q, ¬p ∧ q and ¬p ∧ ¬q.
For three variables p, q and r, the possible minterms are p ∧ q ∧ r, ¬p ∧ q ∧ r, p ∧ ¬q ∧ r,
p ∧ q ∧ ¬r, ¬p ∧ ¬q ∧ r, p ∧ ¬q ∧ ¬r, ¬p ∧ q ∧ ¬r, and ¬p ∧ ¬q ∧ ¬r.
We note that there are 2n minterms for n variables.
Given a number of variables, the sums (or disjunctions) in which each variable or its negation,
but not both, occurs only once are called the maxterms.
For the two variables p and q, the possible maxterms are p ∨ q, p ∨ ¬q, ¬p ∨ q and ¬p ∨ ¬q.
The maxterms are simply the duals of minterms.
A formula (compound proposition) consisting of disjunctions of minterms in the variables
only and equivalent to a given formula is known as its principal disjunctive normal form (PDNF)
or its sum of products canonical form of the given formula. Similarly, a formula consisting of
conjunctions of maxterms in the variables only and equivalent to given formula is known as its
principal conjunctive normal form (PCNF) or its product of sums canonical form.
In order to obtain the PDNF of a formula, we first obtain a DNF of the formula by using the
procedure given above. To get the minterms in the disjunctions, the missing factors are introduced
through the complement law (viz. P ∨ P¬ = T ) and then applying the distributive law. Identical
minterms appearing in the disjunctions are then deleted, as P ∨ P = P. A similar procedure with
necessary modifications is adopted to get the PCNF of a formula.
In order to verify whether two given formulas are equivalent, we may obtain either PDNF or
PCNF of both the formulas and compare them.
Note 2.6.2 If the PDNF of a formula A is known, the PDNF of ¬A will consist of the disjunctions
of the remaining minterms which are not included in the PDNF of A.
To obtain the PCNF of A, we use the fact that A = ¬(¬A) and apply De Morgan’s laws to the
PDNF of ¬A repeatedly.
Definition 2.6.3
(i) The PDNF of (p ∨ ¬q) is given by

p ∨ ¬q ≡ p ∧ (q ∨ ¬q) ∨ ¬q ∧ (p ∨ ¬p), Complement Law

≡ (p ∧ q) ∨ (p ∧ ¬q) ∨ (¬q ∧ p) ∨ (¬q ∧ ¬p), Distributive Law
≡ (p ∧ q) ∨ (p ∧ ¬q) ∨ (p ∧ ¬q) ∨ (¬p ∧ ¬q), Commutative Law
≡ (p ∧ q) ∨ (p ∧ ¬q) ∨ (¬p ∧ ¬q), Idempotent Law

(ii) To get the PCNF of p ↔ q, we proceed as follows:

The PDNF of p ↔ q ≡ (p ∧ q) ∨ (¬p ∧ ¬q) [Assumed from Table 2.11]

∴ PDNF of ¬(p ↔ q) ≡ (¬p ∧ q) ∨ (p ∧ ¬q) (remaining minterms) (2.10)
120 Chapter 2. Predicate Calculus

∴ PCNF of p ↔ q ≡ ¬¬(p ↔ q)
≡ ¬((¬p ∧ q) ∨ (p ∧ ¬q), Form (2.10)
≡ ¬(¬p ∧ q) ∧ ¬(p ∧ ¬q), De Morgan’s law
≡ (p ∨ ¬q) ∧ (¬p ∨ q), De Morgan’s law,
Problem 2.17 Find the disjunctive normal forms of the following statements:
(i) ¬(¬(p ↔ q) ∧ r)
(ii) p ∨ (¬p → (q ∨ (q → ¬r)))
(iii) p ∧ ¬(q ∧ r) ∨ (p → q)
(iv) (p ∧ ¬(q ∨ r)) ∨ (((p ∧ q) ∨ ¬r) ∧ p)
(i)

¬(¬(p ↔ q) ∧ r) ≡ ¬[¬((p ∧ q) ∨ (¬p ∧ ¬q)) ∧ r]

≡ ¬[(¬(p ∧ q) ∧ ¬(¬p ∧ ¬q)) ∧ r]
≡ ¬[((¬p ∨ ¬q) ∧ (p ∨ q)) ∧ r]
≡ [¬(¬p ∨ ¬q) ∨ ¬(p ∨ q) ∨ ¬r]
≡ (p ∧ q) ∨ (¬p ∧ ¬q) ∨ ¬r
≡ (¬p ∧ ¬q) ∨ (p ∧ q) ∨ ¬r

(ii)

p ∨ (¬p → (q ∨ (q → ¬r))) ≡ p ∨ (¬p → (q ∨ (¬q ∨ ¬r)))

≡ p ∨ (p ∨ (q ∨ (¬q ∨ ¬r)))
≡ p ∨ p ∨ q ∨ ¬q ∨ ¬r
≡ p ∨ q ∨ ¬q ∨ ¬r

(iii)

p ∧ ¬(q ∧ r) ∨ (p → q) ≡ p ∧ ¬(q ∧ r) ∨ (¬p ∨ q)

≡ (p ∧ (¬q ∨ ¬r)) ∨ (¬p ∨ q)
≡ (p ∧ ¬q) ∨ (p ∧ ¬r) ∨ (¬p ∨ q)
≡ (p ∧ ¬q) ∨ (p ∧ ¬r) ∨ ¬p ∨ q

(iv)

(p ∧ ¬(q ∨ r)) ∨ (((p ∧ q) ∨ ¬r) ∧ p)

≡ (p ∧ (¬q ∧ ¬r)) ∨ ((p ∧ q) ∧ q) ∨ (¬r ∧ p)
≡ (p ∧ ¬q ∧ ¬r) ∨ (p ∧ q) ∨ (p ∨ ¬r)

Problem 2.18 Find the conjunction normal forms of the following statements:
(i) (p ∧ ¬(q ∧ r)) ∨ (p → q)
(ii) (q ∨ (p ∧ q)) ∧ ¬((p ∨ r) ∧ q)
(iii) (p ∧ ¬(q ∨ r)) ∨ (((p ∧ q) ∨ ¬r) ∧ p
2.6 Normal Forms 121

(i)

(p ∧ ¬(q ∧ r)) ∨ (p → q)
≡ (p ∧ (¬q ∨ ¬r)) ∨ (¬p ∨ q)
≡ {(p ∧ ¬q) ∨ (p ∧ ¬r)} ∨ (¬p ∨ q) Distributive Law
≡ {(p ∨ p) ∧ (p ∨ ¬r) ∧ (¬q ∨ p) ∧ (¬q ∨ ¬r)} ∨ (¬p ∨ q) Extended Distributive Law
≡ {(p ∨ p) ∧ (p ∨ ¬r) ∧ (p ∨ ¬q)} ∧ {(¬p ∨ q ∨ ¬q ∨ ¬r)} Associative Law
≡ (p ∨ p) ∧ (p ∨ ¬r) ∧ (p ∨ ¬q) ∧ (¬p ∨ T ∨ ¬r) (p ∨ T ≡ T )
≡ (p ∨ p) ∧ (p ∨ ¬r) ∧ (p ∨ ¬q) ∧ T (p ∨ T ≡ T )
≡ p ∧ (p ∨ ¬r) ∧ (p ∨ ¬q) (p ∧ T ≡ p)

(ii)

[q ∨ (p ∧ q)] ∧ ¬[(p ∨ r) ∧ q]
≡ q ∧ ¬[(p ∨ r) ∧ q], by absorption law
≡ q ∧ [¬(p ∨ r) ∨ ¬q]
≡ q ∧ [(¬p ∧ ¬r) ∨ ¬q]
≡ q ∧ (¬p ∨ ¬q) ∧ (¬q ∨ ¬r)

(iii)

(p ∧ ¬(q ∨ r)) ∨ (((p ∧ q) ∨ ¬r) ∧ p)

≡ (p ∧ (¬q ∧ ¬r)) ∨ ((p ∨ ¬r) ∧ (q ∨ ¬r) ∧ p)
≡ (p ∧ ¬q ∧ ¬r) ∨ (p ∧ (p ∨ ¬r) ∧ q ∨ ¬r))
≡ (p ∧ ¬q ∧ ¬r) ∨ (p ∧ (q ∨ ¬r)), by absorption law
≡ [(p ∧ (¬q ∧ ¬r)) ∨ p] ∧ [(p ∧ ¬q ∧ ¬r) ∨ (q ∨ ¬r)]
≡ p ∧ [((p ∧ ¬q ∧ ¬r) ∨ ¬r) ∨ q], by absorption law
≡ p ∧ (¬r ∨ q), by absorption law
≡ p ∧ (q ∨ ¬r)

Problem 2.19 Obtain the principal disjunctive normal forms and the principal conjunctive normal
forms of the following statements using truth tables:
(i) (¬p ∨ ¬q) → (p ↔ q)
(ii) p ∨ (¬p → (q ∨ (¬q → r)))
(iii) (p → (q ∧ r)) ∧ (¬p → (¬q ∧ ¬r))
Procedure If the given statement is not a contradiction, then the disjunction (sum) of the
minterms corresponding to the rows of the truth table having truth value T is the required PDNF, as
it is equivalent to the given statement.
For example, if the truth value T of the statement corresponds to the truth values T , T and F
for the variables p, q and r respectively, then the corresponding minterm is taken as (p ∧ q ∧ ¬r).
If the given statement A is not a tautology, we can find the equivalent PCNF as follows:
We write down the PDNF of ¬A, which is the disjunction of the minterms corresponding to
the rows of the truth table having the truth value F. Then if we find ¬¬A(= A), we will get the
required PCNF of A. Equivalently the PCNF is the conjunction of maxterms corresponding to the
F values of A. But the maxterm corresponding to T, T, F value of p, q, r is [(¬p ∨ ¬q ∨ r)]
(i)
122 Chapter 2. Predicate Calculus

p q ¬p ¬q ¬p ∨ ¬q ≡ a p↔q≡b a→b
T T F F F F T
T F F T T T T
F T T F T T T
F F T T T F F

Table 2.30

PDNF of (¬p ∨ ¬q) → (p ↔ q) ≡ (p ∧ q) ∨ (p ∧ ¬q) ∨ (¬p ∧ q), since the minterms correpond-
ing to the 3 T values of the last column are p ∧ q, p ∧ ¬q, ¬p ∧ q.
Now PDNF of ¬(a → b) ≡ ¬p ∧ ¬q
∴ PCNF of (a → b) ≡ ¬(¬p ∧ ¬q) = p ∨ q
2.6 Normal Forms 123

(ii)

p q r ¬p ¬q ¬q → r ≡ a q∨a ≡ b ¬p → b ≡ c p∨c
T T T F F T T T T
T T F F F T T T T
T F T F T T T T T
T F F F T F F T T
F T T T F T T T T
F T F T F T T T T
F F T T T T T T T
F F F T T F F F F

Table 2.31

PDNF of the given statement

= (p ∧ q ∧ r) ∨ (p ∧ q ∧ ¬r) ∨ (p ∧ ¬q ∧ r) ∨ (p ∧ ¬q ∧ ¬r)
∨ (¬p ∧ q ∧ r) ∨ (¬p ∧ q ∧ ¬r) ∨ (¬p ∧ ¬q ∧ r).

Now PCNF of the given statement = ¬(¬p ∧ ¬q ∧ ¬r)

= p∨q∨r

(iii)

p q r ¬p ¬q ¬r q∧r ≡ a p→a≡b ¬q ∧ ¬r ≡ d ¬p → c b∧d

T T T F F F T T F T T
T T F F F T F F F T F
T F T F T F F F F T F
T F F F T T F F T T F
F T T T F F T T F F F
F T F T F T F T F F F
F F T T T F F T F F F
F F F T T T F T T T T

Table 2.32

PDNF of the given statement ≡ (p ∧ q ∧ r) ∨ (¬p ∧ ¬q ∧ ¬r)

PDNF of ¬(b ∧ d) ≡ (p ∧ q ∧ ¬r) ∨ (p ∧ ¬q ∧ r) ∨ (p ∧ ¬q ∧ ¬r)

∨ (¬p ∧ q ∧ r) ∨ (¬p ∧ q ∧ ¬r) ∨ (¬p ∧ ¬q ∧ r)
∴ PCNF of (b ∧ d) ≡ (¬p ∨ ¬q ∨ r) ∧ (¬p ∨ q ∨ ¬r) ∧ (¬p ∨ q ∨ r)
∧ (p ∨ ¬q ∨ ¬r) ∧ (p ∨ ¬q ∨ r) ∧ (p ∨ q ∨ ¬r)

Problem 2.20 Without constructing the truth tables, find the principal disjunctive normal forms of
the following statements:
(i) (¬p → q) ∧ (q ↔ p)
(ii) (p ∧ q) ∨ (¬p ∧ q) ∨ (q ∧ r)
(iii) p ∧ ¬(q ∧ r) ∨ (p → q)
(iv) (q ∨ (p ∧ r)) ∧ ¬((p ∨ r) ∧ q)
124 Chapter 2. Predicate Calculus

(i)

(¬p → q) ∧ (q ↔ p) ≡ (p ∨ q) ∧ ((q ∧ p) ∨ (¬q ∧ ¬p))

≡ (p ∨ q) ∧ ((p ∧ q) ∨ ¬(p ∨ q))
≡ ((p ∨ q) ∧ (p ∧ q)) ∨ ((p ∨ q) ∧ ¬(p ∨ q)) Distributive Law
≡ ((p ∨ q) ∧ (p ∧ q)) ∨ F Distributive Law
≡ (p ∧ (p ∧ q)) ∨ ((q ∧ (p ∧ q)) Distributive Law
≡ (p ∧ q) ∨ (p ∧ q) Idempotent Law
≡ p∧q Idempotent Law

(ii)

(p ∧ q) ∨ (¬p ∧ q) ∨ (q ∧ r)
≡ ((p ∧ q) ∧ (r ∨ ¬r)) ∨ ((¬p ∧ q) ∧ (r ∨ ¬r)) ∨ ((q ∧ r) ∧ (p ∨ ¬p))
≡ (p ∧ q ∧ r) ∨ (p ∧ q ∧ ¬r) ∨ (¬p ∧ q ∧ r)
∨ (¬p ∧ q ∧ ¬r) ∨ (p ∧ q ∧ r) ∨ (¬p ∧ q ∧ r) Distributive Law
≡ (p ∧ q ∧ r) ∨ (p ∧ q ∧ ¬r) ∨ (¬p ∧ q ∧ r) ∨ (¬p ∧ q ∧ ¬r) Deleting repetition

(iii)

p ∧ ¬(q ∧ r) ∨ (p → q)
≡ (p ∧ (¬q ∨ ¬r)) ∨ (¬p ∨ q)
≡ (p ∧ ¬q) ∨ (p ∧ ¬r) ∨ ¬p ∨ q
≡ (p ∧ ¬q) ∨ (p ∧ ¬r) ∨ (¬p ∧ (q ∨ ¬q)) ∨ (q ∧ (p ∨ ¬p))
≡ (p ∧ ¬q) ∨ (p ∧ ¬r) ∨ (¬p ∧ q) ∨ (¬p ∧ ¬q) ∨ (p ∧ q) ∨ (¬p ∧ q)
≡ (p ∧ ¬q) ∨ (p ∧ ¬r) ∨ (¬p ∧ q) ∨ (¬p ∧ ¬q) ∨ (p ∧ q)
[Omitting the repletion of(p ∧ q)]
≡ ((p ∧ ¬q) ∧ (r ∨ ¬r)) ∨ ((p ∧ ¬r) ∧ (q ∨ ¬q)) ∨ ((¬p ∧ q)
∧ (r ∨ ¬r)) ∨ ((¬p ∧ ¬q) ∧ (r ∨ ¬r)) ∨ ((p ∧ q) ∧ (r ∨ ¬r))
≡ (p ∧ ¬q ∧ r) ∨ (p ∧ ¬q ∧ ¬r) ∨ (p ∧ q ∧ ¬r) ∨ (p ∧ ¬q ∧ ¬r)
∨ (¬p ∧ q ∧ r) ∨ (¬p ∧ q ∧ ¬r) ∨ (¬p ∧ ¬q ∧ r) ∨ (¬p ∧ ¬q ∧ ¬r)
∨ (p ∧ q ∧ r) ∨ (p ∧ q ∧ ¬r)
≡ (p ∧ ¬q ∧ r) ∨ (p ∧ ¬q ∧ ¬r) ∨ (p ∧ q ∧ ¬r) ∨ (¬p ∧ q ∧ r)
∨ (¬p ∧ q ∧ ¬r) ∨ (¬p ∧ ¬q ∧ r) ∨ (¬p ∧ ¬q ∧ ¬r) ∨ (p ∧ q ∧ r)

Since all possible minterms are present in the PDNF, we infer that the given statement is a
tautology.
(iv)

(q ∨ (p ∧ r)) ∧ ¬((p ∨ r) ∧ q)
≡ (q ∨ (p ∧ r)) ∧ (¬(p ∨ r) ∨ ¬q)
≡ (q ∨ (p ∧ r)) ∧ ((¬p ∧ ¬r) ∨ ¬q)
≡ (q ∧ ¬p ∧ ¬r) ∨ (q ∧ ¬q) ∨ (p ∧ r ∧ ¬p ∧ ¬r) ∨ (p ∧ r ∧ ¬q)
≡ (¬p ∧ q ∧ ¬r) ∨ F ∨ F ∨ (p ∧ ¬q ∧ r)
≡ (¬p ∧ q ∧ ¬r) ∨ (p ∧ ¬q ∧ r),
2.6 Normal Forms 125

Problem 2.21 Without constructing the truth tables, find the principal conjunctive normal forms of
the following statements:
(i) (p ∧ q) ∨ (¬p ∧ q ∧ r)
(ii) (p ∨ q) ∧ (r ∨ ¬p) ∧ (q ∨ ¬r)
(iii) (p ∨ ¬(q ∨ r)) ∨ (((p ∧ q) ∧ ¬r) ∧ p)
(iv) (p → (q ∧ r)) ∧ (¬p ∧ (¬q ∧ ¬r))
(i)

(p ∧ q) ∨ (¬p ∧ q ∧ r)
≡ ((p ∧ q) ∨ ¬p) ∧ ((p ∧ q) ∨ q) ∧ ((p ∧ q) ∨ r)
≡ (p ∨ ¬p) ∧ (q ∨ ¬p) ∧ (p ∨ q) ∧ (q ∨ q) ∧ (p ∨ r) ∧ (q ∨ r)
≡ T ∧ (¬p ∨ q) ∧ (p ∨ q) ∧ q ∧ (p ∧ r) ∧ (q ∨ r)
≡ ((¬p ∨ q) ∨ (r ∧ ¬r)) ∧ ((p ∨ q) ∨ (r ∧ ¬r)) ∧ q ∨ (p ∧ ¬p)
∧ (p ∨ r) ∨ (q ∧ ¬q) ∧ (q ∨ r) ∨ (p ∧ ¬p) (∵ A ∨ F = A)
≡ (¬p ∨ q ∨ r) ∧ (¬p ∨ q ∨ ¬r) ∧ (p ∨ q ∨ r) ∧ (p ∨ q ∨ ¬r)
∧ (q ∨ p) ∧ (q ∨ ¬p) ∧ (p ∨ r ∨ q) ∧ (p ∨ r ∨ ¬q) ∧ (q ∨ r ∨ p)
∧ (q ∨ r ∨ ¬p)
≡ (¬p ∨ q ∨ r) ∧ (¬p ∨ q ∨ ¬r) ∧ (p ∨ q ∨ r) ∧ (p ∨ q ∨ ¬r)
∧ (p ∨ ¬q ∨ r) ∧ ((q ∨ p) ∨ (r ∧ ¬r)) ∧ ((q ∨ ¬p) ∨ (r ∧ ¬r))

(Omitting repetitions)
≡ (¬p ∨ q ∨ r) ∧ (¬p ∨ q ∨ ¬r) ∧ (p ∨ q ∨ r) ∧ (p ∨ q ∨ ¬r)
∧ (p ∨ ¬q ∨ r)(Deleting repetitions)

(ii) Let

S ≡ (p ∨ q) ∧ (r ∨ ¬p) ∧ (q ∨ ¬r)
S ≡ ((p ∨ q) ∨ (r ∧ ¬r) ∧ ((¬p ∨ r) ∨ (q ∧ ¬q)) ∧ ((q ∨ ¬r) ∨ (p ∧ ¬p))
≡ (p ∨ q ∨ r) ∧ (p ∨ q ∨ ¬r) ∧ (¬p ∨ q ∨ r) ∧ (¬p ∨ ¬q ∨ r)
∧ (p ∨ q ∨ ¬r) ∧ (¬p ∨ q ∨ ¬r)
≡ (p ∨ q ∨ r) ∧ (p ∨ q ∨ ¬r) ∧ (¬p ∨ q ∨ r) ∧ (¬p ∨ ¬q ∨ r)
∧ (¬p ∨ q ∨ ¬r)

(iii) Let

S ≡ (p ∨ ¬(q ∨ r)) ∨ ((p ∧ q) ∧ ¬r) ∧ p

≡ (p ∨ (¬q ∨ ¬r)) ∨ (p ∧ q ∧ ¬r ∧ p)
≡ p ∧ (q ∨ ¬q) ∨ (¬q ∧ ¬r) ∨ (p ∧ q ∧ ¬r)
≡ (p ∧ q) ∨ (p ∧ ¬q) ∨ (¬q ∧ ¬r) ∨ (p ∧ q ∧ ¬r)
≡ ((p ∧ q) ∧ (r ∨ ¬r)) ∨ ((p ∧ ¬q) ∧ (r ∨ ¬r)) ∨ ((¬q ∧ ¬r)
∧ (p ∨ ¬p)) ∨ (p ∧ q ∧ ¬r)

≡ (p ∧ q ∧ r) ∨ (p ∧ q ∧ ¬r) ∨ (p ∧ ¬q ∧ r) ∨ (p ∧ ¬q ∧ ¬r)
∨ (p ∧ ¬q ∧ ¬r) ∨ (¬p ∧ ¬q ∧ ¬r) ∨ (p ∧ q ∧ ¬r)
 126 Chapter 2. Predicate Calculus

S ≡ (p ∧ q ∧ r) ∨ (p ∧ q ∧ ¬r) ∨ (p ∧ ¬q ∧ r) ∨ (p ∧ ¬q ∧ ¬r)
∨ (¬p ∧ ¬q ∧ ¬r) (2.11)

In (2.11), we have got the PDNF of S. Now

¬S ≡ (¬p ∧ q ∧ r) ∨ (¬p ∧ q ∧ ¬r) ∨ (¬p ∧ ¬q ∧ r)

∴ S ≡ ¬¬S ≡ (p ∨ ¬q ∨ ¬r) ∧ (p ∨ ¬q ∨ r) ∧ (p ∨ q ∨ ¬r) (2.12)

(2.12) is the required PCNF of S.

(iv) Let

S ≡ (p → (q ∧ r)) ∧ (¬p ∧ (¬q ∧ ¬r))

≡ (¬p ∨ (q ∧ r)) ∧ (p ∨ (¬q ∧ ¬r))
≡ (¬p ∨ q) ∧ (¬p ∨ r)) ∧ (p ∨ ¬q) ∧ (p ∨ ¬r)
≡ ((¬p ∨ q) ∨ (r ∧ ¬r)) ∧ ((¬p ∨ r) ∨ (q ∧ ¬q)) ∧ ((p ∨ ¬q)
∨ (r ∧ ¬r)) ∧ ((p ∨ ¬r) ∨ (q ∧ ¬q))
≡ (¬p ∨ q ∨ r) ∧ (¬p ∨ q ∨ ¬r) ∧ (¬p ∨ q ∨ r) ∧ (¬p ∨ ¬q ∨ r)
∧ (p ∨ ¬q ∨ r) ∧ (p ∨ ¬q ∨ ¬r) ∧ (p ∨ q ∨ ¬r) ∧ (¬p ∨ ¬q ∨ ¬r)
≡ (p ∨ ¬q ∨ r) ∧ (p ∨ ¬q ∨ ¬r) ∧ (p ∨ q ∨ ¬r) ∧ (¬p ∨ q ∨ r)
∧ (¬p ∨ ¬q ∨ r) ∧ (¬p ∨ q ∨ ¬r)

2.7 Theory of Inference

2.7.1 Introduction
Inference theory is concerned with the inferring of a conclusion from certain hypotheses or basic
assumptions, called premises, by applying certain principles of reasoning, called rules of inference.
When a conclusion derived from a set of premises by using rules of inference, the process of
such derivation is called a formal proof. The rules of inference are only means used to draw a
conclusion from a set of premises in a finite sequence of steps, called argument. These rules will be
given in terms of statement formulas rather than in terms of any specific statements or their truth
values. In this section we deal with the rules of inference by which conclusions are derived from
premises. Any conclusion which is arrived at by following these rules is called a valid conclusion
and the argument is called a valid argument. The actual truth values of the premises and that of the
conclusion do not play any part in the determination of the validity of the argument. However, if
the premises are believed to be true and if proper rules of inference are used, then the conclusion
may be expected to be true.

2.7.2 Truth Table Technique

When A and B are two statement formulas, then B is said to (logically) follow A or B is a valid
conclusion of the premise A, if A → B is a tautology, viz., A ⇒ B. Extending, a conclusion C is said
to follow from a set of premises H1 , H2 , · · · , Hn , if (H1 ∧ H2 ∧ · · · ∧ Hn ) ⇒ C. If a set of premises
and a conclusion are given, it is possible to determine whether the conclusion follows from the
premises by constructing relevant truth tables, as explained in the following example. This method
is known as truth table technique.
For example, let us consider
1. H1 : ¬p, H2 : p ∨ q,C : q
2. H1 : p → q, H2 : q,C : p
1. H1 and H2 are true only in the third row, in which case C is also true. Hence 1 is valid.
 2.7 Theory of Inference 127

2. H1 and H2 are true in the first and third rows, but C is not true in the third row. Hence 2 is
not a valid conclusion.

p q ¬p p∨q p→q
T T F T T
T F F T F
F T T T T
F F T F T

Table 2.33

2.7.3 Rules of Inference

Before we give the frequently used rules of inference in the form of tautologies in a table, we state
two basic rules of inference called rules P and T.
1. Rule P A premise may be introduced at any step in the derivation.
2. Rule T A formula S may be introduced in the derivation, if S is tautologically implied by
one or more preceding formulas in the derivation.

Rule in tautological Name of the rule

(p ∧ q) → p(viz., p ∧ q ⇒ p) Simplification
(p ∧ q) → q(viz., p ∧ q ⇒ q)
p → (p ∨ q) Addition
q → (p ∨ q)
(p → q) → (¬q → ¬p) Contrapositive
[(p) ∧ (q)] → (p ∧ q) Conjunction
[p ∧ (p → q)] → q Modus ponens
[¬q ∧ (p → q)] → ¬p Modus tollens
[(p → q) ∧ (q → r)] → (p → r) Hypothetical syllogism
[(p ∨ q) ∧ ¬p] → q Disjunctive syllogism
[(p ∨ q) ∧ (¬p ∨ r)] → (q ∨ r) Resolution
[(p ∨ q) ∧ (p → r) ∧ (q → r)] → r Dilemma
(a → b), (c → b) ⇔ (a ∨ c) → b Equivalence
¬p ∨ q ⇔ p → q Conditional

Table 2.34: Rules of Inference

2.7.4 Form of Argument

When a set of given statements constitute a valid argument, the argument form will be presented as
in the following example: “If it rains heavily, then travel- ling will be difficult. If students arrive on
time, then travelling was not difficult. They arrived on time. Therefore, it did not rain heavily.”
Let the statements be defined as follows:
p: It rains heavily
q: Travelling is difficult
r: Students arrived on time
Now we have to show that the premises p → q, r → ¬q and r lead to the conclusion ¬p. The
form of argument given as follows shows that the premises lead to the conclusion.
 128 Chapter 2. Predicate Calculus

Step No. Statement Rule Steps Involved Reason

1. p→q P
2. ¬q → ¬p T Contrapositive of 1
3. r → ¬q P
4. r → ¬p T 2, 3 Hypothetical Syllogism
5. r P
6. ¬p T 4, 5 Modus Ponens

2.7.5 Rule CP or Rule of Conditional Proof

In addition to the two basic rules of inference P and T , we have one more basic rule called Rule CP,
which is stated below:
If a formula s can be derived from another formula r and a set of premises, then the statement
(r → s) can be derived from the set of premises alone.
The rule CP follows from the equivalence

p → (r → s) ≡ (p ∧ r) → s

Note 2.7.1 If the conclusion is of the form r → s, we will take r as an additional premise and
derive s using the given premises and r.
If H1 , H2 , H3 , . . . , Hn ⇒ C1 → C2 , using CP rule, it is enough to prove H1 , H2 , H3 , . . . , Hn ,C1 ⇒
C2 . That is, to prove ∼ P ∨ Q, ∼ Q ∨ R, R → S ⇒ P → S, it is enough to prove ∼ P ∨ Q, ∼ Q ∨ R, R →
S, P ⇒ S.

2.7.6 Inconsistent Premises

A set of premises (formulas) H1 , H2 , · · · , Hn is said to be inconsistent, if their conjunction implies a
contradiction.
viz. if H1 ∧ H2 ∧ · · · ∧ Hn ⇒ R ∧ ¬R, for some formula R.
A set of premises is said to be consistent, if it is not inconsistent.

2.7.7 Indirect Method of Proof

The notion of inconsistency is used to derive a proof at times. This procedure is called the indirect
method of proof or proof by contradiction or reduction and absurdum.
In order to show that a conclusion C follows from the premises H1 , H2 , · · · Hn by this method,
we assume that C is false and include ¬C as an additional premise. If the new set of premises is
inconsistent leading to a contradiction, then the assumption that ¬C is true does not hold good.
Hence C is true whenever H1 ∧ H2 ∧ · · · ∧ Hn is true. Thus C follows from H1 , H2 , · · · Hn .
For example, we prove that the premises ¬q, p → q result in the conclusion ¬p by the indirect
method of proof.
We now include ¬¬p as an additional premise. The argument form is given below:

Step No. Statement Rule Steps Involved Reason

1. ¬¬p P
2. p T 1 Double Negation
3. p→q P
4. ¬q → ¬p T 3 Contrapositive
5. ¬q P
6. ¬p T 4,5 Modus ponens
7. p ∧ ¬p T 2,6 Conjunction
8. F T
 2.7 Theory of Inference 129

Thus the inclusion of ¬p leads to a contradiction. Hence ¬q, p → q ⇒ ¬p

2.7.8 Example
Problem 2.22 Find whether the conclusion C follows from the premises H1 , H2 , H3 in the following
cases, using truth table technique:
1. H1 : ¬p, H2 : p ∨ q,C : p ∧ q
2. H1 : p ∨ q, H2 : p → r, H3 : q → r,C : r

Proof.

p q H1 ≡ ¬p H2 ≡ p ∨ q H1 ∧ H2 C ≡ p∧q
T T F T F T
T F F T F F
F T T T T F
F F T F F F

Table 2.35

From table 2.35 H1 and H2 and hence H1 ∧ H2 are true in the third row, in which C is false.
Hence C does no follow from H1 and H2 .

p q r H1 (p ∨ q) H2 (p → r) H3 (q → r) H1 ∧ H2 ∧ H3
T T T T T T T
T T F T F F F
T F T T T T T
T F F T F T F
F T T T T T T
F T F T T F F
F F T F T T F
F F F F T T F

Table 2.36

From table 2.36 H1 , H2 , H3 and hence H1 ∧ H2 ∧ H3 are true in the first, third and fifth rows in
which r is also true.
Hence C follows from H1 , H2 and H3 . ■

Problem 2.23 Show that (t ∧ s) can be derived from the premises p → q, q → ¬r, r, p ∨ (t ∧ s).

Proof.

Step No. Statement Rule Steps Involved Reason

1. p→q P
2. q → ¬r P
3. p → ¬r T 1, 2 Hypothetical syllogism
4. r → ¬p T 3 Contrapositive
5. r P
6. ¬p T 4, 5 Modus ponens
7. p ∨ (t ∧ s) P
8. t ∧s T 6, 7 Disjunctive syllogism
130 Chapter 2. Predicate Calculus

Problem 2.24 Show that (a ∨ b) follows logically from the premises p ∨ q, (p ∨ q) → ¬r, ¬r →
(s ∧ ¬t) and (s ∧ ¬t) → (a ∨ b).

Proof.

Step No. Statement Rule Steps Involved Reason

1. (p ∨ q) → ¬r P
2. ¬r → (s ∧ ¬t) P
3. (p ∨ q) → (s ∧ ¬t) T 1, 2 Hypothetical Syllogism
4. p∨q P
5. s ∧ ¬t T 3, 4 Modus Ponens
6. (s ∧ ¬t) → (a ∨ b) P
7. a∨b T 5, 6 Modus ponens

Problem 2.25 Show that (p → q) ∧ (r → s), (q → t) ∧ (s → u), ¬(t ∧ u) and (p → r) ⇒ ¬p.

Step No. Statement Rule Steps Involved Reason

1. (p → q) ∧ (r → s) P
2. p→q T 1 Simplification
3. r→s T 1 Simplification
4. (q → t) ∧ (s → u) P
5. q→t T 4 Simplification
6. s→u T 4 Simplification
7. p→t T 2, 5 Hypothetical Syllogism
8. r→u T 3, 6 Hypothetical Syllogism
9. p→r P
10. p→u T 8, 9 Hypothetical Syllogism
11. ¬t → ¬p T 7 Contrapositive
12. ¬u → p T 10
13. (¬t ∨ ¬u) → ¬p T 11, 12 Equivalence
14. ¬(t ∧ u) → ¬p T 13 De Morgan’s Law
15. ¬(t ∧ u) P
16. ¬p T 14, 15 Modus Ponens.

Proof. ■

Problem 2.26 Show that (a → b) ∧ (a → c), ¬(b ∧ c), (d ∨ a) ⇒ d

2.7 Theory of Inference 131

Step No. Statement Rule Steps Involved Reason

1. (a → b) ∧ (a → c) P
2. a→b T 1 Simplification
3. a→c T 1 Simplification
4. ¬b → ¬a T 2 Contrapositive
5. ¬c → ¬a T 3 Contrapositive
6. (¬b ∨ ¬c) → ¬a T 4, 5 Equivalence
7. ¬(b ∧ c) → ¬a T De Morgan’s Law
8. ¬(b ∧ c) P
9. ¬a T 7, 8 Modus Ponens
10. d ∨a P
11. (d ∨ a) ∧ ¬a T 9, 10 Conjunction
12. (d ∧ ¬a) ∨ (a ∧ ¬a) T 11 Distributive Law
13. (d ∧ ¬a) ∨ F T 12 Negation Law
14. d ∧ ¬a T 13 Identity Law
15. d T 14 Simplification

Proof. ■

Problem 2.27 Give a direct proof for the implication p → (q → s), (¬r ∨ p), q ⇒ (r → s).

Step No. Statement Rule Steps Involved Reason

1. ¬r ∨ p P
2. r→p T 1 Equivalence of (1)
3. p → (q → s) P
4. r → (q → s) T 2, 3 Hypothetical Syllogism.
5. ¬r ∨ (¬q ∨ s) T 4 Equivalence of (4)
6. q P
7. q ∧ (¬r ∨ ¬q ∨ s) T 5, 6 Conjunction
8. q ∧ (¬r ∨ s) T 7, 8 Negation and Domination Laws
9. ¬r ∨ s T 8 Simplification
10. r→s T 9 Equivalence of (9)

Proof. ■

Problem 2.28 Derive p → (q → s) using the CP-rule (if necessary) from the premises p → (q → r)
and q → (r → s).

Proof. We shall assume p as an additional premise. Using p and the two given premises, we will
derive (q → s). Then, by CP-rule, p → (q → s) is deemed to have been derived from the two given
premises.
132 Chapter 2. Predicate Calculus

Step No. Statement Rule Steps Involved Reason

1. p P (additional)
2. p → (q → r) P
3. q→r T 1, 2 Modus Ponens
4. ¬q ∨ r T 3 Equivalence of (3)
5. q → (r → s) P
6. ¬q ∨ (r → s) T 5 Equivalence of (5)
7. ¬q ∨ (r ∧ (r → s)) T 4, 6 Distributive Law
8. ¬q ∨ s T 7 Modus Ponens
9. q→s T 8 Equivalence of (8)
10. p → (q → s) T 9 CP-rule

Problem 2.29 Use the indirect method to show that r → ¬q, r ∨ s, s → ¬q, p → q ⇒ p.

Proof. To use the indirect method, we will include ¬¬p ≡ p as an additional premise and prove a
contradiction.
Step No. Statement Rule Steps Involved Reason
1. p P (additional)
2. p→q P
3. q T 1, 2 Modus Ponens
4. r → ¬q P
5. s → ¬q P
6. (r ∨ s) → ¬q T 4, 5 Equivalence
7. r∨s P
8. ¬q T 6, 7 Modus Ponens
9. q ∧ ¬q T 3, 8 Conjunction
10. F T 9 Negation Law

Problem 2.30 Show that b can be derived from the premises a → b, c → b, d → (a ∨ c), d, by the
indirect method.
Let us include ¬b as an additional premise and prove a contradiction.

Step No. Statement Rule Steps Involved Reason

1. a→b P
2. c→b P
3. (a ∨ c) → b T 1, 2 Equivalence
4. d → (a ∨ c) P
5. d→b T 3, 4 Hypothetical Syllogism
6. d P
7. b T 5, 6 Modus Ponens
8. ¬b P (additional)
9. b ∧ ¬b T 7, 8 Conjunction
10. F T 9 Negation Law.

Proof. ■
2.7 Theory of Inference 133

Problem 2.31 Using indirect method of proof, derive p → ¬s from the premises p → (q ∨ r),
q → ¬p, s → ¬r, p.

Proof. Let us include ¬(p → ¬s) as an additional premise and prove a contradiction.
Now ¬(p → ¬s) = ¬(¬p ∨ ¬s) = p ∧ s
Hence the additional premise to be introduced may be taken as p ∧ s.

Step No. Statement Rule Steps Involved Reason

1. q → (q ∨ r) P
2. p P
3. q∨r T 1, 2 Modus Ponens
4. p∧s P Additional
5. s T 4 Simplification
6. s → ¬r P
7. ¬r T 5, 6 Modus ponens
8. q T 3, 7 Disjunctive Syllogism
9. q → ¬p P
10. ¬p T 8, 9 Modus Ponens
11. p ∧ ¬p T 2, 10 Conjunction
12. F T 11 Negation Law

Problem 2.32 Prove that the premises p → q, q → r, s → ¬r and p ∧ s are inconsistent.

Proof. If we derive a contradiction by using the given premises, it means that they are inconsistent.

Step No. Statement Rule Steps Involved Reason

1. p→q P
2. q→r P
3. p→r T 1, 2 Hypothetical Syllogism
4. s → ¬r P
5. r → ¬s T 4 Contrapositive
6. q → ¬s T 2, 5 Hypothetical Syllogism
7. ¬q ∨ ¬s T 6 Equivalence of (6)
8. ¬(q ∧ s) T 7 De Morgan’s Law
9. q∧s P
10. (q ∧ s) ∧ ¬(q ∧ s) T 8, 9 Conjunction
11. F T 10 Negation Law

Hence the given premises are inconsistent. ■

134 Chapter 2. Predicate Calculus

Problem 2.33 Prove that the premises a → (b → c), d → (b ∧ ¬c) and (a ∧ d) are inconsistent.

Step No. Statement Rule Steps Involved Reason

1. a∧d P
2. a T 1 Simplification
3. d T 1 Simplification
4. a → (b → c) P
5. b→c T 2, 4 Modus Ponens
6. ¬b ∨ c T 5 Equivalence of (5)
7. d → (b ∧ ¬c) P
8. ¬(b ∧ ¬c) → ¬d T 7 Contrapositive
9. ¬b ∨ c → ¬d T 8 Equivalence
10. ¬d T 6, 9 Modus Ponens
11. d → ¬d T 3, 10 Conjunction
12. F T 11 Negation Law

Proof. Hence the given premises are inconsistent. ■

Problem 2.34 Construct an argument to show that the following premises imply the conclusion “it
rained”.
“If it does not rain or if there is no traffic dislocation, then the sports day will be held and the
cultural programme will go on”; “If the sports day is held, the trophy will be awarded" and “the
trophy was not awarded”.

Proof. Let us symbolise the statement as follows:

p: It rains.
q: There is traffic dislocation.
r: Sports day will be held.
s: Cultural programme will go on.
t: The trophy will be awarded.
Then we have to prove that

(¬p ∨ ¬q) → (r ∧ s), r → t, ¬t ⇒ p

Step No. Statement Rule Steps Involved Reason

1. ¬p ∨ ¬q → r ∧ s P
2. (¬p → (r ∧ s)) ∧ (¬q → (r ∧ s)) T 1 Equivalence
(a ∨ b) → c ≡ (a → c) ∧ (b → c)
3. ¬p → (r ∧ s) T 2 Simplification
4. ¬(r ∧ s) → p T 3 Contrapositive
5. r→t P
6. ¬t → ¬r T 5 Contrapositive
7. ¬t P
8. ¬r T 6, 7 Modus Ponens
9. ¬r ∨ ¬s T 8 Addition
10. ¬(r ∧ s) T 8 De Morgan’s Law
11. p T 4, 10 Modus Ponens

■
 2.8 Predicate Calculus or Predicate Logic 135

Problem 2.35 Show that the following set of premises is inconsistent: If Ravi gets his degree, he
will go for a job. If he goes for a job, he will get married soon. If he goes for higher study, he will
not get married. Ravi gets his degree and goes for higher study.

Proof. Let the statements be symbolised as follows:

p: Ravi gets his degree.
q: He will go for a job.
r: He will get married soon.
s: He goes for higher study.
Then we have to prove that p → q, q → r, s → ¬r, p ∧ s are inconsistent

Step No. Statement Rule Steps Involved Reason

1. p→q P
2. q→r P
3. p→r T 1, 2 Hypothetical Syllogism
4. p∧s P
5. p T 4 Simplification
6. s T 4 Simplification
7. s → ¬r P
8. ¬r T 6, 7 Modus Ponens
9. r T 3, 5 Modus Ponens
10. r ∧ ¬r T 8, 9 Conjunction
11. F T 10 Negation Law

Hence the set of given premises is inconsistent. ■

2.8 Predicate Calculus or Predicate Logic

Introduction
In mathematics and computer programs, we encounter statements involving variables such as
“x > 10′′ , “x = y + 5′′ and “x + y = z′′ . These statements are neither true nor false, when the values
of the variables are not specified.
The statement “x is greater than 10” has 2 parts. The first part, the variable x, is the subject of
the statement. The second part “is greater than 10”, which refers to a property that the subject can
have, is called the predicate. We can denote the statement “x is greater than 10” by the notation
P(x), where P denotes the predicate “is greater than 10” and x is the variable. P(x) is called the
propositional function at x. Once a value has been assigned to the variable x, the statement P(x)
becomes a proposition and has a truth value. For example, the truth values of P(15){≡ 15 > 10}
and P(5){≡ 5 > 10} are T and F respectively. The statements “x = y + 5” and “x + y = z” will be
denoted by P(x, y) and P(x, y, z) respectively. The logic based on the analysis of predicates in any
statement is called predicate logic or predicate calculus.

2.8.1 Quantifiers
Many mathematical statements assert that a property is true 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 statement.
“P(x) is true for all values of x in the universe of discourse” and is denoted by the notation
(x)P(x) or ∀ xP(x). The proposition (x)P(x) or ∀xP(x) is read as “for all x, P(x)” or “for every x,
P(x)”. The symbol ∀ is called the universal quantifier.
 136 Chapter 2. Predicate Calculus

Note 2.8.1 Let us consider

∀xP(x) ≡ ∀x, (x2 − 1) = (x − 1)(x + 1) (2.13)

(2.13) is a proposition and not a propositional function, even though a variable x appears in it. We
need not replace x by a number to obtain a statement. The truth value of ∀xP(x) is T .

Examples
1. If P(x) ≡ {(−x)2 = x2 }, where the universe consists of all integers, then the truth value of
∀x((−x)2 = x2 ) is T .
2. If Q(x) ≡ “2x > x′′ , where the universe consists of all real numbers, then the truth value of
∀xQ(x) is F. For x = 0 the truth value is F.
3. If P(x) ≡ “x2 < 10′′ , where the universe consists of the positive integers 1, 2, 3 and 4, then
∀xP(x) = P(1) ∧ P(2) ∧ P(3) ∧ P(4) and so the truth value of ∀xP(x) = T ∧ T ∧ T ∧ F = F.
Note 2.8.2 We have so far applied universal quantification to propositional functions of
a single variable only. Universal quantification (and also existential quantification, that is
discussed below) can be applied to compound propositional functions such as P(x) ∧ Q(x),
P(x) → Q(x), ¬P(x), P(x) ∨ ¬Q(x) etc. and to propositional functions of many variables, as
given in the following examples.
4. Let P(x) ≡ x is an integer and Q(x) ≡ x is either positive or negative. Then P(x) → Q(x)
is a compound propositional function. Obviously ∀x(P(x) → Q(x)), where the universe of
discourse consists of integers.
5. Let P(x, y) : x is taller than y.
If x is taller than y, then y is not taller than x. viz. P(x, y) → ¬P(y, x)
As this assertion is true for all x and y, it can be symbolically represented as

∀x∀y(P(x, y) → ¬P(y, x))

2.8.2 Existential Quantifier

The existential quantification of P(x) is the proposition.
“There exists at least one x (or an x) such that P(x) is true” and is denoted by the notation ∃xP(x).
The symbol ∃ is called the existential quantifier. The proposition ∃xP(x) is read as “For some
x, P(x)”.

Examples
1. When P(x) denotes the propositional function “x > 3”, the truth value of ∃xP(x) is T , where
the universe of discourse consists of all real numbers, since “x > 3” is true for x = 4.
Note 2.8.3 When the elements of the universe of discourse is finitely many, viz., consists
of x1 , x2 , · · · , xn , then ∃xP(x) is the same as the disjunction P(x1 ) ∨ P(x2 ) ∨ · · · ∨ P(xn ), since
this disjunction is true if and only if at least one of P(x1 ), P(x2 ), · · · , P(xn ) is true.
2. When P(x) denotes “x2 > 10”, where the universe of discourse consists of the positive
integers not exceeding 4, then the truth value of ∃xP(x) is T , since P(1) ∨ P(2) ∨ P(3) ∨ P(4)
is true as P(4) [viz., 42 > 10] is true.

Negation of a Quantified Expression

If P(x) is the statement “x has studied computer programming”, then ∀xP(x) means that “every
student (in the class) has studied computer programming”. The negation of this statement is “It
is not the case that every student in the class has studied computer programming” or equivalently
“There is a student in the class who has not studied computer programming” which is denoted by
∃x¬P(x). Thus we see that ∀xP(x) ≡ ∃x¬P(x).
 2.8 Predicate Calculus or Predicate Logic 137

Similarly, ∃xP(x) means that “there is a student in the class who has studied computer pro-
gramming “The negation of this statement is “Every student in this class has not studied computer
programming”, which is denoted by ∀x¬P(x). Thus we get

¬∃xP(x) ≡ ∀x¬P(x)

Further we note that ¬∀xP(x) is true, when there is an x for which P(x) is false and false when P(x)
is true for every x, since

¬∀xP(x) ≡ ∃x¬P(x)
≡ ¬P(x1 ) ∨ ¬P(x2 ) · · · ∨ ¬P(xn )

¬∃xP(x) is true, when P(x) is false for every x and false when there is an x for which P(x) is true,
since

¬∃xP(x) ≡ ∀x¬P(x)
≡ ¬P(x1 ) ∧ ¬P(x2 ) · · · ∧ ¬P(xn )

2.8.3 Nested (More than One) Quantifiers

There are situations when quantifiers occur in combinations in respect of 1-place or n-place predicate
formulas (i.e., propositional functions containing 1 or n variables). For example let us consider a
2-place predicate formula P(x, y).

Now ∀x∀yP(x, y) ≡ ∀x[∀yP(x, y)]

≡ ∀y[∀xP(x, y)] (2.14)
and ∃x∃yP(x, y) ≡ ∃x[∃yP(x, y)] ≡ ∃y[∃xP(x, y)] (2.15)

From the meaning of quantifiers and by (2.14) and (2.15) the following simplifications hold good:

∀x∀yP(x, y) ⇒ (∃y)∀xP(x, y) ⇒ ∀x∃yP(x, y)

∀y∀xP(x, y) ⇒ (∃x)∀yP(x, y) ⇒ ∀y∃xP(x, y)

Note 2.8.4 The negation of multiply quantified predicate formulas may be obtained by applying
the rules for negation (given earlier) from left to right. Thus

¬[∀x∃yP(x, y)] ≡ ∃x[¬∃yP(x, y)]

≡ ∃x∀y[¬P(x, y)]

2.8.4 Free and Bound Variables

When a quantifier is used on a variable x or when we have to assign a value to this variable to
get a proposition, the occurrence of the variable is said to be bound or the variable is said to be a
bound variable. An occurrence of a variable that is not bound by a quantifier or that is set equal to a
particular value is said to be free.
The part of the logical expression or predicate formula to which a quantifier is applied is called
the scope of the quantifier.
138 Chapter 2. Predicate Calculus

Examples

[Link]. Predicate formula Bound variable and scope Free variable

1. ∀xP(x, y) x; P(x, y) y
2. ∀x(P(x) → Q(x)) x; P(x) → Q(x) −
3. ∀x(P(x) → E(y)Q(x, y)) x; P(x) → E(y)Q(x, y) −
y; Q(x, y)
4. ∀x(P(x) ∧ Q(x)) ∨ ∀yR(y) x; P(x) ∧ Q(x) −
y; R(y)
5. ∃xP(x) ∧ Q(x) First x; P(x) Second x

Table 2.37

Valid Formulas and Equivalences

Let A and B be any two predicate formulas defined over a common universe of discourse E. When
each of the variables appearing in A and B is replaced by any element (object name) of the universe
E, if the resulting statements have the same truth values, then A and B are said to be equivalent to
each other over E and denoted as A ≡ B or A ⇒ B over E. If E is arbitrary, we simply say that A
and B are equivalent and denote it as A ≡ B or A ⇔ B.
Generally, logically valid formulas in predicate calculus can be obtained from tautologies of
propositional calculus by replacing primary propositions (elementary statements) such as p, q, r by
propositional functions.
For example, p ∨ p ≡ T and (p → q) ↔ (¬p ∨ q) ≡ T are tautologies in statement calculus.
If we replace p by ∀R(x) and q by ∃xS(x) in the above, we get the following valid formulas in
predicate calculus.

(∀xR(x)) ∨ (¬∀xR(x)) ≡ T
(∀xR(x) → ∃xS(x)) ↔ ((¬∀xR(x)) ∨ ∃xS(x)) ≡ T

More generally, all the implications and equivalences of the statement calculus can also be consid-
ered as implications and equivalences of the predicate calculus if we replace elementary statements
by primary predicate formulas. For example,

from ¬¬p ⇒ p, we get ¬¬P(x) ≡ P(x) (2.16)

from p ∧ q ≡ q ∧ p, we get P(x) ∧ Q(x, y) ≡ Q(x, y) ∧ P(x) (2.17)
from p → q ≡ ¬p ∨ q, we get P(x) → Q(x) ≡ P(x) ∨ Q(x) (2.18)

(2.16), (2.17) and (2.18) are some examples for valid formulas in predicate calculus.
Apart from the types of valid formulas given above, there are other valid formulas also which
involve quantifiers. Such valid formulas are obtained by using the inference theory of predicate
logic, discussed below:

Inference Theory of Predicate Calculus

Derivations of formal proof in predicate calculus are done mostly in the same way as in statement
calculus, using implications and equivalences, provided that the statement formulas are replaced by
predicate formulas. Also the three basic rules P, T and CP of Inference theory used in statement
calculus can also be used in predicate calculus. Moreover, the indirect method of proof can also be
used in predicate calculus.
Apart from the above rules of inference, we require certain additional rules to deal with predicate
formulas involving quantifiers. If it becomes necessary to eliminate quantifiers during the course
2.8 Predicate Calculus or Predicate Logic 139

of derivation, we require two rules of specification, called US and ES rules. Once the quantifiers
are eliminated, the derivation is similar to that in statement calculus. If it becomes necessary to
quantify the desired conclusion, we require two rules of generalisation, called UG and EG rules.
Rule US Universal Specification is the rule of inference which states that one can conclude that
P(c) is true, if ∀xP(x) is true, where c is an arbitrary member of the universe of discourse. This
rule is also called the universal instantiation.
Rule ES Existential Specification is the rule which allows us to conclude that P(c) is true, if
∃xP(x) is true, where c is not an arbitrary member of the universe, but one for which P(c) is true.
Usually we will not know what c is but know that it exists. Since it exists, we may call it c. This
rule is also called the existential instantiation.
Rule UG Universal Generalisation is the rule which states that ∀xP(x) is true, if P(c) is true,
where c is an arbitrary member (not a specific member) of the universe of discourse.
Rule EG Existential Generalisation is the rule that is used to conclude that ∃xP(x) is true when
P(c) is true, where c is a particular member of the universe of discourse.
■ Example 2.1 Let us consider the following “Famous Socrates argument” which is given by:

All men are mortal. Socrates is a man.

Therefore Socrates is a mortal.
Let us use the notations

H(x): x is a man
M(x): x is a mortal
s: Socrates

With these symbolic notations, the problem becomes

∀x(H(x) → M(x)) ∧ H(s) ⇒ M(s)

The derivation of the proof is as follows:

Step No. Statement Rule Steps Involved Reason

1. ∀x(H(x) → M(x)) P
2. H(s) → M(s) US 2
3. H(s) P
4. M(s) T 2, 3 Modus ponens

■ Example 2.2 Application of any of US, ES, UG and EG rules wrongly may lead to a false
conclusion from a true premise as in the following example.
Let D(u, v) : u is divisible by v, where the universe of discourse is (5, 6, 10, 11).
Then ∃uD(u, 5) is true, since D(5, 5) and D(10, 5) are true.
But ∀uD(u, 5) is false, since D(6, 5) and D(11, 5) are false.
We now give the following derivation:

Step No. Statement Reason

1. ∃uD(u, 5) P
2. D(c, 5) ES, 1
3. ∀xD(x, 5) UG, 2

■
 140 Chapter 2. Predicate Calculus

Note 2.8.5 In step (3), UG has been applied wrongly, since c is not an arbitrary member in step
(2), as c(= 5 or 10) is only a specific member of the given universe of discourse.

2.8.5 Examples
Problem 2.36 If L(x, y) symbolises the statement “x loves y”, where the universe of discourse
for both x and y consists of all people in the world, translate the following English sentences into
logical expressions:
(a) Every body loves z.
(b) Every body loves somebody.
(c) There is somebody whom everybody loves.
(d) Nobody loves everybody.
(e) There is somebody whom no one loves.

Proof. (a) L(x, z) for all x. Hence ∀xL(x, z)

(b) L(x, y) is true for all x and some y. Hence ∀∃yL(x, y)
(c) Eventhough, (c) is the same as (b), the stress is on the existence of somebody (y) whom all x
love.
Hence ∃y∀xL(x, y)
(d) Nobody loves every body
i.e., There is not one who loves everybody Hence

¬∃x∀yL(x, y) ≡ ∀x¬∀yL(x, y)
≡ ∀x∃y¬L(x, y)

(e) The sentence means that there is somebody whom every one does not love. Hence

¬∀x∃yL(x, y) ≡ ∃x¬∃yL(x, y)
≡ ∃x∀y¬L(x, y)

Problem 2.37 Express each of the following statements using mathematical and logical opera-
tions, predicates and quantifiers, where the universe of discourse consists of all computer science
students/mathematics courses.
(a) Every computer science student needs a course in mathematics.
(b) There is a student in this class who owns a personal computer.
(c) Every student in this class has taken at least one mathematics course.
(d) There is a student in this class who has taken at least one mathematics course.

Proof. (a) Let M(x) ≡ ‘x needs a course in mathematics’, where the universe of discourse consists
of all computer science students. Then ∀xM(x).
(b) Let P(x) ≡ ‘x owns a personal computer’, where the universe consists of all students in this
class. Then ∃xP(x)
(c) Let Q(x, y) ≡ ‘x has taken y’, where the universe of x consists of all students in this class and
that of y consists of all mathematics courses. Then ∀x∃yQ(x, y)
(d) Using the same assumptions as in (c), we have ∃x∃yQ(x, y). ■

Problem 2.38 Express the negations of the following statements using quantifiers and in English:
(a) If the teacher is absent, then some students do not keep quiet.
(b) All the students keep quiet and the teacher is present.
(c) Some of the students do not keep quiet or the teacher is absent.
2.8 Predicate Calculus or Predicate Logic 141

(d) No one has done every problem in the exercise.

Proof. (a) Let T represent the presence of the teacher and Q(x) represent “x keeps quiet”. Then the
given statement is:

¬T → ∃xQ(x) ≡ T → ∀xQ(x) ≡ T ∨ ∀xQ(x)

∴ Negation of the given statement is

¬(T ∨ ¬∀xQ(x)) ≡ ¬T ∧ ∀xQ(x)

i.e., the teacher is absent and all the students keep quiet.
(b) The given statement is:

∀xQ(x) ∧ T

∴ The negation of the given statement is

¬(∀xQ(x) ∧ T ) ≡ ¬∀xQ(x) ∨ ¬T
≡ ∃xQ(x) ∨ ¬T

i.e., some students do not keep quiet or the teacher is absent.

(c) The given statement is:

∃x¬Q(x) ∨ ¬T ≡ ¬∀xQ(x) ∨ ¬T

∴ The negation of the given statement is

¬(¬∀xQ(x) ∨ ¬T ) ≡ ∀xQ(x) ∧ T

i.e., All the students keep quiet and the teacher is present.
(d) Let D(x, y) represent “x has done problem y”. The given statement is

(¬∃x)(∀yD(x, y)) (2.19)

The negation of the given statement is

(¬¬∃(x))(∀yD(x, y)) ≡ ∃x∀yD(x, y) (2.20)

i.e., some one has done every problem in the exercise. ■

Problem 2.39 Show that the premises “one student in this class knows how to write programs in
JAVA” and “Everyone who knows how to write programs in JAVA can get a high-paying job” imply
the conclusion “Someone in this class can get a high-paying job”.

Proof. Let C(x) represent “x is in this class” J(x) represent “x knows JAVA programming” and
H(x) represent “x can get a high paying job”.
Then the given premises are ∃x(C(x)∧J(x)) and ∀x(J(x) → H(x)). The conclusion is ∃x(C(x)∧
H(x)).
142 Chapter 2. Predicate Calculus

Step No. Statement Rule Steps Involved Reason

1. ∃x(C(x) ∧ J(x)) P
2. C(a) ∧ J(a) ES 1
3. C(a) T 2 Simplification
4. J(a) T 2 Simplification
5. ∀x(J(x) → H(x)) P
6. J(a) → H(a) US 5
7. H(a) T 4, 6 Modus Ponens
8. C(a) ∧ H(a) T 3, 7 Conjunction
9. ∃x(C(x) ∧ H(x)) EG 8

Problem 2.40 Show, by indirect method of proof, that ∀x(p(x) ∨ q(x)) ⇒ (∀xp(x)) ∨ (∃xq(x)).

Proof. Let us assume that [(∀xp(x)) ∨ (∃xq(x))] as an additional premise and prove a contradiction.

Step No. Statement Rule Steps Involved Reason

1. ¬[(∀xp(x)) ∨ (∃xq(x))] P Additional
2. ¬(∀xp(x)) ∧ ¬(∃xq(x)) T 1 De Morgan’s Law
3. ¬(∀xp(x)) T 2 Simplification
4. ¬(∃xq(x)) T 2 Simplification
5. ∃x¬p(x) T 3 Negation
6. ∀x¬q(x) T 4 Negation
7. ¬p(a) ES 5
8. ¬q(a) US 6
9. ¬p(a) ∧ ¬q(a) T 7, 8 Conjunction
10. ¬(p(a) ∨ q(a)) T 9 De Morgan’s Law
11. ∀x(p(x) ∨ q(x)) P
12. p(a) ∨ q(a) US 11
13. (p(a) ∨ q(a)) ∧ ¬(p(a) ∧ q(a)) T 10, 12 Conjunction
14. F T 13

Problem 2.41 Prove that ∀x(P(x) → (Q(y) ∧ R(x))), ∃xP(x) ⇒ Q(y) ∧ ∃x(P(x) ∧ R(x)).

Step No. Statement Rule Steps Involved Reason

1. ∀x(P(x) → (Q(y) ∧ R(x))) P
2. P(a) → (Q(y) ∧ R(a)) US 1
3. ∃xP(x) P
4. P(a) ES 3
5. Q(y) ∧ R(a) T 2, 4 Modus Ponens
6. Q(y) T 5 Simplification
7. R(a) T 5 Simplification
8. P(a) ∧ R(a) T 4, 7 Conjunction
9. ∃x(P(x) ∧ R(x)) EG 8
10. Q(y) ∧ ∃x(P(x) ∧ R(x) T 6, 10 Conjunction

Proof. ■
2.8 Predicate Calculus or Predicate Logic 143

Problem 2.42 Show that the conclusion ∀x(P(x) → ¬Q(x)) follows from the premises ∃x(P(x) ∧
Q(x)) → ∀y(R(y) → S(y)) and ∃y(R(y) ∧ ¬S(y)).

Step No. Statement Rule Steps Reason

Involved
1. ∃y(R(y) ∧ ¬S(y)) P
2. R(b) ∧ ¬S(b) ES 1
3. ¬(R(b) → S(b)) T 2 Equivalence Ref. Table (2.10)
4. ∃y(¬(R(y) → S(y))) EG 3
5. ¬∀y(R(y) → S(y)) T 4 Negation Equivalence
6. ∃x(P(x) ∧ Q(x)) → ∀y(R(y) → S(y)) P
7. ¬∃x(P(x) ∧ Q(x)) T 5, 6 Modus Tollens
8. ∀x¬((P(x) ∧ Q(x)) T 7 Negative Equivalence
9. ¬(P(a) ∧ Q(a)) US 8
10. ¬P(a) ∨ ¬Q(a) T 9 De Morgan’s law
11. P(a) → ¬Q(a) T 10 Equivalence
12. ∀x(P(x) → ¬Q(x)) UG 11

Proof. ■

Problem 2.43 Prove the derivation ∃xP(x) → ∀x((P(x) ∨ Q(x)) → R(x)), ∃xP(x), ∃xQ(x) ⇒
∃x∃y(R(x) ∧ R(y))

Step No. Statement Rule Steps Reason

Involved
1. ∃xP(x) → ∀x((P(x) ∨ Q(x)) → R(x) P
2. P(a) → ((P(a) ∨ Q(a)) → R(a)) ES and US 1
3. ∃xP(x) P
4. P(a) ES 3
5. (P(a) ∨ Q(a)) → R(a) T 2, 4 Modus Ponens
6. ∃xQ(x) P
7. Q(a) ES 6
8. P(a) ∨ Q(a) T 7 Addition
9. R(a) T 5, 8 Modus Ponens
10. ∃xR(x) EG 9
11. R(a) ES 9
12. R(a) ∧ R(b) T 9, 11 Conjunction
13. ∃y(R(a) ∧ R(y)) EG 12
14. ∃x∃y(R(x) ∧ R(y)) EG 13

Proof. ■

Problem 2.44 Prove the implication ∀x(P(x) → Q(x)), ∀x(R(x) → ¬Q(x)) ⇒ ∀x(R(x) → ¬P(x)).
144 Chapter 2. Predicate Calculus

Step No. Statement Rule Steps Involved Reason

1. ∀x(P(x) → Q(x)) P
2. P(a) → Q(a) US 1
3. ∀x(R(x) → ¬Q(x)) P
4. R(a) → ¬Q(a) US 2
5. Q(a) → ¬R(a) T 4 Contrapositive
6. P(a) → ¬R(a) T 2, 5 Hypothetical Syllogism
7. R(a) → ¬P(a) T 6 Contrapositive
8. ∀xR(x) → ¬P(x)) UG 7

Proof. ■

Problem 2.45 Use the indirect method to prove that the conclusion ∃zQ(z) follows from the
premises ∀x(P(x) → Q(x)) and ∃yP(y).

Proof. Let us assume the additional premise ¬(∃zQ(z)) and prove a contradiction

Step No. Statement Rule Steps Involved Reason

1. ¬(∃zQ(z)) P Additional
2. ∀z(¬Q(z)) T 1 Negation Equivalence
3. ¬Q(a) US 2
4. ∃yP(y) P
5. P(a) ES 4
6. P(a) ∧ ¬Q(a) T 3, 5 Conjunction
7. ¬(¬P(a) ∨ Q(a) T 6 De Morgan’s law
8. ¬(P(a) → Q(a)) T 7 Equivalence Ref. 2.10
9. ∀x(P(x) → Q(x)) P
10. P(a) → Q(a) US 9
11. (P(a) → Q(a)) ∧ ¬(P(a) → Q(a)) T 8, 10 Conjunction
12. F T 11 Negative Law

Problem 2.46 Show that ∀x(P(x) ∨ Q(x)) ⇒ ∀xP(x) ∨ ∃xQ(x), using the indirect method.

Step No. Statement Rule Steps Involved Reason

1. ¬(∀xP(x) ∨ ∃xQ(x)) P Additional
2. ¬(∀xP(x)) ∧ ¬(∃xQ(x)) T 1 De Morgan’s Law
3. ∃x(¬P(x)) ∧ ∀x(¬Q(x)) T 2 Negation Equivalence
4. ∃x(¬P(x)) T 3 Simplification
5. ∀x(¬Q(x)) T 3 Simplification
6. ¬P(a) ES 4
7. ¬Q(a) US 5
8. ¬P(a) ∧ ¬Q(a) T 6, 7 Conjunction
9. ¬(P(a) ∨ Q(a)) T 8 De Morgan’s law
10. ∀x(P(x) ∨ Q(x)) P
11. P(a) ∨ Q(a) US 10
12. (P(a) ∨ Q(a)) ∨ ¬(P(a) ∨ Q(a)) T 9, 11 Conjunction
13. F T 12 Negation Law.