•
•
Rules of Inference
(Rosen, Section 1.6)
•
TOPICS
•
• Logic Proofs •
•via Truth Tables
•via Algebraic Simplification •
•via Inference Rules
CS160 - Summer Semester 2016 2
• ■
✧
✧ ■
•
■
CS160 - Summer Semester 2016 3 CS160 - Summer Semester 2016 4
■ ■
■ ■
■
■
CS160 - Summer Semester 2016 5 CS160 - Summer Semester 2016 6
■
■
■
■
CS160 - Summer Semester 2016 7 CS160 - Summer Semester 2016 8
■ ■
■
■
■
■
CS160 - Summer Semester 2016 9 CS160 - Summer Semester 2016 10
CS160 - Summer Semester 2016 11 CS160 - Summer Semester 2016 12
■ ■ If p, and p implies q, then q
■ Example:
■ p = it is sunny, q = it is hot
■
p → q, it is hot whenever it is sunny
■
“Given the above, if it is sunny, it must
■
be hot”.
■
CS160 - Summer Semester 2016 13 CS160 - Summer Semester 2016 14
■ If not q and p implies q, then not p
(p ∧ (p → q)) → q Example:
p = it is sunny, q = it is hot
p q p→q p ∧ (p → q) (p ∧ (p → q)) → q
p → q, it is hot whenever it is sunny
0 0 1 0 1 “Given the above, if it is not hot, it
0 1 1 0 1 cannot be sunny.”
1 0 0 0 1
1 1 1 1 1
CS160 - Summer Semester 2016 15 CS160 - Summer Semester 2016 16
■ If p implies q, and q implies r, then ■ If p or q, and not p, then q
p implies r Example:
Example: p = it is sunny, q = it is hot
p = it is sunny, q = it is hot, r = it is dry p ∨ q, it is hot or sunny
p → q, it is hot when it is sunny “Given the above, if it not sunny, but it
q → r, it is dry when it is hot is hot or sunny, then it is hot”
“Given the above, it must be dry when
it is sunny”
CS160 - Summer Semester 2016 17 CS160 - Summer Semester 2016 18
■ If p or q, and not p or r, then q or r ■ If p then p or q
Example: Example:
p = it is sunny, q = it is hot, r = it is dry p = it is sunny, q = it is hot
p ∨ q, it is sunny or hot p ∨ q, it is hot or sunny
¬p ∨ r, it is not hot or it is dry “Given the above, if it is sunny, it must
“Given the above, if it is sunny or hot, but be hot or sunny”
not sunny or dry, it must be hot or dry”
Of course!
Not obvious!
CS160 - Summer Semester 2016 19 CS160 - Summer Semester 2016 20
■ If p and q, then p ■ If p and q, then p and q
Example: Example:
p = it is sunny, q = it is hot p = it is sunny, q = it is hot
p ∧ q, it is hot and sunny p ∧ q, it is hot and sunny
“Given the above, if it is hot and sunny, “Given the above, if it is sunny and it is
it must be hot” hot, it must be hot and sunny”
Of course! Of course!
CS160 - Summer Semester 2016 21 CS160 - Summer Semester 2016 22
→ → ¬∨
Step Reason
1. Premise
2. Premise
■
3. Hypothetical Syllogism (1, 2) ■
4. Premise ■
■
5. Modus Ponens (3, 4)
6. Premise
7. Disjunctive Syllogism (5, 6)
CS160 - Summer Semester 2016 23 CS160 - Summer Semester 2016 24
■ Step Reason
■ A → B ∧ (C ∨ D) 1. A → B ∧ (C ∨ D) Premise
2. A Premise
■ A
3. B ∧ (C ∨ D) Modus Ponens (1, 2)
■ ¬C
4. C∨D Simplification (3)
■
5. ¬C Premise
■ D 6. D Disjunctive Syllogism (4, 5)
CS160 - Summer Semester 2016 25 CS160 - Summer Semester 2016 26
Step Reason
Given: Conclude: 1. p → q Premise
p→q ¬q → s 2. ¬q → ¬p Implication law (1)
¬p → r 3. ¬p → r Premise
r→s 4. ¬q → r Hypothetical syllogism (2, 3)
5. r → s Premise
6. ¬q → s Hypothetical syllogism (4, 5)
CS160 - Summer Semester 2016 27 CS160 - Summer Semester 2016 28