Study Guides (238,072)
CS 245 (24)
Nancy Day (5)
Midterm

# Midterm + solution of Winter 2007 useful for pratice

9 Pages
317 Views

School
University of Waterloo
Department
Computer Science
Course
CS 245
Professor
Nancy Day
Semester
Fall

Description
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 ⇒ (Q ⇒ R)) ⇔ ((P ∧ Q) ⇒ R)  1. P ⇒ (Q ⇒ R) assumption   2. P ∧ Q assumption     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 . (P ⇒ (Q ⇒ R)) ⇒ (P ∧ Q ⇒ R) ⇒ I 1 − 7 9. (P ∧ Q) ⇒ R assumption   10. P assumption      11. Q assumption    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 ) R ⇒ ) ∧ )) R R ) (( ⇒ R R ∧ Q ⇒ 23.CLOSED 19, 23 )) ( ) ⇒ Q ¬ R ⇒ Q ( Q ⇒ P ∧ P ¬ ¬ ¬ P 18.19. ) ( 16.17. Q 22.LOSED 18,22 ⇒ AND 13 ∧ P 14.5. (( ( ) ( ¬ R ¬ ⇒ NOT-IMPLIES 14PLIMPL20. 15 ) 13. Q P ∧ ¬ (( 21.CLOSED 16,21 ⇔ NOT-AND 20 )) R ⇒ Q ( ⇒ ( ) R ¬ R ⇒ R 12.CLOSED 6,12 1. ) ⇒ Q ∧ R Q P R (( ) Q 10. NOT-∧ ¬ 1 ⇒ Q ∧ R P Q )) ( ∧ P ¬ Q R P 7. 8. ¬ ⇒ (( 5. 6. ⇒ AND 2¬ AND 5 IMPLIES 10ED 8,11 ( ⇒ 3. 4. ¬ P NOT-IMPLIES 4 9. CLOSED 7,9 IMPLIES 3 2. ( 2 2. x ∨ y,(¬x ∧ (¬w ∨ z)) ∨ (w ∧ z),y ⇒ z ⊢ z 1. x ∨ y premise 2. (¬x ∧ (¬w ∨ z)) ∨ (w ∧ z) premise ▯. y ⇒ z premise 4. y assumption  5. z ⇒ I 3,4 . x assumption  7. ¬x ∧ (¬w ∨ z) assumption    8. ¬x ∧ E 7  ▯ 9. z ¬ E 6,8  10. w ∧ z assumption  11. z ∧ E 10 12. z cases 2,7 − 9,10 − 11 13. z cases 1,4 − 5,6 − 12 1. x ∨ y 2. (¬x ∧ (¬w ∨ z)) ∨ (w ∧ z) 3. y ⇒ z 4. ¬z IMPLIES 3 5. ¬y 14. z CLOSED 4,14 OR 1 6. x 13. y CLOSED 5,13 OR 2 7. ¬x ∧ (¬w ∨ z) 10. w ∧ z AND 7 AND 10 8. ¬x 11. w 9. ¬w ∨ z 12. z CLOSED 6,8 CLOSED 4,12 3 2 Predicate Logic 1. ∀x • P(x) ⇒ Q(x),∀x • ¬Q(x) ⊢ ∀x • ¬P(x) 1. ∀x • P(x) ⇒ Q(x) premise . ∀x • ¬Q(x) premise 3. xg  4. P(x ) ⇒ Q(x ) ∀ E 1  g g 5. ¬Q(x g ∀ E 2 6
More Less

Related notes for CS 245

OR

Don't have an account?

Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Join to view

OR

By registering, I agree to the Terms and Privacy Policies
Just a few more details

So we can recommend you notes for your school.