[UW Logo]

CS 245: Logic and Computation, Winter 2015

David R. Cheriton School of Computer Science

Contents: General Info, Time and Place, Personnel, Announcements, Course Work, Assignments, Resources, Lectures, Tutorials, University Policies


Piazza for announcements and questions.

Learn for marks and assignment solutions.

link to F14 web page

General Information

Time and Place


Tutorials: General Office Hours (changes for specific weeks will be posted on Piazza): Pick-up times for the assignments will be announced on Piazza.


Instructor: Anna Lubiw, DC2334, x34449, alubiw "at" cs.uwaterloo.ca

Support Coordinator: Ahmed HajYasien, ahajyasien

The Support Coordinator handles much of the administrative paperwork for all sections. See the support coordinator regarding

Do not submit requests for changes of section to the Support Coordinator (nor to an instructor). If Quest does not allow you to make a change yourself, contact a CS advisor.

Instructional Assistants: (lead tutorials and hold tutor office hours in the Consulting Centre)


Please see Piazza for questions and announcements.

Course Work


Midterm: The midterm will be Thursday, February 26, 4:30-6:20pm. The midterm will cover all the material up to reading week. You will be given the handouts on logical identities and natural deduction.

Exam: The final exam will be Saturday April 18 at 9 AM. The exam covers the whole course.


The work you hand in must be your own. Acknowledge any sources you have used. You may discuss the assignment questions verbally with others, but you should come away from these discussions with no written or electronic records. Write your solutions in your own words, from your own head.

Assignments are due Mondays, at 4:30pm, in the drop box near MC 4065. No late assignments are allowed, but note that you can skip one assignment without penalty since we only count the best 9 of 10.

Pick-up times for assignments will be announced on Piazza. Solutions will be posted on LEARN.

1 [pdf] Mon. Jan. 12, 4:30pm
2 [pdf] Mon. Jan. 19, 4:30pm
3 [pdf] Mon. Jan. 26, 4:30pm
4 [pdf] Mon. Feb. 2, 4:30pm
5 [pdf] Mon. Feb. 9, 4:30pm
6 [pdf] Mon. Feb. 23, 4:30pm
7 [pdf] Mon. Mar. 9, 4:30pm
8 [pdf] Mon. Mar. 16, 4:30pm
9 [pdf] Mon. Mar. 23, 4:30pm
10 [pdf] Wed. April 1, 4:30pm


Books: Handouts:


Here is a list of the topics covered in each lecture, with the corresponding text book sections, and the lecture notes from class.

L01 Tu Jan  6 Notes Introduction. [H&R] 1.1 [Niss] Ch. 1 and 2.
L02 Th Jan  8 Notes Truth Tables, well-formed formulas. [H&R] 1.3, 1.4.1 [Niss] 3.1 - 3.4
L03 Tu Jan  13 Notes Adequate sets of connectives, equivalence,
logical implication, logical identities.
[Niss] 3.5, 3.7
L04 Th Jan  15 Notes Proofs using logical identities, digital circuits. [Niss] 3.8 (circuits), Ch. 4 (logical identities).
L05 Tu Jan  20 Notes Application of logical identities to code simplification,
start of natural deduction.
[H&R] 1.2.1
L06 Th Jan  22 Notes Natural deduction. [H&R] 1.2.1
L07 Tu Jan  27 Notes Natural deduction is sound and complete.
Conjunctive Normal Form.
[H&R] these topics are in Ch. 1,
but in too much detail.
L08 Th Jan  29 Notes Resolution.
L09 Tu Feb  3 Notes Resolution, resolution refutation, satisfiability.
L10 Th Feb  5 Notes Predicate logic [H&R] 2.1, 2.2.1, 2.2.2
L11 Tu Feb  10 Guest lecture by Nancy Day.
L12 Th Feb  12 Review tutorials -- see Tutorial 6 below.
L13 Tu Feb  24 Notes Interpretations for Predicate logic. [H&R] 2.4 (though terminology differs)
L14 Th Feb  26 Notes Natural Deduction [H&R] 2.3 (though terminology differs)
L15 Tu Mar  3 Notes Natural Deduction [H&R] 2.3 (though terminology differs)
L16 Th Mar  5 Notes Resolution
L17 Tu Mar  10 Notes last part of Resolution. Undecidability.
L18 Th Mar  12 Notes Equality. Peano Arithmetic.
L19 Tu Mar  17 Notes Peano Arithmetic and Induction.
L20 Th Mar  19 Notes Program Verification. [H&R] Ch. 4
L21 Tu Mar  24 Notes Program Verification continued. [H&R] Ch. 4
L22 Th Mar  26 Notes Program Verification continued. [H&R] Ch. 4
L23 Tu Mar  31 Notes Undecidability.
L24 Th April  2 see Summary above Review.


Here is some tutorial material (no guarantee this is precisely what's covered).

T01 Fri Jan  9 Notes
T02 Fri Jan  16 Notes
T03 Fri Jan  23 Notes
T04 Fri Jan  30 Notes
T05 Fri Feb  6 Notes
T06 Thu Feb  12 Notes This was a review session.
T07 Fri Mar  6 Notes
T08 Fri Mar  13 Notes
T09 Fri Mar  20 Notes
T10 Fri Mar  27 Notes

University Policies (University required text)

This course adheres to the UW Senate's statement of academic integrity, specifically:

Academic Integrity

In order to maintain a culture of academic integrity, members of the University of Waterloo community are expected to promote honesty, trust, fairness, respect and responsibility. All members of the UW community are expected to hold to the highest standard of academic integrity in their studies, teaching, and research.

The Office of Academic Integrity's website contains detailed information on UW policy for students and faculty. This site explains why academic integrity is important and how students can avoid academic misconduct. It also identifies resources available on campus for students and faculty to help achieve academic integrity in—and out of—the classroom.


A student who believes that a decision affecting some aspect of his/her university life has been unfair or unreasonable may have grounds for initiating a grievance. Read Policy 70-Student Petitions and Grievances, Section 4.


A student is expected to know what constitutes academic integrity, to avoid committing academic offenses, and to take responsibility for his/her actions. A student who is unsure whether an action constitutes an offense, or who needs help in learning how to avoid offenses (e.g., plagiarism, cheating) or about rules for group work/collaboration should seek guidance from the course professor, academic advisor, or the Undergraduate Associate Dean. When misconduct has been found to have occurred, disciplinary penalties will be imposed under Policy 71—Student Discipline. For information on categories of offenses and types of penalties, students should refer to Policy 71—Student Discipline.

Avoiding Academic Offenses

For information on commonly misunderstood academic offenses and how to avoid them, students should refer to the Faculty of Mathematics Cheating and Student Academic Discipline Guidelines.


A student may appeal the finding and/or penalty in a decision made under Policy 70—Student Petitions and Grievances (other than regarding a petition) or Policy 71—Student Discipline if a ground for an appeal can be established. Read Policy 72—Student Appeals.

Note for students with disabilities

The Office for Persons with Disabilities (OPD), located in Needles Hall, Room 1132, collaborates with all academic departments to arrange appropriate accommodations for students with disabilities without compromising the academic integrity of the curriculum. If you require academic accommodations to lessen the impact of your disability, please register with the OPD at the beginning of each academic term.