Transcript Predicates & Quantifiers

Sections 1.3 and 1.4
Predicates & Quantifiers
1
Propositional Functions
• In a mathematical assertion, such as x < 3,
there are two parts:
– the subject, which is the variable (x in this case)
– the predicate, which is the property the subject
may (or may not) have (< 3 in the example)
• We can denote such a predicate as a
propositional function on x, or P(x)
• When x has a value, P(x) is a proposition
2
Propositional Functions
A propositional function can include more than one variable; for
example:
Let Q(x,y) denote the statement “x is the capital of y”
What are the truth values of:
Q(Denver, Colorado)
Q(Detroit, Michigan)
Q(Massachusetts, Boston)
Q(New York, New York)
3
Propositional Functions and
Programs
• In a program, a selection structure involves
evaluating a propositional function
• For example:
Means let P(x) = x > 0
if (x > 0)
if P(x) is true,
x++;
increment x
otherwise,
do nothing
4
Quantifiers
• As we have seen, we can create a
proposition from a propositional function by
assigning a value to its subject(s)
• We can also create a proposition by
quantifying the propositional function
• There are two types of quantifiers:
– universal
– existential
5
Universal Quantification
• The domain of a problem is called its
universe of discourse
• The universal quantification of P(x) is the
assertion that P(x) is true for all values of x
in the universe of discourse
• Universal quantification is denoted xP(x)
which may be read “for all (or every) value
of x, P(x) is true”
6
Universal Quantification
• Suppose P(x) is the statement “x spends more
than 3 hours every day in class” and the
universe of discourse is the set of all students
• Then xP(x) would be the statement “All
students spend more than 3 hours every day in
class”
• This could also be expressed: x(S(x)  P(x))
where S(x) = “x is a student”
7
Universal Quantification &
Conjunction
When all elements in a universe of discourse can be listed, e.g.
(x1, x2, … , xn) then xP(x) can be written as:
P(x1)  P(x2)  …  P(xn)
For example, suppose P(x) = x < x2 where the universe of
discourse is the positive integers less than 5
For xP(x) to be true, P(0)  P(1)  P(2)  P(3)  P(4) would
have to be true; since 0 < 0 and 1 < 1 are untrue, xP(x) is false
8
Existential Quantification
• The assertion that there is an element with a
certain property
• The notation xP(x) means there exists at
least one element x in the universe of
discourse for which P(x) is true
9
Existential Quantification &
Disjunction
When all elements in a universe of discourse can be listed, e.g.
(x1, x2, … , xn) then xP(x) can be written as:
P(x1)  P(x2)  …  P(xn)
For example, suppose P(x) = x < x2 where the universe of
discourse is the positive integers less than 5
For xP(x) to be true, P(0)  P(1)  P(2)  P(3)  P(4) would
have to be true; since 2 < 4, xP(x) is true
10
Universal vs. Existential
Quantification
xP(x)
xP(x)
True if P(x) is true
for all values of x
in universe of
discourse
False if there
is at least one
value x where
P(x) is false
True if there exists
at least one value x
for which P(x)
is true
False if P(x) is
false for every x
in the universe
of discourse 11
Quantifiers & Looping
• Can be helpful to think in terms of looping
and searching when seeking truth value of a
quantification
• For xP(x), loop through all N values in
universe of discourse; if all are true, xP(x)
is true
• For xP(x), loop through all N values; if
any are true, xP(x) is true
12
Binding Variables
• A variable is said to be bound if it has a
value assigned to it or if a quantifier is used
on it
• A variable is free if neither of these
conditions applies
13
Binding Variables
• In order to turn a propositional function into
a proposition, all variables in the function
must be bound
• Can have multiple quantifications for
propositional functions involving more than
one variable
• The order of quantifiers is important unless
all are of the same type (all existential or all
14
universal)
Example
Are these quantifications logically equivalent?
x y P(x,y)
y x P(x,y)
x y P(x,y)
There exists an x for
which P(x,y) is true
for every value of y
y x P(x,y)
For every value of y there
is a value of x for which
P(x,y) is true
So there must be an x
for which the function is
true regardless of y - x is
an independent constant
So x can depend on y
If the first is true, the second is true - but not vice-versa
15
Translating Quantified
Expressions
Suppose W(x,y) is the propositional function “student x has taken
class y” and the universe of discourse for x is students in this
class, while the universe of discourse for y is classes at Kirkwood
Then the quantification y(W(Tim,y)  W(Dan,y)) means
there exists a class at Kirkwood for which the statements
“Tim has taken this class” and “Dan has taken this class” is true
What does yx(W(x,y)) mean?
16
Translating Quantified
Statements
Suppose the universe of discourse for x, y and z is the set of
real numbers. What is the meaning of the following quantification?
x y z (z * (x + y) = (z * x) + (z * y))
This is the distributive law for multiplication:
For all real numbers x, y and z, the product of z and the sum of
x and y is equal to the sum of the products of z and x and z and y
17
Translating Quantified
Statements
Can translate from English into logical expressions, as well as
vice versa
For example, suppose L(x,y) is the propositional function
x loves y, and the universe of discourse for x and y is all the
people in the world
The quantification “Everybody loves me” can be denoted as:
x L(x, me)
How would you denote “I love everybody” and “Somebody
loves me?”
18
More “love” examples
There is somebody whom everybody loves:
y x L(x,y)
Everybody loves somebody:
x y L(x,y)
There is somebody whom nobody loves:
y x (L(x,y))
19
Nested Loops & Multiple
Quantifications
• x y P(x,y): loop through all values of x;
in each x loop, loop through all values of y;
true if no false values found
• x y P(x,y): loop through all values of x;
loop through all y values at each x until a y
is found for which P(x,y) is true proposition is true if there is such a y for
every x
20
Nested Loops & Multiple
Quantifications
• x y P(x,y): loop through all values of x
until we find an x for which P(x,y) is true
for all values of y
• x y P(x,y): start looping through x values;
at each x, loop through y values - if we hit
at least one x,y where P(x,y) is true, then
the proposition is true
21
Summary of truth values for
multiple quantifications
x y P(x,y) True if P(x,y) is
y x P(x,y) true for every
x,y pair
x y P(x,y) True if there is a
y that makes P(x,y)
true for every x
False if there is at least one
x,y pair for which P(x,y)
is false
False if there is an x for
which P(x,y) is false for
every y
x y P(x,y) True if there is an
x for which P(x,y)
true for every y
False if for every x there
is a y for which P(x,y)
is false
x y P(x,y) True if there is at
y x P(x,y) least 1 x,y pair for
which P(x,y) is true
False if P(x,y) is false
for every x,y pair
22
Negations of quantified
expressions
• The negation of a universal quantification is
the existential quantification of the negation
• The negation of an existential quantification
is the universal quantification of the
negation
23
Negations of quantified
expressions
x P(x)  x P(x)
True if P(x) is false
for every value of x
x P(x)  x P(x)
True if there exists
an x for which P(x)
is false
False if there is an x for
which P(x) is true
False if P(x) is true for
every x
24
Section 1.3
Predicates & Quantifiers
- ends -
25