CS 81: Computability and Logic
Fall 2013

Course Staff and Consulting Hours

Day

Time

Location

Name

How to Contact

Sunday

7-8p

LAC Lab

Lucy Lu

xlu@hmc.edu

Monday

4:15-5:45p

B165 Olin

Prof. Robert Keller

keller@cs.hmc.edu

Monday

8-9p

LAC Lab

Michael Culhane

mculhane@ g.hmc.edu

Monday

9-10p

LAC Lab

Nick Carter

ncarter@ g.hmc.edu

Tuesday

4:15-5:45p

B165 Olin

Prof. Robert Keller

keller@cs.hmc.edu

Tuesday

9-10p

LAC Lab

Nabil Zaman

nzaman@g.hmc.edu

Tuesday

10-11p

LAC Lab

John Sarracino

jsarracino@g.hmc.edu

Wednesday

4:15-5:45p

B165 Olin

Prof. Robert Keller

keller@cs.hmc.edu

Wednesday

8-9p

LAC Lab

Henry Huang

hhuang@g.hmc.edu

Wednesday

8-9p

Edmunds Lab

George Price

gwp02011@pomona.edu

Wednesday

9-10p

Edmunds Lab

Timothy Kaye

timothy.kaye@pomona.edu

 

For quickest response, please use our piazza site.

Submission site for homework

 

Grading Breakdown

Homework

50%

Midterm (16 October 2013 in class)

15%

Final (2-5 PM, Sec. 1: Tuesday 17 December, Sec. 2: Thursday 19 December)

30%

Participation (attendance, asking questions, coming to office hours, etc.)

5%

 

Textbooks

 

Assignments

  1. Assignment 1  (due Wed. night, 11 September 2013)
  2. Assignment 2  (due Wed. night, 18 September 2013)
  3. Assignment 3  (due Wed. night, 25 September 2013)
  4. Assignment 4  (due Wed. night, 2 October 2013)
  5. Assignment 5  (due Wed. night, 9 October 2013)
  6. Assignment 6 (Optional) (due Wed. night, 16 October 2013)
  7. Assignment 7  (due Wed. night, 30 October 2013)
  8. Assignment 8  (due Wed. night, 6 November 2013)
  9. Assignment 9  (due Wed. night, 13 November 2013)
  10. Assignment 10  (due Wed. night, 20 November 2013)
  11. Assignment 11  (due Wed. night, 4 December 2013)
  12. Assignment 12  (due Wed. night, 11 December 2013)

Lecture Slides

1.     Introduction, Propositional Logic, Part 1

2.    Propositional Logic, Part 2, Tableaux

3.    Propositional Logic, Part 3, Natural Deduction

    DNF & CNF, Minterms & Maxterms

4.    Propositional Soundness and Completeness

5.    Predicate Calculus

6.    Predicate Calculus Semantics

7.    Fun With Interpretations

8.    Predicate Calculus Continued

    More Jape Examples

9.    Tableaux for Predicate Logic

10.    Converting a Tableau Proof to Natural Deduction

11.    Resolution Theorem Proving, Part 1

12.    Resolution Theorem Proving, Part 2

13.    Resolution Theorem Proving, Part 3

14.    Program Logic, Part1

15.    Program Logic, Part2

    (Optional: Program Logic, Part3)

16.    Strings, Machines, Languages

17.    Regular Expressions, Product Construction

18.    State Equivalence, Myhill-Nerode Theorem, Non-Regular Languages

19.    Derivatives of Regular Expressions and Languages, Pumping Lemma

20.    Grammars and Their Languages

21.    Pushdown Automata

22.    CYK Parsing Algorithm

22.    Effective Computability

23.    Uncomputability

24.    Reduction

25.    Partial Recursive Functions

    Lambda Calculus

    The Recursion Theorem

Other Items of Interest

·      Propositional tableau construction and tautology checker in Prolog

·      Propositional natural deduction prover in Prolog

·      Interpretation of predicate logic terms and formulas over a finite domain

·       LaTex Formatting Packages for proof boxes and more