Department of Mathematics and Statistics
Faculty of Science and Engineering
AS/SC/MATH 1090 3.00: Introduction to Logic for Computer Science
Winter Term - 2009, Section M

Note: this course is a degree program requirement for Computer Science and Computer Engineering majors. It is expected to be taken in the second year of your studies as it is a prerequisite for a number of core (= required) 3rd year CSE courses.

Learning to use Logic, which is what this course is about, is like learning to use a programming language.

In the latter case, familiar to you from courses such as CSE 1020 3.0, one learns the correct syntax of programs, and also learns what the various syntactic constructs do and mean, that is, their semantics. After that, one embarks, for the rest of the course, on sets of increasingly challenging programming exercises, so that the student becomes proficient in programming in said language.

We will do the exact same thing in MATH1090: We will learn the syntax of the logical language, that is, what syntactically correct proofs look like. We will learn what various syntactic constructs "say" (semantics). We will be pleased to know that correctly written proofs are concise and "checkable" means toward discovering mathematical "truths". We will also learn via a lot of practice how to write a large variety of proofs that certify all sorts of useful "truths" of mathematics.

While the above is our main aim, to equip you with a Toolbox that you can use to discover truths, we will also look at the Toolbox as an object of study and study some of its properties (this is similar to someone explaining to you what a hammer is good for before you take up carpentry). This study belongs to the "metatheory" of Logic.

The content of the course will thus be:

The syntax and semantics of propositional and predicate logic and how to build "counterexamples" to expose fallacies. Some basic and important "metatheorems" that employ induction on numbers, but also on the complexity of terms, formulas, and proofs will be also considered. A judicious choice of a few topics in the "metatheory" will be instrumental toward your understanding of "what's going on here". The mastery of these metatheoretical topics will make you better "users of Logic" and will separate the "scientists" from the mere "technicians". There are a number of methodologies for writing proofs, and we will aim to gain proficiency in two of them. The Equational methodology and the Hilbert methodology. In both methodologies an important required component is the systematic annotation of the proof steps. Such annotation explains why we do what we do and has a function similar to comments in a program.

OK, one can grant that a computer science student needs to learn programming. But Logic? Well, the proper understanding of propositional logic is fundamental to the most basic levels of computer programming, while the ability to correctly use variables, scope and quantifiers is crucial in the use of loops, subroutines, and modules, and in software design. Logic is used in many diverse areas of computer science including digital design, program verification, databases, artificial intelligence, algorithm analysis, computability, complexity, and software specification. Besides, any science that requires you to reason correctly to reach conclusions uses logic.

Text: G. Tourlakis, Mathematical Logic, John Wiley & Sons, 2008. ISBN 978-0-470-28074-4

1. Propositional calculus:
   
   • semantics (truth tables);
   • axioms rules of inference and proofs (Hilbert style and Equational);
   • deduction theorem;
   • connection between the truth table techniques and proof techniques (soundness and completeness);
   • resolution.
2. Predicate calculus:
   
   • axioms rules of inference and proofs (Hilbert style and Equational);
   • adding and removing the universal quantifier;
   • deduction theorem;
   • more Leibniz rules;
   • adding and removing the existential quantifier;
   • properties of equality;
   • connection between syntax and semantics (soundness and counterexample building).

1. Three homework assignments worth 45% (15% each) of the total final grade
2. One mid-term (in-class) test worth 20% of the total final grade
3. One Final Exam worth 35% of the total final grade

1. Instructor: Janvier Nzeutchap, TEL Building, #2026, Ext. 33545, Office hours: Wed. 3pm-5pm