Logic and Computation Fall 2024
CS 245

Course 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

Topic Overview

Introduction

• History, motivation, connections to computer science

Propositional Logic

• Connectives, truth tables, translation between English and propositional logic
• Syntax: formulas in propositional logic. Structural induction and its use in proving statements about formulas
• Semantics: truth valuations, 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 Forms
• Adequate sets of connectives
• 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: Automated proofs: Resolution, Davis-Putnam Procedure; Hardware and software verification

First-Order Logic

• Limitations of propositional logic, and the necessity of first-order logic for reasoning about objects and properties
• Quantifiers, universe of discourse, translation between English and first-order logic formulas
• Syntax of first-order logic, terms, formulas
• Semantics of first-order logic, valuations
• Proving argument validity in first-order logic (semantically)
• Formal deduction in first-order logic; Proving argument validity by formal deduction (syntactically)
• Applications of first-order logic to computer science, such as: Automated theorem provers and verifiers; Databases

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

An Important Application of Logic to Computer Science

• program verification:
  • Hoare triples
  • inference rules for assignments, conditionals, while-loops
  • partial and total completeness

The tentative course schedule is available on the course Web site: https://student.cs.uwaterloo.ca/~cs245/F22/.

Notes:

1. You must pass the weighted exam portion of the course (Midterm Exam, Final Exam) in order to pass the course.
2. Students will not be exempted from more than two Crowdmark assignments for any reason.
3. Here are the details about how late Crowdmark assignments will be handled:
   1. For full credit, you must submit your solutions by the specified due date and time.
   2. A 3% late penalty will be applied for each hour that you are late in submitting.
   3. If you have submitted anything before the deadline, then Crowdmark will not let you re-submit after the deadline passes. This means that you must decide whether to exercise your option to submit late before the deadline, and refrain from making a partial submission in this case.
4. Here are the details about how the practice quizzes will work:
   1. There will be at least one practice quiz per week.
   2. The purpose of the practice quizzes is to give you more frequent practice with the course material than the Crowdmark assignments will.
   3. Each practice quiz will be automatically graded once you submit it, so that you will have immediate feedback about how you did.
   4. You may take each practice quiz as many times as you like.
5. Here are the details about how the marked quizzes will work:
   1. There will be a marked quiz due in each week when there will not be a Crowdmark assignment due or a mid-term examination. The due dates for the marked quizzes are displayed on the course schedule page.
   2. No late submissions of marked quizzes will be accepted.
   3. From the time you start taking the marked quiz, you will have one hour in which to complete it. You must submit your quiz before this hour elapses and before the due date and time to receive credit.
   4. You will have a maximum of two attempts at each marked quiz. If you make two attempts, then the higher grade will count.
   5. Your grading for each marked quiz will be displayed on LEARN after the due date and time has passed.
   6. Your marked quiz will be randomly customized for you. We will ensure that the variations of any given question are all of the same difficulty.

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. [Check the Office of Academic Integrity for more information.]

Grievance: A student who believes that a decision affecting some aspect of their university life has been unfair or unreasonable may have grounds for initiating a grievance. Read Policy 70, Student Petitions and Grievances, Section 4. When in doubt, please be certain to contact the department’s administrative assistant who will provide further assistance.

Discipline: A student is expected to know what constitutes academic integrity to avoid committing an academic offence, and to take responsibility for their actions. [Check the Office of Academic Integrity for more information.] A student who is unsure whether an action constitutes an offence, or who needs help in learning how to avoid offences (e.g., plagiarism, cheating) or about “rules” for group work/collaboration should seek guidance from the course instructor, academic advisor, or the undergraduate associate dean. For information on categories of offences and types of penalties, students should refer to Policy 71, Student Discipline. For typical penalties, check Guidelines for the Assessment of Penalties.

Appeals: A decision made or penalty imposed under Policy 70, Student Petitions and Grievances (other than a petition) or Policy 71, Student Discipline may be appealed if there is a ground. A student who believes they have a ground for an appeal should refer to Policy 72, Student Appeals.

Note for students with disabilities: AccessAbility Services, located in Needles Hall, Room 1401, 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 AccessAbility Services at the beginning of each academic term.

Turnitin.com: Text matching software (Turnitin®) may be used to screen assignments in this course. Turnitin® is used to verify that all materials and sources in assignments are documented. Students' submissions are stored on a U.S. server, therefore students must be given an alternative (e.g., scaffolded assignment or annotated bibliography), if they are concerned about their privacy and/or security. Students will be given due notice, in the first week of the term and/or at the time assignment details are provided, about arrangements and alternatives for the use of Turnitin in this course.

It is the responsibility of the student to notify the instructor if they, in the first week of term or at the time assignment details are provided, wish to submit alternate assignment.