CS245 Study Guide - Midterm Guide: Proof Procedure, Propositional Calculus, Natural Deduction

80 views12 pages
user avatar
Published on 16 Oct 2011
School
University of Waterloo
Department
Computer Science
Course
CS245
Professor
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)
Unlock document

This preview shows pages 1-3 of the document.
Unlock all 12 pages and 3 million more documents.

Already have an account? Log in
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 pq
where pand qmay be compound formulas?
If not, explain why.
Yes, transformational proof can be used to show an argument is valid. You would prove
pqtrue.
2. If ¬ais 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)
Unlock document

This preview shows pages 1-3 of the document.
Unlock all 12 pages and 3 million more documents.

Already have an account? Log in
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.
jp
where
jis “Michael Jackson is a software engineer”
pis “Pigs fly”
2. I will go sledding exactly if school is cancelled and it is not windy.
sc∧ ¬w
where
sis “I will go sledding”
cis “School is cancelled”
wis “It is windy”
Name UW Student ID (page 3 of 12)
Unlock document

This preview shows pages 1-3 of the document.
Unlock all 12 pages and 3 million more documents.

Already have an account? Log in

Document Summary

End time: 6:30 p. m: 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. Yes, transformational proof can be used to show an argument is valid. 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. Provide a boolean valuation in which the following two formulas have di erent truth values: Demonstrate that the formulas have di erent truth values in this boolean valuation. You may refer to the truth tables on the last page. A boolean valuation in which the formulas have di erent truth values is: v(a) = f, v(b) = t, v(c) = t v( (a b c))