Computer Science 2742 -- Logic for Computer Science, Fall 2008
07/12/2008 All lecture notes are now posted. Let me know if you notice mistakes or omissions.
05/12/2008 Corrected a typo in the table on page 5 of the study guide. Thank you very much for pointing it out to me! Please let me know if you notice any more errors or omissions.
04/12/2008 Here are the (corrected) term marks. Please let me know by no later than Monday if any of your assignments or test marks are missing or recorded incorrectly. If you are one of the people with the red empty cell in place of the term mark, please email me immediately!
03/12/2008 Solutions for assignment 5 are now posted. Let me know if there are any mistakes or omissions.
03/12/2008 There will be pre-exam office hours on Monday, Dec 8th, 12pm-4pm. If you would like to see me at some other time, please send me an email.
03/12/2008 Study guide for the final exam is now posted. Let me know if there are any mistakes or omissions.
Old announcements
Course Information Sheet
Lectures: 12:00-12:50 Monday, Wednesday and Friday in EN-1051
Instructor: Antonina
Kolokolova , email: [Your browser cannot view this email address] , office ER-6011.
Instructor office hours: M/W 13:00-13:50
or by appointment.
Textbook: There will be no textbook for this course. We may have some reference books later on.
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).
You are encouraged to use LaTeX for typesetting your assignments. A good introduction to LaTeX is
"Essential LaTeX" .
A study guide for the first test.
A study guide for the second test.
A study guide for the final exam.
- 5/9/2008 Lecture 1: Introduction and beginning of propositional logic
- 8/9/2008 Lecture 2: Truth tables and evaluating propositional formulas.
- 10/9/2008 Lecture 3: Logical identities, equivalences, simplifying propositional formulas.
- 12/9/2008 Lecture 4: Logical equivalences involving implication, contrapositives, types of proofs
- 15/9/2008 Lecture 5: Proof by cases, valid/invalid arguments, modus ponens, rules of inference, CNFs and DNFs
- 17/9/2008 Lecture 6: More about implications, CNFs and DNFs
- 19/9/2008 Lecture 7: Resolution proof system
- 22/9/2008 Lecture 8: Boolean functions, complete set of connectives
- 24/9/2008 Lecture 9: Boolean and arithmetic circuits
- 26/9/2008 Lecture 10: introduction to predicate logic
- 29/9/2008 Lecture 11: Predicate logic: applications to databases, alternation of quantifiers
- 1/10/2008 Lecture 12: Reasoning in predicate logic
- 3/10/2008 Lecture 13: Normal forms, resolution for finite domains, limitations of first-order logic, quantifiers on empty domain.
- 6/10/2008 Lecture 14: Intro set theory, Venn diagrams
- 8/10/2008 Lecture 15: Defining numbers, Russell's paradox, barber of seville
- 17/10/2008 Lecture 16: Proving statements about sets, Boolean algebras.
- 20/10/2008 Lecture 17: Power sets, halting problem
- 22/10/2008 Lecture 18: Functions
- 24/10/2008 Lecture 19: More functions, proving equivalences with N, diagonalization
- 27/10/2008 Lecture 20: Relations, equivalences, transitivity, Caesar cipher
- 29/10/2008 Lecture 21: Cryptography
- 31/10/2008 Lecture 22: Partial orders
- 03/11/2008 Lecture 23: Well-ordering principle, mathematical induction
- 05/11/2008 Lecture 24: More examples of induction
- 07/11/2008 Lecture 25: Strong induction
- 10/11/2008 Lecture 26: Example of using induction: existence and uniqueness of binary representation
- 12/11/2008 Lecture 27: Structural induction, recursive definition, equivalences between induction, strong induction and well-ordering
- 14/11/2008 Lecture 28: Growth of functions, recursively defined functions
- 17/11/2008 Lecture 29: Algorithm correctness, loop invariants
- 24/11/2008 Lecture 30: Recursive algorithm correctness, binary search
- 26/11/2008 Lecture 31: Hilbert's program, theories of arithmetic, Goedel's incompleteness theorems
- 28/11/2008 Lecture 32: Peano Arithmetic, idea of the proof of Goedel's incompleteness theorems