L02: Predicate Logic (First-order logic)

 Outline
 Predicates
 Quantifiers
 Quantifiers with Restricted domains
 Logical Equivalences involving Quantifiers
 Negating Quantified Expressions
 Nested Quantifiers

 Reading
 Kenneth Rosen, Section 1.4-1.5

1
 Predicate Logic

 Suppose we know that “every COMP student is

required to take either COMP 2711 or COMP 2711H”.
 No rules of propositional logic allow us to conclude
the truth of the statement “Chan Tai Man, a COMP
student, is required to take either COMP 2711 or
COMP 2711H”.
 We now study predicate logic which is more powerful
than propositional logic.

2
 Outline

 Predicates
 Quantifiers
 Quantifiers with Restricted Domains
 Logical Equivalences involving Quantifiers
 Negating Quantified Expressions
 Nested Quantifiers

3
 Predicate
 Definition: Informally, a predicate is a statement that
may be true or false depending on the choice of values
of its variables. Each choice of values produces a
proposition.
 More formally, a statement involving n variables x1, x2,
… , xn, denoted by P(x1, x2, … , xn), is the value of the
propositional function P at the n-tuple (x1, x2, … , xn)
and P is called an n-ary predicate.

 Example: P(x) denotes the statement “x is greater than

3”. x is the variable, and P is the predicate “is greater
than 3”

4
 Examples

 Let P(x) denote the statement “x>3”.

What are the truth values of P(4) and P(2)?
 Let A(x) denote the statement “student x is required to
take either COMP 2711 or COMP 2711H”.
Suppose Alice is a COMP student and Bob is a CHEM
student.
What are the truth values of A(Alice) and A(Bob)?
 Let Q(x, y) denote the statement “x=y+3”.
What are the truth values of the propositions Q(1, 2)
and Q(3, 0)?

5
 Outline

 Predicates
 Quantifiers
 Quantifiers with Restricted Domains
 Logical Equivalences involving Quantifiers
 Negating Quantified Expressions
 Nested Quantifiers

6
 Universal Quantification
 We saw that when the variables in a propositional
function are assigned values, the resulting proposition
has a certain truth value.
 Sometimes we may want to say that a predicate is true
over a set of values.
 Definition: The universal quantification of P(x) is the
statement “for all elements x in the domain such that
P(x)”.
 Denote as ∀x P(x). We read it as “for all x P(x)” or “for
every x P(x)”.
 Here ∀ is called the universal quantifier.
 An element for which P(x) is false is called a
counterexample of ∀x P(x).
7
 Domain
 The domain or universe is the set of all possible
values of a variable.
 The domain must always be specified when a universal
quantifier is used; without it, the universal
quantification of a statement is not well defined.
 Generally, an implicit assumption is made that the
domain is nonempty. Otherwise ∀x P(x) is true for any
propositional function P(x) because there are no
elements x in the domain for which P(x) is false.

8
 Examples
 Let P(x) be the statement “x + 1 > x”. What is the truth
value of the quantification ∀x P(x), where the domain
consists of all real numbers?
 Let Q(x) be the statement “x < 2”. What is the truth
value of the quantification ∀x Q(x), where the domain
consists of all real numbers?
 Let P(x) be the statement “x2 > 0”. What is the truth
value of the quantification ∀x P(x), where the domain
consists of all real numbers?
 What is the truth value of “∀x (x2 ≥ x)” if the domain
consists of all real numbers?
What is its truth value if the domain consists of all
integers?
9
 Existential Quantification
 Definition: The existential quantification of P(x) is
the statement “there exists an element x in the domain
such that P(x)”.
 The notation ∃x P(x) denotes the existential
quantification of P(x).
 Here ∃ is called the existential quantifier.
 Note that ∃x means “there exists at least one x in the
domain” but not “there exists one and only one x in
the domain” or “there exists a unique x in the domain”.

10
 Universal and Existential Quantifiers

 When the domain has n elements x1, x2, … , xn

∀x P(x) is the same as P(x1) ^ P(x2) ^ … ^ P(xn),

∃x P(x) is the same as P(x1) ∨ P(x2) ∨ … ∨ P(xn)

11
 Universal and Existential Quantifiers

 Give a counter example when ∀x P(x) is false

 Give an example when ∃x P(x) is true

12
 Examples

 Let P(x) be the statement “x > 3”. What is the truth

value of the quantification ∃x P(x), where the domain
consists of all real numbers?

 Let Q(x) be the statement “x = x + 1”. What is the truth

value of the quantification ∃x Q(x), where the domain
consists of all real numbers?

13
 Outline

 Predicates
 Quantifiers
 Quantifiers with Restricted Domains
 Logical Equivalences involving Quantifiers
 Negating Quantified Expressions
 Nested Quantifiers

14
 Restricted Domains

 Rewrite the following statements into equivalent

statements, where the domain consists of all real numbers
(a) ∀x < 0 (x2 > 0)
The square of a negative real number is positive
(b) ∀y ≠ 0 (y3 ≠ 0)
The cube of every nonzero real number is nonzero
(c) ∃z > 0 (z2 = 2)
There is a positive square root of 2
 Solution
 (a) ∀x (x < 0 → x2 > 0). True
 (b) ∀y (y ≠ 0 → y3 ≠ 0). True
 (c) ∃z (z > 0 ^ z2 = 2). True
15
 Quantifiers with Restricted Domains
 Let U1 and U2 be two domains with U1 ⊆ U2.
 Define Q(x) such that U1 = { x ∈ U2 | Q(x) is true }. Then
 (a) ∀x ∈ U1 (P(x)) 
∀x ∈ U2 (Q(x) → P(x))
Q(x) is false
 (b) ∃x ∈ U1 (P(x)) 
∃x ∈ U2 (Q(x) ^ P(x))
Q(x) is true

Example:
 U1 is all CSE students and U2 is all UST UGs
 Q(x): x is a CSE student (i.e., Q(x) is true ∀x ∈ U1 )
 P(x) : x is required to take COMP2711
 ∀x ∈ U1 (P(x))  ∀x ∈ U2 (Q(x) → P(x))
16
 Restricted Domains
 Consider the following argument:
Premise 1: “All lions are fierce”
Premise 2: “Some lions do not drink coffee”
Conclusion: “Some fierce creatures do not drink coffee”

P(x): “x is a lion”, Q(x): “x is fierce”, R(x): “x drinks

coffee”. Assume the domain consists of all creatures.

Solution
∀x (P(x) → Q(x))
∃x (P(x) ^ ¬ R(x))
∃x (Q(x) ^ ¬ R(x))
We will show in L03 that this argument is valid 17
 Restricted Domains

 “Some lions do not drink coffee” cannot be written as

∃x (P(x) → ¬ R(x))
 P(x) → ¬ R(x) is true whenever x is not a lion
 Thus ∃x (P(x) → ¬ R(x)) is true as long as there is at
least one creature that is not a lion, even if every
lion drinks coffee.

18
 Precedence of Quantifiers

 The quantifiers ∀ and ∃ have higher precedence than

all logical operators.
 Example
 ∀𝑥 𝑃 𝑥 ∨ 𝑄(𝑥) means (∀𝑥 𝑃 𝑥 ) ∨ 𝑄(𝑥), which is not a
valid proposition

19
 Binding Variables

 A variable can be
 bound by a quantifier
 the part of a logical expression bound by a
quantifier is called its scope
 set to a particular value
 otherwise, free
 Example: ∃𝑥 𝑃 𝑥 ∧ 𝑄 𝑥 ∨ ∀𝑥 𝑅 𝑥 ∨ 𝑆(𝑥)
 All variables in a propositional function must be
bound or set to a particular value to turn it into a
proposition.

20
 Outline

 Predicates
 Quantifiers
 Quantifiers with Restricted Domains
 Logical Equivalences involving Quantifiers
 Negating Quantified Expressions
 Nested Quantifiers

21
 Logical Equivalence

 Definition
Statements involving predicates and quantifiers are
logically equivalent if and only if they have the same
truth value no matter which predicates are substituted
into these statements and which (common) domain is
used for the variables in these propositional functions.

We use the notation S ≡ T to indicate that two

statements S and T involving predicates and
quantifiers are logically equivalent.

22
 Logical Equivalence

 Example
Show that ∀x (P(x)^Q(x)) and ∀xP(x) ^ ∀xQ(x) are
logically equivalent
 Proof
 Suppose ∀x (P(x) ^ Q(x)) is true. That is, if a is in the
domain, then P(a) and Q(a) are both true. Thus, ∀x
P(x) is true and so is ∀x Q(x). Thus ∀x P(x) ^ ∀x Q(x)
is true.
 Suppose ∀x P(x) ^ ∀x Q(x) is true. Then, ∀x P(x) is
true and ∀x Q(x) is true. Thus, if a is in the domain,
then P(a) is true and Q(a) is true. Thus, for all a ,
P(a) ^ Q(a) is true. Thus ∀x (P(x) ^ Q(x)) is true.
23
 Logical Equivalence (cont'd)

 The previous logical equivalence shows that we can

distribute a universal quantifier over a conjunction.
∀x (Q(x) ^ P(x)) ≡ ∀x P(x) ^ ∀x Q(x)
 We can also distribute an existential quantifier over a
disjunction (can you prove it?):
∃x (P(x) ∨ Q(x)) ≡ ∃x P(x) ∨ ∃x Q(x)
However, we cannot distribute a universal quantifier
over a disjunction, nor can we distribute an existential
quantifier over a conjunction (next slides):
∀x (P(x) ∨ Q(x)) ∀x P(x) ∨ ∀x Q(x)
∃x (P(x) ^ Q(x)) ∃x P(x) ^ ∃x Q(x)
24
 Logical Equivalence (cont'd)

(i) ∀x (P(x) ∨ Q(x))  ∀x P(x) ∨ ∀x Q(x)

(ii) ∀x (P(x) ∨ Q(x))  ∀x P(x) ∨ ∀x Q(x)
Example: We will show (ii) by giving a counter example
Domain = {a, b, c } a b c
P(a) ∨ Q(a) = T ∨ F = T P T F T
P(b) ∨ Q(b) = F ∨ T = T Q F T T

P(c) ∨ Q(c) = T ∨ T = T
Therefore ∀x (P(x) ∨ Q(x)) is true.

∀x P(x) is false since P(b) is false, ∀x Q(x) is false since

Q(a) is false. Therefore ∀x P(x) ∨ ∀x Q(x) is false.
Therefore ∀x (P(x) ∨ Q(x))  ∀x P(x) ∨ ∀x Q(x) 25
Logical Equivalence (cont'd)

(i) ∃x (P(x) ^ Q(x))  ∃x P(x) ^ ∃x Q(x)

(ii) ∃x (P(x) ^ Q(x))  ∃x P(x) ^ ∃x Q(x)

Example: We will show (ii) by giving a counter

example. Domain = {a, b} a b
∃x P(x) is true since P(a) is true. P T F
∃x Q(x) is true since Q(b) is true. Q F T

Therefore ∃x P(x) ^ ∃x Q(x) is true.

Since there is no one element x in the domain for

which P(x) and Q(x) are both true, ∃x (P(x) ^ Q(x)) is
false.
Therefore ∃x (P(x) ^ Q(x))  ∃x P(x) ^ ∃x Q(x) 26
Logical Equivalence (cont'd)

(i) ∃x (P(x) ^ Q(x))  ∃x P(x) ^ ∃x Q(x)

(ii) ∃x (P(x) ^ Q(x))  ∃x P(x) ^ ∃x Q(x)

Example: We will show (ii) by giving a counter

example. Domain is all integers
P(x): 2x + 1 = 5
Q(x): x2 = 9
∃x P(x) ^ ∃x Q(x) is true because P(2) and Q(3) are
true.
∃x (P(x) ^ Q(x)) is false because there is no one
integer a such that P(a) and Q(a) are both true.
Therefore ∃x (P(x) ^ Q(x))  ∃x P(x) ^ ∃x Q(x)
27
 Outline

 Predicates
 Quantifiers
 Quantifiers with Restricted Domains
 Logical Equivalences involving Quantifiers
 Negating Quantified Expressions
 Nested Quantifiers

28
 Motivation: negation

 Example
Let 𝑃(𝑥) denote the statement “student 𝑥 has iPhone”.
The domain is all students in this class

Express the following statement as a universal

quantification: “every student in the class has an
iPhone”.

Then express the negation of the statement using an

existential Quantifier.

29
 Motivation: negation

 Example
Express the following statement as an existential
quantification: “there is a student in the class who has
an iPhone”.

Then express the negation of the statement using a

universal quantifier.

30
De Morgan's Laws for Quantifiers

31
 De Morgan's Laws for Quantifiers
(cont'd)
 When the domain has n elements x1, x2, … , xn, it
follows that
¬∀x P(x) is the same as ¬ (P(x1) ^ P(x2) ^ … ^ P(xn)),
which is equivalent to ¬P(x1) ∨ ¬P(x2) ∨ … ∨ ¬P(xn) by
De Morgan's laws,
and this is the same as ∃x ¬P(x).

 Similarly,
¬∃x P(x) is the same as ¬ (P(x1) ∨ P(x2) ∨ … ∨ P(xn)),
which by De Morgan's laws is equivalent to ¬P(x1) ^
¬P(x2) ^ … ^ ¬P(xn),
and this is the same as ∀x ¬P(x). 32
 Examples

 Example
What is the negation of the statement
∀x (x2 > x) ?

 Example
What is the negation of the statement
∃x (x2 = 2) ?

33
 Examples

 Example
Show that ¬∀x (P(x)→Q(x)) and ∃x (P(x) ^ ¬Q(x))
are logically equivalent.

 Solution
¬∀x (P(x)→Q(x)) ≡
∃x ¬ (P(x) →Q(x)) ≡
∃x ¬ (¬ P(x) ∨ Q(x)) ≡
∃x (P(x) ^ ¬Q(x))

34
 Outline

 Predicates
 Quantifiers
 Quantifiers with Restricted Domains
 Logical Equivalences involving Quantifiers
 Negating Quantified Expressions
 Nested Quantifiers

35
 Nested Quantifiers

 Example
Assume that the domain for the variables x and y
consists of all real numbers.
The statement
∀x ∀y (x + y = y + x)
says that x + y = y + x for all real numbers x and y.

This is the commutative law for the addition of real

numbers.

36
 Order of Quantifiers
 Examples
The statement
∀x ∃y (x + y = 0)
says that for every real number x , there is a real number y
such that x +y = 0.
This states that every real number has an additive inverse.

What is the truth value of this quantification?

∃y ∀x (x + y = 0)
It is false since there is no value of y that satisfies
the equation x + y = 0 for all values of x.

 Remark: This example illustrates that the order in which

quantifiers appear makes a difference. 37
 Quantifications of Two Variables

 The following table summarizes the meanings of the

different possible quantifications involving two
variables.

38
 Nested quantifications
 Let Q(x, y, z) be the statement “x + y = z”. What are the
truth values of the statements
∀x ∀y ∃z Q(x, y, z)
∃z ∀x ∀y Q(x, y, z),
where the domain of the variables is all real numbers?
 Solution:
 Suppose x and y are assigned values. Then there exists a
real number z such that x + y = z. Thus the first statement
is true.
 There is no value of z that satisfies the equation x + y = z
for all values of x and y. Thus the second statement is false

39
 Nested Quantifications

 Example
Translate the statement “the sum of two positive
integers is always positive” into a logical expression.
 Solution: Domain is all integers
∀x ∀y ( x > 0 ^ y > 0 → x+y > 0)
 Example
Translate the statement “every nonzero real number
has a multiplicative inverse”.
 Solution: Domain is all real numbers
∀x ( x  0 → ∃y (xy = 1))

40
 Translating into English
 Example
Translate the statement
∀x (C(x) ∨ ∃y (C(y) ^ F(x, y)))
into English, where C(x) is “x has a computer”, F(x, y)
is “x and y are friends”, and the domain for both x and
y consists of all students in the school.
 Solution
For every student x in your school, x has a computer
or there is a student y such that y has a computer and x
and y are friends.
Every student either has a computer or has a friend
who has a computer.
41
 Translating into English (cont’d)
 Example
Translate the statement
∃x∀y∀z (F(x, y) ^ F(x, z) ^ (y ≠ z) → ¬F(y, z))
into English, where F(a, b) means a and b are friends
and the domain for x, y, and z consists of all students
in the school.
 Solution
The statement says that there is a student x such that
for all students y and all students z other than y, if x and
y are friends and x and z are friends, then y and z are
not friends.
In other words, there is a student none of whose
friends are also friends with each other. 42
 Translating from English
 Example: Express the statement “if a person is female
and is a parent, then this person is someone’s mother”
as a logical expression using the following predicates,
with a domain consisting of all people.
 𝐹(𝑥): 𝑥 is female
 𝑃(𝑥): 𝑥 is a parent
 𝑀(𝑥, 𝑦): 𝑥 is 𝑦’s mother
 Solution:
∀x (F(x) ^ P(x) → ∃y M(x, y))
Equivalent to
∀x ∃y (F(x) ^ P(x) → M(x, y))

43
 Null Quantifications
 Rules: If 𝑥 does not occur as a free variable in 𝐴, then
 ∀𝑥 𝐴 ∧ 𝑃 𝑥 ≡ 𝐴 ∧ ∀𝑥 𝑃(𝑥)
 ∀𝑥 𝐴 ∨ 𝑃 𝑥 ≡ 𝐴 ∨ ∀𝑥 𝑃(𝑥)
 ∃𝑥 𝐴 ∧ 𝑃 𝑥 ≡ 𝐴 ∧ ∃𝑥 𝑃(𝑥)
 ∃𝑥 𝐴 ∨ 𝑃 𝑥 ≡ 𝐴 ∨ ∃𝑥 𝑃(𝑥)
 Proof: Let the domain of 𝑥 be {𝑥1 , … , 𝑥𝑛 }
 ∀𝑥 𝐴 ∧ 𝑃 𝑥 ≡ 𝐴 ∧ 𝑃 𝑥1 ∧ ⋯ ∧ 𝐴 ∧ 𝑃 𝑥𝑛
≡ 𝐴 ∧ 𝑃 𝑥1 ∧ ⋯ ∧ 𝑃 𝑥𝑛 ≡ 𝐴 ∧ ∀𝑥 𝑃(𝑥)
 ∀𝑥 𝐴 ∨ 𝑃 𝑥 ≡ 𝐴 ∨ 𝑃 𝑥1 ∧ ⋯ ∧ 𝐴 ∨ 𝑃 𝑥𝑛
≡ 𝐴 ∨ 𝑃 𝑥1 ∧ ⋯ ∧ 𝑃 𝑥𝑛 ≡ 𝐴 ∨ ∀𝑥 𝑃 𝑥
 The other two rules can be proved similarly
44
 Null Quantifications: Examples
 ∀𝑥 𝑃 𝑥 ∨ ∀𝑥 𝑄 𝑥
≡ ∀𝑥 𝑃 𝑥 ∨ ∀𝑦 𝑄 𝑦
≡ ∀𝑥 𝑃 𝑥 ∨ ∀𝑦 𝑄 𝑦
≡ ∀𝑥∀𝑦 𝑃 𝑥 ∨ 𝑄 𝑦
≡ ∀𝑦∀𝑥 𝑃 𝑥 ∨ 𝑄 𝑦
 But ∀𝑥 𝑃 𝑥 ∨ 𝑄 𝑥 ∀𝑥 𝑃(𝑥) ∨ ∀𝑥 𝑄(𝑥)
 ∃𝑥 𝑃 𝑥 ∨ ∀𝑦 𝑄 𝑦  ∃𝑥 𝑃 𝑥 ∨ ∀𝑦 𝑄 𝑦
≡ ∃𝑥 𝑃 𝑥 ∨ ∀𝑦 𝑄 𝑦 ≡ ∀𝑦 ∃𝑥 𝑃 𝑥 ∨ 𝑄 𝑦
≡ ∃𝑥∀𝑦 𝑃 𝑥 ∨ 𝑄 𝑦 ≡ ∀𝑦∃𝑥 𝑃 𝑥 ∨ 𝑄 𝑦

 In this case, ∃𝑥 and ∀𝑦 can be swapped (in general,

they can’t)
45
 Null Quantifications: Examples

 ∀𝑥 𝑃 𝑥 → ∃𝑦 𝑄 𝑦 ≡ ∀𝑥∃𝑦 𝑃 𝑥 → 𝑄 𝑦 ?
 No!
 ∀𝑥∃𝑦 𝑃 𝑥 → 𝑄 𝑦  Counterexample:
≡ ∀𝑥∃𝑦 ¬𝑃 𝑥 ∨ 𝑄 𝑦
Domain 𝒂 𝒃
≡ ∀𝑥¬𝑃 𝑥 ∨ ∃𝑦 𝑄 𝑦
𝑃 T F
≡ ¬∃𝑥 𝑃 𝑥 ∨ ∃𝑦 𝑄 𝑦
𝑄 F F
≡ ∃𝑥 𝑃 𝑥 → ∃𝑦 𝑄 𝑦
 ∀𝑥 𝑃 𝑥 → ∃𝑦 𝑄 𝑦
≡ ¬ ∀𝑥 𝑃 𝑥 ∨ ∃𝑦 𝑄 𝑦 ∀𝑥 𝑃 𝑥 → ∃𝑦 𝑄 𝑦 is True
≡ ∃𝑥¬𝑃 𝑥 ∨ ∃𝑦 𝑄 𝑦 ∀𝑥∃𝑦 𝑃 𝑥 → 𝑄 𝑦 is False
≡ ∃𝑥∃𝑦 ¬𝑃 𝑥 ∨ 𝑄 𝑦
≡ ∃𝑥∃𝑦 𝑃 𝑥 → 𝑄 𝑦
46
 Examples
 Example: Express the statement “everyone has exactly
one best friend” as a logical expression using the
following predicates, with a domain consisting of all
people.
 𝐵(𝑥, 𝑦): 𝑦 is 𝑥’s best friend
 Solution:
“x has exactly one best friend” can be represented as
∃y (B(x, y) ^ ∀z ((z ≠ y) → ¬B(x, z)))
There is a person y who is the best friend of x, and then for every
person z if z is not person y, then z is not the best friend of x.
Thus, the original statement can be expressed as
∀x ∃y (B(x, y) ^ ∀z ((z ≠ y) → ¬B(x, z)))
47
 Negating Nested Quantifiers

 Example
Express the negation of the statement ∀x∃y (xy = 1) so
that no negation precedes a quantifier.

48
 Negating nested quantifiers
 Example
Use quantifiers to express the statement “there is a
woman who has taken a flight on every airline in the
world”.
 Solution
Let P(w,f) be “woman w has taken flight f ”
Let Q(f,a) be “f is a flight on airline a ”
∃w ∀a ∃f ( (P(w, f) ^ Q(f, a) )
 Example
Use quantifiers to express the negation of the above
statement so that no negation precedes a quantifier.
∀w ∃a ∀f ( (¬ P(w, f) ∨ ¬ Q(f, a) )
49