Math 39 Homework Schedule

I have learned throughout my life as a composer chiefly through my mistakes and
pursuits of false assumptions, not by my exposure to fonts of wisdom and knowledge.
Igor Stravinsky

Class participation is an essential part of the course; mathematics is not a spectator sport. For this section, class participation consists of reading assignments, quizzes, and homework problems.

Reading Assignments

Reading assignments will be given daily and should be read before coming to class. For some of my thoughts on reading mathematics texts, click here.

Quizzes

Quizzes will be administered at the end of class on Monday covering material presented in lecture the previous week. They will consist of a couple of questions and should only take 10 - 15 minutes to complete. If you do the homework for the lectures given the previous week (including Friday's homework), then you should do fine on the quizzes.

Homework Problems

Homework problems will be assigned daily and collected the following class period. Late homework will not be accepted and a grade of 0 will be assigned (of course, exceptions can be made for emergencies such as illness, death, natural disasters...). I will grade your homework problems and return them as soon as possible, typically during the next class period. The solutions you present must be coherent and written in complete sentences whenever possible. Simply stating answers or turning in garbled, unclear solutions will result in a grade of 0.

The Schedule

On the remainder of this page you will find schedule for the course, including reading assignments, quiz dates and homework assignments. There is also some information concerning the exams, which will be updated periodically to include late-breaking news.

Chapter 1: Informal Statement Calculus

  • Lecture 1 on 9/25 Sections 1.1-1.2 : Statements, Connectives, Truth Tables
  • Lecture 2 on 9/28 Sections 1.3-1.4 : Rules for manipulation, Normal Forms
  • Lecture 3 on 9/30 Sections 1.5-1.6 : Adequate sets of connectives, Validity

Chapter 2: Formal Statement Calculus

  • Lecture 4 on 10/2 Section 2.1 : The formal system L
  • Lecture 5 on 10/5 Section 2.2 : The Adequacy Theorem for L
  • Lecture 6 on 10/7 Section 2.2 : The Adequacy Theorem for L
  • Lecture 7 on 10/9 Sections 2.2 : The Adequacy Theorem

Chapter 3: Informal Predicate Calculus

  • Lecture 8 on 10/12 Sections 3.1-3.2 : Predicates and quantifiers & First order languages
  • Lecture 9 on 10/14 Sections 3.2-3.4 : First-order languages, Interpretations, Satisfaction & Truth
  • Lecture 10 on 10/16 Section 3.4 : Satisfaction & Truth
  • Lecture 11 on 10/19 Section 3.4 : Satisfaction & Truth

Chapter 4: Formal Predicate Calculus

  • Lecture 12 on 10/21 Sections 3.4 - 4.1 : Satisfaction & Truth and the Formal System K(L)
  • Lecture 13 on 10/23 Section 4.1 : The Formal System K(L)
  • Lecture 14 on 10/26 Section 4.1 : The Formal System K(L)
    • There will NOT be a Quiz in honor of your exam on 10/27.
    • The homework is to spend a few minutes reading through the sections that
      we will cover in class on Wednesday 10/28.

Midterm Exam

The midterm exam is on Tuesday, October 27th from 6:00-8:00 pm in 113 SILSBY. The exam is worth 25% of your final grade and will cover the material listed above (i.e., Chapters 1 through 4.1). The exam is designed so that well-prepared students can complete the exam in approximately an hour and a half. However, the exam time is designated as lasting two hours to eliminate (for the most part) time pressures. Please arrive a little early to allow time to get seated, settled, and exams distributed by 6:00. The room contains almost 60 seats and there are only 5 of you; so, there is plenty of room to spread out and leave some empty seats between you and the other test-takers. Finally, bring writing utensils, but not paper.

The format for the exam will be approximately as follows.

  • There will be 10 problems on the exam.
    (Note that the exam is still being developed, and so this number may change.)
  • For some problems, you will be asked to provide definitions, statements of theorems, and examples related to these.
  • You will also be asked to prove some results. These proofs will involve the applications of fundamental concepts and definitions from the course.

Consider preparing for the exam by reviewing your homework and quizzes. When preparing keep in mind that the best way to remember the material is to understand it. Also, be sure to have an example in mind for every definition that you choose to remember; root the abstract ideas we are studying in particular, meaningful examples.

Chapter 4: Formal Predicate Calculus (cont'd)

  • Lecture 15 on 10/28 Sections 4.2 & 4.3 : Equivalence & Substitution and Prenex Form
  • Lecture 16 on 11/2 Section 4.4 : The Adequacy Theorem for K - Some Lemmas
  • Lecture 17 on 11/4 Section 4.4 : The Adequacy Theorem for K
  • Lecture 18 on 11/5 Section 4.4 : The Adequacy Theorem for K
  • Lecture 19 on 11/6 Section 4.4 : The Adequacy Theorem for K
  • Lecture 20 on 11/9 Section 4.5 : The Compactness Theorem & Some Applications
    • Quiz on Lectures 16 - 20
    • Homework 20 due 11/11: class handout.

  • Lecture 21 on 11/11 Section 4.5 : More Compactness Theorem & Applications
    • Homework 20 due 11/13: class handout.

  • Lecture 22 on 11/13 Section 4.5 : Cardinality & the Löwenheim-Skolem-Tarski Theorem
    • Homework 22 due 11/15: class handout.

Chapter 6: The Gödel Incompletenes Theorem

  • Lecture 23 on 11/16 Sections 6.1 & 6.2 : Introduction & Expressibility
    • Quiz on Lectures 20 - 22
    • Homework 23 due 11/18: click here

  • Lecture 24 on 11/18 Sections 6.2 & 6.3 : Representable Functions & Recursive Functions
  • Lecture 25 on 11/19 Sections 6.3 & 6.4 : Recursive Functions & Gödel Numbering
  • Lecture 26 on 11/20 Section 6.5 : The Gödel Incompletenes Theorem
  • Lecture 27 on 11/23 Section 7.1 : Algorithms and Computability
    • Quiz on Lectures 23 - 26; This is the last one!
    • Homework 27 due 11/30: click here

  • Lecture 28 on 11/30 Section 7.2 : Turing Machines
  • Lecture 29 on 12/2 Section 7.2 : Turing Machines

The Final Exam

The final exam is on Tuesday, December 8th from 9:00 - 11:00 AM in 13 Bradley. The exam will be comprehensive, covering all of the material we have discussed in the course. There will be some weighting of problems towards the material from the final half of the course; i.e., about one third of the exam will focus on ideas from the first half and about two thirds of the exam will focus on ideas from the second half of the course.