Dave’s CPSC 121 Tutorial Notes – Week Two
Cheat Sheet Tips
• Arguments:
Premises: w The argument is valid iff:
x [(w) ∧ (x) ∧ (y)] → z
y is a tautalogy
Conclusion: ∴ z
• Rules of Inference:
Modus Ponens: p→q Modus Tollens: p→q
p ∼q
∴ q ∴ ∼p
Generalization: p Specialization: p∧q
(Addition): ∴ p∨q (Simplification): ∴ p
Conjunction: p Elimination: p∨q
q (Disjunctive syllogism): ∼ q
∴ p∧q ∴ p
Transitivity: p→q Proof by cases: p→r
(Hypothetical syllogism): q → r q→r
∴ p→r ∴ (p ∨ q) → r
Resolution: p∨q
∼p ∨ r
∴ (q ∨ r)
• Multiplexer (Selector) Logic:
Variable s is to select between variables p and q:
If s is true then be equal to p, otherwise (s is false) then be equal to q:
(s ∧ p) ∨ (∼ s ∧ q)
1
Sample Problems
1. Proving Logical Equivalence
if you want to prove x ≡ y, you have two methods:
1) Using truth tables, or
2) Using the Equivalence Laws.
We’re focusing on 2) Equivalence Laws:
Always start with just the Left Hand Side (LHS) xor the RHS.
Take a moment to decide which side might be easier for you.
General Format:
Prove x ≡ y:
LHS ≡x
≡ x0 (some Equivalence Law)
≡ x00 (some Equivalence Law)
≡ ...
≡y (some Equivalence Law)
≡ RHS
∴ x≡y
Example:
Prove (∼ p∧ ∼ q) ∨ (p ∧ q) ∨ (r∧ ∼ r) ≡∼ ((p ∨ q)∧ ∼ (p ∧ q))
In this case, starting with the LHS may be easier, but let’s start with the RHS:
RHS ≡∼ ((p ∨ q)∧ ∼ (p ∧ q))
≡∼ (p ∨ q)∨ ∼ (∼ (p ∧ q)) (De Morgan’s)
≡∼ (p ∨ q) ∨ (p ∧ q) (Double Negation)
≡ (∼ p∧ ∼ q) ∨ (p ∧ q) (De Morgan’s)
≡ (∼ p∧ ∼ q) ∨ (p ∧ q) ∨ c (Identity)
≡ (∼ p∧ ∼ q) ∨ (p ∧ q) ∨ (r∧ ∼ r) (Negation)
≡ LHS
∴ (∼ p∧ ∼ q) ∨ (p ∧ q) ∨ (r∧ ∼ r) ≡∼ ((p ∨ q)∧ ∼ (p ∧ q))
Note that if you apply the rules in reverse, you can go in the other direction (LHS to RHS)
2
2. Verifying Arguments
The process of proving an argument is valid has a similar feel to proving logical equivalences, but
they are actually quite different.
However, both logical equivalences and arguments can be verified with a truth table.
Recall the general argument form:
Premises: w The argument is valid iff:
x [(w) ∧ (x) ∧ (y)] → z
y is a tautalogy
Conclusion: ∴ z
Let’s verify the Resolution rule of inference using the truth table method;
Resolution: p∨q
∼p ∨ r
∴ (q ∨ r)
p q r p∨q ∼p ∨ r [(p ∨ q) ∧ (∼ p ∨ r)] (q ∨ r) [(p ∨ q) ∧ (∼ p ∨ r)] → (q ∨ r)
F F F F T F F T
F F T F T F T T
F T F T T T T T
F T T T T T T T
T F F T F F F T
T F T T T T T T
T T F T F F T T
T T T T T T T T
Because the last column is a tautalogy, it means the Resolution rule is valid.
3
3. Valid Arguments
Don’t mix up valid arguments and true conclusions:
Valid arguments can produce false conclusions if the original premises turn out to be false.
Dave’s Absurdity Rule: p
∼p
∴ q
p: Dave is a good TA
q: Dave is Superman
Dave is a good TA
Dave is not a good TA
∴ Dave is Superman
This argument is actually valid. We can verify it with a truth table:
p q [(p) ∧ (∼ p)] → q
F F T
F T T
T F T
T T T
However, clearly one of the original premises was false (I’ll let you decide which one :)
Note that an argument is valid regardless of what the underlying propositional variables represent.
4
4. Making Arguments
When making arguments, we start with some known true things about our universe that we are given
(our premises) and then continue to add more true things we have deduced, until (hopefully) we can
arrive to the desired conclusion.
General Format:
Show that this Argument is valid:
Premises: (1) w
(2) x
(3) y
Conclusion: ∴ z
Deductions: (4) a [Inference Rule ? on (?)]
(5) b [Inference Rule ? on (?)+(?)]
...
(?) z [Inference Rule ? on (?)]
∴ The Argument is valid
Example 1:
Premises: (1) b∨ ∼ c
(2) (c ∧ d) ∨ e
(3) ∼ e ∧ (h → g)
(4) a →∼ b
Conclusion: ∴ ∼a
Deductions: (5) ∼ e Specialization (3)
(6) c ∧ d Elimination (2)+(5)
(7) c Specialization (6)
(8) b Elimination (1)+(7)
(9) ∼ a Modus Tollens (4)+(8)
∴ The Argument is valid
5
Example 2:
Premises: (1) p→r
(2) (s ∧ u) →∼ r
(3) ∼w
(4) (s ∨ w) ∧ u
Conclusion: ∴ (p ∧ q) → r
Deductions: (5) u Specialization (4)
(6) s ∨ w Specialization (4)
(7) s Elimination (3)+(6)
(8) s ∧ u Conjunction (5)+(7)
(9) ∼ r Modus Ponens (2)+(8)
(10) ∼ p Modus Tollens (1)+(9)
(11) ∼ p∨ ∼ q Generalization (10)
(12) ∼ (p ∧ q) Equivalence [De Morgan’s] (11)
(13) ∼ (p ∧ q) ∨ r Generalization (12)
(14) (p ∧ q) → r Equivalence [Definition of →] (13)
∴ The Argument is valid
