# Midterm + solution of Fall 2003 usefule for practice

62 views14 pages

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)

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∼.

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.)

A∩B=∅

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)

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)

## 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)