Course Meetings

Lectures meet Tuesdays and Thursdays.

Tutorials meet Fridays.

Schedule

A schedule (including tentative due dates) can be found here.

Coursework and Evaluation

Weighting

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 hand-write 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.

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)
	Bandar Al-Dhalaan, Artur Back De Luca, Enamul Haque, Piyush Jha, Farnam Mansouri, Argyris Mouzakis, Joel Rorseth, Mohammad Mohibullah Khan Shirazi, Yetian Wang Teaching Assistants

Whom to Contact

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 first-order 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 first-order 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: well-formed-formulas 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, Davis-Putnam 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, well-formed 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, while-loops, 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.

Other Notices

• Academic Integrity Policies
• Intellectual Property
• Note for Students with Disabilities
• Mental Health Support
• Diversity