# CS 245: Logic and Computation — Winter 2019

## General Information

• Course Description: Propositional and predicate logic. Soundness and completeness and their implications. Unprovability of formulae in certain systems. Undecidability of problems in computation, including the halting problem. Reasoning about programs. Correctness proofs for both recursive and iterative program constructions.
• Objectives: At the end of the course, students should be able to
• Formalize English sentences into properly formed formulae in the propositional and predicate logics and to interpret such formulae in English
• Prove the correctness (or incorrectness) of simple formulae in the propositional and predicate logic by natural deduction (or by counterexample) and find errors in purported proofs
• Describe transformational (algebraic) proof for proving statements in the propositional and predicate logic
• Explain the concepts of partial decidability and of undecidability giving examples of each; apply reductions to demonstrate certain problems have these difficulties
• Annotate short programs with loop or recursive invariants to aid in debugging and proving assertions about simple programs
• Prove the correctness of simple programs in a functional language and in a basic subset of an imperative language
• Handbook 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 discrete mathematics skills
• Improve knowledge of propositional and predicate logic, including key notions, such as the distinction between syntax and semantics and between "provable" and "valid"
• Explore the limits of computers, including computability and non-computabilty
• Use logical skills to reason about computer programs
• CS245 2019 Topics

David R. Cheriton School of Computer Science
University of Waterloo