Transcript Propositional Logic Proof

snick

snack
CPSC 121: Models of Computation
2008/9 Winter Term 2
Proof (First Visit)
Steve Wolfman, based on notes by Patrice
Belleville, Meghan Allen and others
Lecture Prerequisites
Read Section 1.3.
Solve problems like Exercise Set 1.3, #1, 3, 4,
6-32, 36-44. Of these, we’re especially
concerned about problems like 12-13 and 3944. Many of these problems go beyond the
pre-class learning goals into the in-class
goals, but they’re the tightest fit in the text.
Complete the open-book, untimed quiz on
WebCT that was due before class.
Learning Goals: Pre-Class
By the start of class, you should be able to:
– Use truth tables to establish or refute the
validity of a rule of inference.
– Given a rule of inference and propositional
logic statements that correspond to the rule’s
premises, apply the rule to infer a new
statement implied by the original statements.
Learning Goals: In-Class
By the end of this unit, you should be able
to:
– Explore the consequences of a set of
propositional logic statements by application
of equivalence and inference rules, especially
in order to massage statements into a desired
form.
Note: in this learning goal, we are not asking you to
memorize the inference rules or their names! However,
as you become familiar with them, you’ll find that your
exploration is easier and more effective.
Quiz 4 Notes (1 of 2)
Correctness problems:
Mostly, problems with “none of the above”:
• aab
p?
• a  b, b  c  a  c
p  (q  r), q  s  ?
Quiz 4 Notes (2 of 2)
Onnagata problems:
• If the onnagata are
incorrect, is the
argument valid?
• Do the two premises
contradict each
other?
Approaches:
• Use our model!
• Prove with a truth table
• Trace the argument
• Build a new argument
and see where it leads
• Assume the opposite of
the conclusion and see
what happens
• Question the premises
What is Proof?
A rigorous mathematical argument
which unequivocally demonstrates
the truth of a given proposition, given
the truth of the proof’s premises.
MathWorld definition: http://mathworld.wolfram.com/Proof.html
My addition in italics.
Problem: Evens and Integers
Problem: Which are there more of, (a)
positive even integers, (b) positive
integers, or (c) neither?
Tasting Powerful Proof:
Some Things We Might Prove
• We can build a “three-way switch” system with any
number of switches.
• There’s no fair way to run elections.
• There are problems no program can solve.
• We can build any digital logic circuit using nothing
but NAND gates.
• We can sort a list by breaking it in half, and then
sorting and merging the halves.
• We can find the GCD of two numbers by finding
the GCD of the 2nd and the remainder when
dividing the 1st by the 2nd.
Meanwhile...
What Is a Propositional Logic
Proof?
An argument in which (1) each line is a
propositional logic statement, (2) each
statement is a premise or follows unequivocally
by a previously established rule of inference
from the truth of previous statements, and (3)
the last statement is the conclusion.
A very constrained form of proof, but a good starting point.
Interesting proofs will usually come in less structured
packages than propositional logic proofs.
Problem: Prop Logic Proof
Problem: prove that...
~(q  r)
(u  q)  s
p  s_____
 ~p
Concept Q:
Limitations of Truth Tables
Why not just use truth tables to prove
propositional logic theorems?
a. No reason; truth tables are enough.
b. Truth tables scale poorly to large problems.
c. Rules of inference and equivalence rules
can prove theorems that cannot be proven
with truth tables.
d. Truth tables require insight to use, while
rules of inference can be applied
mechanically.
Concept Q: Limitations of
Logical Equivalences
Why not use logical equivalences to prove that
the conclusions follow from the premises?
a. No reason; logical equivalences are enough.
b. Logical equivalences scale poorly to large
problems.
c. Rules of inference and truth tables can
prove theorems that cannot be proven with
logical equivalences.
d. Logical equivalences require insight to use,
while rules of inference can be applied
mechanically.
Problem: Onagata
Problem: Critique the following argument.
Premise 1: If women are too close to femininity to
portray women then men must be too close to
masculinity to play men, and vice versa.
Premise 2: And yet, if the onnagata are correct,
women are too close to femininity to portray
women and yet men are not too close to
masculinity to play men.
Conclusion: Therefore, the onnagata are incorrect,
and women are not too close to femininity to
portray women.
Problem:
Who put the cat in the piano?
Hercule Poirot has been asked by Lord Martin to find out who closed
the lid of his piano after dumping the cat inside. Poirot interrogates
two of the servants, Akilna and Eiluj. One and only one of them put
the cat in the piano. Plus, one always lies and one never lies.
Akilna says:
– Eiluj did it.
– Urquhart paid her $50 to help him study.
Eiluj says:
– I did not put the cat in the piano.
– Urquhart gave me less than $60 to help him study.
Problem: Whodunit?
Next Lecture Learning Goals:
Pre-Class
By the start of class, you should be able to:
– Evaluate the truth of predicates applied to
particular values.
– Show predicate logic statements are true by
enumerating examples (i.e., all examples in the
domain for a universal or one for an existential).
– Show predicate logic statements are false by
enumerating counterexamples (i.e., one
counterexample for universals or all in the domain
for existentials).
– Translate between statements in formal predicate
logic notation and equivalent statements in
closely matching informal language (i.e., informal
statements with clear and explicitly stated
quantifiers).
Next Lecture Prerequisites
Review Chapter 1 and be able to solve any
Chapter 1 exercise.
Read Sections 2.1 and 2.3 (skipping the
“Negation” sections in 2.3 on pages 102-104)
Solve problems like Exercise Set 2.1 #1-24 and
Set 2.3 #1-12, part (a) of 14-19, 21-22, 30-31,
part (a) of 32-38, 39, parts (a) and (b) of 4552, and 53-56.
You should have completed the open-book,
untimed quiz on Vista that was due before
this class.
snick

snack
More problems to solve...
(on your own or if we have time)
Problem: Automating Proof
Given:
pq
p  ~q  r
(r  ~p)  s  ~p
~r
Problem: What’s everything you can prove?
Problem: Canonical Form
A common form for propositional logic
expressions, called “disjunctive normal
form” or “sum of products form”, looks like
this:
(a  ~b  d)  (~c)  (~a  ~d)  (b  c  d
 e)  ...
In other words, each clause is built up of
simple propositions or their negations,
ANDed together, and all the clauses are
ORed together.
Problem: Canonical Form
Problem: Prove that any propositional logic
statement can be expressed in disjunctive
normal form.
Mystery #1
Theorem:
p  q
q  (r  s)
~r  (~t  u)
p  t
 u
Is this argument valid or invalid?
Is whatever u means true?
Mystery #2
Theorem:
p
p  r
p  (q  ~r)
~q  ~s
 s
Is this argument valid or invalid?
Is whatever s means true?
Mystery #3
Theorem:
q
p  m
q  (r  m)
m  q
 p
Is this argument valid or invalid?
Is whatever p means true?
Practice Problem (for you!)
Prove that hypothetical syllogism is a valid
rule of inference:
p  q
q  r
 p  r
Practice Problem (for you!)
Prove whether this is a valid rule of
inference:
q
p  q
 p
Practice Problem (for you!)
Are the following arguments valid?
This apple is green.
If an apple is green, it is sour.
 This apple is sour.
Sam is not barking.
If Sam is barking, then Sam is a dog.
 Sam is not a dog.
Practice Problem (for you!)
Are the following arguments valid?
This shirt is comfortable.
If a shirt is comfortable, it’s chartreuse.
 This shirt is chartreuse.
It’s not cold.
If it’s January, it’s cold.
 It’s not January.
Is valid (as a term) the same as true or correct (as English ideas)?
More Practice
Meghan is rich.
If Meghan is rich, she will pay your tuition.
 Meghan will pay your tuition.
Is this argument valid?
Should you bother sending in a check for your
tuition, or is Meghan going to do it?
Problem:
Equivalent Java Programs
Problem: How many valid Java programs
are there that do exactly the same thing?
Resources: Statements
From the Java language
specification, a
standard statement is
one that can be:
http://java.sun.com/docs/books/jls/third_edition/html/statements.html#14.5
Resources: Statements
From the Java language
specification, a
standard statement is
one that can be:
http://java.sun.com/docs/books/jls/third_edition/html/statements.html#14.5
What’s a “Block”?
Back to the Java Language Specification:
http://java.sun.com/docs/books/jls/third_edition/html/statements.html#14.2
What’s a “Block”?
A block is a sequence of statements, local
class declarations and local variable
declaration statements within braces.
…
A block is executed by executing each of the
local variable declaration statements and
other statements in order from first to last
(left to right).
What’s an “EmptyStatement”
Back to the Java Language Specification:
http://java.sun.com/docs/books/jls/third_edition/html/statements.html#14.6
Problem: Validity of Arguments
Problem: If an argument is valid, does that
mean its conclusion is true? If an
argument is invalid, does that mean its
conclusion is false?
Problem: Proofs and
Contradiction
Problem: Imagine I assume premises x, y,
and z and prove F. What can I conclude
(besides “false is true if x, y, and z are
true”)?
Proof Critique
Theorem: √2 is irrational
Proof: Assume √2 is rational, then...
There’s some integers p and q such that √2 = p/q, and
p and q share no factors.
2 = (p/q)2 = p2/q2 and p2 = 2q2
p2 is divisible by 2; so p is divisible by 2.
There’s some integer k such that p = 2k.
q2 = p2/2 = (2k)2/2 = 2k2; so q2 and q are divisible by 2.
p and q do share the factor 2, a contradiction!
√2 is irrational. QED
Problem: Comparing Deduction
and Equivalence Rules
Problem: How are logical equivalence rules
and deduction rules similar and different,
in form, function, and the means by which
we establish their truth?