CS2006D: Discrete Structures

Predicate Logic

Renjith P.

NIT Calicut CS2006D: Discrete Structures 1 / 37

Predicate Logic
How to represent the following statements in Logic?
⋆ All boys are good.
⋆ There are at least two students of this class eligible for B.Tech
(Honours)
⋆ Some students of this class are involved in all forms of sports.
• Predicate logic or First Order Logic (FOL) increases the power of
propositional logic or zeroth order logic (ZOL) by using
predicates and quantifiers.
• ZOL is a special case of FOL where there are no quantifiers.
• Universe of discourse (UOD) or domain is a set under
consideration to describe the given argument.
• Predicates describe the property of elements in UOD and
quantifiers describe how many elements in the UOD satisfy the
property.
NIT Calicut CS2006D: Discrete Structures 2 / 37
Predicate Logic

⋆ Predicate Logic or First order logic are mathematical assertions

containing variables which receive values from a specific domain
and become proposition once its variables are assigned values
from the respective domain.
⋆ The commonly used quantifiers are Universal Quantifier (∀) and
Existential Quantifier (∃).
⋆ The notation P(x) refers to a predicate P such that x in UOD
satisfies P.
⋆ We are interested in knowing how many x in UOD satisfy P.
⋆ The notation ∀xP(x) says, each element in UOD satisfy P and
∃xP(x) says, some element in UOD satisfy P.

NIT Calicut CS2006D: Discrete Structures 3 / 37

Predicate Logic

⋆ The notation ∀x also mean, ’for each x’, ’for every x’, ’for any x’,
’for arbitrary x’ and ’for all x’.
⋆ Similarly, ∃x also mean, ’for some x’, ’at least one x’, and ’there
exists x’.
⋆ We do not have notation to refer to expressions such as ’couple of
x’, ’almost all x’, ’many x’, ’most of x’, ’few of x’, and we use ∃x to
refer to them.

NIT Calicut CS2006D: Discrete Structures 4 / 37

Predicate Logic - Quantifier
⋆ The notation ∀ x P(x) denotes the universal quantification of P(x)
and is evaluated to be True if P(x) evaluates to be True for all
values of x and False otherwise.
As an example,
let P(x) : x is prime, x ∈ N
Q(x) : x is a non-negative integer, x ∈ N
∀ x P(x) has truthvalue False.
∀ x Q(x) has truthvalue True.
⋆ The Existential quantifier ensures that there exists at least one
variable x in the universe of discourse such that the predicate can
be instantiated on.
⋆ Note that if the predicate evaluates to be True for at least one
value of x, then existential quantification has a truth value True,
and False otherwise.
⋆ For instance, consider the above predicate, ∃ x P(x) has truth
value True.
NIT Calicut CS2006D: Discrete Structures 5 / 37
Predicate Logic - Quantifier

⋆ The Uniqueness quantifier denoted as ∃! is read as ′′ there exists

exactly one′′ .
⋆ A uniqueness quantification ∃! x P(x) is evaluated to True if there
exists a unique x for which P(x) is evaluated to True.
⋆ For example, ∃! x [4x + 3 = 11], where x ∈ R.
⋆ Note: Let the elements in the domain be {x1 , x2 , x3 , . . .}, then,
∀ x P(x) ↔ P(x1 ) ∧ P(x2 ) ∧ P(x3 ) ∧ . . .
⋆ Each P(xi ) is a proposition and if each P(xi ) is true then universal
quantifier is evaluated to be true.
∃ x P(x) ↔ P(x1 ) ∨ P(x2 ) ∨ P(x3 ) ∨ . . .
⋆ ∃ ! x P(x) ↔ [P(x1 ) ∧ ¬P(x2 ) ∧ ¬P(x3 ) ∧ ¬P(x4 ) ∧ . . .] ∨
[P(x2 ) ∧ ¬P(x1 ) ∧ ¬P(x3 ) ∧ ¬P(x4 ) ∧ . . .] ∨
[P(x3 ) ∧ ¬P(x1 ) ∧ ¬P(x2 ) ∧ ¬P(x4 ) ∧ . . .] ∨ . . .

NIT Calicut CS2006D: Discrete Structures 6 / 37

Representation in FOL

In general, for x ∈ UOD and a predicate P(x),

⋆ All objects satisfy P(x); denoted as, ∀xP(x)
⋆ All objects do not satisfy P(x); denoted as, ∀x¬P(x)
⋆ Not all objects satisfy P(x); denoted as, ¬∀xP(x) ≡ ∃x¬P(x)
⋆ Some objects satisfy P(x); denoted as, ∃xP(x)
⋆ Some objects do not satisfy P(x); denoted as, ∃x¬P(x)
⋆ None of the objects satisfy P(x); denoted as, ¬∃xP(x) ≡ ∀x¬P(x)

NIT Calicut CS2006D: Discrete Structures 7 / 37

Some Examples
Consider the universe of discourse as integers. We define the follow-
ing predicates over integers. We present logical statements below,
which are in turn represented using quantifiers.
N(x): x is a non-negative integer.
E (x): x is even
O(x): x is odd
P(x): x is prime
1 There exist an even integer ∃ x E (x)
2 Every integer is even or odd ∀ x [E (x) ∨ O(x)]
3 All prime integers are non-negative ∀ x [P(x) → N(x)]
4 There is one and only one even prime ∃ ! x [E (x) ∧ P(x)]
5 The only even prime is two ∀ x [[E (x) ∧ P(x)] → x = 2]
6 Not all integers are odd ∃ x ¬O(x) or ¬∀ x O(x)
7 Not all primes are odd ¬∀ x [P(x) → O(x)] or ∃ x [P(x) ∧ ¬O(x)]
NIT Calicut CS2006D: Discrete Structures 8 / 37
Some More Examples
1 All boys are good
Assuming UOD: set of students
BOY (x) denotes x is a boy, x ∈ UOD
GOOD(x) denotes x is good.
Then, ∀x(BOY (x) → GOOD(x)).
Assuming UOD: set of boys, then ∀x(GOOD(x)).
Assuming UOD: set of things (include living and non-living
things).
HUMAN(x) denotes x is human
Then, ∀x(HUMAN(x) ∧ BOY (x) → GOOD(x)).
2 Some boys are good
FOL: ∃x(BOY (x) ∧ GOOD(x))
This says, there exists x in UOD such that x is a boy and good.
3 Not all boys are good
FOL: ¬∀x(BOY (x) → GOOD(x))
Note ∃x(BOY (x) ∧ ¬GOOD(x)) is equivalent to
¬∀x(BOY (x) → GOOD(x)).
NIT Calicut CS2006D: Discrete Structures 9 / 37
Some More Examples

4 Some boys are not good

FOL: ∃x(BOY (x) ∧ ¬GOOD(x))
5 All boys are not good
FOL: ∀x(BOY (x) → ¬GOOD(x))
6 None of the boys are good
FOL: ¬∃x(BOY (x) ∧ GOOD(x))

NIT Calicut CS2006D: Discrete Structures 10 / 37

An Important Equivalence

Note:
¬∀ x P(x) ↔ ∃ x ¬P(x)

¬∃ x P(x) ↔ ∀ x ¬P(x)

NIT Calicut CS2006D: Discrete Structures 11 / 37

Some More Insights
Justification for the use of implication operator in ∀ and
∧ operator in ∃
⋆ For the statement ”all boys are good”, usage of operator ∧ or ∨ is
incorrect and expresses a different meaning than the context.
⋆ In the context of ∀x, when we say ∀x(P(x) → Q(x)) is true, it
means two things;
(i) both P(x) and Q(x) are true
(ii) ¬P(x) is true and Q(x) is true or false.
− Consider our example ”all boys are good”.
− This expression also means that all girls are good or not good,
which is always true.
− There is no logical operator which expresses just ”all boys are
good” and does not express any other hidden meaning. − Since
implication operator is ’near perfect’ operator, we could use
implication according to the context.
− This operator does not convey any other meaning which is
logically incorrect.
NIT Calicut CS2006D: Discrete Structures 12 / 37
Some More Insights
Justification for the use of implication operator in ∀ and
∧ operator in ∃
⋆ For the statement ”some boys are good”, the apt operator is ∧ and
the logical expression is ∃x(BOY (x) ∧ GOOD(x))
⋆ Suppose, we use implication operator in place of ’logical AND’
operator. Then, the expression is ∃x(BOY (x) → GOOD(x)).
⋆ This implicitly means that some girls are good or some girls are
not good which cannot be inferred from some boys are good.
⋆ Therefore, → operator is not the perfect operator for ∃ quantifier.
⋆ If the context under discussion demands the usage of → in ∃ and
∧ in ∀, then it must be used.
⋆ For example; we express the statement ”there exists a boy such
that if he is eligible for distinction, then he is eligible for honours”
as ∃x(BOY (x) ∧ DIST (x) → HONO(x))
⋆ The statement ”Every natural number is a real number and a
rational number” can be expressed as ∀x(REAL(x) ∧ RAT (x))
NIT Calicut CS2006D: Discrete Structures 13 / 37
Note
The scope of a quantifier is that part of an assertion in which vari-
ables are bounded by the quantifier.
⋆ ∀ x [P(x) ∨ Q(x)] ̸↔ ∀ x P(x) ∨ Q(x) ̸↔ P(x) ∨ ∀ x Q(x)
⋆ ∀ x [P(x) ∨ Q(y )] ↔ ∀ x P(x) ∨ ∀ x Q(y )
⋆ ∃ x [P(x) ∧ Q] ↔ ∃ x P(x) ∧ Q
Compound statements involving predicates
⋆ For every pair of integers x and y there exists a z such that
x +z =y
⋆ The above predicate is represented as ∀ x ∀ y ∃ z [x + z = y ]
⋆ If universe of discourse is integer, then the predicate’s truth value
is True.
⋆ If universe of discourse is N, then the predicate is False for some
predicate constants.
i.e., ¬∀ x ∀ y ∃ z [x + z = y ] =⇒ ∃ x ∃ y ∀ z ¬[x + z = y ] =⇒
∃ x ∃ y ∀ z [x + z ̸= y ], in particular, x = 4, y = 1 and for any z,
x + z ̸= y .
The negation operator flips the quantifier from ∀ to ∃ and vice
versa.
NIT Calicut CS2006D: Discrete Structures 14 / 37
Nested Quantifiers

Logical representation of statements using nested quantifiers

⋆ The sum of two positive integers is always positive.
∀x ∀y (x > 0 ∧ y > 0 → x + y > 0)
⋆ For every real number except 0, there exists a
multiplicative inverse.
∀x (x ̸= 0 → ∃y (xy = 1))
⋆ If a person is female and is a parent, then this person
is someone’s mother.
∀x [female(x) ∧ parent(x) → ∃y (mother (x, y ))]

NIT Calicut CS2006D: Discrete Structures 15 / 37

Nested Quantifiers

⋆ Every train is faster than some cars.

∀x [train(x) → ∃y (car (y ) ∧ faster (x, y ))]
⋆ Some cars are slower than all trains but at least one
train is faster than every car.
∃x [car (x) ∧ ∀y (train(y ) → slower (x, y ))] ∧
∃x [train(x) ∧ ∀y (car (y ) → faster (x, y ))]
⋆ If it rains tomorrow, then somebody will get wet.
P → ∃x (person(x) ∧ wet(x))

NIT Calicut CS2006D: Discrete Structures 16 / 37

Logical Identities

1 ∀ x P(x) → P(c), for some constant c.

2 For some c, P(c) → ∃ x P(x)
3 ∀ x ¬P(x) ↔ ¬∃ x P(x)
4 ∀ x P(x) → ∃ x P(x)
5 ∃ x ¬P(x) ↔ ¬∀ x P(x)
6 ∀ x P(x) ∧ Q ↔ ∀ x [P(x) ∧ Q]
7 ∀ x P(x) ∧ ∀ x Q(x) ↔ ∀ x [P(x) ∧ Q(x)]
8 ∀ x P(x) ∨ ∀ x Q(x) → ∀ x [P(x) ∨ Q(x)]
9 ∃ x [P(x) ∧ Q(x)] → ∃ x P(x) ∧ ∃ x Q(x)
10 ∃x P(x) ∨ ∃ x Q(x) ↔ ∃ x [P(x) ∨ Q(x)]

NIT Calicut CS2006D: Discrete Structures 17 / 37

Rules of Inference

Rules of Inference for Quantified Statements

R ULE OF I NFERENCE N AME

∀x P(x) =⇒ P(c) Universal Instantiation
P(c) for any arbitrary c =⇒ ∀x P(x) Universal Generalization
∃x P(x) =⇒ P(c) for some c Existential Instantiation
P(c) for some c =⇒ ∃x P(x) Existential Generalization

NIT Calicut CS2006D: Discrete Structures 18 / 37

Some Claims
Claim
∀ x P(x) ∧ ∀ x Q(x) ↔ ∀ x [P(x) ∧ Q(x)]

Proof.
Necessity: It follows from definition that [P(x0 ) ∧ P(x1 ) ∧ P(x2 ) ∧ . . .] ∧
[Q(x0 ) ∧ Q(x1 ) ∧ Q(x2 ) ∧ . . .] where {x0 , x1 , x2 , . . .} is the universe of
discourse.
Apply the below rules inductively. For simplicity we work with the
first two terms.
[P(x0 ) ∧ P(x1 )] ∧ [Q(x0 ) ∧ Q(x1 )]
Due to Associativity, and Commutativity,
[P(x0 ) ∧ Q(x0 )] ∧ [P(x1 ) ∧ Q(x1 )]
Once inductive application of the above rules is completed in order for
all elements in the universe of discourse, we get
(P(x0 ) ∧ Q(x0 )) ∧ (P(x1 ) ∧ Q(x1 )) ∧ . . .
By definition, =⇒ ∀x [P(x) ∧ Q(x)]. Necessity follows.
NIT Calicut CS2006D: Discrete Structures 19 / 37
Some Claims

Proof.
Sufficiency: ∀x [P(x) ∧ Q(x)]
By definition, =⇒ (P(x0 ) ∧ Q(x0 )) ∧ (P(x1 ) ∧ Q(x1 )) ∧ . . .
Apply the below rules inductively. For simplicity we work with the
first two terms.
Consider [P(x0 ) ∧ Q(x0 )] ∧ [P(x1 ) ∧ Q(x1 )]
Due to Associativity, =⇒ [P(x0 ) ∧ Q(x0 ) ∧ P(x1 )] ∧ Q(x1 )
Due to Commutativity, =⇒ [P(x0 ) ∧ P(x1 ) ∧ Q(x0 )] ∧ Q(x1 )
Due to Associativity, =⇒ [P(x0 ) ∧ P(x1 )] ∧ [Q(x0 ) ∧ Q(x1 )]
It follows that [P(x0 ) ∧ P(x1 ) ∧ P(x2 ) ∧ . . .] ∧
[Q(x0 ) ∧ Q(x1 ) ∧ Q(x2 ) ∧ . . .]
From necessity and sufficiency, the claim follows.

NIT Calicut CS2006D: Discrete Structures 20 / 37

Some Claims

Claim
∃ x [P(x) ∨ Q(x)] ↔ ∃x P(x) ∨ ∃ x Q(x)

Proof.
From previous claim ∀ x [P(x) ∧ Q(x)] ↔ ∀ x P(x) ∧ ∀ x Q(x)
Inverse, =⇒ ¬∀ x [P(x) ∧ Q(x)] ↔ ¬[∀ x P(x) ∧ ∀ x Q(x)]
De-Morgans law, =⇒ ∃x [¬[P(x) ∧ Q(x)]] ↔ ¬∀ x P(x) ∨ ¬∀ x Q(x)
De-Morgans law, =⇒ ∃x [¬P(x) ∨ ¬Q(x)] ↔ ∃ x ¬P(x) ∨ ∃ x ¬Q(x)
R(x) = ¬P(x) and S(x) = ¬Q(x) =⇒ ∃x [R(x) ∨ S(x)] ↔
∃ x R(x) ∨ ∃ x S(x)

NIT Calicut CS2006D: Discrete Structures 21 / 37

Logical Inference

Question 1
All philosophers are scientists.
All scientists are engineers.
Therefore, all philosophers are engineers.
In FOL, the above arguemnt is translated into
[∀x(P(x) → S(x)) ∧ ∀x(S(x) → E (x))] → ∀x(P(x) → E (x))
U.I of the premise gives;
P(a) → S(a), for any a
S(a) → E (a), for any a
We know that (P → Q) ∧ (Q → R) → (P → R).
Thus, we get, P(a) → E (a). Since a is arbitrary, on UG,
∀x(P(x) → E (x)), the desired claim.

NIT Calicut CS2006D: Discrete Structures 22 / 37

Logical Inference
Question 1.If a teacher teaches DM or DSA, then he is considered to
be a TCS teacher. If he is a TCS teacher, then he teaches GT. He does
not teach GT. Therefore, he does not teach DSA.
A: A teacher teaches DM B: A teacher teaches DSA C: The teacher is
a TCS teacher D: A teacher teaches GT
(A ∨ B) → C . . . (1)
C →D . . . (2)
¬D . . . (3)
∴ ¬B
Proof
From1, 2 : (A ∨ B) → D . . . (4) − Due to Hypothetical Syllogism.
3, 4 : ¬(A ∨ B) . . . (5)
5: ¬A ∧ ¬B . . . (6)
6: ¬B QED
Therefore, the conclusion, teacher does not teach DSA follows from
the given logical argument.
NIT Calicut CS2006D: Discrete Structures 23 / 37
Logical Inference
Question 2. Derive a contradiction for the premises 1-5.

A→B ∨C ... (1)

D → ¬C ... (2)
B → ¬A ... (3)
A ... (4)
D ... (5)

1, 4 : B ∨C ... (6)
2, 5 : ¬C ... (7)
6: ¬C → B ... (8)
7, 8 : B ... (9)
3: A → ¬B ... (10)
4, 10 : ¬B ... (11)
9, 11 : B ∧ ¬B a contradiction

Therefore, the given argument is logically inconsistent.

NIT Calicut CS2006D: Discrete Structures 24 / 37
Logical Inference

Question 3. Show that R ∨ S follows logically from the premises

C ∨D ... (1)
C ∨ D → ¬H ... (2)
¬H → A ∧ ¬B ... (3)
A ∧ ¬B → R ∨ S ... (4)

1, 2 : ¬H . . . (5)
3, 5 : A ∧ ¬B . . . (6)
4, 6 : R ∨ S QED

NIT Calicut CS2006D: Discrete Structures 25 / 37

Logical Inference

Question 4. Show that S ∨ R follows logically from the first three

premises.

P ∨Q . . . (1)
P→R . . . (2)
Q→S . . . (3)

1: ¬Q → P ... (4)
2, 4 : ¬Q → R ... (5)
5: ¬R → Q ... (6)
3, 6 : ¬R → S ... (7)
7 S ∨R QED

NIT Calicut CS2006D: Discrete Structures 26 / 37

Logical Inference

Question 5. If Jack misses many classes through illness, then he fails

high school.
If Jack fails high school, then he is uneducated.
If Jack reads a lot of books, then he is not uneducated.
Jack misses many classes through illness and reads a lot of books.
Check whether the argument is consistent.
J: Jack misses many classes through illness.
H: Jack fails high school.
U: Jack is uneducated.
R: Jack reads a lot of books.
J→H ... (1)
H→U ... (2)
R → ¬U ... (3)
J ∧R ... (4)

NIT Calicut CS2006D: Discrete Structures 27 / 37

Logical Inference

J→H ... (1)

H→U ... (2)
R → ¬U ... (3)
J ∧R ... (4)
Proof :
1, 2 : J→U ... (5)
3: U → ¬R ... (6)
5, 6 : J → ¬R ... (7)
7: R → ¬J ... (8)
4: R ... (9)
8, 9 : ¬J ... (10)
4: J ... (11)
10, 11 : J ∧ ¬J a contradiction

Therefore, the given argument is logically inconsistent.

NIT Calicut CS2006D: Discrete Structures 28 / 37

Questions

Show that the premises “It is not sunny this afternoon and it is colder
than yesterday,” “We will go swimming only if it is sunny,” “If we do
not go swimming, then we will take a canoe trip,” and “If we take a
canoe trip, then we will be home by sunset” lead to the conclusion
”We will be home by sunset.”

NIT Calicut CS2006D: Discrete Structures 29 / 37

Questions

Show that the premises “If you send me an e-mail message, then I will
finish writing the program,” “If you do not send me an e-mail mes-
sage, then I will go to sleep early,” and “If I go to sleep early, then I
will wake up feeling refreshed” lead to the conclusion “If I do not fin-
ish writing the program, then I will wake up feeling refreshed.”

NIT Calicut CS2006D: Discrete Structures 30 / 37

Resolution

((p ∨ q) ∧ (¬p ∨ r )) → (q ∨ r )
Use resolution to show that the hypotheses “Jasmine is skiing or it is
not snowing” and “It is snowing or Bart is playing hockey” imply that
“Jasmine is skiing or Bart is playing hockey.”
Solution
Let p be the proposition “It is snowing,” q the proposition “Jasmine is
skiing,” and r the proposition “Bart is playing hockey.” We can repre-
sent the hypotheses as ¬p ∨ q and p ∨ r , respectively. Using resolution,
the proposition q ∨ r , “Jasmine is skiing or Bart is playing hockey,” fol-
lows

NIT Calicut CS2006D: Discrete Structures 31 / 37

Resolution

⋆ Resolution plays an important role in programming languages

based on the rules of logic, such as Prolog
⋆ It can be used to build automatic theorem proving systems.
⋆ To construct proofs in propositional logic using resolution as the
only rule of inference, the hypotheses and the conclusion must be
expressed as clauses, where a clause is a disjunction of variables
or negations of these variables
Question:
Is the following argument valid?
1 The premises (p ∧ q) ∨ r and r → s imply the conclusion p ∨ s.
2 If you do every problem in this book, then you will learn discrete
mathematics.You learned discrete mathematics. Therefore, you
did every problem in this book.

NIT Calicut CS2006D: Discrete Structures 32 / 37

Questions

Show that the premises “Everyone in this discrete mathematics class

has taken a course in computer science” and “Marla is a student in
this class” imply the conclusion “Marla has taken a course in com-
puter science.”

NIT Calicut CS2006D: Discrete Structures 33 / 37

Questions

Show that the premises “Everyone in this discrete mathematics class

has taken a course in computer science” and “Marla is a student in
this class” imply the conclusion “Marla has taken a course in com-
puter science.”

Let D(x) denote “x is in this discrete mathematics class,” and let C(x)
denote “x has taken a course in computer science.”

NIT Calicut CS2006D: Discrete Structures 33 / 37

Questions
Show that the premises “A student in this class has not read the book,”
and “Everyone in this class passed the first exam” imply the conclu-
sion “Someone who passed the first exam has not read the book.”

NIT Calicut CS2006D: Discrete Structures 34 / 37

Questions
Show that the premises “A student in this class has not read the book,”
and “Everyone in this class passed the first exam” imply the conclu-
sion “Someone who passed the first exam has not read the book.”

Let C(x) be “x is in this class,” B(x) be “x has read the book,” and P (x)
be “x passed the first exam.”

NIT Calicut CS2006D: Discrete Structures 34 / 37