Administrivia Prerequisites and syllabus Exams, HW and grading policy Homework sets Homework solutions Lecture notes

Basic Logic

 

Administrivia

The course meets MWF 11:30PM-12:30PM in DH 2122. If you want to meet, send email to jcumming@andrew.cmu.edu to arrange an appointment.

Homework will be set most Wednesdays, will be due on the following Wednesday, and should be returned graded by the Wednesday after that. Late homework will not be accepted under any circumstances, but the lowest homework score will be dropped. Homework must be word-processed (preferably in LaTeX) and submitted as a PDF enclosure in an email message by the start of class time on Wednesday. The email should be sent to the address lserafin.algebra@gmail.com.

Important note 1: Your homework file should be named according to the scheme "[Your last name]_logic_[Number of the homework].pdf", so that eg Aaron Aardvark's tenth homework set is "Aardvark_logic_10.pdf". I won't guarantee that homework not named like this will get graded in a timely fashion.

Important note 2: I generally encourage cooperation on the homework, but you must write up your solutions by yourself and state with whom you have discussed each problem. Cooperation on the tests is cheating and will lead to serious consequences, which can include failing the course and disciplinary action by the university.

 

Prerequisites and syllabus

Prerequisites: Basic facts about numbers, sets, and logic as covered in the Concepts of Mathematics course. The ability to recognise and write a proof.

Tentative syllabus.

  1. Inductive structures
  2. Unique readability
  3. Propositional logic: formulae and semantics
  4. Proofs in propositional logic
  5. Soundness of the propositional proof system
  6. Completeness of the first-order proof system
  7. First-Order logic: formulae and semantics
  8. Proofs in first-order logic
  9. Soundness of the first-order proof system
  10. Completeness of the first-order proof system
  11. Elementary model theory of first-order logic: compactness, diagrams, types

 

Exams, HW and grading policy

There will be a takehome midterm and a takehome final. Grades will be assigned according to a formula in which (roughly speaking) homework counts 25 percent, the midterm counts 30 percent and the final counts 45 percent.

 

Homework sets and exams

  1. Homework 1 in TeX and PDF. Due by class time on Wed 16.
  2. Homework 2 in TeX and PDF. Due by class time on Wed 23.
  3. Homework 3 in TeX and PDF. Due by class time on Wed 30.
  4. Homework 4 in TeX and PDF. Due by class time on Wed 7.
  5. Homework 5 in TeX and PDF. Due by class time on Wed 4.
  6. Homework 6 in TeX and PDF. Due by class time on Wed 18.
  7. Homework 7 in TeX and PDF. Due by class time on Wed 9.

Homework set and exam solutions

  1. Solutions in TeX and PDF to HWS 1-4. Please contact me if you find a typo or want further explanation.
  2. Solutions in PDF to HWS 5-7. Please contact me if you find a typo or want further explanation.

Lecture notes

Please let me know if you find typos or need clarification.

  1. Notes for week 1
  2. Notes for week 2
  3. Notes for week 3 (part one: proofs), week 3 (part two: soundness), week 3 (part three: completeness).
  4. Notes for week 4
  5. Handout on proofs in FOL, will be integrated into this week's notes.
  6. Notes for week 5
  7. Notes for week 6
  8. Notes for weeks 7 and 8 (not including Friday of week 8)
  9. Notes for weeks 9-10 part a and part b.