Study Guides (238,413)
Canada (115,125)
CS 245 (24)
Nancy Day (5)

Midterm + solution of Winter 2005 useful for practice

12 Pages
Unlock Document

University of Waterloo
Computer Science
CS 245
Nancy Day

University of Waterloo Midterm Examination SOLUTION SET Term: Winter Year: 2005 Student Name UW Student ID Number Course Abbreviation and Number CS 245 Course Title Logic and Computation Sections SE112 - 001 and CS245 - 001, 002, 003 Instructor Shalini Aggarwal, Nancy Day Date of Exam Thursday, February 10, 2005 Time Period Start time: 4:30 p.m. End time: 6:30 p.m. Duration of Exam 2 hours Number of Exam Pages 12 pages (including this cover sheet) Exam Type Closed book Additional Materials Allowed NO ADDITIONAL MATERIALS ALLOWED • Write your name and student number at the bottom of every page. • Write all solutions on the exam. The booklets are for scratch work. • There are blank truth tables on the last page for use with any question. • Good luck everyone! Question Mark Max Marker Question Mark Max Marker 1 5 7 9 2 5 8 6 3 7 9 9 4 12 10 14 5 9 11 11 6 13 Total 100 Name UW Student ID (page 1 of 12) 1 (5 Marks) Short Answer 1. Can transformational proof be used to show an argument in propositional logic is valid? If so, what do you prove in transformational proof about an argument of the form p ⊢ q where p and q may be compound formulas? If not, explain why. Yes, transformational proof can be used to show an argument is valid. You would prove p ⇒ q ⇚⇛ true. 2. If ¬a is a contingent formula in propositional logic, which of the following describes a? satisfiable, contingent 3. What is the name of the argument forms identified by Aristotle? Syllogisms 4. What is the problem with using a proof procedure that is not sound? If a proof procedure is not sound then it might be possible to prove an argument is valid when it is not. 5. What must be true about a set of propositional logic formulas in order to be able to use natural deduction to prove the set is consistent? We can use natural deduction to show a set of formulas is consistent if and only if the con- junction of the formulas is a tautology. Name UW Student ID (page 2 of 12) 2 (5 Marks) Propositional Logic: Formalization Formalize the following sentences in propositional logic. Show the phrase associated with each prime proposition. 1. Michael Jackson is a software engineer only if pigs fly. j ⇒ p where • j is “Michael Jackson is a software engineer” • p is “Pigs fly” 2. I will go sledding exactly if school is cancelled and it is not windy. s ⇔ c ∧ ¬w where • s is “I will go sledding” • c is “School is cancelled” • w is “It is windy” Name UW Student ID (page 3 of 12) 3 (7 Marks) Propositional Logic: Boolean Valuations Provide a Boolean valuation in which the following two formulas have different truth values: ¬(a ∨ b ∨ c) ¬a ∧ b ⇔ a ∨ c Demonstrate that the formulas have different truth values in this Boolean valuation. Show your work. You may refer to the truth tables on the last page. A Boolean valuation in which the formulas have different truth values is: v(a) = F, v(b) = T, v(c) = T v(¬(a ∨ b ∨ c)) = NOT (v(a) OR v(b) OR v(c)) = F v(¬a ∧ b ⇔ a ∨ c) = (NOT v(a) AND v(b)) IFF (v(a) OR v(c)) = T Name UW Student ID (page 4 of 12) 4 (12 Marks) Propositional Logic: Transformational Proof Prove the following using transformational proof: (c ⇒ ¬a ⇒ b) ∧ (b ⇔ ¬a) ∧ ¬(b ∧ ⇚⇛ (a ∨ b) ∧ (¬b ∨ ¬a) (c ⇒ ¬a ⇒ b) ∧ (b ⇔ ¬a) ∧ ¬(b ∧ a) ⇚⇛ (¬c ∨ (¬a ⇒ b)) ∧ (b ⇔ ¬a) ∧ ¬(b ∧ a) Impl ⇚⇛ (¬c ∨ (¬a ⇒ b)) ∧ (¬a ⇒ b) ∧ (b ⇒ ¬a) ∧ ¬(b ∧ a) Equiv ⇚⇛ (¬a ⇒ b) ∧ (b ⇒ ¬a) ∧ ¬(b ∧ a) Simp II ⇚⇛ (¬¬a ∨ b) ∧ (¬b ∨ ¬a) ∧ ¬(b ∧ a) Impl × 2 ⇚⇛ (a ∨ b) ∧ (¬b ∨ ¬a) ∧ ¬(b ∧ a) Neg ⇚⇛ (a ∨ b) ∧ (¬b ∨ ¬a) ∧ (¬b ∨ ¬a) DM ⇚⇛ (a ∨ b) ∧ (¬b ∨ ¬a) Idemp Name UW Student ID (page 5 of 12) 5 (9 Marks) Propositional Logic: Semantic Tableaux Prove the following is a valid argument using semantic tableaux. Do not use any logical laws from transformational proof in your semantic tableaux proof. ¬a ⇒ b ∨ c, b ⇒ d, ¬(c ∨ d) |ST a 1 ¬a ⇒ b ∨ c 2 b ⇒ d 3 ¬(c ∨ d) 4 ¬a NOT-OR 3 5 ¬c 6 ¬d IMPLIES 2 8 d
More Less

Related notes for CS 245

Log In


Don't have an account?

Join OneClass

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

Sign up

Join to view


By registering, I agree to the Terms and Privacy Policies
Already have an account?
Just a few more details

So we can recommend you notes for your school.

Reset Password

Please enter below the email address you registered with and we will send you a link to reset your password.

Add your courses

Get notes from the top students in your class.