Study Guides (390,000)
CA (150,000)
UW (7,000)
CS (400)
CS245 (20)
Midterm

# CS245 Study Guide - Midterm Guide: Natural Deduction, Qi

Department
Computer Science
Course Code
CS245
Professor
Nancy Day
Study Guide
Midterm

This preview shows pages 1-3. to view the full 9 pages of the document.
CS 245 Winter 2009
Review Problems on Propositional and Predicate Logic
Natural Deduction and Semantic Tableaux
Prove the following arguments are valid or show that they are invalid by providing a coun-
terexample and demonstrating that your counterexample shows the argument is invalid. Use
both natural deduction and semantic tableaux. Do not use any logical laws from transfor-
1 Propositional Logic
1. âŠ¢(Pâ‡’(Qâ‡’R)) â‡”((Pâˆ§Q)â‡’R)
ï£®
ï£¯
ï£¯
ï£¯
ï£¯
ï£¯
ï£¯
ï£¯
ï£¯
ï£°
1. Pâ‡’(Qâ‡’R) assumption
ï£®
ï£¯
ï£¯
ï£¯
ï£¯
ï£°
2. Pâˆ§Qassumption
3. Pâˆ§E 2
4. Qâˆ§E 2
5. Qâ‡’Râ‡’E 1,3
6. Râ‡’E 4,5
7. Pâˆ§Qâ‡’Râ‡’I 2 âˆ’6
8. (Pâ‡’(Qâ‡’R)) â‡’(Pâˆ§Qâ‡’R)â‡’I 1 âˆ’7
ï£®
ï£¯
ï£¯
ï£¯
ï£¯
ï£¯
ï£¯
ï£¯
ï£¯
ï£°
9. (Pâˆ§Q)â‡’Rassumption
ï£®
ï£¯
ï£¯
ï£¯
ï£¯
ï£°
10. Passumption
ï£®
ï£°
11. Qassumption
12. Pâˆ§Qâˆ§I 10,11
13. Râ‡’E 9,12
14. Qâ‡’Râ‡’I 11 âˆ’13
15. Pâ‡’(Qâ‡’R)â‡’I 10 âˆ’14
16. ((Pâˆ§Q)â‡’R)â‡’(Pâ‡’(Qâ‡’R)) â‡’I 9 âˆ’15
17. (Pâ‡’(Qâ‡’R)) â‡”(Pâˆ§Qâ‡’R)â‡”I 8,16
1

Only pages 1-3 are available for preview. Some parts have been intentionally blurred.

1. Â¬(Pâ‡’(Qâ‡’R)) â‡”((Pâˆ§Q)â‡’R)
2. (Pâ‡’(Qâ‡’R)) âˆ§ Â¬((Pâˆ§Q)â‡’R)
NOT-IFF 1
3. Pâ‡’(Qâ‡’R)
4. Â¬((Pâˆ§Q)â‡’R)
AND 2
5. Pâˆ§Q
6. Â¬R
NOT-IMPLIES 4
7. P
8. Q
AND 5
9. Â¬P
CLOSED 7,9
IMPLIES 3
10. Qâ‡’R
11. Â¬Q
CLOSED 8,11
IMPLIES 10
12. R
CLOSED 6,12
13. Â¬(Pâ‡’(Qâ‡’R)) âˆ§((Pâˆ§Q)â‡’R)
14. Â¬(Pâ‡’(Qâ‡’R))
15. ((Pâˆ§Q)â‡’R)
AND 13
16. P
17. Â¬(Qâ‡’R)
NOT-IMPLIES 14
18. Q
19. Â¬R
NOT-IMPLIES 17
20. Â¬(Pâˆ§Q)
IMPLIES 15
21. Â¬P
CLOSED 16,21
NOT-AND 20
22. Â¬Q
CLOSED 18,22
23. R
CLOSED 19, 23
2

Only pages 1-3 are available for preview. Some parts have been intentionally blurred.

2. xâˆ¨y, (Â¬xâˆ§(Â¬wâˆ¨z)) âˆ¨(wâˆ§z), y â‡’zâŠ¢z
1. xâˆ¨ypremise
2. (Â¬xâˆ§(Â¬wâˆ¨z)) âˆ¨(wâˆ§z) premise
3. yâ‡’zpremise
î€”4. yassumption
5. zâ‡’I 3,4
ï£®
ï£¯
ï£¯
ï£¯
ï£¯
ï£¯
ï£¯
ï£¯
ï£¯
ï£°
6. xassumption
ï£®
ï£°
7. Â¬xâˆ§(Â¬wâˆ¨z) assumption
8. Â¬xâˆ§E 7
9. zÂ¬E 6,8
î€”10. wâˆ§zassumption
11. zâˆ§E 10
12. zcases 2,7âˆ’9,10 âˆ’11
13. zcases 1,4âˆ’5,6âˆ’12
1. xâˆ¨y
2. (Â¬xâˆ§(Â¬wâˆ¨z)) âˆ¨(wâˆ§z)
3. yâ‡’z
4. Â¬z
5. Â¬y
IMPLIES 3
6. x
OR 1
7. Â¬xâˆ§(Â¬wâˆ¨z)
OR 2
8. Â¬x
9. Â¬wâˆ¨z
CLOSED 6,8
AND 7
10. wâˆ§z
11. w
12. z
CLOSED 4,12
AND 10
13. y
CLOSED 5,13
14. z
CLOSED 4,14
3