Transcript Chapter 3.1-3.3 - Help-A-Bull

Discrete Mathematics and Applications
Chapter 3: The Logic of
Quantified Statements
Yan Zhang ([email protected])
Department of Computer Science and Engineering, USF
Limitations of the Propositional Logic
Suppose we have:
– “Every computer connected to the university network is
functioning properly.”
– “MATH3 is one of the computers connected to the university
network”.
• Does it follow that “MATH3 is functioning properly” ?
• This cannot be expressed in propositional logic.
• We need a language to talk about objects, their
properties and their relations.
2
Limitations of the Propositional Logic
• Statements that must be repeated for many objects
Example:
– If John is a CS USF student then John has passed COT3100.
Translation:
– John is a CS USF student −> John has passed COT3100.
Similar statements can be written for other CS USF students:
– Ann is a CS USF student −> Ann has passed COT3100
– Ken is a CS USF student −> Ken has passed COT3100
–…
• Solution: make statements with variables
– If 𝑥 is a CS USF student then 𝑥 has passed COT3100
– 𝑥 is a CS USF student −> 𝑥 has passed COT3100
3
Limitations of the Propositional Logic
• Statements that define the property of the group of objects
• Example:
– All new cars must be registered.
– Some of the CS graduates graduate with honors.
• Solution: make statements with quantifiers
– Universal quantifier : the property is satisfied by all members of the
group
– Existential quantifier : at least one member of the group satisfy the
property
4
Predicate vs. Propositional Logic
Predicate logic extend propositional logic by the three new
features:
– Variables: 𝑥, 𝑦, 𝑧, ⋯ (subject of the statement)
– Predicates (i.e., propositional functions): 𝑃 𝑥 , 𝑄 𝑥 , 𝑅 𝑦 , 𝑀 𝑥, 𝑦 , ⋯ .
(a property that the subject of the statement can have)
– Quantifiers: ∀, ∃. (make statements about groups of objects)
• The symbolic analysis of predicates and quantified
statements is called the predicate logic.
• The symbolic analysis of ordinary compound statements is
called the statement logic or propositional logic.
5
Discrete Mathematics and Applications
Chapter 3: The Logic of
Quantified Statements
3.1 Predicates and Quantified Statements I
Yan Zhang ([email protected])
Department of Computer Science and Engineering, USF
Predicates
• A predicate is a declarative sentence whose true/false value
depends on one or more variables and becomes a statement
when specific values are substituted for the variables.
• The domain of a predicate variable is the set of all values that may
be substituted in place of the variable.
• A predicate 𝑃(𝑥) assigns a value true or false to each 𝑥 in
domain 𝐷 depending on whether the property holds or not for 𝑥.
• The true set of 𝑃(𝑥), denoted as {𝑥 ∈ 𝐷|𝑃(𝑥)}, is the set of all
elements of 𝐷 that make 𝑃(𝑥) true when they are substituted for 𝑥.
• The statement 𝑃(𝑥) is also said to be the value of the
propositional function 𝑃 at 𝑥.
7
Predicates: Exercise
• Denote the statement “𝑥 is greater than 3” by 𝑃(𝑥),
where 𝑃 is the predicate “is greater than 3” and 𝑥 is the
variable.
• The statement “𝑥 is greater than 3” has two parts:
– The subject: 𝑥 is the subject of the statement
– The predicate: “is greater than 3” (a property that the subject can
have)
8
Predicates: Exercise
Given each propositional function determine its true/false
value when variables are set as below.
•
𝑃(𝑥) = x > 3
𝑃(4) is true.
𝑃 2 is false
• 𝑃𝑟𝑖𝑚𝑒(𝑥) = “𝑥 is a prime number."
Prime(2) is true, since the only numbers that divide 2 are 1 and itself.
Prime(9) is false, since 3 divides 9.
• 𝑄(𝑥, 𝑦) = “𝑥 = 𝑦 + 3.”
𝑄(1,2) is false
𝑄(3,0) is true
9
Predicates vs. Propositions
Assume a predicate 𝑃(𝑥) that represents the statement:
• 𝑥 is a prime number
What are the truth values of:
• 𝑃 2
𝑇
• 𝑃 3
𝑇
• 𝑃 4
𝐹
• 𝑃 5
𝑇
• 𝑃 6
𝐹
• 𝑃 7
𝑇
All statements P(2), P(3), P(4), P(5), P(6), P(7) are propositions
10
Predicates vs. Propositions
Assume a predicate P(x) that represents the statement:
• x is a prime number
What are the truth values of:
• 𝑃 2
𝑇
• 𝑃 3
𝑇
• 𝑃 4
𝐹
• 𝑃 5
𝑇
• 𝑃 6
𝐹
• 𝑃 7
𝑇
Is P(x) is a proposition? No. Many possible substitutions are
possible.
11
Predicates: Exercise
Finding the True Set of a Predicate 𝑄(𝑛): “𝑛 is a factor of 8.”
a. The domain of 𝑛 is the set of 𝑍 + of all positive integers.
b. The domain of 𝑛 is the set of 𝑍 of all integers.
Solution:
a. The truth set is {1, 2, 4, 8} because these are exactly the positive
integers that divide 8 evenly.
b. The truth set is {-8, -4, -2, -1, 1, 2, 4, 8} because these are exactly
the positive integers that divide 8 evenly, without leaving a
remainder.
12
Quantifiers
• Quantification: express the extent to which a predicate is
true over a range of elements. In English, the words all,
some, many, none, and few are used in quantifications.
• The two most important quantifiers are:
– Universal quantifiers (∀): a predicate is true for every element
under consideration
Example: “ all CS USF students have to pass COT3100”
– Existential quantifiers (∃): a predicate is true for one or more
element under consideration
Example: “some of CS USF students graduate with honor.”
13
Universal Statement
Definition
• Let 𝑄(𝑥) be a predicate and 𝐷 the domain of 𝑥.
• A universal statement is a statement of the form “∀𝑥 ∈ 𝐷, 𝑄(𝑥)”, where
∀ is called the Universal Quantifier.
• It is defined to be true if, and only if, 𝑄(𝑥) is true for every 𝑥 in 𝐷.
• It is defined to be false if, and only if, 𝑄(𝑥) is false for at least one 𝑥 in
𝐷, which is called a counterexample to the universal statement.
Let 𝑃(𝑥) be “ 𝑥 2 > 10”. Find the truth value of ∀𝑥 𝑃(𝑥) for the following domains:
 the set of real numbers: ℝ
 False. 3 is a counterexample.
 the set of positive integers not exceeding 4: {1, 2, 3, 4}
 False. 3 is a counterexample.
 the set of real numbers in the interval [10, 39.5]
 True. It takes a bit longer to verify than in false statements. Let 𝑥 ∈ [10, 39.5].
Then 𝑥 ≥ 10 which implies 𝑥 2 ≥ 102 = 100 > 10, and so 𝑥 2 > 10.
14
Example 3 – Truth and Falsity of Universal
Statements
a. Let D = {1, 2, 3, 4, 5}, and consider the statement
Show that this statement is true.
b. Consider the statement
Find a counterexample to show that this statement is
false.
15
Example 3 – Solution
a. Check that “𝑥 2 ≥ 𝑥” is true for each individual x in D.
Hence “∀𝑥 ∈ 𝐷, 𝑥 2 ≥ 𝑥” is true.
• This technique used to show the truth of the universal
statement is called the method of exhaustion.
• It consists of showing the truth of the predicate
separately for each individual element of the domain.
• This method can, in theory, be used whenever the
domain of the predicate variable is finite.
16
Example 3 – Solution
b. Counterexample: Take 𝑥 =
is a real number) and
1
2
. Then 𝑥 is in 𝑹 (since
1
2
Hence “∀𝑥 ∈ 𝑹, 𝑥 2 ≥ 𝑥” is false.
17
Existential Statement
Definition
• Let 𝑄(𝑥) be a predicate and 𝐷 the domain of 𝑥.
• An existential statement is a statement of the form “∃𝑥 ∈
𝐷 such that 𝑄(𝑥)”, where ∃ is called the Existential Quantifier.
• It is defined to be true if, and only if, 𝑄(𝑥) is true for at least one 𝑥 in 𝐷,
which is called a witness to the existential statement..
• It is defined to be false if, and only if, 𝑄(𝑥) is false for all 𝑥 in 𝐷.
Let 𝑃(𝑥) be “ 𝑥 2 > 10”. Find the truth value of ∃𝑥 𝑃(𝑥) for the following domains:
 the set of real numbers: ℝ
 True. 10 is a witness.
 the set of positive integers not exceeding 4: {1, 2, 3, 4}
 True. 4 is a witness.
 the set of real numbers in the interval [0, 9.8]
 False. Let 𝑥 ∈ [0, 9.8]. Then 0 ≤ 𝑥 ≤ 9.8 which implies 𝑥 2 ≤ 9.8 < 10, and
so 𝑥 2 < 10.
18
Example 4 – Truth and Falsity of
Existential Statements
a. Consider the statement
∃𝑚 ∈ 𝑍 + such that 𝑚2 = 𝑚.
Show that this statement is true.
Solution:
• Observe that 12 = 1. Thus “𝑚2 = 𝑚” is true for at least
one integer m. Hence “∃𝑚 ∈ 𝑍 + such that 𝑚2 = 𝑚” is
true.
19
Example 4 – Truth and Falsity of
Existential Statements
b. Let 𝐸 = {5, 6, 7, 8} and consider the statement
∃𝑚 ∈ 𝐸 such that 𝑚2 = 𝑚.
Show that this statement is false.
Solution:
• Note that 𝑚2 = 𝑚 is not true for any integers 𝑚 from 5
through 8:
Thus “∃𝑚 ∈ 𝐸 such that 𝑚2 = 𝑚” is false.
20
Summary of Quantified Statements
• If the domain is empty,
– ∀𝑥 𝑃(𝑥) is true for any propositional function 𝑃(𝑥), since there are
no counterexamples in the domain.
– ∃𝑥 𝑄(𝑥) is false because there can is no element in the domain for
which 𝑄(𝑥) is true.
• When ∀𝑥 𝑃(𝑥) and ∃𝑥 𝑃(𝑥) are true and false?
Statement
When True?
When False?
∀𝑥 𝑃(𝑥)
𝑃(𝑥) is true for every 𝑥
There is an 𝑥 for which 𝑃(𝑥) is false.
∃𝑥 𝑃(𝑥)
There is some 𝑥 for
which 𝑃(𝑥) is true
𝑃(𝑥) is false for every 𝑥
• Suppose the elements in the universe of discourse can be
enumerated as 𝑥1 , 𝑥2 , … , 𝑥𝑁 then:
– ∀𝑥 𝑃(𝑥) is true whenever 𝑃(𝑥1 )⋀𝑃(𝑥2 )⋀ … ⋀𝑃(𝑥𝑁 ) is true
– ∃𝑥 𝑃(𝑥) is true whenever 𝑃(𝑥1 )⋁𝑃(𝑥2 )⋁ … ⋁𝑃(𝑥𝑁 ) is true.
21
Formal Versus Informal Language
It is important to be able to translate from formal to informal
language when trying to make sense of mathematical
concepts that are new to you.
It is equally important to be able to translate from informal to
formal language when thinking out a complicated problem.
22
Example 5 – Translating from Formal to
Informal Language
Rewrite the following formal statements in a variety of equivalent
but more informal ways. Do not use the symbol ∀ or ∃.
a.
Solution:
All real numbers have nonnegative squares.
Or: Every real number has a nonnegative square.
Or: Any real number has a nonnegative square.
Or: The square of each real number is nonnegative.
23
Example 5 – Translating from Formal to
Informal Language
Rewrite the following formal statements in a variety of equivalent
but more informal ways. Do not use the symbol ∀ or ∃.
b.
Solution:
All real numbers have squares that are not equal to −1.
Or: No real numbers have squares equal to −1.
(The words none are or no . . . are are equivalent to the
words all are not.)
24
Example 5 – Translating from Formal to
Informal Language
Rewrite the following formal statements in a variety of equivalent
but more informal ways. Do not use the symbol ∀ or ∃.
c.
Solution:
There is a positive integer whose square is equal to itself.
Or: We can find at least one positive integer equal to its own
square.
Or: Some positive integer equals its own square.
Or: Some positive integers equal their own squares.
25
Universal Conditional Statements
• The universal conditional statement:
∀𝑥, if 𝑃 𝑥 then 𝑄(𝑥)
Example: Writing universal conditional statements formally.
• If a real number is an integer, then it is a rational number.
– ∀𝑥 ∈ 𝑅, if 𝑥 ∈ 𝑍 then 𝑥 ∈ Q
• All bytes have eight bits.
– ∀𝑥 if 𝑥 is a byte then 𝑥 has eight bits.
• No fire trucks are green.
– ∀𝑥 if 𝑥 is a fire truck then 𝑥 is not green.
26
Example 8 – Writing Universal Conditional
Statements Informally
Rewrite the following statement informally, without quantifiers
or variables.
∀𝑥 ∈ 𝑹, if 𝑥 > 2 then 𝑥 2 > 4.
Solution:
If a real number is greater than 2 then its square is greater than 4.
Or: Whenever a real number is greater than 2, its square is greater
than 4.
Or: The square of any real number greater than 2 is greater than 4.
Or: The squares of all real numbers greater than 2 are greater than 4.
27
Equivalent Forms of Universal Statements
• A statement of the form
∀𝑥 ∈ 𝑈, if 𝑃 𝑥 then 𝑄(𝑥)
can always be rewritten in the form
∀𝑥 ∈ 𝐷, 𝑄(𝑥)
by narrowing 𝑈 to be the domain 𝐷 consisting of all
values of the variable 𝑥 that make 𝑃(𝑥) true.
• Conversely, a statement of form
∀𝑥 ∈ 𝐷, 𝑄(𝑥)
can be rewritten as
∀𝑥, if 𝑥 in 𝐷 then 𝑄(𝑥)
28
Example 10 – Equivalent Forms for
Universal Statements
Rewrite the following statement in the two forms “∀x,
if ______ then ______” and “∀ ______x, _______”:
All squares are rectangles.
Solution:
∀x, if x is a square then x is a rectangle.
∀ squares x, x is a rectangle.
29
Equivalent Forms of Existential Statements
Similarly, a statement of the form
“∃𝑥 such that 𝑝(𝑥) and 𝑄(𝑥)”
can be rewritten as
“∃𝑥 ∈ 𝐷 such that 𝑄(𝑥),”
where 𝐷 is the set of all 𝑥 for which 𝑃(𝑥) is true.
30
Example 11 – Equivalent Forms for
Existential Statements
A prime number is an integer greater than 1 whose only
positive integer factors are itself and 1. Consider the statement
“There is an integer that is both prime and even.”
Let 𝑃𝑟𝑖𝑚𝑒(𝑛) be “𝑛 is prime” and 𝐸𝑣𝑒𝑛(𝑛) be “𝑛 is even.” Use
the notation 𝑃𝑟𝑖𝑚𝑒(𝑛) and 𝐸𝑣𝑒𝑛(𝑛) to rewrite this statement in
the following two forms:
a. ∃𝑛 such that ______ ∧ ______ .
b. ∃ ______ 𝑛 such that ______.
Solution:
a. ∃𝑛 such that 𝑃𝑟𝑖𝑚𝑒(𝑛) ∧ 𝐸𝑣𝑒𝑛(𝑛).
b. Two answers: ∃ a prime number 𝑛 such that 𝐸𝑣𝑒𝑛(𝑛).
∃ an even number 𝑛 such that 𝑃𝑟𝑖𝑚𝑒(𝑛).
31
Implicit Quantification
Definition:
• Implicit universal quantification: a statement is equivalent
to a universal statement, but it does not contain the word
all, every, any or each.
• Implicit existential quantification: a statement is
equivalent to an existential statement, but it does not
contain the word a, an or some.
⇒ A double arrow is used to indicate implicit quantification
symbolically.
𝑥>2
⇒
𝑥2 > 4
32
Implicit Quantification
Notation:
Let 𝑃(𝑥) and 𝑄(𝑥) be predicates and suppose the common
domain of 𝑥 is 𝐷.
• The notation 𝑃 𝑥 ⇒ 𝑄(𝑥) means that every element in the
truth set of 𝑃(𝑥) is in the truth set of 𝑄(𝑥), or, equivalently,
∀𝑥, 𝑃(𝑥) → 𝑄(𝑥).
• The notation 𝑃 𝑥 ⟺ 𝑄(𝑥) means that 𝑃(𝑥) and 𝑄(𝑥) have
identical truth sets, or, equivalently, ∀𝑥, 𝑃(𝑥) ↔ 𝑄(𝑥).
33
Example 12 – Using ⇒ and ⇔
Let
𝑄(𝑛) be “𝑛 is a factor of 8,”
𝑅(𝑛) be “n is a factor of 4,”
𝑆(𝑛) be “n < 5 and n  3,”
and suppose the domain of n is 𝒁+ , the set of positive
integers. Use the ⇒ and ⇔ symbols to indicate true
relationships among 𝑄(𝑛), 𝑅(𝑛), and 𝑆(𝑛).
34
Example 12 – Solution
1. when the domain of 𝑛 is 𝒁+ , the truth set of 𝑄(𝑛) is {1, 2,
4, 8}, and the truth set of R(n) is {1, 2, 4}.
Thus it is true that every element in the truth set of 𝑅(𝑛)
is in the truth set of 𝑄(𝑛), or, equivalently,
∀𝑛 in 𝒁+ , 𝑅(𝑛) → 𝑄(𝑛).
Therefore, 𝑅(𝑛) ⇒ 𝑄(𝑛), or, equivalently
𝑛 is a factor of 4 ⇒ 𝑛 is a factor of 8.
35
Example 12 – Solution
2. The truth set of 𝑆(𝑛) is {1, 2, 4}, which is identical to the
truth set of 𝑅(𝑛), or, equivalently,
∀𝑛 in 𝒁+ , 𝑅(𝑛) ↔ 𝑆(𝑛).
So 𝑅(𝑛) ⇔ 𝑆(𝑛), or, equivalently,
𝑛 𝑖𝑠 𝑎 𝑓𝑎𝑐𝑡𝑜𝑟 𝑜𝑓 4 ⇔ 𝑛 < 5 𝑎𝑛𝑑 𝑛  3.
Moreover, since every element in the truth set of 𝑆(𝑛) is
in the truth set of 𝑄(𝑛), or, equivalently,
∀𝑛 in 𝒁+ , 𝑆(𝑛) → 𝑄(𝑛), then 𝑆(𝑛) ⇒ 𝑄(𝑛),
or, equivalently,
𝑛 < 5 and 𝑛  3 ⇒ 𝑛 is a factor of 8.
36
Discrete Mathematics and Applications
Chapter 3: The Logic of
Quantified Statements
3.2 Predicates and Quantified Statements II
Yan Zhang ([email protected])
Department of Computer Science and Engineering, USF
Negation of a Universal Statement
• The negation of a statement of the form
∀𝑥 in 𝐷, 𝑄(𝑥)
Is logically equivalent to a statement of the form
∃𝑥 in 𝐷 such that ~𝑄(𝑥)
Symbolically, ~ ∀𝑥 in 𝐷, 𝑄(𝑥) ≡ ∃𝑥 in 𝐷 such that ~𝑄(𝑥)
• The negation of a universal statement (“all are”) is logically
equivalent to an existential statement (“some are not” or
“there is at least one that is not”).
38
Negation of an Existential Statement
• The negation of a statement of the form
∃𝑥 in 𝐷 such that 𝑄(𝑥)
Is logically equivalent to a statement of the form
∀𝑥 in 𝐷, ~𝑄(𝑥)
Symbolically, ~ ∃𝑥 in 𝐷 such that 𝑄(𝑥) ≡ ∀𝑥 in 𝐷, ~𝑄(𝑥)
• The negation of an existential statement (“some are”) is
logically equivalent to a universal statement (“none are” or
“all are not”).
39
Example 1 – Negating Quantified Statements
Write formal negations for the following statements:
a. ∀ primes p, p is odd.
b. ∃ a triangle T such that the sum of the angles of T
equals 200.
Solution:
a. By applying the rule for the negation of a ∀ statement,
you can see that the answer is
∃a prime p such that p is not odd.
b. By applying the rule for the negation of a ∃ statement,
you can see that the answer is
∀ triangles T, the sum of the angles of T does not equal
200.
40
Negation of Quantified Statements
• The rules for negations for quantifiers are called De
Morgan’s laws for quantifiers
De Morgan’s Laws for Quantifiers
Negation Equivalent Statement
When is Negation True? When False?
~∃𝑥 𝑃(𝑥)
∀𝑥 ~𝑃(𝑥)
𝑃(𝑥) is false for every 𝑥. There is an 𝑥 for which
𝑃(𝑥) is true
~∀𝑥 𝑃(𝑥)
∃𝑥 ~𝑃(𝑥)
There is an 𝑥 for which
𝑃(𝑥) is false.
𝑃(𝑥) is true for every 𝑥.
41
Negations of Universal Conditional
Statements
• Negation of a universal conditional statement
~ ∀𝑥, if 𝑃 𝑥 then 𝑄 𝑥 ≡ ∃𝑥 such that 𝑃 𝑥 and ~𝑄 𝑥
or
~ ∀𝑥, 𝑃 𝑥 → 𝑄 𝑥
≡ ∃𝑥 such that 𝑃 𝑥 ∧ ~𝑄 𝑥
• Proof:
By the definition of the negation of a universal statement:
~ ∀𝑥, 𝑃 𝑥 → 𝑄 𝑥 ≡ ∃𝑥 such that ~ 𝑃 𝑥 → 𝑄 𝑥
Since ~ 𝑃 𝑥 → 𝑄 𝑥
≡ 𝑃 𝑥 ∧ ~𝑄(𝑥)
We have ~ ∀𝑥, 𝑃 𝑥 → 𝑄 𝑥
≡ ∃𝑥 such that 𝑃 𝑥 ∧ ~𝑄 𝑥
42
Example 4 – Negating Universal
Conditional Statements
Write a formal negation for statement (a) and an informal
negation for statement (b).
a. ∀ people 𝑝, if 𝑝 is blond then 𝑝 has blue eyes.
•
∃ a person 𝑝 such that 𝑝 is blond and 𝑝 does not has blue eyes.
b. If a computer program has more than 100,000 lines, then
it contains a bug.
•
There is at least one computer program that has more 100,000
lines and does not contain a bug.
43
The Relation among ∀, ∃,∧, and ∨
• The negation of a for all statement is a there
exists statement.
• The negation of a there exists statement is a for
all statement.
If 𝑄(𝑥) is a predicate and D = {𝑥1 , 𝑥2 , ⋯ , 𝑥𝑛 }, then
• ∀𝑥 in 𝐷, 𝑄 𝑥 ≡ 𝑄 𝑥1 ∧ 𝑄 𝑥2 ∧ ⋯ ∧ 𝑄 𝑥𝑛
• ∃𝑥 in 𝐷 such that 𝑄 𝑥 ≡ 𝑄 𝑥1 ∨ 𝑄 𝑥2 ∨ ⋯ ∨ 𝑄 𝑥𝑛
44
Vacuous Truth of Universal Statements
In general, a statement of the form
is called vacuously true or true by default if, and
only if, P(x) is false for every x in D.
45
Variants of Universal Conditional
Statements
Consider a statement of the form: ∀𝑥 ∈ 𝐷, if 𝑃(𝑥) then 𝑄(𝑥).
• Its contrapositive is the statement:
∀𝑥 ∈ 𝐷, if ~𝑄(𝑥) then ~P(𝑥)
• Its converse is the statement:
∀𝑥 ∈ 𝐷, if 𝑄(𝑥) then P(𝑥)
• Its inverse is the statement:
∀𝑥 ∈ 𝐷, if ~𝑃(𝑥) then ~Q(𝑥)
46
Variants of Universal Conditional
Statements - Exercise
Write a formal and an informal contrapositive, converse, and inverse for the
statement:
If a real number is greater tan 2, then its square is greater than 4.
•
•
Formal version of this statement is ∀𝑥 ∈ 𝑅, if 𝑥 > 2 then 𝑥 2 > 4.
Contrapositive:
– ∀𝑥 ∈ 𝑅, if 𝑥 2 ≤ 4 then 𝑥 ≤ 2.
– If the square of a real number is less or equal to 4, then this real number is less or
equal to 2.
•
Converse:
– ∀𝑥 ∈ 𝑅, if 𝑥 2 > 4 then 𝑥 >2.
– If the square of a real number is greater than 4, then this real number is greater than 2.
•
Inverse:
– ∀𝑥 ∈ 𝑅, if 𝑥 ≤ 2 then 𝑥 2 ≤ 4.
– If a real number is less than or equal to 2, then the square of the number is
less than or equal to 4.
47
Variants of Universal Conditional Statements
A universal conditional statement is logically equivalent to its
contrapositive:
∀𝑥 ∈ 𝐷, if 𝑃(𝑥) then 𝑄 𝑥 ≡ ∀𝑥 ∈ 𝐷, if ~𝑄(𝑥) then ~P(𝑥)
• Any particular x in D that makes “if P(x) then Q(x)” true also makes “if
~Q(x) then ~P(x)” true (by the logical equivalence between p  q and
~q  ~p).
• It follows that the sentence “If P(x) then Q(x)” is true for all x in D if, and
only if, the sentence “If ~Q(x) then ~P(x)” is true for all x in D.
A universal conditional statement is not logically equivalent to
its converse.
∀𝑥 ∈ 𝐷, if 𝑃(𝑥) then 𝑄 𝑥 ≢ ∀𝑥 ∈ 𝐷, if 𝑄(𝑥) then P(𝑥)
A universal conditional statement is not logically equivalent to
its inverse.
∀𝑥 ∈ 𝐷, if 𝑃(𝑥) then 𝑄 𝑥 ≢ ∀𝑥 ∈ 𝐷, if ~𝑃(𝑥) then ~Q(𝑥)
48
Necessary and Sufficient Conditions, Only If
The definitions of necessary, sufficient, and only if can also
be extended to apply to universal conditional statements.
49
Example 6 – Necessary & Sufficient Conditions
Rewrite the following statements as quantified conditional
statements. Do not use the word necessary or sufficient.
a. Squareness is a sufficient condition for rectangularity.
Solution:
A formal version of the statement is
∀x, if x is a square, then x is a rectangle.
Or, in informal language:
If a figure is a square, then it is a rectangle.
50
Example 6 – Necessary & Sufficient Conditions
Rewrite the following statements as quantified conditional
statements. Do not use the word necessary or sufficient.
b. Being at least 35 years old is a necessary condition for
being President of the United States.
Solution:
A formal version of the statement is
∀ people x, if x is younger than 35, then x cannot be
President of the United States.
Or, by the equivalence between a statement and its
contrapositive:
∀ people x, if x is President of the United States, then x
is at least 35 years old.
51
Discrete Mathematics and Applications
Chapter 3: The Logic of
Quantified Statements
3.3 Statements with Multiple Quantifiers
or Nested Quantifiers
Yan Zhang ([email protected])
Department of Computer Science and Engineering, USF
Nested Quantifiers
• Two quantifiers are nested if one is in the scope of the other.
• Everything within the scope of a quantifier can be thought of
as a propositional function.
Example
• “∀𝑥 ∃𝑦 (𝑥 + 𝑦 = 0)” is the same as “∀𝑥 𝑄(𝑥)”, where 𝑄(𝑥) is
“∃𝑦 (𝑥 + 𝑦 = 0)”.
 for every real number 𝑥 there is a real number 𝑦 such that 𝑥 + 𝑦 = 0.
 This states that every real number has an additive inverse.
53
Summary of Quantification of Two Variables
Statement
When True?
When False?
∀𝑥∀𝑦 𝑃(𝑥, 𝑦)
∀𝑦∀𝑥 𝑃 𝑥, 𝑦
𝑃(𝑥, 𝑦) is true for every pair
𝑥, 𝑦.
There is a pair 𝑥, 𝑦 for
which 𝑃(𝑥, 𝑦) is false.
∀𝑥∃𝑦 𝑃(𝑥, 𝑦)
For every 𝑥 there is a 𝑦 for
which 𝑃(𝑥, 𝑦) is true.
There is an 𝑥 such that
𝑃(𝑥, 𝑦) is false for every 𝑦.
∃𝑥∀𝑦 𝑃(𝑥, 𝑦)
There is an 𝑥 for which
𝑃(𝑥, 𝑦) is true for every 𝑦.
For every 𝑥 there is a 𝑦 for
which 𝑃(𝑥, 𝑦) is false.
∃𝑥∃𝑦 𝑃(𝑥, 𝑦)
∃𝑦∃𝑥 𝑃 𝑥, 𝑦
There is a pair 𝑥, 𝑦 for which
𝑃(𝑥, 𝑦) is true.
𝑃(𝑥, 𝑦) is false for every
pair x, 𝑦.
54
Translating Math Statements into Nested
Quantifiers
Translate the following statements:
1. “The sum of two positive integers is always positive.”
•
“For every two integers, if these integers are both positive, then the
sum of these integers is positive”
∀𝑥∀𝑦 𝑥 > 0 ⋀ 𝑦 > 0 → 𝑥 + 𝑦 > 0 , where 𝑥 ∈ ℝ, 𝑦 ∈ ℝ
•
“For every two positive integers, the sum of these integers is positive”
∀𝑥∀𝑦 𝑥 + 𝑦 > 0 , where 𝑥 ∈ ℝ+ , 𝑦 ∈ ℝ+
2. “Every real number except zero has a multiplicative inverse.” (a
multiplicative inverse of 𝑥 is 𝑦 such that 𝑥𝑦 = 1).
•
•
“For every real number 𝑥 except zero, 𝑥 has a multiplicative inverse”
“for every real number 𝑥, if 𝑥 ≠ 0, then there exists a real number 𝑦
such that 𝑥𝑦 = 1”
∀𝑥 𝑥 ≠ 0 → ∃𝑦 𝑥𝑦 = 1
55
Negations of Nested Quantifiers
• Negations of Nested Quantifiers
~ ∀𝑥 in 𝐷, ∃𝑦 in 𝐸 such that 𝑃 𝑥, 𝑦 ≡
∃𝑥 in 𝐷 such that ∀𝑦 in 𝐸, ~𝑃 𝑥, 𝑦
~ ∃𝑥 in 𝐷 such that ∀𝑦 in 𝐸, 𝑃 𝑥, 𝑦 ≡
∀𝑥 in 𝐷, ∃𝑦 in 𝐸 such that ~𝑃 𝑥, 𝑦
Proof:
• Recall De Morgan’s Laws for Quantifiers:
– ~ ∀𝑥 in 𝐷, 𝑃(𝑥) ≡ ∃𝑥 in 𝐷 such that ~𝑃 𝑥
– ~ ∃𝑥 in 𝐷 such that 𝑄(𝑥) ≡ ∀𝑥 in 𝐷, ~𝑄(𝑥)
~ ∀𝑥 in 𝐷, ∃𝑦 in 𝐸 such that 𝑃 𝑥, 𝑦
≡ ∀𝑥 in 𝐷 such that ~ ∃𝑦 in 𝐸 such that 𝑃 𝑥, 𝑦
≡ ∀𝑥 in 𝐷 such that ∀𝑦 in 𝐸, ~𝑃 𝑥, 𝑦
56
Negating Nested Quantifiers - Exercise
• Express the negation of the statement ∀𝑥∃𝑦(𝑥𝑦 = 1) so
that no negation precedes a quantifier.
 The negation of ∀𝑥∃𝑦(𝑥𝑦 = 1) is ~∀𝑥∃𝑦 𝑥𝑦 = 1
 Now use De Morgan’s Laws to move the negation as far inwards
as possible.
~∀𝑥∃𝑦 𝑥𝑦 = 1 ≡ ∃𝑥~∃𝑦(𝑥𝑦 = 1)
by De Morgan’s for ∀
≡ ∃𝑥∀𝑦~ 𝑥𝑦 = 1
by De Morgan’s for ∃
≡ ∃𝑥∀𝑦 𝑥𝑦 ≠ 1
57
Negating Nested Quantifiers - Exercise
• Use quantifiers to express the statement that “There
does not exist a woman who has taken a flight on every
airline in the world.”
 Formulate: ~∃𝑤∀𝑎∃𝑓 𝑃 𝑤, 𝑓 ⋀ 𝑄(𝑓, 𝑎)
 Now use De Morgan’s Laws to move the negation as far inwards
as possible.
~∃𝑤∀𝑎∃𝑓 𝑃 𝑤, 𝑓 ⋀𝑄(𝑓, 𝑎)
≡ ∀𝑤~∀𝑎∃𝑓 𝑃 𝑤, 𝑓 ⋀𝑄(𝑓, 𝑎)
by De Morgan’s for ∃
≡ ∀𝑤∃𝑎~∃𝑓 𝑃 𝑤, 𝑓 ⋀𝑄(𝑓, 𝑎)
by De Morgan’s for ∀
≡ ∀𝑤∃𝑎∀𝑓~ 𝑃 𝑤, 𝑓 ⋀𝑄(𝑓, 𝑎)
by De Morgan’s for ∃
≡ ∀𝑤∃𝑎∀𝑓 ~𝑃 𝑤, 𝑓 ∨ ~𝑄(𝑓, 𝑎)
by De Morgan’s for ⋀
• “For every woman there is an airline such that for all flights, this
woman has not taken that flight or that flight is not operated by this
airline.”
58
The Order of Quantifiers
Let 𝑃(𝑥, 𝑦) be the statement “𝑥 + 𝑦 = 𝑦 + 𝑥".
Consider ∀𝑥∀𝑦 𝑃(𝑥, 𝑦) and ∀𝑦∀𝑥 𝑃 𝑥, 𝑦 :
• What is the meaning of each of these statements?
 ∀𝑥∀𝑦 𝑃(𝑥, 𝑦): “For all real numbers 𝑥, for all real numbers 𝑦, 𝑥 +
𝑦 = 𝑦 + 𝑥.”
 ∀𝑦∀𝑥 𝑃(𝑥, 𝑦): “For all real numbers 𝑦, for all real numbers 𝑥, 𝑥 +
𝑦 = 𝑦 + 𝑥.”
• What is the truth value of each of these statements?
 Based on the commutative law for addition, both are true.
• Are they equivalent?
 They have the same meaning and they are equivalent.
• Principle: the order of nested universal quantifiers in a statement
without other quantifiers can be changed without changing the
meaning of the quantified statement.
59
The Order of Quantifiers
Let 𝑄(𝑥, 𝑦) be the statement “𝑥 + 𝑦 = 0”
Consider ∃𝑦∀𝑥𝑄(𝑥, 𝑦) and ∀𝑥∃𝑦𝑄(𝑥, 𝑦):
• What is the meaning of each of these statements?
 ∃𝑦∀𝑥𝑄(𝑥, 𝑦): “There is a real number 𝑦 such that for every real number
𝑥, 𝑄(𝑥, 𝑦)”
 ∀𝑥∃𝑦𝑄(𝑥, 𝑦): “For every real number 𝑥, there is a real number 𝑦 such
that 𝑄(𝑥, 𝑦)”
• What is the truth value of each of these statements?
 No matter what value of 𝑦 is chosen, there is only one value of 𝑥 for which 𝑥 +
𝑦 = 0. Because there is no real number 𝑦 such that 𝑥 + 𝑦 = 0 for all real
numbers 𝑥, the statement ∀𝑥∃𝑦𝑄(𝑥, 𝑦) is false.
 Given a real number 𝑥, there is a real number 𝑦 such that 𝑥 + 𝑦 = 0;
namely, 𝑦 = −𝑥. Hence, the statement ∀𝑥∃𝑦𝑄(𝑥, 𝑦) is true.
• Are they equivalent?
 No
• In a statement containing both ∀ and ∃, changing the order of the
quantifiers usually changes the meaning of the statement.
60
Formal Logical Notation
• The formal logic notation involves using predicates to
describe all properties of variables and omitting the
words such that in existential statements.
• The formalism also depends on the following facts:
“∀𝑥 in 𝐷, 𝑃(𝑥)” can be written as “∀𝑥 𝑥 in 𝐷 → 𝑃(𝑥) ”
“∃𝑥 in 𝐷 such that 𝑃(𝑥)” can be written as “∃𝑥 𝑥 in 𝐷 ∧ 𝑃(𝑥) ”
61
Thank You !!
62