For unlimited access to Study Guides, a Grade+ subscription is required.

University of Waterloo

Final Examination

SOLUTION SET

Term: Winter Year: 2005

Student Name

UW Student ID Number

Course Abbreviation and Number SE112/CS245

Course Title Logic and Computation

Sections SE112-001, CS245-001, 002

Instructor Nancy Day

Date of Exam Friday, April 8, 2005

Time Period Start time: 2:00 p.m. End time: 5:00 p.m.

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.

•Enjoy the summer everyone!

Question Mark Max Marker Question Mark Max Marker

7 5

1 6 8 9

2 7 9 7

3 5 10 10

4 5 11 10

5 10 12 10

6 7 13 9

Total 100

Name UW Student ID Number (page 1 of 14)

1 (6 Marks) Short Answer

1. (1 mark) What is the diﬀerence between partial correctness and total correctness in program

veriﬁcation?

Total correctness requires termination and partial correctness does not require termination.

or

Total correctness = partial correctness + termination

2. (1 mark) Write a formula that is an invariant of every loop.

true or a∨ ¬a, etc.

All tautologies are invariants of every loop.

3. (1 mark) If we prove that the set of propositional logic formulas containing a, b, ¬cis incon-

sistent, does that mean that the set containing a, b, c is consistent? Circle “yes” or “no”. No

explanation is required.

No, aand bcould be inconsistent by themselves and changing the third formula wouldn’t

matter.

4. (2 marks) For f:A→Bwhere #A= #B, answer the following (circle “yes” or “no”; no

explanation is required):

Is f∼a function? Yes

Is f∼total? Yes

Is f∼injective? Yes

Is f∼surjective? Yes

5. (1 mark) What does it mean if a proof procedure is not complete?

Using the proof procedure, you may not be able to ﬁnd a proof for a valid argument.

Name UW Student ID Number (page 2 of 14)

2 (7 Marks) Propositional Logic: Transformational Proof

Prove the following using transformational proof:

(p∨ ¬q)∧ ¬(p∧((r∧q)⇒p)) ⇚⇛ ¬(q∨p)

(p∨ ¬q)∧ ¬(p∧((r∧q)⇒p))

⇚⇛ (p∨ ¬q)∧ ¬(p∧(¬(r∧q)∨p)) Impl

⇚⇛ (p∨ ¬q)∧ ¬pSimp II

⇚⇛ (p∧ ¬p)∨(¬q∧ ¬p) Distr

⇚⇛ false ∨(¬q∧ ¬p) Contr

⇚⇛ ¬q∧ ¬pSimp I

⇚⇛ ¬(q∨p) DM

Name UW Student ID Number (page 3 of 14)