Module 7

Introduction to Logic

7.1 Logic of Statements (SL)

We study logic to differentiate between valid and invalid arguments. An argument is a set of state-
ments which has two parts: a set of premises and a conclusion. Each premise is a statement which is
assumed to hold for the sake of the argument. The conclusion is a statement claimed to hold by the
argument. An argument has the structure
Premises: Statement1, . . ., Statementk; therefore
Conclusion: Statementc.
The following are instances of arguments:

• Statement1: If today is Monday, then Mr. X gets |5.

Statement2: Today is Monday.
Statementc: (Therefore,) Mr. X gets |5.

• Statement1: If today is Monday, then Mr. X gets |5.

Statement2: Mr. X gets |5.
Statementc: (Therefore,) Today is Monday.

• Statement1: If today is Monday, then Mr. X gets |5.

Statement2: Today is Tuesday.
Statementc: (Therefore,) Mr. X gets |5.

• Statement1: If today is Monday, then Mr. X gets |5.

Statement2: Today is Tuesday.
Statementc: (Therefore,) Mr. X does not get |5.

We understand that the first one is a valid argument, whereas the next three are not. In order to
determine whether an argument is valid or not, we need to know the logical form of a statement. A
simple statement is an expression which is either false or true but not both. Complex statements are
made out of simple ones by using the words ‘not’, ‘and’, ‘or‘, ‘implies’ and ‘if and only if’.
For example, ‘Today is Monday’ is a statement. ‘Today is Tuesday’ is a statement. ‘Today is not
Monday’ is a statement. ‘Today is Monday and today is Tuesday’ is also a statement.
Using symbols for simple statements and the words ‘not’, ‘and’, ‘or‘, ‘implies’ and ‘if and only if’
help us in seeing the logical structure of a statement. Normally, we use the symbols p, q, r, p1, p2, . . .
to denote simple statements. The quoted words are denoted by ¬, ∧, ∨, → and ↔, respectively.
Then the complex statements are made using these symbols along with parentheses by following some
specified rules.

133
 We abbreviate the phrase ‘Logic of Statements’ to ‘SL’ and present it in the following three sections.

7.2 Formulas and truth values in SL

Definition 7.2.1. Fix a countable set A = {p1, p2, . . .} of symbols. Each element of A is called
an atomic formula. An atomic formula is also called an atomic variable. The special symbols
¬, ∧, ∨, → and ↔ are called connectives; their names are ‘negation’, ‘conjunction’, ‘disjunction’,
‘implication’, and ‘biconditional’, respectively. The well formed formulas, or formulas, for short,
are generated by using the following rules recursively:
F1: Each atomic formula is a formula.
F2: If x is a formula, then (¬x) is a formula.
F3: If x and y are formulas, then (x ∧ y), (x ∨ y), (x → y) and (x ↔ y) are formulas.

The connective that has been introduced last in the process of generation of the formula is called the
principal connective in that formula.

The connectives ∨, ∧, →, and ↔ always connect two old formulas to create a new one. This is
why they are called binary connectives. The connective ¬ is used on a single old formula to give a
new one. So, it is called a unary connective. Notice that in every formula, there is a matching pair of
parentheses.

Example 7.2.2.
1. The expression (¬p5) is a formula.
Ans: Since p5 ∈ A, by (F1), it is a formula. By (F2), (¬p5) is a formula. The principal
connective in the formula is ¬.
2. The expression (¬(p3 ∧ (¬p4))) is a formula.
Ans: p3, p4 ∈ A; by (F1), these are formulas. By (F2), (¬p4) is a formula. By (F3), (p3 ∧(¬p4))
is a formula. Next, by (F2), (¬(p3 ∧(¬p4))) is a formula. The principal connective in the formula
is ¬.
3. The expression (p1 → (p1 ∨ p1)) is a formula.
Ans: By (F1), p1 is a formula. By (F3), (p1 ∨ p1) is a formula. Once more, by (F3), (p1 →
(p1 ∨ p1)) is a formula. The principal connective in the formula is →.
4. The expression (p1 ∨ ((¬(p1 → p1)) ↔ (p3 ∧ p5))) is a formula.
Ans: By (F1), p1, p3 and p5 are formulas. By (F3), (p1 → p1) and (p3 ∧ p5) are formulas.
By (F2), (¬(p1 → p1)) is a formula. Next, by two applications of (F3), (p1 ∨ ((¬(p1 → p1)) ↔
(p3 ∧ p5))) is a formula. The principal connective in this formula is ∨.
5. The expression ¬p9 is not a formula since according to our formation rules, a pair of parentheses
should have been used. Of course, with the pair of parentheses, the expression (¬p9) is a
formula, where the principal connective is ¬. Similarly, (¬(p4)) is not a formula due to extra
pair of parentheses, but (¬p4) is a formula with the principal connective as ¬.
6. The expression (p4 ∨ p5 is not a formula, but (p4 ∨ p5) is a formula with the principal connective
as ∨.
7. The expression (p6 ∨p1)∧(¬p4)) has one extra right parenthesis. Also, the connective ∧ demands
an extra pair of outer parentheses; that is, a left parenthesis is missing. We see that ((p6 ∨ p1) ∧
(¬p4)) is a formula with the principal connective as ∧.
7.2. FORMULAS AND TRUTH VALUES IN SL 135

Convention: For our comfort, we use the symbols p, q, r, . . . with or without subscripts for atomic
formulas in place of p1, p2, . . .. Similarly, we ignore the outer parentheses in a formula. By using
precedence rules we also cut short some more parentheses. The precedence rules are as follows:
1. ¬ has the highest precedence.
2. ∧ and ∨ have the next precedence.
3. → and ↔ have the least precedence.

Recall that when we say that × has more precedence over +, the expression x × y + z × w means
. Σ
(x × y) + (z × w) . If ambiguity results from using this convention in a context, we expand the
abbreviated formulas to formulas and decide the case. We illustrate the convention in the following
example.

Example 7.2.3. 1. By abbreviating p5 as p, we abbreviate (¬p5) as ¬p.

2. To abbreviate the formula (¬(p3 ∧ (¬p4))), we write p3 as p, p4 as q. Using the precedence rules,
our abbreviation is ¬(p3 ∧ ¬p4).
3. Writing p1 as p, we abbreviate (p1 → (p1 ∨ p1)) as p → p ∨ p.
4. Write p1 as p, p3 as q, and p5 as r. Then the formula (p1 ∨ ((¬(p1 → p1)) ↔ (p3 ∧ p5))) is
abbreviated to p ∨ (¬(p → p) ↔ q ∧ r)).

To be careful, we should not abbreviate different atomic formulas to the same symbol in any
context. For instance in the last part of the above example, we should not abbreviate both p1 and p3
as p.
Assuming familiarity with the process of abbreviation, we regard abbreviated formulas as formulas.
Since statements are supposed to be either true or false, we now discuss how to assign truth values
to formulas. Observe that any formula has occurrences of some finite number of atomic variables.
Further, if X is any formula, then either X = pi, an atomic variable, or X is in one of the forms:
¬p, p ∧ q, p ∨ q, p → q, or p ↔ q for formulas p, q, with the principal connective as ¬, ∧, ∨, →, ↔,
respectively.

Definition 7.2.4. Let X be a formula. Let B be the set of all formulas generated from the atomic
variables occurring in X. A truth assignment (appropriate to X) is a function f : B → {T, F }
satisfying the following conditions:
1. For an atomic variable pi, either f (pi) = T or f (pi) = F .
For formulas p and q,

2. f (¬p) = F if f (p) = T , and f (¬p) = T if f (p) = F .

3. f (p ∧ q) = T if f (p) = f (q) = T , and (p ∧ q) = F otherwise.
4. f (p ∨ q) = F if f (p) = f (q) = F , and f (p ∨ q) = T otherwise.
5. f (p → q) = F if f (p) = T, f (q) = F , and f (p → q) = T otherwise.
6. f (p ↔ q) = T if f (p) = f (q), and f (p ↔ q) = F otherwise.

Sometimes we write ‘f (p1, . . . , pk) is a formula’ to mean that ‘f is a formula involving the atomic
formulas p1, . . . , pk’. Let f (p1, . . . , pk) be a formula. Then, the truth value of f is determined based on
the truth values of the atomic formulas p1, , pk. Since, there are 2 assignments for each pi, 1 ≤ i ≤ k,
there are 2k ways of assigning truth values to these atomic formulas. A truth table for a formula
f (p1, . . . , pk) is a table which systematically lists the truth values of f under every possible assignment
7.3. EQUIVALENCE AND NORMAL FORMS IN SL 136

of truth values to the involved atomic formulas. The above definition of assignment of truth values
can be depicted in a truth table. It is as follows.

Understanding the connectives in a Truth table:

p q p∧q p q p∨q p q p→q p q p↔q

p ¬p T T T T T T T T T T T T
T F T F F T F T T F F T F F
F T F T F F T T F T T F T F
F F F F F F F F T F F T

Assignment of truth values to ¬p, p ∧ q, p ∨ q, p → q, p ↔ q

For instance, look at the table for →. The second row there tells that when p is assigned T and q is
assigned F , p → q is assigned F . In all other cases, p → q is assigned T .

Read T as ‘true’ and F as ‘false’. Observe that ¬ makes a true statement false and a false statement
true. The formula p ∧ q is true if and only if both p, q are true; p ∨ q is true if and only if at least
one of p, q is true; p ↔ q is true when either both p, q are true, or when both p, q are false. The
case that ‘p → q is true’ closely resembles the sentence ‘if p is true, then q is true’, though not very
obvious. (We illustrate this case in Example 7.2.6 below.) Accordingly, we also read the connectives
¬, ∧, ∨, → and ↔ as not, and, or, then1 and if and only if, respectively.

Example 7.2.5. The following is a truth table for the formula p ∨ (q ∧ r).

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

Example 7.2.6. Consider the formula p → q, where p and q symbolize the English statements as
follows:
p: you attend the class.
q: you understand the subject.
Then, p → q is the statement ‘if you attend the class, then you understand the subject’. The formula
p → q is true under the first three cases as explained below.
1. p is true and q is true. This means ‘you attend the class and understand the subject’. Here,
p → q is true.
2. p is false and q is false. This means ‘you do not attend the class and do not understand the
subject’. In this case, p → q is true.
3. p is false and q is true. This means ‘you do not attend the class but understand the subject’.
Here also, p → q is true.
1
In many texts, p → q is read as ‘if p then q’. However, it will be easier to read it as ‘p then q’.
7.3. EQUIVALENCE AND NORMAL FORMS IN SL 137

4. p is true and q is false. This means ‘you attend the class and do not understand the subject’.
Then p → q is false.

Thus, a conditional p → q is true when either p is false or q is true.

PRACTICE 7.2.7.
. Σ
1. Draw a truth table for the formula p ∧ ¬p → (p ∨ ¬q) .
2. Can both the formulas p → q and q → p be F for some assignment on p and q?

Depending on the structure of a formula f (p1, . . . , pn) it receives a truth value under an assignment
of truth values to the atomic formulas p1, . . . , pn. It is quite possible that the formula receives the
truth value T under an assignment and it receives the truth value F under another assignment. In
this connection we isolate those formulas which receive the same truth value under each assignment.

Definition 7.2.8. A contradiction is a formula which takes the truth value F under each assignment.
A tautology is a formula which takes the truth value T under each assignment. Often we write a
contradiction as ⊥ and a tautology as T.

For example, p∧¬p is a contradiction and p∨¬p is a tautology. Once a tautology and a contradiction
are given new tautologies and contradictions can be obtained by using the following theorem.

Theorem 7.2.9. Let A be a formula having at least one occurrence of an atomic variable p. Let B be
any formula. Denote by A[p/B] the formula obtained by replacing each occurrence of p by B in A.
1. If A is a contradiction, then A[p/B] is a contradiction.
2. If A is a tautology, then A[p/B] is a tautology.

Proof. Let A be a contradiction. For ease in notation, write A = A(p; p1, . . . , pn), where other than p,
the atomic variables occurring in A are p1, . . . , pn. Similarly, write A[p/B] = A(B; p1, . . . , pn). Let f
be any truth assignment that assigns truth values to p, p1, . . . , pn and also to all atomic variables
occurring in B.
If f assigns T to B, then the value of A[p/B] is the same as that of A(T ; p1, . . . , pn), which is F
since A is a contradiction.
If f assigns F to B, then the value of A[p/B] is the same as that of A(F ; p1, . . . , pn), which is F
since A is a contradiction.
Hence, A[p/B] takes the value F under the assignment f . Since f is an arbitrary assignment, we
conclude that A[p/B] is a contradiction. This proves the first statement.
Statement 2 is proved similarly.

For example, ((p → q) ∧(q ↔ r)) ∧¬((p → q) ∧(q ↔ r)) is a contradiction, since it is obtained from
p ∧ ¬p by replacing p with ((p → q) ∧ (q ↔ r)). Similarly, ((p → q) ∧ (q ↔ r)) ∨ ¬((p → q) ∧ (q ↔ r))
is a tautology since it is obtained from p ∨ ¬p by replacing p with ((p → q) ∧ (q ↔ r)).

7.3 Equivalence and Normal forms in SL

In an algebraic identity such as (x + y)2 = x2 + 2xy + y2, when we replace the variables x, y with
some numbers we see that both the sides give the same value. Such expressions help us in simplifying
algebraic expressions. Analogously, we introduce the notion of equivalence which will help us in
simplifying formulas.
7.3. EQUIVALENCE AND NORMAL FORMS IN SL 138

Definition 7.3.1. Two formula A and B are called equivalent if under any truth assignment, both
receive the same truth value. When A and B are equivalent, we write A ≡ B.

Thus, equivalent formulas are evaluated the same in each row of their truth table. Notice that
the set of atomic variables occurring in both the formulas may not be same; so a truth table is to be
constructed taking care of all the atomic variables involved.

Example 7.3.2.
1. Is p → q ≡ ¬q → ¬p?
Ans: We construct a truth table as follows.

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

Since in each row of the truth table, the truth values of the two formulas match, they are
equivalent.
2. Is p ≡ p ∧ (q ∨ (¬q))?
Ans: The truth table is constructed below.

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

Since in each row of the truth table the values of p and that of p ∧ (q ∨ (¬q)) match, they are
equivalent.

PRACTICE 7.3.3. Is p ∨ ¬p ≡ q ∨ ¬q?

When many atomic variables are involved, it may be time consuming to construct a truth table.
In such a case, equivalence may be shown by using one of the following methods:
1. A ≡ B if and only if whenever A is true, B is true, and whenever B is true, A is also true.
2. A ≡ B if and only if whenever B is false, A is false, and whenever B is false, A is also false.

Example 7.3.4. Show that p → q ≡ ¬q → ¬p.

Ans: p → q is false if and only if p is true and q is false
if and only if ¬p is false and ¬q is true
if and only if ¬q → ¬p is false.
Hence p → q ≡ ¬q → ¬p.

Proposition 7.3.5. [Laws] Let p, q, r be formulas. Then the following equivalences hold:
1. [Commutativity] p ∨ q ≡ q ∨ p, p ∧ q ≡ q ∧p
2. [Associativity] p ∨ (q ∨ r) ≡ (p ∨ q) ∨ r, p ∧ (q ∧ r) ≡ (p ∧ q) ∧ r
3. [Distributivity] p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r), p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r)
7.3. EQUIVALENCE AND NORMAL FORMS IN SL 139

4. [De Morgan] ¬(p ∨ q) ≡ ¬p ∧ ¬q, ¬(p ∧ q) ≡ ¬p ∨ ¬q

5. [Idempotence] p ∨ p ≡ p, p ∧ p ≡p
6. [Constants] ⊥ ∨ p ≡ p, ⊥ ∧ p ≡ ⊥, T ∨ p ≡ T, T ∧ p ≡ p, p ∨ ¬p ≡ T, p ∧ ¬p ≡ ⊥,
where ⊥ denotes contradiction and T denotes tautology.
7. [Double Negation] ¬(¬p) ≡ p
8. [Absorption] p ∨ (p ∧ q) ≡ p, p ∧ (p ∨ q) ≡ p
9. [Implication] p → q ≡ ¬p ∨ q, ¬(p → q) ≡ p ∧ ¬q
10. [Contraposition] p → q ≡ ¬q → ¬p, p → ¬q ≡ q → ¬p
11. [Biconditional] p ↔ q ≡ (p ∧ q) ∨ (¬p ∧ ¬q), p ↔ q ≡ (¬p ∨ q) ∧ (p ∨ ¬q),
p ↔ q ≡ (p → q) ∧ (q → p)

Proof. Construct the truth tables and verify.

Remark 7.3.6. The statement q → p is called the converse of the statement p → q. In general, a
statement is not equivalent to its converse. Reason: The assignment f that assigns T to p and F to
q, assigns F to p → q but assigns T to q → p. Also, the assignment g that assigns T to q and F to p
assigns F to q → p while it assigns T to p → q. Compare this with the Rule of Contraposition. The
contrapositive of a statement p → q is ¬q → ¬p. The rule says that a statement is equivalent to its
contrapositive.

The above laws help us in proving equivalence of some formulas, in addition to the method of
truth tables and helps us in analyzing when the formulas are true or false.

Example 7.3.7. We use the laws to show the following:

1. p → (q → r) ≡ (p ∧ q) → r.
2. ¬(p ↔ q) ≡ ¬p ↔ q.
3. p → q ≡ p ↔ p ∧ q.

Ans:

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

≡ (¬p ∨ ¬q) ∨ r Associativity
≡ ¬(p ∧ q) ∨ r De Morgan
≡ (p ∧ q) → r as p → p ≡ (¬p) ∨ q
. Σ
(2) ¬(p ↔ q) ≡ ¬ (p ∧ q) ∨ (¬p ∧ ¬q) Biconditional
≡ ¬(p ∧ q) ∧ ¬(¬p ∧ ¬q) De Morgan
≡ (¬p ∨ ¬q) ∧ (p ∨ q) De Morgan, Double negation
≡ (¬p ∧ p) ∨ (¬p ∧ q) ∨ (¬q ∧ p) ∨ (¬q ∧ q) Distributivity
≡ (¬p ∧ q) ∨ (¬q ∧ p) Constants
≡ (¬p ∧ q) ∨ (¬¬p ∧ ¬q) Double negation
≡ ¬p ↔ q Biconditional
. Σ
(3) p ↔ p ∧ q ≡ ¬p ∨ (p ∧ q) ∧ p ∨ ¬(p ∧ q) Biconditional
. Σ
≡ ¬p ∨ (p ∧ q) ∧ (p ∨ (¬p ∨ ¬q)) De Morgan
≡ (¬p ∨ p) ∧ (¬p ∨ q) ∧ (p ∨ (¬p ∨ ¬q)) Distributivity
≡ ¬p ∨ q Constants
≡ p →q Implication
7.3. EQUIVALENCE AND NORMAL FORMS IN SL 140

PRACTICE 7.3.8.
1. Does the absorption law imply p ∨ (p ∧ (¬q)) ≡ p and p ∧ (p ∨ (¬q)) ≡ p?
. Σ
2. Write a statement equivalent to (p → q) → p → (q → ¬r) where → and ↔ do not occur.
Simplify so that the number of occurrences of connectives is minimum.

Any formula has a truth table. On the other hand, if a truth table is given, can we construct a
formula corresponding to it? For example, can we have a formula involving the atomic variables p, q, r
such that the formula receives the truth value T under the assignment T, F, T to p, q, r, respectively?
We see that the formula p ∧ ¬q ∧ r does the job.

Definition 7.3.9. A truth function of n variables is any function from {T, F }n → {T, F }. A truth
function is expressed by a formula if the formula has the same truth table as that of the truth
function.

If φ is a truth function of n variables p1, . . . , pn, then a truth table can be constructed to depict
it. Such a truth table will have n columns and 2n rows, each row showing the different assignments of
truth values to the variables. The (n + 1)-th column is filled with T or F corresponding to each row.
For example, the truth function φ : {T, F }2 → {T, F } given by

φ(T, T ) = T, φ(T, F ) = F, φ(F, T ) = T, φ(F, F ) = F

is depicted by the truth table

p q φ
T T T
T F F
F T T
F F F
n
Notice that there are 22 number of truth functions involving n number of variables. Obviously,
any formula is a truth function. The question is whether any truth function can be expressed by a
formula.

Experiment: Consider the variables p, q, r in that order.

A formula which takes value T only on the assignment TTT is p ∧ q ∧ r. Verify.
A formula which takes value T only on the assignment TTF is p ∧ q ∧ ¬r. Verify.
Give a formula which takes value T only on the assignment FTF .
Give a formula which takes value T only on the assignments TTF and FTF .
Give a formula which takes value T only on the assignments TFT , TTF and TFF .
Give a formula f which takes value T only on the assignments FTF and FFF , i.e., whose truth table
is the following:
p q r A
T T T F
T T F F
T F T F
T F F F
F T T F
F T F T
F F T F
F F F T
7.3. EQUIVALENCE AND NORMAL FORMS IN SL 141

Theorem 7.3.10. Each truth function of n variables is expressed by a formula involving n variables.

Proof. Let φ be a truth function of n variables. Let p1, . . . , pn be n number of atomic variables. If
rng φ = {F }, then A ≡ ⊥. Thus, take A = p1 ∧ ¬p1 ∧ p2 ∧ · · · ∧ pn. Otherwise, collect all those
assignments f such that φ(f ) = T . Suppose this set is {f1 , . . . , fm}. Corresponding to each fi, define
the formula Bi = r1 ∧ r2 ∧ · · · ∧ rn, where for 1 ≤ j ≤ n,

pj if f (p j) = T
rj =
¬pj if f (p j) = F.

Notice that the formula Bi takes the value T only on the assignment fi. Thus, A = B1 ∨ B2 ∨ · · · ∨ Bm
is the required formula.

Example 7.3.11. Construct a formula that expresses the truth function φ given by

p q φ
T T T
T F T
F T F
F F F

Ans: The truth function φ is true only for the truth assignments f1 and f2, where f1(p) = f1(q) = T
and f2(p) = T, f2(q) = F . The corresponding formulas are B1 = p ∧ q and B2 = p ∧ ¬q. So the formula
that expresses φ is (p ∧ q) ∨ (p ∧ ¬q).

As the proof of Theorem 7.3.10 shows, each truth function can be expressed by a formula which
has a special form. In particular, every formula can be equivalently expressed by a formula in such a
special form. We define such a special form, along with another related special form.

Definition 7.3.12. An atomic formula and the negation of an atomic formula are together called
literals. We say that a formula A is in disjunctive normal form (in short, DNF) if it is a disjunction
of conjunctions of literals. We say that a formula A is in conjunctive normal form (in short, CNF)
if it is a conjunction of disjunctions of literals. Both DNF and CNF are called normal forms.

Example 7.3.13. The formulas (p ∧ ¬q) ∨ ¬r and (p ∧ ¬q) ∨ (q ∧ ¬r) ∨ (r ∧ s) are in DNF; (p ∨ ¬q) ∧ r
and (p ∨ q) ∧ (q ∨ ¬r) ∧ (r ∨ s) are in CNF; while p, p ∨ q, ¬p ∧ q are in both CNF and DNF.

PRACTICE 7.3.14. Write 5 formulas in CNF involving p, q, r.

Theorem 7.3.15. Any formula is equivalent to a formula in DNF, and also to a formula in CNF.

Proof. Since each formula is a truth function, the first assertion follows from Theorem 7.3.10. The
second assertion can be proved similarly. Alternatively, if A is a formula, get a DNF for ¬A; then
negate the DNF and use the distributivity laws to get an equivalent CNF.

PRACTICE 7.3.16. Write all the truth functions on two variables and write formulas for them.

A CNF and/or DNF representation of a formula can be computed by using equivalences. First, we
eliminate the connectives → and ↔ by using the laws of Implication and Biconditional, i.e., by using
the equivalences x → y ≡ ¬x ∨ y and x ↔ y ≡ (¬x ∨ y) ∧ (x ∨ ¬y). Next, we use the law of De Morgan
and Double negation, that is, ¬(x ∨ y) ≡ (¬x ∧ ¬y), ¬(x ∧ y) ≡ (¬x ∨ ¬y) and ¬¬x ≡ x so that the
7.3. EQUIVALENCE AND NORMAL FORMS IN SL 142

earlier obtained formula is equivalent to the one, in which each occurrence of the connective ¬ precedes
atomic variables. Finally, we use the laws of distributivity to obtain an equivalent formula, which is
in CNF and/or DNF. The formula so obtained can also be simplified using the laws of Absorption.
The following examples illustrate this method.

Example 7.3.17. Find a formula in DNF and also one in CNF equivalent to

((p → q) ∧ (q → r)) ∨ ((p ∧ q) → r).

We apply various laws in bringing the formula to its DNF and CNF as follows. Complete this by
mentioning the laws at each step.

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

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

Ans: Using Distributivity on (¬p ∨ q) ∧ (¬q ∨ r), we get the DNF as

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

Using Distributivity on the whole formula, we get the CNF as

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

Notice that the CNF can be simplified using Absorption laws. The simplified formula equivalent
to the original formula is ¬p ∨ ¬q ∨ r, which is in both DNF and CNF.

EXERCISE 7.3.18.
1. Use induction on the number of connectives to show that any formula is equivalent to a formula
in DNF and a formula in CNF.
2. A set of connectives is called adequate if every other connective can be expressed in terms of
the given ones. For instance, DNF and CNF conversion show that {¬, ∧, ∨} is an adequate
set. Determine which are adequate:
(a) {¬, ∧} (b) {¬, ∨} (c) {¬, →} (d) {∧, ∨} (e) {¬, ↔} (f) {→, ∨, ∧}.
3. Fill in the blanks to prove that ‘f ≡ g’ if and only if ‘f ↔ g is a tautology’.
Proof. Assume that f ≡ g. Let b be an assignment. Then, the value of f and g are the same
under b. Thus, the value of f ↔ g is T under b. As b is an arbitrary assignment, we see that
f ↔ g is a tautology.
Therefore, if f is T under b, then g is T under b. That is, f → g and g → f are both T under
b. Thus, f ↔ g is T under the assignment b.
Conversely, suppose that f ↔ g is a tautology. Assume that f ƒ≡ g. Then, there is an assignment b
under which f and g take different truth values.
So, suppose that f takes T and g takes F under b. Then f → g is F under b and hence f ↔ g
takes F under b, a contradiction. A similar contradiction is obtained if f takes F and g takes
T under b.

4. The dual P ∗ of a formula P involving the connectives ∨, ∧, ¬ is obtained by interchanging ∨

with ∧. For instance, the dual of ¬(p ∨ q) ∧ r is ¬(p ∧ q) ∨ r. Prove the following:
7.4. INFERENCES IN SL 143

(a) Let A(p1, . . . , pk) be a formula involving the atomic variables p1, . . . , pk and connectives ∨, ∧
and ¬. If A(¬p1, . . . , ¬pk) is obtained by replacing pi with ¬pi in A for 1 ≤ i ≤ k, then
A(¬p1 , . . . , ¬pk ) ≡ ¬A∗ (p1 , . . . , pk ).
(b) Let A, B be formulas that use only the connectives ∨, ∧ and ¬. If A ≡ B, then A∗ ≡ B ∗ .

7.4 Inferences in SL

We now turn our attention towards the main goal of logic: when is a given argument valid? An
argument has the form: “ S1, . . . , Sn. Therefore, Q. ”. Here, S1, . . . , Sn and Q are sentences in some
natural language. To translate such an argument to SL involves translating the sentences to formulas
in SL. Suppose S1, . . . , Sn, Q are translated to the formulas P1, . . . , Pn, C, respectively. Our goal is
to determine whether C is true under the assumption that each of P1, . . . , Pn is true. The translated
entity corresponding to the argument is denoted by

P1 , . . . , Pn ⇒
?
C

and is called an inference. We use the terminology that P1, . . . , Pn are premises and C is the conclusion
of this inference. Once the truth of C is determined from the assumption that P1, . . . , Pn are true, we
would like to write
the inference P1 , . . . , Pn ⇒
? C is valid.

This last assertion is written as

P1, . . . , Pn ⇒ C.

We formally define the notions involved.

Definition 7.4.1. An inference is an expression of the form {P1 , . . . , Pn } ⇒

?
C, where P1, . . . , Pn
?
and C are formulas. We also write the inference as P1, . . . , Pn ⇒ C. The formulas P1, . . . , Pn are
called the premises or hypotheses, and C is called the conclusion of the inference. We say that
the inference is valid if (P1 ∧ · · · ∧ P n) → C is a tautology; in this case, we write {P 1, . . . , P n} ⇒ C,
and also P 1, . . . , Pn ⇒ C. We read the symbol ⇒ as ‘implies’. When the inference is valid, we also
say that C is a logical conclusion of the premises P 1, . . . , P n.

Example 7.4.2.

1. Is the following argument valid?

If x = 4, then discrete math is bad. Discrete math is bad. Therefore, x = 4.

Ans: Denote ‘x = 4’ by p and ‘discrete mathematics is bad’ by q. The argument is translated

to SL as the inference {p → q, q} ⇒
?
p. The question is whether the inference is valid or not,
i.e., whether {p → q, q} ⇒ p. We need to determine whether (p → q) ∧ q → p is a tautology or
not.
Consider the assignment f with f (p) = F and f (q) = T . In this assignment, p → q is T ;
(p → q) ∧ q is T ; consequently, (p → q) ∧ q → p is F . Hence, the argument is invalid.
2. Is the following argument valid?

If discrete math is bad, then x = 4. Discrete math is bad. Therefore, x = 4.

7.4. INFERENCES IN SL 144

Ans: Denote ‘x = 4’ by p and ‘discrete mathematics is bad’ by q. The argument is translated

into the inference {q → p, q} ⇒
? p. To determine whether it is valid, we need to find whether

(q → p) ∧ q → p is a tautology.
For this, suppose there is an assignment for which (q → p) ∧ q → p takes the value F . Then for
that assignment, p must be F and (q → p) ∧ q must be T . As (q → p) ∧ q is T , q must be T and
q → p must be T . Thus, we need to have, p is F , q is T , and q → p is T . This is impossible.
Hence, there is no assignment for which (q → p) ∧ q → p is F . Hence, it is a tautology. So p
logically follows from q → p and q. That is, {q → p, q} ⇒ p. The argument is valid.
Remark 7.4.3. Let A, B be formulas. A ⇒ B means that A → B is a tautology. Similarly, B ⇒ A
means B → A is a tautology. Hence “A ⇒ B and B ⇒ A” is same as “A ↔ B is a tautology”, which
is again same as A ≡ B. Thus, sometimes A ≡ B is also written as A ⇔ B.

While proving an inference to be correct, we only show that the falsity of the conclusion does not
go along with the truth of the premises, i.e., the premises and the negation of the conclusion cannot
be true simultaneously. And, if the conclusion of an inference is in the form p → q, we often ignore
the cases when p is false. This is so because when p is false, p → q is true, and in this case, we need
not use any premise towards a correct inference. These two proof methods are encapsulated in the
following result.
Theorem 7.4.4. Let A1, . . . , An and X, Y be formulas.
1. [Rule of Contradiction] A1, . . . , An ⇒ X if and only if A1 ∧ · · · ∧ An ∧ ¬X is a contradiction.
2. [Rule of Deduction] A 1, . . . , An ⇒ X → Y if and only if A 1, . . . , A n, X ⇒ Y .

Proof. (1) Suppose A1 , . . . , An ⇒ X. Let f be a truth assignment. Then f assigns T to A1 ∧· · ·∧An →

X. If f assigns any one of A1, . . . , An to F , then it assigns F to A1 ∧ · · · ∧ An ∧ ¬X. Otherwise, f
assigns T to each of A1, . . . , An. Since f assigns T to A1 ∧ · · · ∧ An → X, f assigns T to X. In this
case, f assigns F to A1 ∧ · · · ∧ An ∧ ¬X. Hence, each assignment f assigns F to A1 ∧ · · · ∧ An ∧ ¬X.
Thus, A1 ∧ · · · ∧ An ∧ ¬X is a contradiction.
Conversely, suppose A1 ∧ · · · ∧ An ∧ ¬X is a contradiction. Let f be an assignment. If f assigns F
to any of A 1, . . . , A n, then f assigns T to A 1, . . . , An → X. Otherwise, suppose f assigns T to all of
A 1, . . . , A n. Since A1 ∧ · · · ∧ An ∧ ¬X is a contradiction, f assigns F to ¬X. That is, f assigns T to
X. Hence, f assigns T to A 1, . . . , An → X. That is, each assignment f assigns T to A 1, . . . , An → X.
Therefore, A 1, . . . , An ⇒ X.
(2) We use (1) repeatedly and the equivalence ¬(X → Y ) ≡ X ∧ ¬Y to obtain the following:
A 1 , . . . , An ⇒ X → Y
if and only if A1 ∧ · · · ∧ An ∧ ¬(X → Y ) is a contradiction
if and only if A1 ∧ · · · ∧ An ∧ X ∧ ¬Y is a contradiction
if and only if A1 ∧ · · · ∧ An ∧ X ⇒ Y .

Example 7.4.5. [MP, MT, HS, AI, OI]

1. Show that p, p → q ⇒ q.
Ans: Suppose p and p → q are T (under an assignment). Suppose q is F (under the same
assignment). As p → q is T , p must be F . This is a contradiction.

Alternate. By the rule of Deduction, (p, p → q) ⇒ q ≡ (p → q, p) ⇒ q if and only if

p → q ⇒ p → q if and only if (p → q) → (p → q) is a tautology; and this is true.
This inference is called Modus Ponens, often abbreviated to MP.
7.4. INFERENCES IN SL 145

2. Show that ¬q, p → q ⇒ ¬p.

Ans: Suppose ¬q and p → q are T . If ¬p is F , then p is T . Now that p → q is T , we see that q
is T . This is a contradiction.

Alternate. By the rule of Deduction, ¬q, p → q ⇒ ¬p if and only if (p → q) → (¬q → ¬p) is

a tautology; and this follows from Contraposition.
This inference is called Modus Tolens, often abbreviated to MT.
3. Show that p → q, q → r ⇒ p → r.
Ans: Suppose p → r is F . Then p is T and r is F . As r is F and q → r is T , q must be F . As
q is F and p → q is T , p is F , a contradiction.

Alternate. Using the rule of Deduction, we need to show that p → q, q → r, p ⇒ r. Using

Modus Ponens p, p → q ⇒ q, we have (p → q, q → r, p) ≡ (q, q → r) which in turn implies r
(again using Modus Ponens).
This inference is called Hypothetical Syllogism abbreviated to HS.
4. Show that p → q, p → r ⇒ p → q ∧ r.
Ans: Suppose p is T . Since p → q is T , q is T . Since p → r is T , r is T . Then q ∧ r is T . Hence
p → q ∧ r is T .
This inference is called And Introduction, abbreviated to AI.
5. Show that p → r, q → r ⇒ p ∨ q → r.
Ans: Suppose p ∨ q → r is F . Then p ∨ q is T and r is F . Since r is F and the premise p → r
is T , we have p is F . Similarly, the premise q → r gives q is F . Now, the three statements p is
F , q is F and p ∨ q is T lead to a contradiction.
This inference is called Or Introduction, abbreviated to OI.

As you see, correctness of an inference may be proved in three ways. Consider an inference

A1 , . . . , An ⇒
?
C.

We find out the atomic formulas involved in all the formulas Ai and C. Then we construct a truth
table having columns devoted to all Ais and also C. Next, we mark all those rows, where all Ais are
T . In all these rows, check whether C is also T . If yes, then the inference is correct, else, the inference
is incorrect. This method of proof is called Proof by Truth Table.
Instead of constructing a truth table, one analyzes all possibilities of assigning truth values to the
atomic formulas so that the premises are true, and then shows that in all these cases, the conclusion
is also true. This method also comes under the method of truth table.
In another variation of the truth table method, we consider all possibilities of assigning truth values
to the atomic variables so that the conclusion is false. In each of these cases, we show that at least
one premise becomes false. This method is sometimes referred to as the indirect truth table method.
Thus, the truth table method has three varieties of proofs: one - construction of truth table, two
- analyzing the cases when premises are true, and three - analyzing the cases when the conclusion
is false. We see that when the conclusion is in the form p → q, it is advantageous to use the third
variation.
Alternatively, we may use the laws and the already known valid inferences such as Modus Ponens,
Modus Tolens, Hypothetical Syllogism, And Introduction, and Or Introduction to construct a proof of
7.4. INFERENCES IN SL 146

the required inference. In this method, a proof is defined as a finite sequence of formulas, where each
formula is either a premise (some Ai), or a tautology, or is derived from earlier formulas using some
law or already known valid inferences. The last formula in such a sequence must be the conclusion C.
Such a proof is called a Direct Proof. If the conclusion C is in the form p → q, then we may use p
as a new premise, and construct a proof with conclusion q. In symbols,

A1, . . . , An ⇒ p → q if and only if A1, . . . , An, p ⇒ q

This follows from the rule of Deduction; see Theorem 7.4.4.

As the third alternative, we construct a proof using the rule of Contradiction. Such a proof is called
an Indirect proof. In such a proof, one uses ¬C as a new premise, and then derives a contradiction.
Schematically,
A 1, . . . , An ⇒ C if and only if A 1, . . . , A n, ¬C ⇒ ⊥

This method is justified by the rule of Contradiction as shown in Theorem 7.4.4. While constructing
the proof, when we find that some formula X has appeared in a line, and also ¬X has appeared
in some line, then it would mean that the same set of premises imply X as well as ¬X. This is a
contradiction. Thus we mention these two lines as our justification and write ⊥ on the last line.
In practice, we use the rule of Deduction and the rule of Contradiction to bring the given inference
to another form and proceed towards constructing a proof of the new inference. We explain these
methods of proof in the following example.

Example 7.4.6. Determine validity of the following argument:

The meeting can take place if all members are informed in advance and there is quorum
(a minimum number of members are present). There is a quorum if at least 15 members
are present. Members would have been informed in advance if there was no postal strike.
Therefore, if the meeting was canceled, then either there were fewer than 15 members
present or there was a postal strike.

Ans: Let us symbolize the simple statements as follows:

m: the meeting takes place;
a: all members are informed;
f : at least fifteen members are present;
q: the meeting had quorum;
p: there was a postal strike.
We need to determine the validity of the inference

q ∧ a → m, f → q, ¬p → a ⇒
?
¬m → ¬f ∨ p.

Proof by Truth table: In this case, we have five atomic formulas; the truth table will consist of 25 rows.
After construction, we will find that there are more than twenty cases, where the premises are true.
In all theses cases, we will find that the conclusion is also true.
However, this is time consuming. Even analyzing the truth values so that the premises are true is
no less time consuming. We will rather use the indirect truth table method.
Suppose the conclusion ¬m → (¬f ∨ p) is F and each of the premises q ∧ a → m, f → q and
¬p → a is T .
Now, ¬m → (¬f ∨ p) is F means ¬f ∨ p is F and ¬m is T . Hence, the atomic variables m, f and
p take values F, T and F , respectively. Since f → q is T and f is T , q must be T . Similarly, ¬p → a
7.4. INFERENCES IN SL 147

is T gives a is T . Then (q ∧ a) → m is T and both q and a are T give m is T . This contradicts ¬m

taking the value T .
Therefore, the inference is valid; that is, q ∧ a → m, f → q, ¬p → a ⇒ ¬m → ¬f ∨ p; and hence
the argument is valid.
Direct Proof: First, we plan how to go about: from f → q and ¬p → a, we get f ∧ ¬p → q ∧ a. Then
q ∧ a → m gives f ∧ ¬p → m. Its contrapositive is ¬m → ¬f ∨ p. This plan is rewritten as a proof
below, where we mention the justification on the right side, which may be a tautology, a premise, a
law, or a known rule (valid inference) that uses previous lines.

1. f ∧ ¬p → f (p ∧ q ⇒ p)
2. f ∧ ¬p → ¬p (p ∧ q ⇒ q)
3. f →q (Premise)
4. f ∧ ¬p → q (1, 3, HS)
5. ¬p → a (Premise)
6. f ∧ ¬p → a (2, 5, HS)
7. f ∧ ¬p → (q ∧ a) (4, 6, AI)
8. q ∧ a→ m (Premise)
9. f ∧ ¬p → m (7, 8, HS)
10. ¬m → ¬(f ∧ ¬p) (Contraposition)
11. ¬m → ¬f ∨ ¬¬p (De Morgan)
12. ¬m → ¬f ∨ p (Double negation)
Indirect Proof: Using the rule of Deduction and Contradiction, we have
q ∧ a → m, f → q, ¬p → a ⇒ ¬m → ¬f ∨ p
if and only if q ∧ a → m, f → q, ¬p → a, ¬m ⇒ ¬f ∨ p
if and only if q ∧ a → m, f → q, ¬p → a, ¬m, ¬(¬f ∨ p) ⇒ ⊥.
We then proceed to construct a proof of the last assertion.

1. ¬(¬f ∨ p) (premise)
2. f ∧ ¬p (De Morgan, Double negation)
3. f (p ∧ q ⇒ p)
4. ¬p (p ∧ q ⇒ q)
5. f →q (Premise)
6. q (3, 5, MP)
7. ¬p → a (Premise)
8. a (4, 7, MP)
9. q ∧ a (6, 8, AI)
10. q ∧ a → m (Premise)
11. m (9, 10, MP)
12. ¬m (Premise)
13. ⊥ (11, 12)

EXERCISE 7.4.7.
1. List all the nonequivalent formulas involving atomic variables p and q which take truth value T
on exactly half of the assignments.
2. Let A and B be two formulas involving the atomic variables p1, . . . , pk. Prove that A ≡ B if and
only if ‘A ↔ B is a tautology’.
7.4. INFERENCES IN SL 148

3. Prove (p → q ∨ r) ≡ (p ∧ ¬q → r) in three different ways: truth table method, simplification, by

proving both p → q ∨ r ⇒ p ∧ ¬q → r and p ∧ ¬q → r ⇒ p → q ∨ r.
4. Determine which of the following are logically equivalent:
(a) q → s
(b) (p → r ∨ s) ∧ (q ∧ r → s)
(c) (s → q ∨ r) ∧ (q ∧ s → r)
(d) p ∨ r ∨ (s → p)Σ∧ .p → (s → r) Σ
. Σ . Σ
(e) p ∨ s ∨ (q → p) ∧ p → (q → s) .

5. Let A be a formula that involves the connectives ∧, ∨, →, and atomic variables p1, · · · , pk.
Show that the truth value of A is T under the assignment f (p1) = · · · = f (pk) = T .
6. Verify the following assertions by analyzing truth table, and also by constructing a proof:
(a) p ∧ q ⇒ p
(b) p ⇒ p ∨ q
(c) ¬p ⇒ p → q
(d) ¬(p → q) ⇒ p
(e) ¬p, p ∨ q ⇒ q
(f) p, p → q ⇒ q
(g) ¬q, p → q ⇒ ¬p
(h) p → q, q → r ⇒ p → r
(i) p ∨ q, p → r, q → r ⇒ r
(j) p ↔ q ≡ (p ∧ q) ∨ (¬p ∧ ¬q)
(k) p ∧ q, p ∨ q ⇒ p → q
(l) p0 → p1, p1 → p2, . . . , p9 → p10 ⇒ ¬p0 ∨ p5.
(m) ¬p ∨ q → r, s ∨ ¬q, ¬t, p → t, ¬p ∧ r → ¬s ⇒ ¬q.
(n) p → q, r ∨ s, ¬s → ¬t, ¬q ∨ s, ¬s, ¬p ∧ r → u, w ∨ t ⇒ u ∧ w.

7. [Monotonicity] Let S1 ⊆ S2 be finite sets of formulas and let A be a formula. Show that if
S1 ⇒ A, then S2 ⇒ A. (We have used this result without mention.)
8. Determine which of the following arguments is/are correct:
(a) If discrete math is bad, then computer programming is bad. If linear algebra is good, then
discrete math is good. If complex analysis is good, then discrete math is bad. If computer
programming is good, then linear algebra is bad. Complex analysis is bad and hence, at least
one more subject is bad. (Assume that a subject is either bad or good.)
(b) Three persons X, Y and Z are making statements. We know that if X is wrong, then Y is
right; if Y is wrong, then Z is right; and if Z is wrong, then X is right. Does it follow that
at least two of them are always right?
(c) If the lecture proceeds, then either black board is used or the slides are shown or the tablet
pc is used. If the black board is used, then students at the back bench are not comfortable
in reading the black board. If the slides are shown, then students are not comfortable with
the speed. If the tablet pc is used, then it causes a lot of small irritating disturbances to the
instructor. The lecture proceeds and the students are comfortable. Therefore, the instructor
faces disturbances.
7.5. PREDICATE LOGIC (PL) 149

9. The normal forms can be used for inferences. The clue lies in seeing when a normal form is a
tautology or a contradiction. Let A = C1 ∨· · ·∨Cm be a formula in DNF and let B = D1 ∧· · ·∧Dn
be a formula in CNF, where C is are conjunctions of literals and D j s are disjunctions of literals.
Prove the following:
(a) A is a tautology if and only if each Ci has an occurrence of p and also ¬p for some atomic
variable p. Such a p may vary from Ci to Ci.
(b) B is a contradiction if and only if each Di has an occurrence of p and also ¬p for some
atomic variable p. Such a p may vary from Dj to Dj.
Ans: Similar to the first part.

10. Let A and B be two formulas having the truth tables given below. How many nonequivalent
formulas C involving the atomic formulas p, q, r are there such that {A, B} ⇒ C?

p q r A p q r B
T T T T T T T T
T T F F T T F F
T F T T T F T T
T F F T T F F F
F T T F F T T T
F T F T F T F F
F F T F F F T T
F F F F F F F F

. Σ
11. How many assignments of truth values to p, q, r and w are there for which (p → q) → r → w
is true? Guess a formula in terms of the number of variables.
12. Assume that F ≤ T . Let φ and ψ be two truth functions on the variables p 1, . . . , p9. Suppose
that for each assignment f , we have φ(f ) ≤ ψ(f ). Does this imply that φ → ψ is a tautology?
13. Consider the set S of all nonequivalent formulas written using two atomic variables p and q.
For A, B ∈ S, define A ≤ B if A ⇒ B. Prove that this is a partial order on S. Draw its Hasse
diagram.

7.5 Predicate logic (PL)

How do we symbolize the argument ‘x runs faster than y, y runs faster than z, hence x runs faster
than z’? It is clear that, it is not {p, q} ⇒ r, as it is an invalid argument, whereas the given argument
is valid. Notice that we are making this statement on a set, where the elements are comparable as
to who runs faster than whom. In other words, we require something called a predicate faster(x, y)
which takes truth values T or F depending on the inputs as elements from such a set.

Definition 7.5.1. A k-place predicate P (x1, . . . , xk) is a sentence involving the variables x1, . . . , xk
to which a truth value can be assigned under each assignment of values to x1, . . . , xk from a nonempty
set, called a universe of discourses (UD).

Example 7.5.2.
1. Let P (x) mean ‘x > 0’. Then P (x) is a 1-place predicate. On the UD: [−1, 1], i.e., when an
element a ∈ [−1, 1] is selected corresponding to x, the resulting statement P (a) is either T or F .
2. Let P (x, y) mean ‘x2 + y2 = 1’. Then P (x, y) is a 2-place predicate. On the UD: R, when two
elements a, b ∈ R are selected corresponding to x, y, the resulting statement P (a, b) is either T
or F .
7.5. PREDICATE LOGIC (PL) 150

3. Let P (x, y, z) mean ‘x and y are children of z’. Then P (x, y) is a 3-place predicate. On the
UD: the set of all human beings, when three human beings a, b, c are selected corresponding to
x, y, z, the resulting statement P (a, b, c) is either T or F .

Definition 7.5.3. The well formed formulas, called formulas for short, of Predicate logic (PL)
are generated by using the following rules recursively:
1. Any predicate is a formula, called an atomic formula.
2. If A, B are formulas, then (¬A), (A ∧ B), (A ∨ B), (A → B) and (A ↔ B) are formulas.
3. If A is a formula and x is a variable, then (∀x A) and (∃x A) are formulas.

The symbols ∀ and ∃ are called quantifiers, where ∀ is the universal quantifier and ∃ is the existential
quantifier. Read ∀ as ‘for each’ and ∃ as ‘there exists’.
. . ΣΣ
For example, (¬(∃x P (x, y, z))), (∀y (¬(∃x P (x, y, z)))), ∀z ¬((∃z R(z)) → R(z)) are formulas.

Remark 7.5.4. We use the same term formula to mean a formula in SL, and one in PL. Notice that
PL is an extension of SL; so there should not be any confusion in the use of this term.

Definition 7.5.5. Let P be a formula.

1. In (∀x P ) or (∃x P ) the formula P is called the scope of the quantifier (extent to which that
quantification applies).
2. (a) If no quantifier occurs in P , then any occurrence of x in (∀x P ) is said to be bound by the
quantifier ∀, and any occurrence of x in (∃x P ) is said to be bound by the quantifier ∃.
(b) If some quantifiers occur in P , then any occurrence of x in (∀x P ) which is not already bound
by any quantifier occurring in P , is said to be bound by this occurrence of ∀. A similar statement
holds for the quantifier ∃.
3. An occurrence of a variable in a formula is called a free occurrence if that occurrence of the
variable is not bound by any quantifier. A variable in a formula is called a free variable if it
has at least one free occurrence in the formula.

Example 7.5.6. Let P (x, y, z) and R(z) be predicates.

1. In (∃x P (x, y, z)), the occurrence of y and z are free and both the occurrences of x are bound.
2. In (∀y (∃x P (x, y, z))), all occurrences of x and y are bound and the occurrence of z is free.
. . ΣΣ
3. In ∀z (∃zR(z)) → R(z) , the middle two z’s are bound by ∃ and the first and the last
occurrences of z are bound by ∀.1

Convention: Once the formation of formulas, scope, bound and free occurrences of variables are
understood, we will put forth the precedence rules so that formulas can be written in an abbreviated
form. The precedence rules are the following:
1. Outer parentheses are ignored.
2. ¬, ∀ and ∃ have the highest precedence.
3. ∧ and ∨ have the next precedence.
4. → and ↔ have the least precedence.
Normally, we do not repeat the variable symbols used in the quantifiers. We will see that this formula is equivalent
1

. . ΣΣ
to ∀z (∃yR(y)) → R(z) .
7.5. PREDICATE LOGIC (PL) 151

For example, using the precedence rules, the formulas

. . ΣΣ . . ΣΣ
(¬(∃x P (x, y, z))), (∀y (¬(∃x P (x, y, z)))), ∀z ¬((∃zR(z)) → R(z)) , ∀z (∃yR(y)) → R(z)

are respectively abbreviated to

¬∃x P (x, y, z), ∀y ¬∃x P (x, y, z), ∀z¬(∃zR(z) → R(z)), ∀z(∃yR(y) → R(z)).

We will use the abbreviated formulas with the understanding that in case an ambiguity arises, we
would resort back to the original form.
Definition 7.5.7. 1. Let A be a formula. An interpretation for A means fixing a nonempty set
UD (called the universe of discourse), assigning values to the free variables in A, and giving
meanings of the predicates in A. Schematically,
fix UD, assumed to be nonempty,
An interpretation for A : assign values to the free variables ocurring in A,
give meanings to the predicates occurring in A.
If x is a variable, its value must be an element of UD; and if P (x1, . . . , xn) has n arguments,
then its meaning must be an n-ary relation on UD.
2. Let I be an interpretation for a formula ∀xP . Then we say ‘∀xP is T under I’ if for each a ∈ UD,
the value of P |x=a is T . Here, P |x=a means the expression obtained from P by replacing each
free occurrence of x with a.
Similarly, we say ‘∃xP is T under I’ if for some a ∈ UD, the value of P |x=a is T .
3. If P is a formula, then it will have a truth value T or F under each interpretation. (So you can
imagine a formula as a huge truth table.)
4. At times, the meaning of a formula under an interpretation, is also called an interpretation.
Remark 7.5.8. Formally, an interpretation I gives meaning to a predicate P (x1 , . . . , xn ) by assigning
it to an n-ary relation, say, P J on the UD. So, P |x1 =a1 ,...,xn =an means (a1 , . . . , an ) ∈ P J . For ease in
notation, we continue with the informal assertion “P |x=a means the expression obtained from P by
replacing each free occurrence of x with a”, which is applied recursively.

Example 7.5.9. Consider the formula ∀x P (x, y).

1. Take N as UD. Let P (x, y) mean ‘x > y’. Let us assign 1 to the free variable y. Then the
formula is interpreted as ‘each natural number is greater than 1’, which has truth value F .
2. Take N as UD. Let P (x, y) mean ‘x + y is an integer’, and assign y to 2. Then the formula is
interpreted as ‘when we add 2 to each natural number we get an integer’; it has truth value T .
Example 7.5.10. Let UD be the set of all human beings. Consider the 2-place predicate R(x, y): ‘x
runs faster than y’. Then
1. ∀x ∀y R(x, y) means ‘each human being runs faster than every human being’.
2. ∀x ∃y R(x, y) means ‘for each human being there is a human being who runs slower’.
3. ∃x ∃y R(x, y) means ‘there is a human being who runs faster than some human being’.
4. ∃x ∀y R(x, y) means ‘there is a human being who runs faster than every human being ’.
Remark 7.5.11. [Translation] We expect to see that our developments on logic help us in drawing
appropriate conclusions. In order to do that we must know how to translate an English statement
into a formal logical statement that involves no English words. We may have to introduce appropriate
variables and required predicates. We may have to specify the UD, but normally we use the most
general UD.
7.5. PREDICATE LOGIC (PL) 152

Example 7.5.12.
1. Translate: Each person in this class room is either a BTech student or an MSc student.
Ans: Does the statement guarantee that there is a person in the room? No. All it says, if there
is a person, then it has certain properties. Let P (x) mean ‘x is a person in this class room’;
B(x) mean ‘x is a BTech student’; and M (x) mean ‘x is an MSc student’. Then the formula is
. Σ
∀x P (x) → B(x) ∨ M (x) .
2. Translate: There is a student in this class room who speaks Hindi or English.
Ans: Does the statement guarantee that there is a student in the room? Yes. Let S(x) mean ‘x
is a student in this class room’; H(x) mean ‘x speaks Hindi’; and E(x) mean ‘x speaks English’.
. Σ
Then the formula is ∃x S(x) ∧ (H(x) ∨ E(x)) .
. Σ
Note that ∃x S(x) → H(x) ∨ E(x) is not the correct translation. Why?1

Notice that if a formula in PL has no free variables, then its translation into English will result in
a statement. Similarly, when English statements are translated into PL-formulas, they will result in
formulas having no free variables.

Example 7.5.13. Using the vocabulary Q(x): x is a rational number, R(x): x is a real number, and
L(x): x is less than 2, the following formulas are translated into English sentences, as shown:
. Σ
1. ∀x Q(x) → R(x) : Every rational number is a real number.
. Σ
2. ∃x ¬Q(x) ∧ R(x) : There is a real number which is not rational.
. Σ
3. ∀x Q(x) ∧ L(x) → R(x) ∧ L(x) : Every rational number less than 2 is a real number less than
2.
. Σ . Σ
4. ∀x Q(x) ∧ L(x) → ∀x R(x) ∧ L(x) : If each rational number is less than 2, then each real
number is less than 2.

EXERCISE 7.5.14. Translate the following sentences into PL:

1. If there is a man on Mars, he is a genius.
2. For each student in IITG there is a student in IITG with more CPI.
3. Every natural number is either the square of a natural number or its square root is irrational.
4. For every real number x there is a real number y such that x + y = 0.
In the rest of the exercises, fill in the blank with a PL-formula so that the definition will be
complete.
5. A subset S ⊆ Rn is called compact, if —. Use the predicates O(x, A): x is an open cover of A;
S(x, y): x is a subset of y; and C(x, A): x is a finite cover of A.
6. A function f : R → R is called continuous at a point a, if —. Use UD = R and the predicates
P (x): x is positive; and Q(x, y, z): |x − y| < z.
7. A function f : R → R is called continuous if —. Use UD = R and the predicates P (x): x is
positive; and Q(x, y, z): |x − y| < z.
8. A function f : R → R is called uniformly continuous if —. Use UD = R and the predicates
P (x): x is positive; and Q(x, y, z): |x − y| < z.
9. A function f : S → T is called a bijection if —. Use predicates B(x, A): x is an element of A;
and E(x, y): x is equal to y.
1
Remember, ∃x (P (x) → Q(x)) never asserts P (x). But ∃x (P (x) ∧ Q(x)) asserts both P (x) and Q(x).
7.6. EQUIVALENCES AND VALIDITY IN PL 153

7.6 Equivalences and Validity in PL

In parallel with SL, we isolate those formulas which receive the truth value T under every interpreta-
tion; and use this notion to define equivalence of two given formulas.

Definition 7.6.1. A formula is called valid if every interpretation evaluates it to T . A formula,

which receives the truth value F under each interpretation is called unsatisfiable. Two formulas A
and B are called equivalent, written A ≡ B, if A ↔ B is valid.

Notice that formulas A and B are equivalent if and only if under each interpretation, A and B
have the same truth value.
In first line of the next example what is unary relation? One assigns
x to a or a to x at different places in different paragraphs
Example 7.6.2. Let R(x) be a predicate.
1. R(x) → R(x) is valid.
Reason: To see this, suppose I is an interpretation that fixes R(x) to a unary relation, say, RJ
on some UD; and that assigns x to some element, say, a ∈ UD. Notice that RJ ⊆ UD. Now, I
assigns T to R(x) if and only if a ∈ RJ . The formula R(x) → R(x) is interpreted as the sentence:
if a ∈ RJ , then a ∈ RJ . This sentence is true in any UD. Since I is an arbitrary interpretation,
we conclude that R(x) → R(x) is valid.

2. R(x) ∧ ¬R(x) is unsatisfiable.

Reason: Consider an interpretation I with any UD. Suppose I assigns x to b ∈ UD; and
interprets R(x) as the unary relation RJ ⊆ UD. The formula R(x) ∧ ¬R(x) is interpreted as the
statement: b ∈ RJ and b ƒ∈ RJ . This is false. Since I is an arbitrary interpretation, R(x) ∧ ¬R(x)
is unsatisfiable.
3. Are the formulas ∀x R(x) and ∀z R(z) equivalent?
Reason: Let I be an interpretation. Under I, suppose that the formula ∀x R(x) is T . It means
that for each a ∈ UD, the value of P (a) is T . Then ∀z R(z) is T under I. The argument is
similar if ∀x R(x) is F under I. Since I is an arbitrary interpretation, the two formulas are
equivalent.
Similarly, ∃x R(x) ≡ ∃y R(y).
. Σ . Σ
4. Consider the formulas ∀z ∃z R(z) → R(z) and ∀y ∃z R(z) → R(y) . Let I be an interpreta-
. Σ . Σ
tion. Assume that ∀ z ∃z R(z). → R(z) is T under
Σ
I. This means ∃z R(z) → R(z) |z=a is T
for each a ∈ UD. This means ∃z R(z) → R(a) is T for each a ∈ UD. But this also means that
. Σ
∀y ∃z R(z) → R(y) is T under I.
. Σ . Σ
Similarly, if∀z ∃z R(z) → R(z) is F under I, then ∀y ∃z R(z) → R(y) is F under I. As I is
. Σ . Σ
arbitrary, ∀z ∃z R(z) → R(z) ≡ ∀y ∃z R(z) → R(y) .

Proposition 7.6.3. Let P and Q be formulas. The following are true:

1. All tautologies of SL are valid in PL.
2. If P is valid and x is any variable, then both ∀x P and ∃x P are valid.
3. ¬(∀x P ) ≡ ∃x ¬P , ¬(∃x P ) ≡ ∀x ¬P .

4. ∀x ∀y P ≡ ∀y ∀x P , ∃x ∃y P ≡ ∃y ∃x P .
5. ∀x (P ∧ Q) ≡ ∀x P ∧ ∀x Q , ∃x (P ∨ Q) ≡ ∃x P ∨ ∃x Q.
7.6. EQUIVALENCES AND VALIDITY IN PL 154

Proof. (1) In a tautology of SL, replace all atomic formulas by predicates of PL (chosen respectively).
For instance, in the tautology p → (q → p), replacing p by P (x, y) and q by R(x, y, z), we get the
formula P (x, y) → (R(x, y, z) → P (x, y)). The assertion says that the resulting formula of PL is valid.
Observe that the connectives are interpreted the same way in PL as in SL. Therefore, the assertion
holds.
(2) Let P be a valid formula and let x be any variable. Let I be an interpretation. Let a ∈ UD. Since
P is valid, P |x=a is T . This holds for each element a of UD. So, both the statements
“There exists a ∈ UD, P |x=a is T .” and “For each a ∈ UD, P |x=a is T .”
hold. (Recall that UD ƒ= ∅.) Therefore, under I, both ∃x P and ∀x P are T . Since I is an arbitrary
interpretation, both ∃x P and ∀x P are valid.
(3) Assume that under some interpretation I, the formula ¬(∀x P ) is T . So, ∀x P is F under I. That
is, for some a ∈ UD, P |x=a is F under I. Thus, ¬(P |x=a) is T under I. Hence, ∃x¬P is T under I.
Conversely, suppose that ∃x ¬P is T under an interpretation I. Then there is an a ∈ UD such that
(¬P )|x=a is T under I. This means, P |x=a is F under I. Hence, ∀xP is F under I. That is, ¬(∀xP )
is T under I. This proves the first assertion.
For the second assertion, we use the first assertion as follows:

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

(4) Consider the formulas ∃x ∃y P and ∃y ∃xP . Let I be an interpretation. Suppose ∃x ∃y P is T

under I. Then for some a ∈ UD, we have (∃y P )|x=a is T under I. Then again, for some b ∈ UD, we
have P |x=a,y=b is T under I. Since P |x=a,y=b = P |y=b,x=a, we see that (∃x P )|y=b is T under I. This
means ∃y ∃x P is T under I. A similar argument shows that if ∃y ∃x P is T under I, then ∃x ∃y P is
also T under I. This proves the second assertion.
For the first assertion, we use the second as follows:

∀x ∀y P ≡ ¬¬(∀x ∀y P ) ≡ ¬(∃x ∃y ¬P ) ≡ ¬(∃y ∃x ¬P ) ≡ ∀y ∀x¬¬P ≡ ∀y ∀x P.

(5) Let I be an interpretation under which ∀x (P ∧Q) is T . Then for each element a ∈ UD, (P ∧Q)|x=a
. Σ . Σ . Σ . Σ
is T . However, (P∧ Q) |x=a = P |x=a ∧ Q| x=a . Thus, both P |x=a and Q|x=aare T under I.
. Σ
Now, for each element a∈ UD, P|x=a is T under I implies that ∀x P is T under I. Similarly, for
. Σ
each element a ∈ UD, Q|x=a is T under I implies that ∀x Q is T under I. Therefore, ∀x P ∧ ∀x Q
is T under I.
Conversely, suppose ∀x P ∧ ∀x Q is T under I. Then both ∀x P and ∀x Q are T under I. Then for
each element a ∈ UD, P |x=a is T , and for each element b ∈ UD, Q|x=b is T . Let c ∈ UD. It follows
that under I, P |x=c is T and Q|x=c is T . That is, for each c ∈ UD, (P ∧ Q)|x=c is T under I. Hence
∀x (P ∧ Q) is T under I.
We conclude that under I, the formula ∀x (P ∧ Q) ↔ (∀x P ) ∧ (∀x Q) is T . Since I is an arbitrary
interpretation, this biconditional is valid, so that ∀x (P ∧ Q) ≡ ∀x P ∧ ∀x Q.
The second assertion is obtained from the first as in the following:
. Σ
∃x (P ∨ Q) ≡ ¬¬∃x (P ∨ Q) ≡ ¬∀x ¬(p ∨ Q) ≡ ¬∀x (¬P ∧ ¬Q) ≡ ¬ (∀x ¬P ) ∧ (∀x ¬Q)
. Σ . Σ
≡ ¬ ¬(∃x P ) ∧ ¬(∃x Q) ≡ ¬¬ (∃x P ) ∨ (∃x Q) ≡ ∃x P ∨ ∃x Q.

The first part in Proposition 7.6.3 says that all the rules of the logic of Statements also hold in
Predicate logic. For instance, the p ∨ ¬p being a tautology, it follows that ∀x P ∨ ¬∀x, P is valid.
Again, ¬∀x P ≡ ∃x ¬P . Hence ∀x P ∨ ∃x ¬P is valid. You may similarly obtain many more valid
formulas in PL, and formulate many equivalences accordingly.
7.6. EQUIVALENCES AND VALIDITY IN PL 155

In the following example, we show that different quantifiers do not commute, ∀ does not distribute
over ∨, and ∃ does not distribute over ∧.

Example 7.6.4.

1. ∃x ∀y P ƒ≡ ∀y ∃x P .
Reason: Consider P as the predicate Q(x, y) in the UD = N. Interpret Q(x, y) as ‘x > y’. Then
∃x ∀y P is the formula ∃x ∀yQ(x, y). It means ‘There is a natural number larger than all natural
numbers’. Clearly, this is false. The formula ∀y ∃x P is ∀y ∃x Q(x, y). It means ‘for each natural
number there is a larger natural number’, which is true.

2. ∀x (P ∨ Q) ƒ≡ ∀x P ∨ ∀x Q.
Reason: Consider P as the predicate O(x) and Q as the predicate E(x) in the UD = N. Interpret
O(x) as ‘x is odd’, and E(x) as ‘x is even’. Then ∀x (P ∨ Q) is the formula ∀x (O(x) ∨ E(x)). It
means each natural number is either odd or even. This is true. Now, ∀x P ∨ ∀x Q is the formula
∀x O(x) ∨ ∀x E(x). It means Either all natural numbers are odd, or all natural numbers are
even. Clearly, this is false.

3. ∃x (P ∧ Q) ƒ≡ ∃x P ∧ ∃x Q.
Reason: Consider the predicates and their interpretations as in (2). The formula ∃x (P ∧ Q) is
interpreted as ‘there is a natural number which is both odd and even’. This is false. Where as
the formula ∃x P ∧ ∃x Q is interpreted as the true sentence ‘there exists a natural number which
is odd, and also there exists a natural number which is even’.
. Σ . Σ
Example 7.6.5. Is ∀x R(x) → ∃y R(y) ∧ P (x, y) ≡ ∀x ∃y R(x) → R(y) ∧ P (x, y) ?
Ans: First, let us check the validity of X → Y , where
. Σ . Σ
X = ∀x R(x) → ∃y R(y) ∧ P (x, y) , Y = ∀x ∃y R(x) → R(y) ∧ P (x, y) .

Suppose that X → Y is invalid. So there is an interpretation I under which X is T and Y is F .

As Y is F , we see that for some a ∈ UD,
. Σ
∃y R(a) → R(y) ∧ P (a, y) is F .
. Σ
That is, for each y ∈ UD, R(a) → R(y) ∧ P (a, y) is F .
That is, R(a) is T and for each y, R(y) ∧ P (a, y) is F .
That is, R(a) is T and ∃y (R(y) ∧ P (a, y)) is F .
That is, R(a) → ∃y (R(y) ∧ P (a, y)) is F .
. Σ
This leads to a contradiction since X = ∀x R(x) → ∃y R(y) ∧ P (x, y) is T .
Similarly, one shows that Y → X is valid.
. Σ
Alternate. Write A = R(x) → ∃y R(y) ∧ P (x, y) and B = ∃y R(x) → R(y) ∧ P (x, y) . Consider
an element a ∈ UD. If R(a) is F , Then both X and Y are T . So, suppose R(a) is T . Notice that
. Σ
R(a) → ∃y (R(y) ∧ P (a, y)) and ∃y R(a) → (R(y) ∧ P (a, y) have the same truth value. Thus, A ≡ B.
It follows that ∀xA ≡ ∀xB, that is, X ≡ Y .

EXERCISE 7.6.6.
. Σ
1. Show that ∀x R(x) → ∃y (R(y) ∧ P (x, y)) is not valid.
. Σ . Σ
2. Show that ∀x P (x) → Q(x) → ∃x ¬P (x) → ¬Q(x) is not valid.

3. Let P and Q be formulas. Determine whether ∀x(P → Q) ≡ ∀xP → ∀xQ.

7.6. EQUIVALENCES AND VALIDITY IN PL 156

7.7 Inferences in PL
As in SL, we translate arguments to inferences in PL. The validity of inferences are defined in an
analogous manner.

Definition 7.7.1. An inference is an expression of the form {P1 , . . . , Pn } ⇒ ?

C, where the formulas
P 1, . . . , Pn are called premises or hypotheses, and the formula C is called the conclusion of the
inference. We say that the inference is valid, and write {P 1, . . . , P n} ⇒ C, if (P1 ∧ · · · ∧ P n ) → C is
valid. In such a case, we also say that C is a logical conclusion of the premises P 1, . . . , P n.
We abbreviate {P1 , . . . , Pn } ⇒
?
C to P1 , . . . , Pn ⇒
?
C and {P1 , . . . , Pn } ⇒ C to P1 , . . . , Pn ⇒ C;
and read the symbol ⇒ as ‘implies’.

It follows that X ≡ Y if and only if both X ⇒ Y and Y ⇒ X hold.

Since PL is an extension of SL, we will use all the laws and rules including the Rules of Contradiction
and Deduction. Moreover, to prove that P1, . . . , Pn ⇒ C, all that we have to do is assume that all
premises P1, . . . , Pn are T under an arbitrary interpretation I and show that under the same I, C
must be T . Alternatively, using the rule of Contradiction, P1, . . . , Pn ⇒ C can be proved by assuming
that an interpretation I makes the conclusion C false, and then showing that I makes at least one of
the premises P1, . . . , Pn false.
We have seen in Example 7.6.4 that some of the equivalences do not hold. In fact, we have shown
that one part of the equivalences fail. Namely,

∀y ∃x P ƒ⇒ ∃x ∀y P, ∀x (P ∨ Q) ƒ⇒ ∀x P ∨ ∀x Q, ∃x P ∧ ∃x Q ƒ⇒ ∃x (P ∧ Q).

We show that their converse implications hold.

Proposition 7.7.2. Let P and Q be formulas. Then the following assertions hold:
1. ∃x ∀y P ⇒ ∀y ∃x P .
2. ∀x P ∨ ∀x Q ⇒ ∀x (P ∨ Q).
3. ∃x (P ∧ Q) ⇒ ∃x P ∧ ∃x Q.

Proof. (1) Let I be an interpretation under which ∃x ∀y P is T . and ∀y ∃x P is F . Then there is an

element a ∈ UD such that (∀y P )|x=a is T . Then for each b ∈ UD, P |x=a,y=b is T . It implies that for
each b ∈ UD, (∃y P )|x=a is T . Hence ∀y ∃x P is T . Since I is an arbitrary interpretation, we conclude
that ∃x ∀y P ⇒ ∀y ∃x P .
(2) Let I be an interpretation under which ∀x P ∨ ∀x Q is T . If ∀x P is T , then for each a ∈ UD,
P |x=a is T . However, P |x=a is T implies that P |x=a ∨ Q|x=a is T ; and P |x=a ∨ Q|x=a = (P ∨ Q)|x=a. Thus,
for each a ∈ UD, (P ∨ Q)|x=a is T . So, under I , ∀x (P ∨ Q) is T . Similarly, it follows that if
∀x Q is T under I, then ∀x (P ∨ Q) is also T . In any case, ∀x (P ∨ Q) is T under I. Since I is an
arbitrary interpretation, ∀x P ∨ ∀x Q ⇒ ∀x (P ∨ Q).
(3) We know ¬(∃x P ∧ ∃x Q) ≡ ∀x ¬P ∨ ¬∀x ¬Q. By (2), ∀x ¬P ∨ ¬∀x ¬Q ⇒ ∀x (¬P ∨ ¬Q). Now,
∀x (¬P ∨ ¬Q) ≡ ∀x ¬(P ∧ Q) ≡ ¬∃x (P ∧ Q). Hence, ¬(∃x P ∧ ∃x Q) ⇒ ¬∃x (P ∧ Q). This is same
as ∃x (P ∧ Q) ⇒ ∃x P ∧ ∃x Q.

Example 7.7.3. Any student who appears in the exam and gets a score below 30, gets F grade. A
student x0 has not written the exam. Therefore x0 should get F grade. Do you agree?
Ans: Let S(x) mean ‘x is a student, E(x) mean ‘x writes the exam’, B(x) mean ‘x gets a score
below 30’, and F (x) mean ‘x gets F grade’.
7.7. INFERENCES IN PL 157
. Σ
We want to see whether1 ∀x S(x) ∧ E(x) ∧ B(x) → F (x) , S(x0 ) ∧ ¬E(x0 ) ⇒ F (x0 ).
Take the following interpretation: S(x) is ‘x is a positive real number’, E(x) is ‘x is a rational
√
number’, B(x) is ‘x is an integer’, F (x) is ‘x is a natural number’, and x0 = 2.
√
In this interpretation, the premises mean ‘every positive integer is a natural number’ and ‘ 2 is
a positive real number which is not rational’. Both of them are true. Whereas the conclusion means
√
‘ 2 is a natural number’, which is false. So the argument is incorrect.
Example 7.7.4. Translate the following argument into PL and then check whether it is correct:

All scientists are human beings. Therefore, all children of scientists are children of human
beings.

Ans: Let S(x) mean ‘x is a scientist’, H(x) mean ‘x is a human being’, and C(x, y) mean ‘x is a child of
y’. Then our hypothesis is ∀x (S(x) → H(x)). A few possible translation of the conclusion are the
following:
1. ∀x (∃y (S(y) ∧ C(x, y)) → ∃z (H(z) ∧ C(x, z))). It means ‘for each x, if x has a scientist father
then x has a human father’. This is a correct translation.
2. ∀x (∀y (S(y)∧C(x, y)) → ∀z (H(z)∧C(x, z))). The statement means ‘for all x, if x is a (common)
child of all scientists, then x is a (common) child of all human beings’. This is a wrong translation.
3. ∀x (S(x) → ∀y (C(y, x) → ∃z (H(z) ∧ C(y, z)))). This means ‘for each x, if x is a scientist, then
each child of x has a human father’. This is also a correct translation.
4. ∀x ∀y (S(x) ∧ C(y, x)) → ∀x ∀y (H(x) ∧ C(x, y)). This means ‘if each x is a scientist and each y
is a child of x (y can be equal to x), then each x is a human being and each y is a child of x’.
This is a wrong translation.

So, let us check whether ∀x (S(x) → H(x)) ⇒ ∀x (∃y (S(y) ∧ C(x, y)) → ∃z (H(z) ∧ C(x, z))). Let
I be an interpretation under which ∀x (S(x) → H(x)) is T . Let b be any element of UD.
Suppose that ∃y (S(y)∧C(b, y)) is T under I. Then there is an element a ∈ UD such that S(a)∧C(b, a)
is T . Since ∀x (S(x) → H(x)) is T , we see that S(a) → H(a) is T . It follows that H(a) ∧ C(b, a) is T .
Hence under I, ∃z (H(z) ∧ C(b, z)) is T .
Using the Rule of Deduction, we conclude that under I, the formula ∃y (S(y) ∧ C(b, y)) →
∃z (H(z) ∧ C(b, z)) is T . Since this holds for any arbitrary element b ∈ UD, we conclude that under I,
. Σ
∀x ∃y (S(y) ∧ C(x, y)) → ∃z (H(z) ∧ C(x, z)) is T . Since I is an arbitrary interpretation, this proves
that the conclusion logically follows from the premise.

Example 7.7.5. Let P be a formula and let R be a formula that does not have any occurrence of x.
Show that
∀x (R ∨ P ) ≡ R ∨ ∀x P, ∀x (R → P ) ≡ R → ∀x P,
∃x (R ∧ P ) ≡ R ∧ ∃x P, ∃x (R → P ) ≡ R → ∃x P.

∀x P → R ≡ ∃x (P → R), ∃x P → R ≡ ∀x (P → R).

Ans: We already know that ∀x R ∨ ∀x P ⇒ ∀x (R ∨ P ). Since R does not have any occurrence of
x, R ≡ ∀x R. Hence R ∨ ∀x P ⇒ ∀x (R ∨ P ). For the converse, let I be an interpretation under
which ∀x (R ∨ P ) is T . Then for each element a ∈ UD, (R ∨ P )|x=a is T . Since R does not have any
occurrence of x, (R ∨ P )|x=a = R ∨ P |x=a. So, under I, either R is T or for each a ∈ UD, P |x=a is T .
Actually x0 here is not a variable; it is a constant. Constants are interpreted as elements of UD just like variables,
1

but their occurrence in a formula is never categorized into bound or free.

7.7. INFERENCES IN PL 158

That is, under I, R ∨ ∀x P is T . Since I is an arbitrary interpretation, ∀x (R ∨ P ) ⇒ R ∨ ∀x P . We

conclude that ∀x (R ∨ P ) ≡ R ∨ ∀x P .
Others follow from the above by using the equivalences A → B ≡ ¬A ∨ B, ¬∀x A ≡ ∃x¬A,
¬∃x A ≡ ∀x ¬A, ¬¬A ≡ A, ¬(A ∨ B) ≡ ¬A ∧ ¬B and ¬(A ∧ B) ≡ ¬A ∨ ¬B.

Remark 7.7.6.
1. If S is a given set and P is a formula, sometimes we use ∀(x ∈ S)P and ∃(x ∈ S)P . These are
nothing but ∀x(E(x) → P ) and ∃x(E(x) ∧ P ), respectively, where, E(x) means x ∈ S.
2. At times, while dealing with real numbers or very familiar sets, we use certain predicate symbols
in an informal way. For example, we may write x ∈ S instead of using something like E(x, S);
or we may use x > 0 instead of using something like P (x).
For example, in the set R, the meaning of
. Σ
∃(s > 0) ∀(δ > 0)(0 < |x − a| < δ → |f (x) − A| < s)

is: “the set {|f (x) − A| : x ∈ R, 0 < |x − a|} has an upper bound s”.

Logic is used primarily to define and argue about mathematical systems. The predicate logic
developed so far is not enough to do that, in general. We need to extend it further by including the
equality predicate, constants, and function symbols. The equality predicate is a predicate like any
other but it is to be interpreted as the equality or identity relation on any UD. For instance, Peano’s
axioms formulated to define the natural number system uses the constant symbol 1, the function
symbol S and the equality predicate =. Such an extension of PL is called the first order logic, which
we do not deal with here. However, the logical structure to tackle mathematical theories is provided
by PL.
In some of the exercises that follow you may use constants and the equality predicate freely if
required for translation into the formal language of PL. Revisit Example 7.7.3, where we have used a
constant symbol x0.

EXERCISE 7.7.7.
1. Let f : R R→be a function and let a, A R.∈Write a formal definition of lim f (x) = A.
ƒ
x→a
2. In the following, fill in the blank with a PL-formula so that the definition will be complete:
(a) A subset S ⊆ Rn is called connected if —.
(b) A set S is called a group if —.
(c) A subset S ⊆ Rn is called a subspace if —.
(d) A function f : Rn → Rk is called a linear transformation if —.
(e) A function f : (S, ◦) → (T, +) is called a group isomorphism if —.
(f) A function f : V → W is called a vector space isomorphism if —.

3. Translate and check for validity of the following arguments.

(a) The decimal representation of a rational number either terminates or recurs, whereas that
of an irrational number neither terminates nor recurs. The square root of a natural number
either has a decimal representation which terminates or has a non-terminating decimal
representation and also a non-recurring decimal representation. The square root of all
natural numbers which are squares have decimal representations that terminate. Therefore,
the square root of a natural number which is not a square is an irrational number.
7.7. INFERENCES IN PL 159

(b) For any two algebraic numbers a and b, a ƒ= 0, 1 and b irrational, we

have that ab istranscendental. The number i (imaginary unit) is irrational
and algebraic. The number i is not equal to 0 or 1. Therefore, the
number ii is transcendental.
(c) Each student writes the exam using blue ink or black ink. A student who
writes the exam using black ink and does not write his/her roll number
gets an F grade. A student who writes the exam using blue ink and
does not have his/her ID card gets an F grade. A student who has
his/her ID card has written the exam with black ink. Therefore a student
who passes the exam must have written his roll number.
Use predicates S(x): x is a student , B(x): x write the exam using blue
ink, Bl(x): x write the exam using black ink, R(x): x writes roll number,
I(x): x has ID card, F (x): x gets F grade.
(d) Check whether the following argument is correct:
Every mango is either an apple or an orange. Every pineapple is a
mango. No apples are pineapples. Every object is either an apple or a
pineapple or a mango or an orange. Therefore, if an apple is a pineapple,
then it is an orange.
Use predicates M (x): x is a mango, A(x): x is an apple, P (x): x is a pineapple,
O(x): x
is an orange.