QUANTIFIERS

QUANTIFIERS
Discrete Structures 1
Lecture 3
Discrete Mathematics and Its

em.parac@gmail.com Applications by Kenneth H. Rosen 1
Introduction
 Logic that deals with propositions is incapable
of describing most of the statements in
mathematics and computer science. For
example
p: n is an odd integer.
The statement p is not a proposition because
the truth or falsity of p depends on the value
of n.
 Since most statements in mathematics and
computer science use variables, we must
extend the system of logic to include such
mathematical statements.
Universe of Discourse
 Definition: Let P(x) be a statement involving
the variable x and let D be a set. We call P a
propositional function (with respect to D)
if for each x in D, P(x) is a proposition. We
call D the domain of discourse of P.
 A propositional function P, by itself, is neither
true nor false. However, for each x in its
domain of discourse, P(x) is a proposition and
is, therefore, either true of false.
 P is also called a predicate.
Example 1
 Let P(n) = n is an odd integer and
D be the set of positive integers.
 Then P is a propositional function with
domain of discourse D since for each n in D,
P(n) is a proposition.
 For example,
if n = 1, we obtain the proposition
1 is an odd integer (which is true)
if n = 2, we obtain the proposition
2 is an odd integer (which is false)
Example 2
 The following are propositional
functions:
 n2 + 2n is an odd integer (D = set of
positive integers)
 x2 – x – 6= 0 (D = set of real numbers)
 The student gets a GPA of 3.0 or better
during the 2nd semester SY 2005-2006 (D
= set of students in CIT)
 The actress has won a FAMAS award. (D =
set of actresses)
Quantifiers
 Most of the statements in mathematics and
computer science use terms such as “for
every” and “for some.” For example, in
mathematics we have the statements:
 For every triangle T, the sum of the angles
of T is equal to 180°.
 For some triangle S, the sum of two angles
is less than 90°.

 Universal and Existential Quantifiers
Universal Quantifier
 Definition: Let P be a propositional function with
domain of discourse D. The statement
for every x, P(x)
is said to be a universally quantified
statement. The symbol  means “for every.”
Thus the statement above may be written
x, P(x).
The symbol  is called a universal quantifier.
 The statement for every x, P(x) is true if P(x) is
true for every x in D and false if P(x) is false for
at least one x in D .
Existential Quantifier
 Definition: Let P be a propositional function
with domain of discourse D. The statement
for some x, P(x)
is said to be an existentially quantified
statement. The symbol  means “for some.”
Thus the statement above may be written
x, P(x).
The symbol  is called an existential
quantifier.
 The statement for some x, P(x) is true if P(x)
is true for at least one x in D and false if P(x)
is false for every x in D.
Binding Variables
 We call the variable x in the propositional function P(x) a
free variable. (The idea is that x is “free” to roam over
the domain of discourse). We call the variable x in the
universally quantified statement
x, P(x)
or the existentially quantified statement
x, P(x)
a bound variable. (The idea is the x is “bound” by the
quantifier  or .) We previously pointed out that a
propositional function does not have a truth value.
Quantifiers assign a truth value to the propositional
function.
 In general, an unquantified statement is not a
proposition and a quantified statement is a proposition.
Binding Variables
 The part of a logical expression to
which a quantifier is applied is called
the scope of this quantifier.
 In the statement x P(x,y), the variable
x is bound by the existential
quantification x, but the variable y is
free because it is not bound by a
quantifier and no value is assigned to it.
Binding Variables
 In the statement x (P(x)  Q(x))  y
R(y), all variables are bound. The scope
of the first quantifier, x, is the
expression P(x)  Q(x) because x is
applied only to P(x)  Q(x), and not to
the rest of the statement. Similarly, the
scope of the second quantifier, y is the
expression R(y).
Remarks
 The symbol  may be read “for every,” “for
all,” or “for any.”
 The symbol  may be read “for some,” “for at
least one,” or “there exists.”
 Sometimes, to specify the domain of
discourse D, we write a universally quantified
statement as
for every x in D, P(x)
and we write an existentially quantified
statement as
for some x in D, P(x).
Remarks
 The universally quantified statement
for every x, P(x)
is false if for at least one x in the
domain of discourse, the proposition
P(x) is false. A value x in the domain of
discourse that makes P(x) false is called
a counterexample to the statement
for every x, P(x).
Table 1. Quantifiers
Statement When True? When False?
x P(x) P(x) is true for There is an x for

every x. which P(x) is false.
x P(x) There is an x for P(x) is false for

which P(x) is true. every x.

Exercise
 Let P(x) be the statement “x = x2.” If the
universe of discourse consists of the integers,
what are the truth values?
a. P(0)
b. P(1)
c. P(2)
d. P(-1)
e. x P(x)
f. x P(x)
Negating Quantified
Statements
 x P(x)  x P(x)
 Example: Let P(x) be “x has taken a
course in calculus.” The negation of this
statement is “It is not the case that
every student in the class has taken a
course in calculus.” This is equivalent to
“There is student in the class who has
not taken a course in calculus.”
Negating Quantified
Statements
 x P(x)  x P(x)
 “It is not the case that there is a
student in this class who has taken a
course in calculus.” This is equivalent to
“Every student in this class has not
taken calculus.”

Table 2. Negating Quantified
Statements
Negation Equivalent When True? When False?
Statement
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.
Exercise
 Translate each of these statements into logical
expressions using predicates, quantifiers, and
logical connectives. (Let P(x)=“x is perfect”
and F(x)=“x is your friend”)
1. No one is perfect.
2. Not everyone is perfect.
3. All your friends are perfect.
4. One of your friends is perfect.
5. Everyone is your friend and is perfect.
6. Not everybody is your friend or someone is not
perfect. Discrete Mathematics and Its
Exercise
 Determine the truth value of each of
these statements if the universe of
discourse for all variables consists of all
integers.
a. n (n2  0)
b. n (n2 = 2)
c. n (n2  n)
d. n (n2 < 0)
Exercise
 Determine the truth value of each
statement where the domain of
discourse is the set of real numbers.
1. xy (x2 < y+1)
2. xy (x2 < y+1)
3. x y (x2 + y2 = 13)
4. xy (x2 + y2 = 13)


QUANTIFIERS

Uploaded by

Copyright:

Available Formats

QUANTIFIERS

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

QUANTIFIERS

Uploaded by

Copyright:

Available Formats

QUANTIFIERS

Discrete Mathematics and Its

is less than 90°.

Statement When True? When False?

x P(x) P(x) is true for There is an x for

x P(x) There is an x for P(x) is false for

Discrete Mathematics and Its

Discrete Mathematics and Its

x P(x) x P(x) There is an x P(x) is true for

Discrete Mathematics and Its

You might also like