Transcript Document

snick

snack
CPSC 121: Models of Computation
2012 Summer Term 2
Rewriting Predicate Logic Statements
Steve Wolfman, based on notes by
Patrice Belleville and others
1
Outline
•
•
•
•
•
Prereqs, Learning Goals, and Quiz Notes
Reminder about the Challenge Method
Generalized De Morgan’s Law
Brief Problems and Discussion
Next Lecture Notes
2
Learning Goals: Pre-Class
By the start of class, you should be able to:
– Determine the negation of any quantified statement.
– Given a quantified statement and an equivalence rule,
apply the rule to create an equivalent statement
(particularly the De Morgan’s and contrapositive
rules).
– Prove and disprove quantified statements using the
“challenge” method (Epp, 3d edition, page 99).
– Apply universal instantiation, universal modus
ponens, and universal modus tollens to predicate
logic statements that correspond to the rules’
premises to infer statements implied by the premises.
3
Learning Goals: In-Class
By the end of this unit, you should be able
to:
– Explore alternate forms of predicate logic
statements using the logical equivalences you
have already learned plus negation of
quantifiers (a generalized form of De
Morgan’s Law).
4
Quiz 6 Notes
~(There is a student in CS who uses all of
Lisp and Prolog and Haskell.)
Let’s figure out what this is logically
equivalent to…
5
Quiz 6 Notes
What’s in a name?
y  B, x  C, P(y)  Q(x).
x  B, y  C, P(x)  Q(y).
6
Quiz 6 Notes
x  D, Q(x) 
[(y  D, P(x, y))  ~(y  D, P(x, y))].
For what value of R(x) is this the same as:
x  D, Q(x)  [R(x)  ~R(x)]?
a. R(x)  y  D, P(x, y)
b. R(x)  y  D, P(x, y)
c. R(x)  P(x, y)
d. None of these, but there is such an R(x).
e. None of these, and there is no such R(x).
7
Outline
•
•
•
•
•
Prereqs, Learning Goals, and Quiz Notes
Reminder about the Challenge Method
Generalized De Morgan’s Law
Brief Problems and Discussion
Next Lecture Notes
8
Reminder: Challenge Method
A predicate logic statement is like a game with
two players:
• you (trying to prove the statement true)
• your adversary (trying to prove it false).
The two of you pick values for the quantified
variables working from the outside (left) in.
Your adversary picks the values of universally
quantified variables.
You pick the values of existentially quantified
variables.
9
Challenge Method Continued
If there’s a strategy for you such that no
strategy of the adversary’s can beat you,
the statement is true.
If there’s a strategy for the adversary such
that no strategy of yours can beat the
adversary, the statement is false.
10
What does it mean to say:
“I have a winning strategy at Nim”?
11
Is  the same as ?
You’re playing on the side of truth*. Which
of these will likely be easier to prove?
xS,yS,Supes(x,y).
xS,yS,Supes(x,y).
a.  version
b.  version
c. Neither, since they’re logically equivalent.
d. It’s impossible to tell.
*Also
justice and
the Canadian Way.

12
Outline
•
•
•
•
•
Prereqs, Learning Goals, and Quiz Notes
Reminder about the Challenge Method
Generalized De Morgan’s Law
Brief Problems and Discussion
Next Lecture Notes
13
De Morgan’s Law and
Negating Quantifiers
Consider the statement:
x  Z+, Odd(x)  Even(x)
This is essentially an infinitely big AND:
(Odd(1)  Even(1))  (Odd(2)  Even(2)) 
(Odd(3)  Even(3))  ...
What happens if we negate it?
14
De Morgan’s Law and
Negating Quantifiers
Consider the statement:
x  Z+, x*x = x.
This is essentially an infinitely big OR:
(1*1 = 1)  (2*2 = 2)  (3*3 = 3)  ...
What happens if we negate it?
15
Generalized De Morgan’s
(for Quantifiers)
~x, P(x)  x, ~P(x)
~x, P(x)  x, ~P(x)
(The quantifier changes when a negation
moves across it.)
P(x) could be anything, of course!
16
It can be a “helper predicate”.
De Morgan’s
with Multiple Quantifiers
Which of the following are equivalent to:
~n0  Z0, n  Z0, n > n0  F(a1, a2, n).
a.
b.
c.
d.
e.
n0 
n0 
n0 
n0 
n0 
Z0,
Z0,
Z0,
Z0,
Z0,
~n  Z0, n > n0  F(a1, a2, n).
n  Z0, ~(n > n0)  F(a1, a2, n).
n  Z0, ~(n > n0  F(a1, a2, n)).
n  Z0, ~(n > n0  F(a1, a2, n)).
n  Z0, n > n0  ~F(a1, a2, n).
17
Outline
•
•
•
•
•
Prereqs, Learning Goals, and Quiz Notes
Reminder about the Challenge Method
Generalized De Morgan’s Law
Brief Problems and Discussion
Next Lecture Notes
18
Which Logical Equivalences
Apply?
All of them!
But… we have to be sure to carefully “line up” the
parts of the logical equivalence with the parts of
the logical statement.
19
Problem: Lists (aka Arrays)
Let Length(a, len) mean that list a has the length
len. Let A be the set of all arrays.
Problem: Use logical equivalence to show that
these translations of “an array has exactly one
length” are logically equivalent:
a  A, len  N, Length(a,len) 
(len2  N, Length(a, len2)  len = len2).
a  A, len  N, Length(a,len) 
(~len2  N, Length(a, len2)  lenlen2).
20
Outline
•
•
•
•
•
Prereqs, Learning Goals, and Quiz Notes
Reminder about the Challenge Method
Generalized De Morgan’s Law
Brief Problems and Discussion
Next Lecture Notes
21
Learning Goals: In-Class
By the start of class, you should be able to:
– Explore alternate forms of predicate logic
statements using the logical equivalences you
have already learned plus negation of
quantifiers (a generalized form of De
Morgan’s Law).
22
Learning Goals: Pre-Class
Be able for each proof strategy below to:
– Identify the form of statement the strategy can prove.
– Sketch the structure of a proof that uses the strategy.
Strategies: constructive/non-constructive proofs of
existence ("witness"), disproof by counterexample,
exhaustive proof, generalizing from the generic
particular ("WLOG"), direct proof ("antecedent
assumption"), proof by contradiction, and proof by
cases.
23
Alternate names are listed for some techniques.
Lecture Prerequisites
In the “Textbook and References” section of
the course website:
– Reread the “Rewriting Predicate Logic” sections
– Read the “Proof Techniques” sections
Complete the open-book, untimed quiz on
Vista that is due before class.
24
snick

snack
More problems to solve...
(on your own or if we have time)
25
Why Voting?
A voting system is software. It describes how to
compute a winner from the raw data of marked
ballots... When [voters, candidates, and
strategists] are able to use the system to defeat
the overall will of the voters, blame is properly
laid on the system itself.
- William Poundstone, Gaming the Vote
We now play with Arrow’s Impossibility Theorem because
it’s a fascinating proof. But.. Poundstone would remind
us that there are systems not subject to this theorem!
Informal Definition: “Independence
of Irrelevant Alternatives” (IIA)
Philosopher Sidney Morgenbesser is ordering
dessert. The waiter says they have apple and
blueberry pie. Morgenbesser asks for apple.
The waiter comes back out and says “Oh, we have
cherry as well!”
“In that case,” says Morgenbesser, “I’ll take the
blueberry.”
>
but
>
>
Huh??
Formal Definition: “Independence
of Irrelevant Alternatives” (IIA)
If under a particular set of votes, society
prefers A to B, society must still prefer A to
B if voters rearrange their preferences but
maintain their relative rankings of A and B.
1
C
A
D
E
B
2
B
A
D
C
E
3
A
C
D
E
B
4
A
E
B
C
D
5
D
E
C
B
A
S
A
.
.
.
B
1
E
A
C
B
D
2
C
E
B
A
D
3
A
B
C
D
E
4
C
A
E
B
D
5
D
B
E
C
A
S
A
.
.
.
B
General Definition:
“Pareto (In)Efficiency”
If a change in the solution can make
everyone better off, then the solution is
“Pareto inefficient”. (Used beyond elections!)
Question: Which of these is not Pareto Efficient?
Candidate (“option”)
Key:
A
B
Voter
C
D
E
Formal Voting Definition:
“Pareto Efficiency”
For any two candidates A and B, if everyone
prefers candidate A to candidate B,
society must prefer A to B.
Key:
Candidate (“option”)
Voter
Formal Definition: “Dictatorship”
In a dictatorship, no matter how everyone
votes, society’s preference order precisely
follows one voter’s preference order (even
if no one knows who that person is).
1
C
A
D
E
B
2
B
A
D
C
E
3
A
C
D
E
B
4
A
E
B
C
D
5
D
E
C
B
A
S
A
E
B
C
D
1
E
A
C
B
D
2
C
E
B
A
D
3
A
B
C
D
E
4
C
A
E
B
D
5
D
B
E
C
A
S
C
A
E
B
D
All hail 4!
Arrow’s Impossibility Theorem
Arrows Theorem shows, for any voting
system*, if the system exhibits IIA and
Pareto efficiency, then it’s a dictatorship.
Let V be the set of all voting systems and
IIA(v), PE(v), and D(v) describe the three
properties.
Problem: Prove using logical equivalences
that “there’s no such thing as a fair voting
system”.
*Technically:
ranking-based systems on
32
elections with  2 voters and  3 candidates.
Arrow’s Impossibility Theorem
Which can you prove?
a. ~x  V, IIA(v)  PE(v)  ~D(v).
b. x  V, IIA(v)  PE(v)  ~D(v).
c. x  V, D(v)  IIA(v)  PE(v).
d.x  V, D(v).
e. None of these.
33
Problem: Bosses
Top(x): x is the president
Report(x, y): x reports (directly) to y
P: the set of all people in the organization
Imagine a hierarchical organization in which everyone has
exactly one boss except the president.
Let the domain of all variables be P. Which of these
statements is true in any such organization?
x  P, y  P, Top(x)  Report(x, y)
A. The first one.
y  P, x  P, Top(x)  Report(x, y)
B. The second one.
C. Both
D. Neither
34
E. Not enough info