Course Meetings
Lectures meet Tuesdays and Thursdays.
Section  Time (Tue & Thu)  Room  Instructor 

LEC 001  10:00am–11:20am  MC 1056  Kris Frasheri 
LEC 002  11:30am–12:50pm  MC 1056  Yizhou Zhang 
LEC 003  1:00pm–2:20pm  MC 4021  Yizhou Zhang 
Tutorials meet Fridays.
Section  Time (Friday)  Room 

TUT 101  9:30am–10:20am  MC 4040 
TUT 102  10:30am–11:20am  MC 4040 
TUT 103  11:30am–12:20pm  MC 4058 
TUT 104  12:30pm–1:20pm  MC 4058 
Schedule
A schedule (including tentative due dates) can be found here.
Coursework and Evaluation
Weighting
Assignments  20% 
Midterm Exam  30% 
Final Exam  50% 
Assignments
 Assignments will be submitted, and results distributed, via Crowdmark.
 Late submissions for assignments receive a mark of zero. Submit early and often, so that you have time to resolve any technical issues with Crowdmark before the due time.
 Make sure that your submissions are easily readable, especially if you choose to handwrite your answers, take photos of them, and upload the photos.
 Do your own work. In your submissions, acknowledge everyone you consulted when working on the assignment. 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.
Exams
 Exams will be written in person. The written papers will be scanned and uploaded into Crowdmark for marking.
 You must pass the exams (by weighted average) to pass the course.
Examples:
 A student gets 40% on the midterm and 60% on the final. The weighted
average of the exams is
(40%×30% + 60%×50%)/(30%+50%) = 52.5%.
The student passes the exams.  A student gets 60% on the midterm and 40% on the final. The weighted
average of the exams is
(60%×30% + 40%×50%)/(30%+50%) = 47.5%.
The student fails the exams and thus fails the course.
 A student gets 40% on the midterm and 60% on the final. The weighted
average of the exams is
Piazza
This course uses Piazza as an online discussion forum. You are encouraged to post any questions you might have about the course material. For administrative questions unrelated to the course material, please see below for whom to contact. The course staff monitor the forum regularly, and you will usually get a response within two business days if you make your question clear.
You are encouraged to answer questions on Piazza. Thinking through other students' questions and writing down a response is a good exercise and earns you good karma. But please avoid giving away details of your solution to any homework problems.
By default, your posts are visible to the course staff and other students, and you should prefer this mode so that others can benefit from your question and the answer. However, you can post privately so that only the course staff can see your question, and you should do so if your post might reveal information about a solution to a homework problem. If you post privately, we reserve the right to make your post public if we think the class will benefit. You can post anonymously if you wish not to reveal your identity to other students.
The discussion forum is the most effective way to communicate with the course staff. However, please do not post things that add no useful technical information; posts like "I have the same question as this one posted" or "I agree with this comment" should be avoided.
Important course announcements will be posted on Piazza, so check in often.
Course Staff and Office Hours
Office hours start in the second week of classes. Times and locations are subject to change. For questions concerning course material, please join us during the instructors' and the instructional apprentices' office hours. For administrative questions, contact the coordinator, Dalibor Dvorski.
Kris Frasheri
Instructor 
Office hour: Tuesdays, 15:00–16:00 (on campus: DC 2127)  
Yizhou Zhang
Instructor 
Office hour: Wednesdays, 12:00–13:00 (online: Zoom) 

Dalibor Dvorski Course Coordinator 
Email: ddvorski@uwaterloo.ca  
Jianlin Li Instructional Apprentice 
Office hours: Tuesdays, 9:00–10:00
(online: Teams)
and Fridays, 13:30–15:30 (on campus: MC 4065) 

Pablo Millán Arias Instructional Apprentice 

Monireh Safari Instructional Apprentice 
Office hours: Mondays, 12:00–14:00 (online: Teams)  
Teaching Assistants 
Whom to Contact
Course overrides  CS advisors: https://cs.uwaterloo.ca/advising 
Course material and assignment clarifications  Make a public post on Piazza or bring up during office hours 
Regrading requests  Regrading requests are handled through LEARN dropboxes. Instructions will be posted after release of marks. 
Course access including late enrollment  Coordinator: ddvorski@uwaterloo.ca 
Illness or unforeseen circumstances  Coordinator: ddvorski@uwaterloo.ca 
Crowdmark issues  Coordinator: ddvorski@uwaterloo.ca 
Incompletes (INCs)  Coordinator: ddvorski@uwaterloo.ca 
Accessability requests  AccessAbility Services: https://uwaterloo.ca/accessabilityservices 
Course Overview
Description
CS 245 plays a key role in the development of mathematical skills required in the Computer Science program, and thus complements MATH 135 (Algebra), MATH 239 (Graph Theory and Enumeration), and STAT 230 (Probability). The course covers a variety of topics related to logic and computation that are required as background for other courses in computer science. It differs both in tone and content from a logic course one would typically find in a mathematics program. The course aims to
 Develop mathematical reasoning skills
 Improve understanding of propositional and firstorder logic, including key notions, such as: expressing natural language statements as logical formulas, distinguishing between correct and incorrect reasoning (between valid and invalid logical arguments), constructing a formal proof, distinguishing between syntax and semantics
 Explore the limits of computers, including decidability and undecidability
Objectives
At the end of the course, students should be able to
 Formalize English sentences into properly formed formulas in propositional and firstorder logic and, conversely, interpret such formulas in English
 Formalize the notion of correct reasoning and proof, and be able to construct formal proofs
 Realize the limitations of formal proof systems
 Understand the applications of logic to computer science
Syllabus
 introduction: history, motivation, connections to computer science
 propositional logic
 connectives, truth tables, translation of English sentences into propositional logic syntax: wellformedformulas in propositional logic; structural induction and its use in proving statements about logic formulas
 semantics: value assignments, how to (semantically) prove that arguments in propositional logic are valid (i.e., correct, sound)
 essential laws for propositional logic, formula simplification, Conjunctive/Disjunctive Normal Form(s)
 adequate set of connectives
 Boolean algebra, logic gates, circuit design, circuit minimization
 formal deduction for propositional logic; proving arguments valid by formal deduction (syntactically)
 soundness and completeness of formal deduction
 applications of propositional logic to computer science, such as: analysis and simplification of code; automated proofs: resolution, DavisPutnam Procedure; hardware and software verification
 predicate logic:
 limitations of propositional logic, and the necessity of predicate logic for reasoning about objects and properties
 quantifiers, universe of discourse, translation of English sentences into predicate logic formulas
 syntax of predicate logic, wellformed formulae
 semantics of predicate logic, interpretations
 proving argument validity in predicate logic (semantically)
 formal deduction in predicate logic; proving argument validity by formal deduction (syntactically)
 applications of predicate logic to computer science, such as theorem provers
 decidability and Peano arithmetic:
 Turing machine as a model of computation
 undecidability: basic notions, undecidability of the halting problem and other problems
 the Peano axioms for number theory (including the induction axiom), undecidability of Peano arithmetic
 Gödel's incompleteness theorem
 program verification, an important application of logic to computer science:
 Hoare triples
 inference rules for assignments, conditionals, whileloops, arrays
 partial and total completeness
Recommended Text
The recommended textbook is Mathematical Logic for Computer Science (2nd Edition) by Lu Zhongwan. Students may access an electronic version of the textbook through the library. Please note that this book does not cover all the material presented in the course, and is meant mainly for definitions, notation, and the sections on formal deduction. For the rest of the material, students should use the lecture slides as the main reference. Lecture slides are available electronically on LEARN.