Transcript PPTX

Module 4: Propositional Logic
Proofs
Due dates
• Pre-class quiz #5 is due Sunday January 29th at
19:00
• Assigned reading for the quiz:
• Epp, 4th edition: 3.1, 3.3
• Epp, 3rd edition: 2.1, 2.3
• Assignment #2 is due Thursday February 2nd at
4pm.
2
Learning goals: pre-class
• By the start of this 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.
3
Learning goals: in-class
• By the end of this module, you should be able to
• Determine whether or not a propositional logic
proof is valid, and explain why it is valid or invalid.
• 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.
• Devise and attempt multiple different, appropriate
strategies for proving a propositional logic
statement follows from a list of premises.
4
CPSC 121: the BIG questions:
• How can we convince ourselves that an algorithm
does what it's supposed to do?
• We need to prove that it works.
• We have done a few proofs in the last week or so.
• Now we will learn
• How to decide if a proof is valid in a formal setting.
• (soon) How to write proofs in English.
5
Module 4 outline
• Proofs and their meaning.
• A propositional logic proof.
• The onnagata problem.
• Further exercises.
6
What is a proof?
• A rigorous formal argument that demonstrates
the truth of a proposition, given the truth of the
proof’s premises.
• A proof is used to convince other people (or
yourself) of the truth of a conditional proposition.
• Writing a proof:
• You do it step by step.
• Make sure that you justify how each step relates to
the previous steps.
7
Things we might prove
• We can build a combinational circuit matching any
truth table.
• We can build any combinational logic circuit using
only 2-input NOR gates.
• The maximum number of swaps we need to order
n students is n(n-1)/2.
• No general algorithm exists to sort n values using
fewer than n log2n comparisons.
• There are problems that no algorithm can solve.
8
Review questions
• How do we use a truth table to prove that an
argument is valid?
• If a premise is p -> q, what are some possible ways
that I can transform this premise using rules of
inference or logical equivalence laws?
• If p ^ q is true, what do I know about p and q?
• If p v q is true and q is false, what do I know about
p?
What does it mean for an argument to be
valid?
Suppose that you proved
this:
Premise 1
...
Premise n
\ Conclusion
Does it mean:
a. If all of the premises are true,
then the conclusion is true.
b. The implication premise 1 ^ …
^ premise n -> conclusion is
true.
c. The implication premise 1 ^ …
^ premise n -> conclusion is a
tautology.
d. 2 of (a), (b), and (c) are true.
e. All of (a), (b), and (c) are true.
10
What does it mean for an argument to be
valid?
Suppose that you proved
this:
Premise 1
...
Premise n
\ Conclusion
Does it mean:
a. If all of the premises are true,
then the conclusion is true.
b. The implication premise 1 ^ …
^ premise n -> conclusion is
true.
c. The implication premise 1 ^ …
^ premise n -> conclusion is a
tautology.
d. 2 of (a), (b), and (c) are true.
e. All of (a), (b), and (c) are true.
11
What does it mean for an argument to be
valid?
Suppose that you proved
this:
Premise 1
Does it mean:
a. All of the premises are true.
b. The conclusion is true.
...
c. Both (a) and (b) are true.
Premise n
d. Neither of (a) and (b) is true.
\ Conclusion
12
What does it mean for an argument to be
valid?
Suppose that you proved
this:
Premise 1
Does it mean:
a. All of the premises are true.
b. The conclusion is true.
...
c. Both (a) and (b) are true.
Premise n
d. Neither of (a) and (b) is true.
\ Conclusion
13
What does it mean for an argument to be
valid?
Suppose that you proved
this:
Premise 1
...
Premise n
\ Conclusion
Does it mean:
a. It is possible for the premises
to contradict each other.
b. It is possible for the
conclusion to be a
contradiction.
c. Both (a) and (b) are true.
d. Neither of (a) and (b) is true.
14
What does it mean for an argument to be
valid?
Suppose that you proved
this:
Premise 1
...
Premise n
\ Conclusion
Does it mean:
a. It is possible for the premises
to contradict each other.
b. It is possible for the
conclusion to be a
contradiction.
c. Both (a) and (b) are true.
d. Neither of (a) and (b) is true.
15
What does it mean for an argument to
be valid?
• If an argument is valid,
• We know that if all the premises are true, then
the conclusion is true.
• We do not know
• Whether any premise is true, or
• Whether the conclusion is true.
Module 4 outline
• Proofs and their meaning.
• A propositional logic proof.
• The onnagata problem.
• Further exercises.
17
A propositional logic proof
• A propositional logic proof is a sequence of
propositions, where each proposition is one of
• A premise
• The result of applying a logical equivalence or a
rule of inference to one or more earlier
propositions.
• and whose last proposition is the conclusion.
• These are good starting point, because they are
simpler than the more free-form proofs we will
discuss later
• Only a limited number of choices at each step.
18
A propositional logic proof
Prove that the following argument is valid:
1 ~(𝑞 ∨ 𝑟)
2 (𝑢 ∧ 𝑞) ⟷ 𝑠
3 ~𝑠 → ~𝑝
\ ~𝑝
19
Proof strategies
• Work backwards from the end
• Play with alternate forms of premises
• Identify and eliminate irrelevant information
• Identify and focus on critical information
• Step back from the problem frequently to think about
assumptions you might have wrong or other
approaches you could take.
• If you don’t know whether the argument is valid or
not, alternate between
• trying to prove it, and
• trying to disprove it by finding a counterexample.
20
Limitations of truth tables
Why can we 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 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.
▷
21
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 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.
▷
22
Module 4 outline
• Proofs and their meaning.
• A propositional logic proof.
• The onnagata problem.
• Further exercises.
24
The onnagata problem
• Critique the following argument, drawn from an
article by Julian Baggini on logical fallacies.
• 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.
• Note: onnagata are male actors portraying female
characters in kabuki theatre.
25
Which definitions should we use?
Onnagata: which definitions should we use?
a.w = women, m = men, f = femininity, m = masculinity, o =
onnagata, c = correct
b.w = women are too close to femininity, m = men are too
close to masculinity, pw = women portray women, pm =
men portray men, o = onnagata are correct
c.w = women are too close to femininity to portray women,
m = men are too close to masculinity to portray men, o =
onnagata are correct
d.None of these, but another set of definitions works well.
e.None of these, and this problem cannot be modeled well
with propositional logic.
▷
26
Translating English into propositional
logic expressions
• 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.
▷
27
Do the premises contradict each other?
• Do the two premises contradict each other (that
is, is p1 ^ p2 always false)?
a. Yes
b. No
c. Not enough information to tell
▷
28
What can we prove?
• We can prove that the Onnagata are wrong.
• We can not prove that women are not too close
to femininity to portray women.
29
One last question
Consider the following:
Alice is rich
If Alice is rich then she will pay your tuition
\ Alice will pay your tuition.
Is this argument valid?
Should you pay your tuition, or should you
assume that Alice will pay it for you? Why?
30
Module 4 outline
• Proofs and their meaning.
• A propositional logic proof.
• The onnagata problem.
• Further exercises.
31
Module 4.3: Further exercises
Prove that the following argument is valid:
p q
q  (r ^ s)
~r v (~t v u)
p^t
\u
Given the following, what is everything you can prove?
p q
p v ~q v r
(r ^ ~p) v s v ~p
~r
32
Module 4.3: Further exercises
Further exercises
Hercule Poirot has been asked by Lord Maabo to find
out who closed the lid of his piano after dumping the
cat inside. Poirot interrogates two of the servants,
Pearrh and Dr. Utuae. One and only one of them put
the cat in the piano. Plus, one always lies and one
never lies.
Dr. Utuae: I did not put the cat in the piano. Tgahaa
gave me less than $60 to help her study.
Pearrh: Dr. Utuae did it. Tgahaa paid him $50 to
help her study.
Who put the cat in the piano?
33