Transcript Rewriting Predicate Logic Statements

snick

snack
CPSC 121: Models of Computation
2009 Winter Term 1
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
Lecture Prerequisites
Reread Sections 2.1 and 2.3 (including the negation
part that we skipped previously).
Read Sections 2.2 and 2.4.
Solve problems like Exercise Set 2.1 #25-28 and 3031; Set 2.2 #1-25 and 27-36; Set 2.3 #13-20, 2329, 40-42, and 45-52; and Set 2.4 #2-19, and 2834.
(You needn’t learn the “diagram” technique, but it
may make more sense than other explanations!)
Complete the open-book, untimed quiz on Vista
that’s due before the next class.
3
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.
4
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).
5
Quiz 6 Notes
6
Outline
•
•
•
•
•
Prereqs, Learning Goals, and Quiz Notes
Reminder about the Challenge Method
Generalized De Morgan’s Law
Brief Problems and Discussion
Next Lecture Notes
7
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.
8
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.
9
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
10
E. Not enough info
Reminder: Challenge Method
Your adversary picks universally quantified
variables.
You pick existentially quantified variables.
If you change the turn order (by switching an
existential/universal), you may change the
way the game works!
If you swap two neighbouring existentials, you
change what order you announce your
choices in but don’t change the strategies.
(And similarly for universals.)
11
Outline
•
•
•
•
•
Prereqs, Learning Goals, and Quiz Notes
Reminder about the Challenge Method
Generalized De Morgan’s Law
Brief Problems and Discussion
Next Lecture Notes
12
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?
13
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?
14
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.)
15
De Morgan’s
with Multiple Quantifiers
What can we do with the negation on a statement like:
~n0  Z0, n  Z0, n > n0  Faster(a1, a2, n)
a. The negation cannot be moved inward.
b. The negation can only move across one quantifier
because the Generalized De Morgan’s rule only
handles one quantifier.
c. The negation could be moved across the existential
or across both of the quantifiers.
d. The negation must be moved across both quantifiers
because a negation cannot appear between
quantifiers.
e. None of these.
16
Outline
•
•
•
•
•
Prereqs, Learning Goals, and Quiz Notes
Reminder about the Challenge Method
Generalized De Morgan’s Law
Brief Problems and Discussion
Next Lecture Notes
17
Which Logical Equivalences
Apply?
Which propositional logic equivalences apply to
predicate logic? (Answers taken from your quiz
notes.)
a. Modus ponens, modus tollens, and De Morgan's
(not all equivalences!)
b. ~(P(x)  Q(x))  P(x)  ~Q(X)
c. Commutative, Associative, and “definition of
conditional”
d. All propositional logic equivalences apply to
predicate logic.
e. Some other answer is correct.
18
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  Z0, Length(a,len) 
(len2  Z0, Length(a, len2)  len = len2).
a  A, len  Z0, Length(a,len) 
(~len2  Z0, Length(a, len2)  lenlen2).
19
Outline
•
•
•
•
•
Prereqs, Learning Goals, and Quiz Notes
Reminder about the Challenge Method
Generalized De Morgan’s Law
Brief Problems and Discussion
Next Lecture Notes
20
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).
21
Learning Goals: “Pre-Class”
After the Ch 3 readings and lecture through slide “A
New Proof Strategy ‘Antecedent Assumption’” of
the next slide set, you should be able for each
proof strategy below to: (1) identify the form of
statement the strategy can prove and (2) sketch
the structure of a proof that uses the strategy.
Strategies: constructive/non-constructive proofs of
existence (“witness” proofs), disproof by counterexample, exhaustive proof, generalizing from the
generic particular (“WLOG”), direct proof
(“antecedent assumption”), proof by contradiction,
and proof by cases.
22
Alternate names are listed for some techniques.
Lecture “Prerequisites”
Reread Ch 2 and be able to solve any of the
problems in that chapter.
Read Sections 3.1, Theorem 3.4.1 and pages 159163 (“Representations of Integers”), 3.6, and 3.7.
Be able to solve (or at least outline the proof
structure of) problems like: 3.1 2-16, 18-61 (20-23
are particularly relevant!), 3.4 #24-27, 29-30, and
49-53, and 3.6 #1-27 (19-20 are particularly
relevant!).
Complete the open-book, untimed quiz on Vista
that’s due after some lecture!
23
snick

snack
More problems to solve...
(on your own or if we have time)
24
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
31
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.
32