Page 1 of 6
Discrete Mathematics
Predicates and Quantifiers
Predicates
Propositional logic is not enough to express the meaning of all statements in mathematics
and natural language.
Examples:
Is “𝑥 > 1” True or False?
Is “𝑥 is a great tennis player” True or False?
Predicate Logic
Variables: 𝑥, 𝑦, 𝑧, etc.
Predicates: 𝑃(𝑥), 𝑄(𝑥), etc.
Quantifiers: Universal and Existential.
Connectives from propositional logic carry over to predicate logic.
A predicate 𝑃(𝑥) is a declarative sentence whose truth value depends on one or more
variables.
𝑃(𝑥) is also said to be the value of the propositional function 𝑃 at 𝑥.
𝑃(𝑥) becomes a proposition when a value of 𝑥 is assigned from the domain 𝑈.
Examples (Propositional Functions):
1. Let 𝑃(𝑥) be “𝑥 ≥ 1.” Determine the truth value of
a. 𝑃(2) b. 𝑃(−2) → 𝑃(1)
2. Let 𝑅(𝑥, 𝑦, 𝑧) be “𝑥 + 𝑦 = 𝑧.” Find these truth values:
a. 𝑅(2, −1, 5) b. 𝑅(𝑥, 3, 𝑧)
© 2020, I. Perepelitsa
Page 2 of 6
Quantifiers
We need quantifiers to express the meaning of English words including all and some:
“All students in this class are computer science majors”
“There is a math major student in this class”
The two most important quantifiers are:
Universal Quantifier, “For all,” symbol: ∀
Existential Quantifier, “There exists,” symbol: ∃
We write as in ∀𝑥 𝑃(𝑥) and ∃𝑥 𝑃(𝑥).
∀𝑥 𝑃(𝑥) asserts 𝑃(𝑥) is true for every 𝑥 in the domain.
If = {𝑥1 , 𝑥2 , … , 𝑥𝑛 } , then ∀𝑥 𝑃(𝑥) = 𝑃(𝑥1 ) ∧ 𝑃(𝑥2 ) … ∧ 𝑃(𝑥𝑛 ).
∃𝑥 𝑃(𝑥) asserts 𝑃(𝑥) is true for some 𝑥 in the domain.
If = {𝑥1 , 𝑥2 , … , 𝑥𝑛 } , then ∃𝑥 𝑃(𝑥) = 𝑃(𝑥1 ) ∨ 𝑃(𝑥2 ) … ∨ 𝑃(𝑥𝑛 ).
Examples:
1. Let 𝑃(𝑥): “𝑥 > −𝑥” with the domain of all positive real numbers.
Find the truth value of ∀𝑥 𝑃(𝑥).
2. Let 𝑃(𝑥): “𝑥 > −𝑥” with the domain of all real numbers.
Find the truth value of ∀𝑥 𝑃(𝑥).
The truth value of ∃𝑥 𝑃(𝑥) and ∀𝑥 𝑃(𝑥) depends BOTH on the propositional function
𝑃(𝑥) and on the domain 𝑈.
Quantifiers
Statement When True? When False?
∀𝑥 𝑃(𝑥) 𝑃(𝑥) is true for every 𝑥. There is an x for which
𝑃(𝑥) is false.
∃𝑥 𝑃(𝑥) There is an x for which 𝑃(𝑥) 𝑃(𝑥) is false for every 𝑥.
is true.
© 2020, I. Perepelitsa
Page 3 of 6
Example: Suppose the domain of the propositional function 𝑃(𝑥): 𝑥 2 ≤ 𝑥 consists of
{1, 2, 3}. Write out each of the following propositions using conjunction or disjunction and
determine its truth value.
1. ∀𝑥 𝑃(𝑥) 2. ∃𝑥 𝑃(𝑥)
An element for which 𝑃(𝑥) is false is called a counterexample of ∀𝑥 𝑃(𝑥)
Precedence of Quantifiers
The quantifiers ∀ and ∃ have higher precedence than all the logical operators.
Example: ∀𝑥 𝑃(𝑥) ∨ 𝑄(𝑥) means (∀𝑥 𝑃(𝑥)) ∨ 𝑄(𝑥). ∀𝑥 (𝑃(𝑥) ∨ 𝑄(𝑥)) means something
different.
Negating Quantifiers
De Morgan laws for quantifiers (the rules for negating quantifiers) are:
¬∀𝑥 𝑃(𝑥) ≡ ∃𝑥¬𝑃(𝑥)
¬∃𝑥 𝑃(𝑥) ≡ ∀𝑥¬ 𝑃(𝑥)
Example: Express each of these statements using quantifiers. Then form a negation of the
statement, so that no negation is left of a quantifier. Next, express the negation in simple
English.
1. “Some old dogs can learn new tricks.”
© 2020, I. Perepelitsa
Page 4 of 6
2. “Every bird can fly.”
3. ∀𝑥(𝑥 2 > 𝑥)
© 2020, I. Perepelitsa
Page 5 of 6
Translating from English into Logical Expressions
Examples: Translate the statements into the logical symbols. Let 𝑥 be in set of all students
in this class.
1. Someone in your class can speak Hindi.
2. Everyone in your class is friendly.
3. There is a student in your class who was not born in California.
𝐻(𝑥) = “ 𝑥 𝑠𝑝𝑒𝑎𝑘𝑠 𝐻𝑖𝑛𝑑𝑖”, 𝐹(𝑥) = “ 𝑥 𝑖𝑠 𝑓𝑟𝑖𝑒𝑛𝑑𝑙𝑦, ” 𝐶(𝑥) = “ 𝑥 𝑤𝑎𝑠 𝑏𝑜𝑟𝑛 𝑖𝑛 𝐶𝑎𝑙𝑖𝑓𝑜𝑟𝑛𝑖𝑎. ”
Example: Translate the following sentence into predicate logic and give its negation:
“Every student in this class has taken a course in Java.”
Solution:
First, decide on the domain U!
Solution 1: If U is all students in this class, define a propositional function J(x)
denoting “x has taken a course in Java” and translate as
Solution 2: But if U is all people, also define a propositional function S(x) denoting “x
is a student in this class” and translate as
© 2020, I. Perepelitsa
Page 6 of 6
Example: Translate the following sentence into predicate logic:
“Some student in this class has taken a course in Java.”
Solution:
First, decide on the domain U!
Solution 1: If U is all students in this class, translate as
Solution 2: But if U is all people, then translate as
© 2020, I. Perepelitsa
