COMP 2742 -- Logic for Computer Science, Winter 2014

Announcements | Course information | Assignments and tests | Lecture notes


older announcements...


Course information

Lectures: 12:00-12:50 Monday, Wednesday and Friday in EN-1052
Antonina Kolokolova , email: [Your browser cannot view this email address] , office ER-6033.
Instructor office hours: Monday 2:30-2:30pm and Tuesday 12-1pm, or by appointment.
Textbook: There will be no textbook for this course; the course notes will be posted online.
Reference books:

Marking scheme ( tentative! ): 4 assignments of 10% each, a midterm test 20% and a final exam 40%. Note that the last assignment will be due during the last week of the semester (to provide adequate preparation for the final exam).

Tentative course description
Logic has been called the "calculus of computer science": just as sciences such as physics that deal with continuous realm rely on calculus techniques, we rely on logic. Indeed, so many areas of our field are based on logic: from designing circuits to determining complexity of problems; from verifying correctness of algorithms and devising database queries to automated reasoning in artificial intelligence.

This course is intended to be an introduction to mathematical logic with emphasis on Computer Science applications and methodologies. We will cover propositional and predicate logic with applications to Boolean circuits and database querying, respectively; that will also cover Resolution proof technique, which is the basis of most modern-day automated problem solvers. Then we will discuss basic proof techniques such as mathematical induction, again with computer science applications including proving algorithm correctness. Throughout the course, we will also discuss impossibility results, in particular Goedel's incompleteness theorem.



Assignment 1. Assignment 2. Assignment 3. Assignment 4.

You are encouraged to use LaTeX for typesetting your assignments. A good (though a bit outdated) introduction to LaTeX is "Essential LaTeX" .

Policy on collaboration: The work you submit must be your own. You may discuss problems from assignments with each other; however, you should prepare written solutions alone. Plagiarism is a serious academic offense and will be dealt with accordingly.


Lecture notes

I will be posting lecture notes as we go; you are welcome to check the lecture notes from the previous run of this course. At your suggestion, here is a study guide from CS2742 Winter 2013 . Please consult it for notation that you might not know. This covers all the material from the last Winter's offering of COMP 2742; it is likely that we will cover different material in a different order, etc. In any case, please do not expect that you have to know this before taking this class.