Midterm + solution of Fall 2003 usefule for practice
62 views14 pages
University of Waterloo
Term: Fall Year: 2003
UW Student ID Number
Course Abbreviation and Number CS245
Course Title Logic and Computation
Sections 001 and 002
Instructor Nancy Day
Date of Exam Monday, December 8, 2003
Time Period Start time: 9:00 a.m. End time: 12:00 noon
Duration of Exam 3 hours
Number of Exam Pages 14 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.
•Happy Holidays everyone!
Question Mark Max Marker Question Mark Max Marker
1 1 (Bonus) 8 9
2 6 9 7
3 6 10 10
4 4 11 8
5 5 12 5
6 11 13 9
7 10 14 9
CS245 Name UW Student ID Number (page 1 of 14)
2 (6 Marks) Short Answer
1. (2 marks) For f:A7→B, if #A > #B, answer whether f∼is total or not, injective or not,
and surjective or not. Also, write the type of f∼.
Type of f∼
2. (1 mark) Write a formula in set theory that means that two sets Aand Bare disjoint. (Do
not use quantiﬁers.)
3. (1 mark) What does the term “paradox” mean?
A paradox is a sound argument that leads to a contradiction.
4. (2 marks) Name two factors that are relevant in determining whether or not it was worthwhile
to carry out formal veriﬁcation of the software in the Darlington Nuclear Power Plant.
•potential loss of life associated with a software bug
•potential environmental damage associated with a software bug
•availability of skilled workers
•reliability of the hardware
CS245 Name UW Student ID Number (page 2 of 14)
3 (6 Marks) Propositional Logic: Transformational Proof
Prove the following using transformational proof:
c∨d⇒ ¬d∧b∧ ¬cWV ¬(¬d⇒c)
c∨d⇒ ¬d∧b∧ ¬c
WV ¬(c∨d)∨ ¬d∧b∧ ¬cImpl
WV ¬c∧ ¬d∨ ¬d∧b∧ ¬cDM
WV ¬d∧ ¬c∨ ¬d∧ ¬c∧bComm ×2
WV ¬d∧ ¬cSimp II
WV ¬(d∨c) DM
WV ¬(¬¬d∨c) Neg
WV ¬(¬d⇒c) Impl
CS245 Name UW Student ID Number (page 3 of 14)
End time: 12:00 noon (cid:15) write your name and student number at the bottom of every page. (cid:15) write all solutions on the exam. The booklets are for scratch work. (cid:15) happy holidays everyone! Uw student id number (page 1 of 14) 2 (6 marks) short answer: (2 marks) for f : a 7(cid:26)! B, if #a > #b, answer whether f (cid:24) is total or not, injective or not, and surjective or not. B (cid:26) a: (1 mark) write a formula in set theory that means that two sets a and b are disjoint. (do not use quanti(cid:12)ers. ) Possible answers: (cid:15) cost (cid:15) potential loss of life associated with a software bug (cid:15) potential environmental damage associated with a software bug (cid:15) availability of skilled workers (cid:15) reliability of the hardware. Uw student id number (page 2 of 14)