CSC102 - Discrete Structures
(Discrete Mathematics)
Lecture # 8
Lecture Outline
• Ch. 1.4 Predicates and Quantifiers
– Translation of Quantified Statements
– Negating Quantified Statements
– Four Aristotelian forms
Summary
Statement When True? When False?
xP(x) P(x) is true for every There is an x for which
x. P(x) is false.
∃x P(x) There is an x for P(x) is false for every x.
which P(x) is true.
Quantifiers with Restricted
Domain
Quantifiers with Restricted Domain
• An abbreviated notation is often used to
restrict the domain of a quantifier.
• In this notation, a condition (a variable must
satisfy ) is included after the quantifier.
• ∀𝑥 < 0 𝑥 2 > 0 where domain is real
numbers
Restricted Domain-Rule for universal
Quantification
• ∀𝑥 < 0 𝑥 2 > 0 ≡ ∀𝑥 (𝑥 < 0) → (𝑥 2 > 0)
• The restriction of a universal quantification is
the same as the universal quantification of a
conditional statement.
Restricted Domain-Rule for universal
Quantification
∀𝑦 ≠ 0 𝑦 3 ≠ 0
≡ ∀𝑦 𝑦 ≠ 0 → 𝑦 3 ≠ 0
Restricted Domain-Rule for
Existential Quantification
• ∃𝑧 > 0 𝑧 2 = 2 ≡ ∃𝑧 𝑧 > 0 ∧ 𝑧 2 = 2
• The restriction of an existential quantification
is the same as the existential quantification of
a conjunction.
Precedence of Quantifiers
⚫The quantifiers and have higher
precedence then all logical operators
from propositional calculus.
⚫ e.g x P(x) Q(x) is the disjunction of
x P(x) and Q(x).
A Note on quantifiers
• Recall that a proposition is a statement that is either true
or false
– P(x) is not a proposition
• Recall that P(x) is a propositional function/Predicate
– Let P(x) be “x == 0”
• There are two ways to change a propositional function into
a proposition:
– Supply it with a value
» For example, P(5) is false, P(0) is true
– Provide a quantification
» For example, x P(x) is false and x P(x) is true
» Let the universe of discourse be the real numbers
Translating From English
• Express the statement “Every student in this
class has studied calculus” using predicates
and quantifiers.
• Solution:
“For every student x in this class, x has studied
calculus.”
Domain: Class
C(x) = “x has studied calculus.”
∀xC(x)
Translating From English
Re-express the statement with domain for all people.
“For every person x, if person x is a student in this class then x
has studied calculus.”
Let C(x) = “x has studied calculus.”
S(x) = “person x is a student in this class.”
The domain for x consists of all people.
• The statement can be expressed as ∀x(S(x) → C(x)).
Note: Our statement cannot be expressed as ∀x(S(x) ∧ C(x))
because this statement says that all people are students in this
class and have studied calculus!
Translating From English to Logical Expressions
• Let R(x) = “x can speak Russian”
C(x) = “x knows the computer language C++.”
The domain for quantifiers consists of all students of university.
• Some student in your university can speak Russian and know C++ .
∃𝒙 𝑹 𝒙 𝑪 𝒙
Translating From English to Logical Expressions
• Let R(x) = “x can speak Russian”
C(x) = “x knows the computer language C++.”
• There is a student in the university who can
speak Russian but who doesn’t know C++.
∃𝒙 𝑹 𝒙 ¬𝑪 𝒙
Translating From English to Logical Expressions
• Let R(x) = “x can speak Russian”
C(x) = “x knows the computer language C++.”
• Every student either can speak Russian or knows C++.
∀𝒙 𝑹 𝒙 𝑪 𝒙
Translating From English to Logical Expressions
• Let R(x) = “x can speak Russian”
C(x) = “x knows the computer language C++.”
• No student can speak Russian or knows C++.
∀𝒙¬ 𝑹 𝒙 𝑪 𝒙 /¬∃𝒙 𝑹 𝒙 𝑪 𝒙
Negating Quantified Expressions
• Negation of Universal Quantification
“Every student in this class has studied calculus.”
• This statement is a universal quantification, namely, ∀xC(x),
– C(x) is the statement “x has studied calculus”
– Domain consists of the students in the class.
• The negation of this statement is
– “It is not the case that every student in this class has studied calculus.”
– This is equivalent to “There is a student in this class who has not studied
calculus.”
• This is simply the existential quantification of the negation of the
original propositional function, namely, ∃x ￢C(x).
Negating Quantified Expressions
• Negation of Existential Quantification
What is the negation of the statement “There is an honest
politician”?
Solution:
• Let H(x) denote “x is honest politician.”
• The statement is represented by ∃xH(x), where the domain consists
of all politicians.
• Negation= It is not the case that there is an honest politician(not
even a single one). Which means every politician is dishonest. ∀x
￢H(x)
Negating Quantified Expressions
Negation Equivalent When is When False?
Statement Negation
True?
￢∃x P(x) ∀x ￢ P(x) For every x, There is an x
P(x) is false. for which
P(x) is true.
￢∀x P(x) ∃x ￢ P(x) There is an x P(x) is true for
for which P(x) every x.
is false.
Negating Quantified Expressions
• Consider the statement:
– All students in this class have red hair
• What is required to show the statement is false?
– There exists a student in this class that does NOT
have red hair
• To negate a universal quantification:
– change to an existential quantification
– negate the propositional function
– ¬x P(x) = x ¬P(x)
Negating Quantified Expressions
Example:
What is the negation of the statement “All Americans eat
cheeseburgers”?
Solution:
• C(x) denote “x eats cheeseburgers.”
• The statements represented by ∀xC(x), where the domain
consists of all Americans.
• The negation of this statement is ￢∀xC(x), which is equivalent
to ∃x￢C(x).
• This negation can be expressed as “Some American does not
eat cheeseburgers” and “There is an American who does not
eat cheeseburgers.”
Negating Quantified Expressions
Negating Quantified Expressions
x ( x x )
2
x ( x = x )
2
x ( x x )
2
x ( x = x )
2
x( x x )
2
x( x = x )2
x ( x x )
2
x ( x x )
2
De Morgan’s Laws for Quantifiers
• 𝑥 𝑃(𝑥) ≡ 𝑃(𝑥1) 𝑃(𝑥2) … 𝑃(𝑥𝑛)
• ∃𝑥𝑃 𝑥 ≡ 𝑃(𝑥1 ) 𝑃(𝑥2 )… . 𝑃 𝑥𝑛
• ¬∃𝑥𝑃 𝑥 ≡ ¬(𝑃(𝑥1 ) 𝑃(𝑥2 )… . 𝑃 𝑥𝑛 )
≡ ¬𝑃(𝑥1 ) ¬𝑃(𝑥2 ) … . ¬(𝑃 𝑥𝑛 )
≡ ∀𝑥¬𝑃(𝑥)
• ¬∀𝑥𝑃 𝑥 ≡ ¬(𝑃(𝑥1 ) 𝑃(𝑥2 ) … . 𝑃 𝑥𝑛 )
≡ ¬𝑃(𝑥1 ) ¬𝑃(𝑥2 ) … . ¬(𝑃 𝑥𝑛 )
≡ ∃𝑥¬𝑃(𝑥)
The Four Aristotelian Forms
These are four of the most common quantificational
sentences used in quantificational reasoning.
1. All A's are B's
2. Some A's are B's
3. No A's are B's
4. Some A's are not B's
The First Aristotelian Form
• The Form: All A's are B’s
• Example: All comedian are funny.
– Rephrase: For every x, if x is a comedian then x is
funny
– Translation: ∀x (Comedian(x) → Funny(x))
– This translation has the form: ∀x (A(x) → B(x))
• General Fact
– All A's are B's translates as ∀x (A(x) → B(x))
The Second Aristotelian Form
• The Form: Some A's are B’s
• Example: Some comedian are funny
– Rephrase: Some thing x is both comedian and funny
– Translation: x (Comedian(x) Funny(x))
– This translation has the form: x (A(x) B(x))
• General Fact
– Some A's are B's translates as x (A(x) B(x))
The Third Aristotelian Form
• The Form: No A's are B’s
• Example: No students are failed
– Rephrase: For every x, if x is a student then x is not
failed
– Translation: ∀x (Student(x) → Failed(x))
– This translation has the form: ∀x (A(x) → B(x))
• General Fact
– No A's are B's translates as ∀x (A(x) → B(x))
The Fourth Aristotelian Form
• The Form: Some A's are not B’s
• Example: Some excuses are not believable
– Rephrase: For some x, x is an excuse and x is not
believable
– Translation: x (Excuse(x) Believable(x))
– This translation has the form: x (A(x) B(x))
• General Fact
– Some A's are not B's translates as x (A(x) B(x))
Summary
• The Aristotelian Forms and Their Translations
– All A's are B's ∀x (A(x) → B(x))
– Some A's are B's x (A(x) B(x))
– No A's are B's ∀x (A(x) → B(x))
– Some A's are not B’s x (A(x) B(x))
Predicates - Examples
L(x) = “x is a lion.”
F(x) = “x is fierce.”
C(x) = “x drinks coffee.”
Assuming that the domain consists of all creatures.
• All lions are fierce.
x (L(x) → F(x))
• Some lions don’t drink coffee.
x (L(x) C(x))
• Some fierce creatures don’t drink coffee.
x (F(x) C(x))
Chapter Reading and Exercises
• Chapter 1, Kenneth H. Rosen, Discrete Mathematics and Its
Applications, Section 1.4
• Question # 1 to 14, 17, 18, 33,35, 61(a, b, c), 62( a, b, c), 63(a, b,
c, d)
