Page 1 of 5

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:

1
 Page 2 of 5

a. 𝑅(2, −1, 5) b. 𝑅(𝑥, 3, 𝑧)

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

2
 Page 3 of 5

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.

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.”

1
 Page 4 of 5

2. “Every bird can fly.”

3. ∀𝑥(𝑥2 > 𝑥) 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:

2
 Page 5 of 5

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

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