Course: PSU CS 251 - Discrete Structures II (Spring 2010)

Weekly outline

General
CS 251 is an introduction to formal logic and related mathematics, as used in modern computer science. Please see the course syllabus, below, for detailed information and background.
29 March - 4 April
- Introduction to the course; Introduction to propositional logic
- Truth value, meaning, and interpretation
- HW 1 - Formulae and truth values Quiz
- Reading: Chapter 6
- Introduction to the course; Introduction to propositional logic
- Truth value, meaning, and interpretation
- HW 1 - Formulae and truth values Quiz
- Reading: Chapter 6
5 April - 11 April
- Normal forms; abbreviated forms; equivalence
- HW 2 - Elementary Logic Assignment
- Formal proofs; conditional and indirect proofs; proof systems
- Normal forms; abbreviated forms; equivalence
- HW 2 - Elementary Logic Assignment
- Formal proofs; conditional and indirect proofs; proof systems
12 April - 18 April
- Prop. modeling; satisfiability and tautology
- Predicate logic
- HW 3 - Propositional Reasoning Assignment
- Prop. modeling; satisfiability and tautology
- Predicate logic
- HW 3 - Propositional Reasoning Assignment
19 April - 25 April
- Predicate normal forms; meaning and interpretation; decidability
- Midterm 1 review
- Reading: Chapter 7
- HW 4 - Predicate Logic Assignment
- Example problem for midterm 1 File
- Predicate normal forms; meaning and interpretation; decidability
- Midterm 1 review
- Reading: Chapter 7
- HW 4 - Predicate Logic Assignment
- Example problem for midterm 1 File
26 April - 2 May
- Midterm 1
- Midterm 1 Key File
- Predicates and functions; equality and arithmetic
- Resolution theorem proving
- Reading: Chapter 8 sec 8.1, Chapter 9 sec 9.1
- Midterm 1
- Midterm 1 Key File
- Predicates and functions; equality and arithmetic
- Resolution theorem proving
- Reading: Chapter 8 sec 8.1, Chapter 9 sec 9.1
3 May - 9 May
- Predicate modeling; satisfiability and validity
- Equational modeling; recursive equations
- Predicate modeling; satisfiability and validity
- Equational modeling; recursive equations
10 May - 16 May
- Algebras; abstract algebras
- Abstract Data Types; ADT laws
- Reading: Chapter 10
- HW 5 - Resolution Assignment
- Algebras; abstract algebras
- Abstract Data Types; ADT laws
- Reading: Chapter 10
- HW 5 - Resolution Assignment
17 May - 23 May
- Midterm 2
- More ADTs; using ADTs
- Midterm 2
- More ADTs; using ADTs
24 May - 30 May
- Midterm 2 Key File
- Modeling computer programs
- Proving computer programs correct
- Reading: Chapter 8 sec. 8.2
- Midterm 2 Key File
- Modeling computer programs
- Proving computer programs correct
- Reading: Chapter 8 sec. 8.2
31 May - 6 June
- Monday 31 May: Memorial Day, no class
- Proving computer programs correct; programs with ADTs
- Final Review
- Monday 31 May: Memorial Day, no class
- Proving computer programs correct; programs with ADTs
- Final Review
7 June - 13 June
The final exam for CS 251 Spring 2010 will be held Wed June 9 12:30-14:20 as per University guidelines.