COMP 2742 -- Logic for Computer Science, Winter 2013

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: Mon 4pm, Tue 2pm and Thur 12pm, or by appointment.
Textbook: There will be no textbook for this course; however, the course notes will be posted online.
Reference books:

Marking scheme ( tentative! ): ~5 assignments of 7% each, two midterm tests 15% each and a final exam 35%. 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. ( LaTeX source ) Due Jan 23, 2013 Assignment 2. ( LaTeX source ) Due Feb 1, 2013.
Assignment 3. Feb 25, 2013. ( LaTeX source ) Assignment 4. Due March 11, 2013. ( LaTeX source )
Assignment 5. Due Apr 3, 2013.

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.

A study guide for the first test. A study guide for the second test. A study guide for the final exam.