UFUG 2106 : Discrete

Mathematics
Chapter 03: The Logic of Quantified Statements

Recommended readings: Pages 108-118; 122-129; 131-

141; 146-156
ACK: Part of the PPTs are built from the PPT slides from Instructor’s
Companion Website of the textbook.
Outline
1. Predicates and Quantified Statements I
2. Predicates and Quantified Statements II
3. Statements with Multiple Quantifiers
4. Arguments with Quantified Statements

2
Learning Outcomes
● Foundational Concepts
o Identify the basic components of predicate logic: predicates, quantifiers, and domains
● Translation and Symbolization
o Translate natural language statements into predicate logic notation and vice versa,
accurately applying quantifiers, predicates, and logical connectives.
● Quantifiers
o Determine the scope of quantifiers and differentiate between free and bound variables.
o Apply negation to quantified statements using De Morgan’s laws for quantifiers
o Analyze statements with nested quantifiers
● Arguments with Quantified Statements
o Determine whether a predicate logic formula is valid (true in all interpretations) or
satisfiable (true in at least one interpretation)
o Apply key equivalences and inference rules to manipulate and simplify formulas
o Construct formal proofs involving quantified statements using direct methods, contrapositive,
or contradiction

3
Motivation
● In Chapter 2 we learned propositional logic that studies
statements with {~, ∧, ∨, → , ⟷ }.
o We can use propositional logic to make deductive reasoning and solve some
puzzles!
● But consider the following logic problems:
o All students in UFUG 2106 passed the exam.
o Jack is a student of UFUG 2106.
o Did Jack pass the exam?

● Propositional logic cannot be easily applied to the above problems.

Predicates

Example 3.1.1 - Finding Truth Values of a Predicate

5
Truth Set of a Predicate

Example 3.1.2 – Finding the Truth Set of a Predicate

6
Quantifiers
● One sure way to change predicates into statements is to assign
specific values to all their variables.
● For example, if x represents the number 35, the sentence “x is
(evenly) divisible by 5” is a true statement since 35 = 5 ·7.
o Another way to obtain statements from predicates is to add quantifiers.
● Quantifiers are words that refer to quantities such as “some” or
“all” and tell for how many elements a given predicate is true.
The Universal Quantifier: ∀
● The symbol ∀ is called the universal quantifier. Depending on the
context, it is read as “for every,” “for each,” “for any,” “given any,” or
“for all.”
● For example, another way to express the sentence “Every human
being is mortal” or “All human beings are mortal” is to write
o ∀ human being x, x is mortal,
● which you would read as “For every human being x, x is mortal.”
The Universal Quantifier: ∀
● If you let H be the set of all human beings, then you can symbolize
the statement more formally by writing
∀x ∈ H, x is mortal.
Example 3.1.3 – Truth and Falsity of Universal Statements

● Let D = {1, 2, 3, 4, 5}, and consider the statement

o Write one way to read this statement out loud, and show that it is true.

● Consider the statement

o Find a counterexample to show that this statement is false.

The Existential Quantifier: ∃
The symbol ∃ denotes “there exists” and is called the existential
quantifier.
For example, the sentence “There is a student in Math 140” can be
written as
∃ a person p such that p is a student in Math 140,
or, more formally,
∃ p ∈ P such that p is a student in Math 140,
where P is the set of all people.
The Existential Quantifier: ∃
● The domain of the predicate variable is generally indicated either
between the ∃ symbol and the variable name or immediately
following the variable name, and the words such that are inserted
just before the predicate.
Example 3.1.4 – Truth and Falsity of Existential Statements

a. Consider the statement

Write one way to read this statement out loud, and show that it is true.

b. Let E = {5, 6, 7, 8} and consider the statement

Show that this statement is false.

Formal vs. 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.
Example 3.1.7 – Translating from Informal to Formal Language

Rewrite each of the following statements formally. Use quantifiers and

variables.

a. All triangles have three sides.

b. No dogs have wings.

c. Some programs are structured.

Universal Conditional Statements
● An important form of statement in mathematics is the universal
conditional statement:
∀x, if P(x) then Q(x).
Example 3.1.9 – Writing Universal Conditional Statements Formally

Rewrite each of the following statements in the form

a. If a real number is an integer, then it is a rational number.

b. All bytes have eight bits.

c. No fire trucks are green.

Equivalent Forms of Universal and Existential Statements

Observe that the two statements “∀ real number x, if x is an integer

then x is rational” and “∀ integer x, x is rational” mean the same thing
because the set of integers is a subset of the set of real numbers.

Both have informal translations “All integers are rational.” In fact, a

statement of the form ∀𝑥 ∈ 𝑈, if 𝑃(𝑥) then 𝑄(𝑥)

can always be rewritten in the form ∀𝑥 ∈ 𝐷, 𝑄(𝑥)

by narrowing 𝑈 to be the subset 𝐷 consisting of all values of the

variable 𝑥 that make 𝑃(𝑥) true.
Equivalent Forms of Universal and Existential Statements

Conversely, a statement of the form

∀𝑥 ∈ 𝐷, 𝑄(𝑥)
can be rewritten as
∀𝑥, if 𝑥 is in 𝐷 then 𝑄(𝑥).

Example 3.1.10 – Equivalent Forms for Universal Statements

Rewrite the following statement in the two forms

All squares are rectangles.

Example 3.1.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 Prime(n) be “n is prime” and Even(n) be “n is even.” Use the
notation Prime(n) and Even(n) to rewrite this statement in the
following two forms:
Bound Variables and Scope
● Consider the following statements:
o For every integer 𝑥, 𝑥 2 ≥ 0
o There exists a real number 𝑥 such that 𝑥 3 = 8
● Statements (1) and (2) both call the variable x, but the x in Statement (1)
serves a different function from the x in Statement (2).

● We say that the variable x is bound by the quantifier that controls it and
that its scope begins when the quantifier introduces it and ends at the
end of the quantified statement.
Implicit Quantification
Consider the statement

If a number is an integer, then it is a rational number.

As shown earlier, this statement is equivalent to a universal statement.

However, it does not contain the telltale word all or every or any or
each.

The only clue to indicate its universal quantification comes from the
presence of the indefinite article a. This is an example of implicit
universal quantification.
Implicit Quantification
Existential quantification can also be implicit. For instance,
the number 24 can be written as a sum of two even integers
can be expressed formally as
∃ even integers 𝑚 and 𝑛 such that 24 = 𝑚 + 𝑛
Example 3.1.12 – Using ⇒ and ⇔
Let
𝑄(𝑛) be “n 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 𝑆(𝑛). (Mentimeter)
Outline
1. Predicates and Quantified Statements I
2. Predicates and Quantified Statements II
3. Statements with Multiple Quantifiers
4. Arguments with Quantified Statements

25
Negations of Quantified Statements
● The general form of the negation of a universal statement follows
immediately from the definitions of negation and of the truth values
for universal and existential statements.
Negations of Quantified Statements
Thus
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”).
Note that when we speak of logical equivalence for quantified statements,
we mean that the statements always have identical truth values no matter what
predicates are substituted for the predicate symbols and no matter what sets are
used for the domains of the predicate variables.
 Negations of Quantified Statements

Thus
The negation of an existential statement (“some are”) is
logically equivalent to a universal statement (“none are”
or “all are not”).
Example 3.2.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°
.
Example 3.2.2 – More Negations
Rewrite the following statements formally. Then write formal and
informal negations.
a. No politicians are honest.

b. The number 1,357 is not divisible by any integer between 1 and 37.
Negations of Universal Conditional Statements
● By definition of the negation of universal statements,
Example 3.2.4 – Negating Universal Conditional Statements

Write a formal negation for statement (a) and an informal negation for
statement (b).

a. ∀ person p, if p is blond then p has blue eyes.

b. If a computer program has more than 100,000 lines, then it

contains a bug.
The Relation among ∀, ∃, ∧, and ∨
● The negation of a for all statement is a there exists statement, and
the negation of a there exists statement is a for all statement.
● These facts are analogous to De Morgan’s laws, which state that the
negation of an and statement is an or statement and that the negation
of an or statement is an and statement. This similarity is not
accidental.
● In a sense, universal statements are generalizations of and
statements, and existential statements are generalizations of or
statements.
The Relation among ∀, ∃, ∧, and ∨
If 𝑄(𝑥) is a predicate and the domain D of x is the set {𝑥1 , 𝑥2 , … , 𝑥𝑛 },
then the statements

are logically equivalent.

Similarly, if 𝑄(𝑥) is a predicate and 𝐷 = {𝑥1 , 𝑥2 , … , 𝑥𝑛 } then the
statements

are logically equivalent.

Vacuous Truth of Universal Statements
Suppose a bowl sits on a table and next to the bowl is a pile of five
blue and five gray balls, any of which may be placed in the bowl. If
three blue balls and one gray ball are placed in the bowl, as shown in
the figure, the statement “All the balls in the bowl are blue” would be
false (since one of the balls in the bowl is gray).
Vacuous Truth of Universal Statements
Now suppose that no balls at all are placed in the bowl, as shown in
the figure.
Vacuous Truth of Universal Statements
Consider the statement
All the balls in the bowl are blue.
Is this statement true or false? The statement is false if, and only if, its
negation is true. And its negation is
There exists a ball in the bowl that is not blue.
But the only way this negation can be true is for there actually to be a
nonblue ball in the bowl. And there is not! Hence the negation is false,
and so the statement is true “by default.”
Vacuous Truth of Universal Statements
In general, a statement of the form

∀𝑥 in 𝐷, if 𝑃(𝑥) then 𝑄(𝑥)

is called vacuously true or true by default if, and only if, 𝑃(𝑥) is
false for every 𝑥 in 𝐷.
Variants of Universal Conditional Statements
● A conditional statement has a contrapositive, a converse, and an
inverse. The definitions of these terms can be extended to universal
conditional statements.
Example 3.2.5 – Contrapositive, Converse, and Inverse of a Universal
Conditional Statement

Write a formal and an informal contrapositive, converse, and inverse

for the following statement:
If a real number is greater than 2, then its square is greater than 4.
Necessary and Sufficient Conditions, Only If
● The definitions of necessary, sufficient, and only if can also be
extended to apply to universal conditional statements.
Example 3.2.6 – Necessary and Sufficient Conditions

Rewrite each of the following as a universal conditional statement,

quantified either explicitly or implicitly. Do not use the word necessary
or sufficient.

a. Squareness is a sufficient condition for rectangularity.

b. Being at least 35 years old is a necessary condition for being

president of the United States.
Outline
1. Predicates and Quantified Statements I
2. Predicates and Quantified Statements II
3. Statements with Multiple Quantifiers
4. Arguments with Quantified Statements

43
Statements with Multiple Quantifiers
When a statement contains more than one kind of quantifier, we
imagine the actions suggested by the quantifiers as being performed in
the order in which the quantifiers occur.

For instance, consider a statement of the form

∀𝑥 in set 𝐷, ∃𝑦 in set 𝐸 such that 𝑥 and 𝑦 satisfy property 𝑃(𝑥, 𝑦)
Example 3.3.1 – Truth of a ∀∃ Statement in a Tarski
World
●Consider the Tarski world shown in Figure 3.3.1. (Mentimeter)

For every triangle x, there is a square y such that x

and y have the same color.

•Figure 3.3.1
Example 3.3.2 – Truth of a ∃∀ Statement in a Tarski World

Consider the Tarski world shown in Figure 3.3.1. (Mentimeter)

There is a triangle x such that for every circle y,

x is to the right of y.

•Figure 3.3.1
Statements with Multiple Quantifiers
Example 3.3.3 – Interpreting Statements with More Than One
Quantifier
A college cafeteria line has four stations: salads, main courses,
desserts, and beverages.
o The salad station offers a choice of green salad or fruit salad;
o the main course station offers spaghetti or fish;
o the dessert station offers pie or cake;
o and the beverage station offers milk, soda, or coffee.
Three students, Uta, Tim, and Yuen, go through the line and make the
following choices:

Uta: green salad, spaghetti, pie, milk

Tim: fruit salad, fish, pie, cake, milk, coffee
Yuen: spaghetti, fish, pie, soda
Example 3.3.3 – Interpreting Statements with More Than One
continued
Quantifier
These choices are illustrated in the figure.
Example 3.3.3 – Interpreting Statements with More Than One
continued
Quantifier
Write each of following statements informally and find its truth value.

a. ∃ an item I such that ∀ student S, S chose I.

b. ∃ a student S such that ∀ item I, S chose I.
c. ∃ a student S such that ∀ station Z, ∃ an item I in Z such that S
chose I.
d. ∀ student S and ∀ station Z, ∃ an item I in Z such that S chose I.

(Mentimeter)
Translating from Informal to Formal Language
Most problems are stated in informal language, but solving them
often requires translating them into more formal terms.

Example 3.3.4 – Translating Statements with Multiple Quantifiers from

Informal to Formal Language
The reciprocal of a real number a is a real number b such that ab = 1. The
following two statements are true. Rewrite them formally using quantifiers and
variables.
a. Every nonzero real number has a reciprocal.
b. There is a real number with no reciprocal.
Example 3.3.7 – The Definition of Limit of a Sequence

We say that the limit of the sequence an as n goes to infinity equals L

and write if, and only if, the values of an become arbitrarily
close to L as n gets larger and larger without bound.
More precisely, this means that given any positive number ε, we can
find an integer N such that whenever n is larger than N, the number an
sits between L − ε and L + ε on the number line.

●Symbolically:
o∀ε > 0, ∃ an integer N such that ∀ integer n,
oif n > N then L − ε < an < L + ε.
Negations of Statements with More Than One
Quantifier
You can use the same rules to negate statements with several
quantifiers that you used to negate simpler quantified statements. We
know that
and
Thus
Negations of Statements with More Than One
Quantifier
These facts are summarized as follows:
Example 3.3.8 – Negating Statements in a Tarski continued
World
Write a negation for each of the following statements, and determine
which is true, the given statement or its negation.

a. For every square x, there is a circle y

such that x and y have the same color.

b. There is a triangle x such that for

every square y, x is to the right of y.
Order of Quantifiers
Consider the following two statements:

∀ person x, ∃ a person y such that x loves y.

∃ a person y such that ∀ person x, x loves y.

Note that except for the order of the quantifiers, these statements are
identical.

However, the first means that given any person, it is possible to find
someone whom that person loves, whereas the second means that
there is one amazing individual who is loved by all people.
Order of Quantifiers
The two sentences illustrate an extremely important property about
statements with two different quantifiers.

Interestingly, however, if one quantifier immediately follows another

quantifier of the same type, then the order of the quantifiers does not
affect the meaning.
Order of Quantifiers
Consider the commutative property of addition of real numbers, for
example:

∀ real number 𝑥 and ∀ real number 𝑦, 𝑥 + 𝑦 = 𝑦 + 𝑥.

This means the same as

∀ real number 𝑦 and ∀ real number 𝑥, 𝑥 + 𝑦 = 𝑦 + 𝑥.

Thus the property can be expressed a little less formally as

∀ real numbers 𝑥 and 𝑦, 𝑥 + 𝑦 = 𝑦 + 𝑥.

Formal Logical Notation
In some areas of computer science, logical statements are expressed
in purely symbolic notation.

The 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:
“∀x in D, P(x)” can be written as “∀x (x in D → P(x)),”
and
“∃x in D such that P(x)” can be written as “∃x (x in D ∧ P(x)).”
Formal Logical Notation
The disadvantage of the fully formal notation is that because it is
complex and somewhat remote from intuitive understanding, when we
use it, we may make errors that go unrecognized.

The advantage, however, is that operations, such as taking negations,

can be made completely mechanical and programmed on a computer.

Taken together, the symbols for quantifiers, variables, predicates, and

logical connectives make up what is known as the language of first-
order logic.
Summary of Two Quantifiers
Outline
1. Predicates and Quantified Statements I
2. Predicates and Quantified Statements II
3. Statements with Multiple Quantifiers
4. Arguments with Quantified Statements

62
Arguments with Quantified Statements
The rule of universal instantiation says the following:

Use of the words universal instantiation indicates that the truth of a

property in a particular case follows as a special instance of its more
general or universal truth.
Arguments with Quantified Statements
The validity of this argument form follows immediately from the
definition of truth values for a universal statement. One of the most
famous examples of universal instantiation is the following:

All men are mortal.

Socrates is a man.
∴ Socrates is mortal.
 Arguments with Quantified Statements
Example: Simplify
𝑟 𝑘+1 ⋅ 𝑟
where 𝑟 is a particular real number and 𝑘 is a particular integer.

You know the following universal statements are true:

1. For every real number 𝑥 and for all integers 𝑚 and 𝑛, 𝑥 𝑚 ⋅ 𝑥 𝑛 = 𝑥 𝑚+𝑛
2. For every real number 𝑥, 𝑥 1 = 𝑥
Arguments with Quantified Statements
So you proceed as follows:
Step 1

Step 2

by basic algebra.

Here is the reasoning behind steps 1 and 2.

Step 1: For every real number x, 𝑥 1 = 𝑥 universal truth
r is a particular real number. particular instance

conclusion
Arguments with Quantified Statements
Step 2: For every real number 𝑥 and for all integers 𝑚 universal truth
and 𝑛, 𝑥 𝑚 ⋅ 𝑥 𝑛 = 𝑥 𝑚+𝑛
𝑟 is a particular real number and 𝑘 + 1 and 1 are particular instance
particular integers.
conclusion

Both arguments are examples of universal instantiation.

Universal Modus Ponens
The rule of universal instantiation can be combined with modus
ponens to obtain the valid form of argument called universal modus
ponens.
Example 3.4.2 – Drawing Conclusions Using Universal Modus Ponens

Write the conclusion that can be inferred using universal modus

ponens.
If T is any right triangle with
hypotenuse 𝑐 and legs 𝑎 and
𝑏, then
The triangle shown at the right
is a right triangle with both
legs equal to 1 and hypotenuse
c.
∴
Use of Universal Modus Ponens in a Proof

Here is a proof that the sum of any two even integers is even.
It makes use of the definition of even integer: an integer is even if,
and only if, it equals twice some integer (or, more formally: ∀ integer
𝑥, 𝑥 is even if, and only if, ∃ an integer 𝑘 such that 𝑥 = 2𝑘.)
Universal Modus Tollens
Another crucially important rule of inference is universal modus tollens.
Its validity results from combining universal instantiation with modus
tollens. Universal modus tollens is the heart of proof of contradiction,
which is one of the most important methods of mathematical
argument.
Example 3.4.3 – Recognizing the Form of Universal Modus
Tollens
Rewrite the following argument using quantifiers, variables, and
predicate symbols. Write the major premise in conditional form. Is this
argument valid? Why?

All human beings are mortal.

Zeus is not mortal.
∴ Zeus is not human.
Converse Error and Inverse Error
Creating Additional Forms of Argument
Universal modus ponens and modus tollens were obtained by
combining universal instantiation with modus ponens and modus
tollens. In the same way, additional forms of arguments involving
universally quantified statements can be obtained by combining
universal instantiation with other of the valid argument forms.
Rules of Inference for Quantified Statements
Example of Argument with Predicates
Example of Argument with Predicates
Example of Argument with Predicates
Example of Argument with Predicates