# Final + Solution of Winter 2005 useful for practice

135 views14 pages
16 Oct 2011
School
Course
Professor

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
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)
Unlock document

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

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 fa function? Yes
Is ftotal? Yes
Is finjective? Yes
Is fsurjective? 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)
Unlock document

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

2 (7 Marks) Propositional Logic: Transformational Proof
Prove the following using transformational proof:
(p∨ ¬q)∧ ¬(p((rq)p)) ¬(qp)
(p∨ ¬q)∧ ¬(p((rq)p))
(p∨ ¬q)∧ ¬(p(¬(rq)p)) Impl
(p∨ ¬q)∧ ¬pSimp II
(p∧ ¬p)(¬q∧ ¬p) Distr
false (¬q∧ ¬p) Contr
¬q∧ ¬pSimp I
¬(qp) DM
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.