Quantified Statements

Quantified Statements
• Quantified statements are statements containing the words

“all” or “some” that denotes quantities.
• The validity of quantified statements cannot be ascertain
using rules of inference.
• The statement is split into two, the subject and the
predicate.
• “The symbolic analysis of predicates and quantified
statements is called the predicate calculus.
• In grammar, predicates is part of the sentence that
describes the subject.
• In logic, “predicate is a sentence that contains a finite
number of variables and becomes a statement when
specific values are substituted for the variables.”
o The predicate must include the set of values that can be used
to replace the variables called the domain.
o Note that without the domain the truth of the predicate
cannot be ascertain.
• “If P(x) is a predicate and x has domain D, the truth set of
P(x) is the set of all elements of D that make P(x) true when
they are substituted for x. The truth set of P(x) is denoted
{x ∈ D | P(x)}.”
• Example 1: Let Q(n) be the predicate “n is a factor of 8.”
Find the truth set of Q(n) if
a. the domain of n is the set Z+ of all positive integers
b. the domain of n is the set Z of all integers
Solution:
a. The truth set is {1, 2, 4, 8}
b. The truth set is (1, 2, 4, 8, -1, -2, -4, - 8)
Universal Quantification
• Quantifiers refer to the scope in the domain that the given
predicate is true.
• Universal quantifier uses the words “some” or “all”
• The symbol ∀ to denote universal quantification.
• The sentence “All fish have scales.” can be written as
∀ fish x, x has scales.
o When describing the properties that the variable x satisfies, use
the singular verb.
• Given a universal statement is a statement of the form “∀x ∈
D, Q(x).”
o The predicate Q(x) is true if in each element in D, Q(x) is true.
o If there is at least one element in D that makes Q(x) false, then
the Q(x) is false.
o The element that makes Q(x) is false is called a
counterexample.
• Example 2: Let M = {-2, -1, 0, 1, 2, 3}, and the statement ∀𝑥 ∈
𝑀, 𝑥 2 ≥ 𝑥. Show that this statement is true.
SOLUTION: Substituting each element in M into x, we got
(-2)2 ≥ -2, (-1)2 ≥ -1, (0)2 ≥ 0, (1)2 ≥ 1, (2)2 ≥ 2, (3)2 ≥ 3
each of these statements is true, therefore, ∀𝑥 ∈ 𝑀, 𝑥 2 ≥ 𝑥 is
true.
• Example 2: given the statement ∀𝑥 ∈ ℝ, 𝑥 2 ≥ 𝑥 , find a
counterexample.
SOLUTION: for this problem we will have x = 0.5
(0.5)2 ≥ 0.5, 0.25 ≥ 0.5 – this is false
Existential Quantifier
• An existential statement is a quantified statement using the
for ∃𝑥 ∈ 𝐷 𝑠𝑢𝑐ℎ 𝑡ℎ𝑎𝑡 𝑄 𝑥 .
o This can be read as, there exist x which is an element of D such
that Q(x).
o It is true if there is at least one element in D that makes Q(x)
true.
o It is false if none of the elements in D will make Q(x) true.
• Example 3: Given the statement ∃𝑥 ∈ ℝ, 𝑥 2 ≥ 𝑥. Show that this
statement is true.
SOLUTION: take x = 2, 22 ≥ 2, 4 ≥ 2 – this is true, therefore,
the statement ∃𝑥 ∈ ℝ, 𝑥 2 ≥ 𝑥 is true.
• Example 4: let M = {0.2, 0.3, 0.9}, and ∃𝑥 ∈ 𝑀, 𝑥 2 ≥ 𝑥. Show
that the statement is true.
SOLUTION: replace each element of M into x
0.22 ≥ 0.2, 0.32 ≥ 0.3, 0.92 ≥ 0.9
0.04 ≥ 0.2 0.09 ≥ 0.3 0.81 ≥ 0.9
None of the elements in M makes the statement true, so, the
statement ∃𝑥 ∈ 𝑀, 𝑥 2 ≥ 𝑥 is false.
• Implicit Quantification
o A statement that contains the indefinite article “a” or “an” is a
statement with implied universal quantification.
• “if a number is an integer, then it is a rational number.” in
this statement, the phrase, “a number is an integer…” implies
that the quantification is universal – all integers.
• Negations of Quantified Statements
o Universal Quantification:
~(∀𝑥 ∈ ℤ, 𝑅(𝑥)) ≡ ∃𝑥 ∈ ℤ 𝑠𝑢𝑐ℎ 𝑡ℎ𝑎𝑡 ~𝑅(𝑥)
o Existential Quantification:
∃𝑥 ∈ ℤ 𝑠𝑢𝑐ℎ 𝑡ℎ𝑎𝑡 𝑅 𝑥 ≡ ∀𝑥 ∈ ℤ, ~𝑅(𝑥)
• Negations of Universal Conditional Statements
∼(∀x, P(x) → Q(x)) ≡ ∃x such that (P(x)∧ ∼Q(x))
Additional Examples
1. Let Q(n) be the predicate “n2 ≤ 30.”
a. Write Q(2), Q(−2), Q(7), and Q(−7), and indicate which of
these statements are true and which are false.
b. Find the truth set of Q(n) if the domain of n is Z, the set of all
integers.
c. If the domain is the set Z+ of all positive integers, what is the
truth set of Q(n)?
2. Find counterexamples to show that the statements below
are false.
a. ∀x ∈ R, x > 1/x.
b. ∀a ∈ Z, (a − 1)/a is not an integer.
c. ∀ positive integers m and n, (m ∙ n) ≥ m + n

3. Let R be the domain of the predicate variable x. Which of
the following are true and which are false? Give counter
examples for the statements that are false.
a.x > 2 ⇒ x > 1
b.x > 2 ⇒ x2 > 4
c. x2 > 4 ⇒ x > 2
d.x2 > 4 ⇔ |x| > 2

4. Write a formal negation for each of the following
statements:
a. ∀ fish x, x has gills.
b. ∀ computers c, c has a CPU.
c. ∃ a movie m such that m is over 6 hours long

5. Let D = {−48, −14, −8, 0, 1, 3, 16, 23, 26, 32, 36}. Determine
which of the following statements are true and which are
false. Provide counterexamples for those statements that
are false.
a. ∀x ∈ D, if x is odd then x > 0.
b. ∀x ∈ D, if x is less than 0 then x is even.
c. ∀x ∈ D, if x is even then x ≤ 0.
d. ∀x ∈ D, if the ones digit of x is 2, then the tens digit is 3 or 4.
e. ∀x ∈ D, if the ones digit of x is 6, then the tens digit is 1 or 2.

Sources :
Epp, Susanna S. (2011). Discrete Mathematics With
Applications, Fourth Edition. Brooks/Cole
Cengage Learning
Garnier Rowan and John Taylor (2002). Discrete
Mathematics for New Technology, Second Edition.
IOP Publishing Ltd.
Haggard, Gary, John Schlipf, and Sue Whitesides (2009).
Discrete Mathematics for Engineers and Scientists,
Cengage Learning Asia Pte Ltd.
Rosen, Kenneth H.. (2008) Discrete Mathematics and Its
Applications, 6th ed. McGraw Hill.

Quantified Statements

Uploaded by

Copyright:

Available Formats

Quantified Statements

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Quantified Statements

Uploaded by

Copyright:

Available Formats

Quantified Statements

• Quantified statements are statements containing the words

b. ∀a ∈ Z, (a − 1)/a is not an integer.

c. ∀ positive integers m and n, (m ∙ n) ≥ m + n

b.x > 2 ⇒ x2 > 4

d.x2 > 4 ⇔ |x| > 2

b. ∀ computers c, c has a CPU.

c. ∃ a movie m such that m is over 6 hours long

b. ∀x ∈ D, if x is less than 0 then x is even.

d. ∀x ∈ D, if the ones digit of x is 2, then the tens digit is 3 or 4.

e. ∀x ∈ D, if the ones digit of x is 6, then the tens digit is 1 or 2.

You might also like