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-
mational proof in your proofs.
1 Propositional Logic
1. (P(QR)) ((PQ)R)
1. P(QR) assumption
2. PQassumption
3. PE 2
4. QE 2
5. QRE 1,3
6. RE 4,5
7. PQRI 2 6
8. (P(QR)) (PQR)I 1 7
9. (PQ)Rassumption
10. Passumption
11. Qassumption
12. PQI 10,11
13. RE 9,12
14. QRI 11 13
15. P(QR)I 10 14
16. ((PQ)R)(P(QR)) I 9 15
17. (P(QR)) (PQR)I 8,16
1

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

1. ¬(P(QR)) ((PQ)R)
2. (P(QR)) ∧ ¬((PQ)R)
NOT-IFF 1
3. P(QR)
4. ¬((PQ)R)
AND 2
5. PQ
6. ¬R
NOT-IMPLIES 4
7. P
8. Q
AND 5
9. ¬P
CLOSED 7,9
IMPLIES 3
10. QR
11. ¬Q
CLOSED 8,11
IMPLIES 10
12. R
CLOSED 6,12
13. ¬(P(QR)) ((PQ)R)
14. ¬(P(QR))
15. ((PQ)R)
AND 13
16. P
17. ¬(QR)
NOT-IMPLIES 14
18. Q
19. ¬R
NOT-IMPLIES 17
20. ¬(PQ)
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. xy, (¬x(¬wz)) (wz), y zz
1. xypremise
2. (¬x(¬wz)) (wz) premise
3. yzpremise
4. yassumption
5. zI 3,4
6. xassumption
7. ¬x(¬wz) assumption
8. ¬xE 7
9. z¬E 6,8
10. wzassumption
11. zE 10
12. zcases 2,79,10 11
13. zcases 1,45,612
1. xy
2. (¬x(¬wz)) (wz)
3. yz
4. ¬z
5. ¬y
IMPLIES 3
6. x
OR 1
7. ¬x(¬wz)
OR 2
8. ¬x
9. ¬wz
CLOSED 6,8
AND 7
10. wz
11. w
12. z
CLOSED 4,12
AND 10
13. y
CLOSED 5,13
14. z
CLOSED 4,14
3
You're Reading a Preview

Unlock to view full version