Transcript CSS342: Quantifiers

CSS342: Quantifiers
Professor: Munehiro Fukuda
CSS342: Quantifiers
1
Review of Propositions
• Proposition: a statement that is either true or false, but not
both
• Example:
–
–
–
–
1 < 4 is true.
2 > 5 is false.
3 is an odd number
Then, how about x is an odd number?
• The statement “X is an odd number”:
– is true if x = 103
– is false if x = 8
– Most of the statements in math and CS use variables.
• We need to extend the system of logic!
CSS342: Quantifiers
2
Propositional Functions
• P(x): a statement involving the variable x
– Example: x is an odd number.
– P(x) itself is not a proposition.
– For each x in the domain D of discourse of P, if D is the set
of positive integers, P(x) is a proposition
•
•
•
•
P(1): 1 is an odd number (= true).
P(2): 2 is an odd number (= false).
…
Either true or false
• X: a free variable, (i.e., free to roam over the domain
D)
• How about for every x or for some x, P(x) is
true/false?
– Most statements in math and CS use such phrases.
CSS342: Quantifiers
3
Universally Quantified Statements
• x, P(x)
A
– Meaning:
– :
– P(x):
– X:
for every x, P(x), for all x, P(x), or
for any x, P(x)
a universal quantifier
a universally qualified statement
a bound variable, (i.e., bound by the
quantifier )
if P(x) is true for every x in D
if P(x) is false for at least one x in D
A
A
– is true:
– is false:
CSS342: Quantifiers
4
Universally Quantified Statements
Example 1
• For every real number x, if x > 1, then x + 1 > 1
is true.
• To be true, we need to consider all cases:
x ≤ 1 and x > 1
• Proof:
(1 ) If x ≤ 1,
the hypothesis x > 1 is false,
thus the conditional proposition is true.
(2) If x > 1,
x + 1 > x (always true)
since x > 1, x + 1 > x > 1
Thus, the conditional proposition is true.
Therefore, this universally quantified statement is true.
CSS342: Quantifiers
5
Universally Quantified Statements
Example 2
• For every real number x, x2 – 1 > 0
is false.
• To be false, we only need to show a counterexample:
x=1
• Proof:
If x = 1, the proposition 12 – 1 > 0 is false
The value 1 is a counterexample.
Thus, this universally quantified statement is false
CSS342: Quantifiers
6
Existentially Quantified Statements
• x, P(x)
E
– Meaning:
– :
– P(x):
– X:
for some x, P(x), for at least one x, P(x),
or there exists x such that, P(x)
an existential quantifier
a existentially qualified statement
a bound variable, (i.e., bound by the
quantifier )
if P(x) is true for at least one x in D
if P(x) is false for every x in D
E
E
– is true:
– is false:
CSS342: Quantifiers
7
Existentially Quantified Statements
Example 1
• For some positive integer n, if n is prime, then n +
1, n + 2, n + 3, and n + 4 are not prime.
is true.
• To be true, we only need to show at least one case
makes it true:
x=1
• Proof: If n = 23,
n + 1 = 24 (=3 * 8) is not prime
n + 2 = 25 (=5 * 5) is not prime
n + 3 = 26 (=2 * 13) is not prime
n + 4 = 27 (=3 * 9) is not prime
Thus, the proposition is true.
Therefor, this existentially quantified statement is true.
CSS342: Quantifiers
8
Existentially Quantified Statements
Example
2
2
• For some real number x, 1 / (x + 1) > 1
is false.
• To be false, we need to consider all cases:
This in turn means that for all real number x, 1 / (x2 + 1) ≤ 1
• Proof:
Since 0 ≤ x2 for every real number x,
1 ≤ x2 + 1
By dividing both sides of this inequality expression by
x2 + 1
1 / (x2 + 1) ≤ 1
Is true.
Therefore, 1 / (x2 + 1) >1 is false for every real number x.
CSS342: Quantifiers
9
E
A
xP(x) and xP(x)
• If it is not the case that P(x) is true for every
x, there is a counterexample showing that
P(x) is not true for at least one x.
Domain D
Domain D
P(x) ≠ true(false)
P(x) = true
P(x) = true
P(x) = true
≡
CSS342: Quantifiers
P(x) = true
P(x) = true
10
A
E
xP(x) and xP(x)
• If it is not the case that P(x) is true for some
x, P(x) is false for every x.
Domain D
Domain D
P(x) = true
P(x) = false
P(x) = false
≡
CSS342: Quantifiers
P(x) = false
P(x) = false
P(x) = false
11
Generalized De Morgan Laws for
Logic
If P is a propositional funciton, each pair of
propositions in (a) and (b) is logically
equivalent, (i.e., has the same truth values.)
and
and
A
xP(x)
xP(x)
E
A
E
A)
B)
xP(x)
xP(x)
CSS342: Quantifiers
12
Generalized De Morgan Laws for
Logic (Cont’d)
• For every x, P(x) means
– P(1) && P(2) && … && P(n)
• For some x, P(x) means
– P(1) || P(2) || … || P(n)
• x, P(x) ≡ x, P(x) means
– !(P(1) && P(2) && … && P(n)) ≡ !P(1) || !P(2) || … || !P(n)
• x, P(x) ≡ x, P(x) means
– !(P(1) || P(2) || … || P(n)) ≡ !P(1) && !P(2) && … && !P(n))
CSS342: Quantifiers
13
A
E
E
A
Revisiting Existentially Quantified
Statement Example 2
• For some real number x, 1 / (x2 + 1) > 1 is false.
• Let P(x) be 1 / (x2 + 1) > 1, then
x, P(x)
• According to De Morgan Laws,
we may prove x, P(x)
This in turn means that for all real number x,
1 / (x2 + 1) > 1 is false, (i.e., 1 / (x2 + 1) ≤ 1)
• Proof:
Since 0 ≤ x2 for every real number x, 1 ≤ x2 + 1
E
A
By dividing both sides of this inequality expression by x2 + 1
1 / (x2 + 1) ≤ 1
CSS342: Quantifiers
14
Two-Variable Propositional Function
• P(x, y): x + y = 0
• x, y, x + y = 0 is true.
– Proof: for any x, we can find at least y = -x.
Thus, x + y = x – x = 0
• y, x, x + y = 0 is false.
– Proof: if it is true, the statement can be replaced with
constant Y
x, x + Y = 0
However, we can choose x = 1 – Y, such that
x + Y = 1 – Y + Y = 1 ≠ 0.
E A
A E
A
CSS342: Quantifiers
15
The Logic Game
• Given a propositional function, P(x, y)
You and your opponent play a logic game.
– Your goal: make P(x, y) true
– You can: choose a bound variable of to make it true
– Your opponent, Farley’s goal: make P(x, y) false
– Farley can: choose a bound variable of to make it false
E
A
• Play with P(x, y): x + y = 0
CSS342: Quantifiers
16
The Logic Game (Cont’d)
E A
•
x, y, P(x, y):
– No matter what Farley chooses for x, you choose y = -x.
– You win. P(x, y) is true.
A E
•
x, y, P(x, y):
– Regardless of what you choose for x, Farley chooses y = 1- x.
– Farley wins. P(x, y) is false.
A A
•
x, y, P(x, y):
– Farley chooses x and y such that x + y ≠ 0, (e.g., x = 0, y = 1)
– Farley wins. P(x, y) is false.
E E
•
x, y, P(x, y)
– You choose x and y such that x + y = 0, (e.g., y = -x or x=1, y= -1)
– You win. P(x, y) is true.
CSS342: Quantifiers
17