CPSC 121 – Models of Computation
Module 04. Propositional Logic Proofs
Prof. Karina Mochetti
2020.W1
Module 04. Propositional Logic Proofs
CPSC 121 – Models of Computation 1 / 40
Announcements
What is new!
http://www.cs.ubc.ca/~mochetti/CPSC121.html
Module 04. Propositional Logic Proofs
CPSC 121 – Models of Computation 2 / 40
Goals
Use truth tables to establish or refute the validity of a rule of inference.
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.
Module 04. Propositional Logic Proofs
CPSC 121 – Models of Computation 3 / 40
Reading Review
Argument
An argument is a sequence of statements ending in a conclusion. An argument is called valid if, and only if, whenever statements are substituted that make all the premises true, the conclusion is also true.
If p then q
p ∴q
An argument form is an abstract representation with variables. All statements in an argument are called premises (or assumptions or hypotheses).
The final statement or statement form is called the conclusion. The symbol ∴ means therefore and is placed before the conclusion.
Module 04. Propositional Logic Proofs
CPSC 121 – Models of Computation 4 / 40
Reading Review
Validity
An argument form is valid when no matter what particular statements are substituted for the statement variables in its premises, if the resulting premises are all true, then the conclusion is also true.
p q r p→q∨∼r q→p∧r p→r FT FT
p → q ∨ ∼r F q→p∧r F
F
F
T
T
F
T
T
T
T
F
T
F
T
T
T
F
F
F
T
T
F
T
F
T
T
F
T
F
T
T
T
T
∴p→r
TF T
T TT
Module 04. Propositional Logic Proofs
CPSC 121 – Models of Computation 5 / 40
Reading Review
Rule of Inference
A rule of inference is a form of argument that is valid, such as modus ponens and modus tollens.
Modus Ponen
p→q
p ∴q
Modus Tollens
p→q
∼q ∴ ∼p
Module 04. Propositional Logic Proofs
CPSC 121 – Models of Computation 6 / 40
Reading Review
Fallacy
A fallacy is an error in reasoning that results in an invalid argument, such as converse error and inverse error.
Converse Error
p→q
q ∴p
Inverse Error
p→q
∼p ∴ ∼q
Module 04. Propositional Logic Proofs
CPSC 121 – Models of Computation 7 / 40
Quiz #04 Feedback
Yay! Very well done overall!!! \o/
Question 4: Use the table below to determine whether this proposed rule of inference is valid. If the rule is invalid, select any one line of the truth table which proves that the rule is invalid.
F
T
F
T
p ∧ ∼p ∴q
p q p∧∼p FF FF TF TF
Module 04. Propositional Logic Proofs
CPSC 121 – Models of Computation 8 / 40
Proofs and their Meaning
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.
Every step must be well justified.
Writing a proof is a bit like writing a function: you do it step by step, and make sure that you understand how each step relates to the previous steps.
Module 04. Propositional Logic Proofs
CPSC 121 – Models of Computation 9 / 40
Proofs and their Meaning
Things we might prove:
We can build a combinational circuit matching any truth table.
We can build any combinational logic circuit using only 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 log2 n comparisons.
There are problems that no algorithm can solve.
Module 04. Propositional Logic Proofs
CPSC 121 – Models of Computation 10 / 40
Proofs and their Meaning
Suppose that you proved this: Premise 1
…
Premise n
∴ Conclusion
Does it mean:
a. Premises 1 to n are true.
b. Conclusion is true.
c. Premises 1 to n are not a contradiction. d. Conclusion isn’t a contradiction.
e. None of the above.
Module 04. Propositional Logic Proofs
CPSC 121 – Models of Computation 11 / 40
Proofs and their Meaning
What does this argument mean? Premise 1
…
Premise n
∴ Conclusion
a. Premise 1 ∧ … ∧ Premise n ∧ Conclusion
b. Premise 1 ∨ … ∨ Premise n ∨ Conclusion
c. (Premise 1 ∧ … ∧ Premise n) → Conclusion d. (Premise 1 ∧ … ∧ Premise n) ↔ Conclusion e. None of the above.
Module 04. Propositional Logic Proofs
CPSC 121 – Models of Computation 12 / 40
Proofs and their Meaning
Let’s consider invalid the rule:
p→q
q ∴p
What can we say about the truth value of p? a. p is true
b. p is false
c. p might be either true or false
d. p can be neither true nor false
Module 04. Propositional Logic Proofs
CPSC 121 – Models of Computation 13 / 40
Propositional Logic Proofs
Propositional Logic Proofs
A propositional logic proof is a sequence of propositions, where each proposition is one of either a premise or the result of applying a logical equivalence or a rule of inference to one or more earlier propositions.
The last proposition is the conclusion.
This is simpler than the more free-form proofs, only a limited number of choices at each step.
Module 04. Propositional Logic Proofs
CPSC 121 – Models of Computation 14 / 40
Rules of Inference
Modus Ponens
p→q
p ∴q
pq
F
F
T TT
q
p→q
p
F
T
F
T
T
F
F
F
T
T
T
T
Modus Tollens
p→q
∼q ∴ ∼p
p ∼p FT F
T
T
q
p→q
∼q
F
T
T
T
T
F
F
F
T
T
T
F
Module 04. Propositional Logic Proofs
CPSC 121 – Models of Computation 15 / 40
Rules of Inference
Generalization
p ∴p∨q
p p∨q F
F TT TT
q
p
F
F
T
F
F
T
T
T
Specialization
p∧q ∴p
pp
F
F
T TT
q
p∧q
F
F
T
F
F
F
T
T
Module 04. Propositional Logic Proofs
CPSC 121 – Models of Computation 16 / 40
Rules of Inference
Conjuction
p
q ∴p∧q
p p∧q F
F
T TT
q
p
q
F
F
F
T
F
T
F
T
F
T
T
T
Elimination
q
p∨q
∼q
F
F
T
T
T
F
F
T
T
T
T
F
pp p∨q F
∼q F
∴p
TT T
Module 04. Propositional Logic Proofs
CPSC 121 – Models of Computation 17 / 40
Rules of Inference
Transitivity
q
r
p→q
q→r
F
F
T
T
F
T
T
T
T
F
T
F
T
T
T
T
F
F
F
T
F
T
F
T
T
F
T
F
T
T
T
T
p→q
q→r ∴p→r
p p→r FT FT F FT T
T
T TT
Module 04. Propositional Logic Proofs
CPSC 121 – Models of Computation 18 / 40
Rules of Inference
Proof by Cases
q
r
p∨q
p→r
q→r
F
F
F
T
T
F
T
F
T
T
T
F
T
T
F
T
T
T
T
T
F
F
T
F
T
F
T
T
T
T
T
F
T
F
F
T
T
T
T
T
p∨q p→r q→r
∴r
pr
F
F
F FT T TT T TT
Module 04. Propositional Logic Proofs
CPSC 121 – Models of Computation 19 / 40
Rules of Inference
Resolution
q
r
p∨q
∼p ∨ r
F
F
F
T
F
T
F
T
T
F
T
T
T
T
T
T
F
F
T
F
F
T
T
T
T
F
T
F
T
T
T
T
p q∨r F
F
p∨qFT ∼p∨rF T
∴q∨r
T TT T TT
p
F T
Contradiction
p→F ∴ ∼p
p→F
∼p
T
T
F
Module 04. Propositional Logic Proofs
CPSC 121 – Models of Computation 20 / 40
Rules of Inference
Modus Ponens [M. PON]
p→q
p ∴q
Modus Tollens [M. TOL]
p→q
∼q ∴ ∼p
Generalization [GEN]
pq ∴p∨q ∴p∨q
Specialization [SPEC]
p∧q p∧q ∴p ∴q
Conjunction [CONJ]
p
q ∴p∧q
Elimination [ELIM]
p∨q p∨q
∼q ∼p ∴p ∴q
Transitivity [TRANS]
p→q
q→r ∴p→r
Proof by Cases [CASE]
p∨q p→r q→r
∴r
Contradiction [CONT]
p→F ∴ ∼p
Resolution [RES]
p∨q
∼p ∨ r ∴q∨r
Module 04. Propositional Logic Proofs
CPSC 121 – Models of Computation 21 / 40
Example
Prove that the following argument is valid:
p∨q
∼p
q → ∼r
r ∨ (s ∧ t ∧ u)
∴u
Module 04. Propositional Logic Proofs
CPSC 121 – Models of Computation 22 / 40
Example
Prove that the following argument is valid:
01. p∨q
02. ∼p
03. q → ∼r
04. r ∨ (s ∧ t ∧ u)
Module 04. Propositional Logic Proofs
CPSC 121 – Models of Computation 23 / 40
Example
Prove that the following argument is valid:
01. p∨q
02. ∼p
03. q→∼r
04. r∨(s∧t∧u)
05. q Elimination from (01) and (02)
Module 04. Propositional Logic Proofs
CPSC 121 – Models of Computation 23 / 40
Example
Prove that the following argument is valid:
01. p∨q
02. ∼p
03. q→∼r
04. r∨(s∧t∧u)
05. q
06. ∼r
Elimination from (01) and (02) Modus Ponens from (03) and (05)
Module 04. Propositional Logic Proofs
CPSC 121 – Models of Computation 23 / 40
Example
Prove that the following argument is valid:
01. p∨q
02. ∼p
03. q→∼r
04. r∨(s∧t∧u)
05. q
06. ∼r
07. (s ∧ t ∧ u)
Elimination from (01) and (02) Modus Ponens from (03) and (05) Elimination from (04) and (06)
Module 04. Propositional Logic Proofs
CPSC 121 – Models of Computation 23 / 40
Example
Prove that the following argument is valid:
01. p∨q
02. ∼p
03. q→∼r
04. r∨(s∧t∧u)
05. q
06. ∼r
07. (s ∧ t ∧ u)
08. u
∴u
Elimination from (01) and (02) Modus Ponens from (03) and (05) Elimination from (04) and (06) Specialization from (07)
Module 04. Propositional Logic Proofs
CPSC 121 – Models of Computation 23 / 40
Questions?
Ask CPSC 121
http://www.cs.ubc.ca/~mochetti/askCPSC121.html
Module 04. Propositional Logic Proofs
CPSC 121 – Models of Computation 24 / 40
The Fire-Trolls Problem
Fire-Trolls Problem1 from Quiz #4:
Premise 1: If dragons are too scaly to portray dragons then
trolls must be too smelly to play trolls, and vice versa.
Premise 2: And yet, if the fire-trolls are correct, dragons are too scaly to portray dragons and yet trolls are not too smelly to play trolls.
Conclusion: Therefore, the fire-trolls are incorrect, and dragons are not too scaly to portray dragons.
Note: fire-trolls are trolls portraying dragons in mystical theater.
1taken from an article by Julian Baggini on logical fallacies.
Module 04. Propositional Logic Proofs
CPSC 121 – Models of Computation 25 / 40
The Fire-Trolls Problem
Fire-trolls: which definitions should we use?
a. d = dragons, t = trolls, sc = scaly, sm = smelly, ft =
fire-trolls, c = correct
b. d = dragons are too scaly, t = trolls are too smelly, pd = dragons portray dragons, pt = trolls portray trolls, o = fire-trolls are correct
c. d = dragons are too scaly to portray dragons, t = trolls are too smelly to portray trolls, o = fire-trolls 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.
Module 04. Propositional Logic Proofs
CPSC 121 – Models of Computation 26 / 40
The Fire-Trolls Problem
Fire-trolls: do the two premises contradict each other (that is, is p1 ∧ p2 ≡ F )?
a. Yes
b. No
c. Not enough information to tell
Module 04. Propositional Logic Proofs
CPSC 121 – Models of Computation 27 / 40
The Fire-Trolls Problem
What can we prove?
We can prove that the fire-trolls are wrong.
We can not prove that dragons are not too scaly to play dragons.
We can not prove that trolls are not too smelly to play trolls. We can prove that this argument is not valid.
Module 04. Propositional Logic Proofs
CPSC 121 – Models of Computation 28 / 40
The Fire-Trolls Problem
What can we prove?
We can prove that the fire-trolls are wrong.
We can not prove that dragons are not too scaly to portray dragons.
We can not prove that trolls are not too smelly to play trolls. We can prove that this argument is not valid.
d:dragonstooscaly d t o d↔t o→d∧∼t ∼o∧∼d
FT F
F
T d↔t T
o → d ∧ ∼t T F ∴ ∼o ∧ ∼d T
to play dragons t: trolls too smelly
to play trolls
o: fire-trolls correct F
F
F
T
T
F
T
T
F
T
F
F
T
T
T
F
F
F
F
F
T
F
T
F
T
T
F
T
T
T
T
T
F
Module 04. Propositional Logic Proofs
CPSC 121 – Models of Computation 29 / 40
Proof Strategies
Look at the information you have:
Is there irrelevant information you can ignore?
Is there critical information you should focus on?
CPSC 121 – Models of Computation 30 / 40
Module 04. Propositional Logic Proofs
Proof Strategies
Look at the information you have:
Is there irrelevant information you can ignore?
Is there critical information you should focus on?
Work backwards from the end, especially if you have made some progress but are missing a step or two.
CPSC 121 – Models of Computation
30 / 40
Module 04. Propositional Logic Proofs
Proof Strategies
Look at the information you have:
Is there irrelevant information you can ignore?
Is there critical information you should focus on?
Work backwards from the end, especially if you have made some progress but are missing a step or two.
Don’t be afraid of inferring new propositions, even if you are not quite sure whether or not they will help you get to the conclusion you want.
CPSC 121 – Models of Computation
30 / 40
Module 04. Propositional Logic Proofs
Proof Strategies
Look at the information you have:
Is there irrelevant information you can ignore?
Is there critical information you should focus on?
Work backwards from the end, especially if you have made some progress but are missing a step or two.
Don’t be afraid of inferring new propositions, even if you are not quite sure whether or not they will help you get to the conclusion you want.
If you are not sure of the conclusion, alternate between:
– trying to find an example that shows the statement is false, using the place where your proof failed to help you design the counterexample.
– trying to prove it, using your failed counterexample to help you write the proof.
Module 04. Propositional Logic Proofs
CPSC 121 – Models of Computation 30 / 40
Proof Strategies
Example: prove that the following argument is valid:
p
p→r
p → ∼s
p → (q ∨ ∼r) ∼q ∨ s
∴s
Module 04. Propositional Logic Proofs
CPSC 121 – Models of Computation 31 / 40
Proof Strategies
Example: prove that the following argument is valid:
01. p
02. p→r
03. p→∼s
04. p→(q∨∼r)
05. ∼q∨s
Module 04. Propositional Logic Proofs
CPSC 121 – Models of Computation 32 / 40
Proof Strategies
Example: prove that the following argument is valid:
01. p
02. p→r
03. p→∼s
04. p→(q∨∼r)
05. ∼q∨s
06. r
Modus Ponens from (01) and (02)
Module 04. Propositional Logic Proofs
CPSC 121 – Models of Computation 32 / 40
Proof Strategies
Example: prove that the following argument is valid:
01. p
02. p→r
03. p→∼s
04. p→(q∨∼r)
05. ∼q∨s
06. r
07. q ∨ ∼r
Modus Ponens from (01) and (02) Modus Ponens from (01) and (04)
Module 04. Propositional Logic Proofs
CPSC 121 – Models of Computation 32 / 40
Proof Strategies
Example: prove that the following argument is valid:
01. p
02. p→r
03. p→∼s
04. p→(q∨∼r)
05. ∼q∨s
06. r
07. q ∨ ∼r
08. q
Modus Ponens from (01) and (02) Modus Ponens from (01) and (04) Elimination from (06) and (07)
Module 04. Propositional Logic Proofs
CPSC 121 – Models of Computation 32 / 40
Proof Strategies
Example: prove that the following argument is valid:
01. p
02. p→r
03. p→∼s
04. p→(q∨∼r)
05. ∼q∨s
06. r
07. q ∨ ∼r
08. q
09. s
Modus Ponens from (01) and (02) Modus Ponens from (01) and (04) Elimination from (06) and (07) Elimination from (05) and (08)
Module 04. Propositional Logic Proofs
CPSC 121 – Models of Computation 32 / 40
Proof Strategies
Example: prove that the following argument is valid:
01. p
02. p→r
03. p→∼s
04. p→(q∨∼r)
05. ∼q∨s
06. ∼s
Modus Ponens from (01) and (03)
Module 04. Propositional Logic Proofs
CPSC 121 – Models of Computation 33 / 40
Proof Strategies
Example: prove that the following argument is valid:
01. p
02. p→r
03. p→∼s
04. p→(q∨∼r)
05. ∼q∨s
06. ∼s
Modus Ponens from (01) and (03)
Since we can prove either s and ∼s this is a contradiction (there is no row with all premises true). Note that the argument is still valid, since there is not a case in which all premises are true.
Module 04. Propositional Logic Proofs
CPSC 121 – Models of Computation 33 / 40
Proof Strategies
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.
Module 04. Propositional Logic Proofs
CPSC 121 – Models of Computation 34 / 40
Proof Strategies
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.
Module 04. Propositional Logic Proofs
CPSC 121 – Models of Computation 35 / 40
Questions?
Ask CPSC 121
http://www.cs.ubc.ca/~mochetti/askCPSC121.html
Module 04. Propositional Logic Proofs
CPSC 121 – Models of Computation 36 / 40
Exercise
Prove that the following argument is valid:
p→q
q → (r ∧ s) ∼r ∨ (∼t ∨ u) p∧t
∴u
Module 04. Propositional Logic Proofs
CPSC 121 – Models of Computation 37 / 40
Exercise: Solution
Prove that the following argument is valid:
01. p→q
02. q→(r∧s)
03. ∼r∨(∼t∨u)
04. p∧t
05. p
06. q
07. r∧s
08. r
09. ∼t∨u
10. t
11. u
Specialization from (04)
Modus Ponens from (01) and (05) Modus Ponens from (02) and (06) Specialization from (07) Elimination from (03) and (08) Specialization from (04) Elimination from (09) and (10)
Module 04. Propositional Logic Proofs
CPSC 121 – Models of Computation 38 / 40
More Exercises
Given the following, what is everything you can prove?
p→q
p ∨ ∼q ∨ r
(r ∧ ∼p) ∨ s ∨ ∼p ∼r
Hercule Poirot has been asked by Lord Rumpd Dalton to find out who closed the lid of his piano after dumping the cat inside. Poirot interrogates two of the servants, Meece Pink and Jhyl Klone. One and only one of them put the cat in the piano. Plus, one always lies and one never lies.
– Jhyl Klone: I did not put the cat in the piano. Ayul Parn gave me less than $60 to help her study.
– Meece Pink: Jhyl Klone did it. Ayul Parn paid him $50 to help her study.
Who put the cat in the piano?
Module 04. Propositional Logic Proofs
CPSC 121 – Models of Computation 39 / 40
Meme
Module 04. Propositional Logic Proofs
CPSC 121 – Models of Computation 40 / 40