COMP 1002 -- Introduction to Logic for Computer Scientists, Fall 2017
- 16/11/2017 We will have the practice exam in the lab on Nov 30th, 9-11am, for both sections. Please let me know as soon as possible if you would like to write the practice exam, but cannot make it there at that time! The exam is optional; however, your final exam mark will be the maximum of the practice exam and the actual final exam marks.
- 16/11/2017 Since Friday is on Monday schedule, there is an extra lecture for Section 1, 1-2pm on Friday, Nov 17. In order not to get out of sync with Section 2, we will spend this lecture doing more induction examples (to help with assignment 5, which is due next Monday). Section 2 students are also welcome to come, if you are free at that time.
- 1/11/2017 There will be no office hours by Antonina Kolokolova until after Nov 13th (out of town). There will still be office hours by John Shieh.
- 19/10/2017 Clarification on assignment 3: for 1a, it is much easier if you only use predicate Parent. For 1b, however, use both Parent and "=".
- 15/10/2017 Assignment 3 is now posted. Due Oct 23rd, 10pm. Type it up and upload to D2L; here is the LaTeX source.
- 11/10/2017 We very much apologize for the wording in the last example in unification slides... We have removed that example from the lecture slides.
- 11/10/2017 Midterm exam is on Monday, Oct 16th (both sections). It will cover the material from assignments 1 and 2, and labs 1, 2 and 3 (that is, up to and including lecture 11). The midterm is closed-book, no aids allowed. To prepare for the midterm, please see a sample midterm and a study guide .
- 11/10/2017 Remember that Wednesday Oct 11 is on Monday schedule, so Section 1 does have a lecture on Wednesday, Oct 11.
- 30/9/2017 Assignment 2 is now posted. Due Oct 6th, 10pm. Type it up and upload to D2L; here is the LaTeX source, if you'd like to try LaTeX.
- 24/9/2017 Reminder: Assignment 1 is due tomorrow (Monday), at 10pm. Please type it up and submit on D2L, making sure to include your name on the assignment. If you like, you can use LaTeX for typesetting it; here is the LaTeX source,; download LaTeX for your system, or use an online LaTeX editor such as ShareLaTeX. If you have any questions, both instructors have office hours on Mondays: 10-10:45am John Shieh and 5-6pm Antonina Kolokolova.
- 14/9/2017 Assignment 1 is now posted. Due Sep 25th, 10pm. Type it up and upload to D2L; here is the LaTeX source, if you'd like to try LaTeX.
- 13/9/2017 Here is Lab 1 for Sep 19 and Sep 21 lab sections. Please go over the "individual work" portion of the lab in advance, to give you enough time to solve everything.
- 7/9/2017 Office hours by Antonina will be at 5pm on Mondays and Thursdays, in ER-6033.
- 7/9/2017 The first lab for section 1 will be Thursday, Sep 21st, and for section 2 will be Tuesday, Sep 19th.
Course website:
http://www.cs.mun.ca/~kol/courses/1002-f17 . Also see D2L .
Instructors and lectures:
- Section 1: Monday, Tuesday and Thursday, 1pm-1:50pm in SN-2101
Antonina
Kolokolova , email:[Your browser cannot view this email address] , office ER-6033.
- Section 2: Monday, Wednesday and Friday, 11am-11:50am in EN-1052
John Shieh , email:[Your browser cannot view this email address] , office EN-2012.
Labs: Thursday (section 1) / Tuesday (section 2) 9am-11:50am in CS-1019.
Instructor office hours: Antonina Kolokolova: Monday and Thursday, 5-6pm, in ER-6033.
John Shieh: Monday 10-10:45am and Friday 1-1:50pm, in EN-2012.
Textbook: Discrete Mathematics and Its Applications: Kenneth H. Rosen.
Reference book:
Discrete Mathematics With Applications: Susanna S. Epp
Marking scheme:
Lab quizzes 24% total (lowest mark dropped), 5 assignments of 6% each, a midterm test 15% (Oct 16th) and a final exam 31%. Note
that the last assignment may be due during the last week of the
semester (to provide adequate preparation for the final exam).
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, including the 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. We will also touch upon basic combinatorics, counting methods and probability, and theory of computation.
Labs start on Sep 19th (Section 2) and Sep 21st (Section 1). Every lab will end with a quiz, worth 3%; the lowest quiz mark will be dropped. You have to be in the lab to write the quizzes. Tentative lab dates are as follows:
Assignments will be due on Sep 25, Oct 6, Oct 23, Nov 6 and Nov 20. All assignments should be uploaded to D2L by 10pm on the due date.
Please type up your assignment and upload it on D2L as a pdf file. If you know how to use LaTeX (or want to learn an easy way to typeset mathematics), this would be a perfect choice; otherwise, use whichever word processor you are comfortable with.
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.
I will be posting slides as we go; you are welcome to check the slides from the previous semester.
- 7/9/2017 Lecture 1: Introduction
- 11/9/2017 Lecture 2: Language of logic, truth tables
- 12/9/2017 Lecture 3: Knights and knaves, negation, de Morgan's laws
- 14/9/2017 Lecture 4: Negation, de Morgan's laws, simplifications
- 18/9/2017 Lecture 5: More on simplifications, equivalences
- 19/9/2017 Lecture 6: Implications, contrapositive, converse, inverse
- 21/9/2017 Lecture 7: Natural deduction, arguments, validity, modus ponens
- 25/9/2017 Lecture 8: Resolution, CNFs, million dollar problem
- 26/9/2017 Lecture 9: Formulas vs. circuits, canonical CNF/DNF, complete set of connectives
- 28/9/2017 Lecture 10: Sets, predicates, quantifiers
- 2/10/2017 Lecture 11: Mixed quantifiers and negation, prenex normal form
- 3/10/2017 Lecture 12: Theorems, theories, axioms, counterexamples
- 5/10/2017 Lecture 13: Rules of inference in predicate logic, universal modus ponens, instantiation/generalization
- 11/10/2017 Lecture 14: Resolution in predicate logic, unification
- 17/10/2017 Lecture 15: Types of proofs, modular arithmetic, direct proofs and proofs by contraposition
- 19/10/2017 Lecture 16: Proofs by cases, square root of 2 is irrational, operations on sets
- 23/10/2017 Lecture 17: Cardinalities, powersets, cartesian product, laws of set theory, Boolean algebra
- 24/10/2017 Lecture 18: Relations and functions
- 26/10/2017 Lecture 19: Countable and uncountable sets, diagonalization, Halting problem
- 30/10/2017 Lecture 20: Properties of binary relations, equivalences, orders
- 31/10/2017 Lecture 21: Sequences, recurrences, growth of functions
- 2/11/2017 Lecture 22: Recursive definitions of sets, trees. Grammars.
- 6/11/2017 Lecture 23: Fractals, regular languages, finite automata, Turing machines Fractal grower
- 7/11/2017 Lecture 24: Mathematical induction
- 9/11/2017 Lecture 25: Structural induction
- 14/11/2017 Lecture 26: Combinatorics
- 16/11/2017 Lecture 27: Probabilities
- 20/11/2017 Lecture 28: Conditional probabilities, independence, Monty Hall puzzle
- 21/11/2017 Lecture 29: Bayes theorem, expectations