Midterm + solution of Fall 2003 usefule for practice

62 views14 pages
Published on 16 Oct 2011
School
University of Waterloo
Department
Computer Science
Course
CS245
Professor
University of Waterloo
Final Examination
SOLUTION SET
Term: Fall Year: 2003
Student Name
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
Total 100
CS245 Name UW Student ID Number (page 1 of 14)
Unlock document

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

Already have an account? Log in
2 (6 Marks) Short Answer
1. (2 marks) For f:A7B, if #A > #B, answer whether fis total or not, injective or not,
and surjective or not. Also, write the type of f.
Yes No
Total
Injective
Surjective
Type of f
BA
2. (1 mark) Write a formula in set theory that means that two sets Aand Bare disjoint. (Do
not use quantiﬁers.)
AB=
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.
Possible answers:
cost
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)
Unlock document

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

Already have an account? Log in
3 (6 Marks) Propositional Logic: Transformational Proof
Prove the following using transformational proof:
cd⇒ ¬db∧ ¬cWV ¬(¬dc)
cd⇒ ¬db∧ ¬c
WV ¬(cd)∨ ¬db∧ ¬cImpl
WV ¬c∧ ¬d∨ ¬db∧ ¬cDM
WV ¬d∧ ¬c∨ ¬d∧ ¬cbComm ×2
WV ¬d∧ ¬cSimp II
WV ¬(dc) DM
WV ¬(¬¬dc) Neg
WV ¬(¬dc) Impl
CS245 Name UW Student ID Number (page 3 of 14)
Unlock document

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

Already have an account? Log in

Document Summary

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)