Prof Hayward's homepage for CMPUT 272 (fall 2011) formal systems and logic

• instructor: Prof. Hayward
• Required Text: Edward A. Bender and S. Gill Williamson. "A Short Course in Discrete Mathematics". Dover (2005), ISBN 0-486-43946-1 (also available on the web at no cost).
• Required Extra Material: Variants and Invariants.

• assignments
  • 1 2 3 4 5 midterm A midterm B
• lecture notes
  • unit BF
  • unit Lo
  • beans
  • unit NT
  • crypto
  • sets
  • functions
  • equivalence/order
• book of the day
• old midterm
• old final

lecture schedule (sign in to moodle to see assignments, sample exams, and seminar coverage)

week	date	topics
1	Sep 8	overview   extra material: variants and invariants
2	Sep 13-15	BF 1: boolean functions   BF 2: number systems and computer arithmetic
3	Sep 20-22	Lo 1: propositional logic
4	Sep 27-29	Asn #1 due 1230 Sep 27   Lo 2: predicate logic
5	Oct 4-6	NT 1: basic facts about numbers
6	Oct 11-13	Asn #2 due 1230 Oct 11   NT 2: cryptography and secrecy
7	Oct 18-20	Midterm Oct 20 (in class, closed book, coverage to end of week 6)
8	Oct 25-27	SF 1: sets
9	Nov 1-3	Asn #3 due 1230 Nov 1   SF 2: functions
10	Nov 8	IS 1: induction
11	Nov 15-17	Asn #4 due 1230 Nov 15   EO 1: equivalence
12	Nov 22-24	EO 2: order
13	Nov 29-Dec 1	Asn #5 due 1230 Nov 29   EO 2: order
14	Dec 6	review

university calendar description CMPUT 272 Formal Systems and Logic (see also department course description) *3 (fi 6) (either term, 3-1s-1.5). An introduction to the tools of set theory, logic, and induction, and their use in the practice of reasoning about algorithms and programs. Basic set theory. The notion of a function. Counting. Propositional and predicate logic and their proof systems. Inductive definitions and proofs by induction. Program specification and correctness. Prerequisites: Any 100-level CMPUT course or SCI 100.

course objectives This course is the first theory course in computing science and its nature is mathematical. You will be exposed to basic tools of logic, set theory, and number theory. You will practice proving theorems and reasoning about some basic algorithms.

student responsibilities Preview the lecture content before coming to the class. Review the lecture coverage after class to identify unclear points. Do assignments. Review solutions to the assignments. Forward constructive feedback to the instructors and/or TAs.

code of student behaviour

recording of teaching permitted only with the prior written consent of the instructor or if recording is part of an approved accommodation plan

grading scheme

• 45% 5 assignments (9% each)
• 18% midterm (in class, closed book)
• 37% final (3 hours, closed book)

notes

• no late assignments
• You are allowed/encouraged to discuss the assignments with each other, but you must write your solutions alone and independently. In particular, you are not allowed to take any written (or recorded) notes from your discussions. You must list the names of students you have discussed the assignment with, and any other sources that you have used on the front page of your assignment, or a statement that no sources other than the course text and lecture materials were consulted.
• Any questions concerning the marking of a midterm (by instructors) or an assignment (by TAs) should be brought to the attention of the marker within 72 hours of the time at which the papers are returned to the class in question; after that time, marks cannot be changed.