Ma 6c:  Introduction to Discrete Mathematics (Spring 2015-16)

ANNOUNCEMENTS


COURSE DESCRIPTION

The material covered in this term will include an introduction to mathematical logic, including propositional and predicate (or first-order) calculus, computability theory, and computational complexity.  We will discuss the syntax and semantics of formal languages, formal proofs, the Gödel Completeness and Incompleteness Theorems, undecidability and intractability, and the P=NP problem.


PREREQUISITES

TBA


SCHEDULE

TR 13:00 - 14:25, 142 Keck.


INSTRUCTORS

Martino Lupini
HARRY BATEMAN INSTRUCTOR IN MATHEMATICS
260 Sloan
626-395-4340

lupini@caltech.edu


TA's

Jim Tao

307 Kellogg

(626) 395-4081

jtao@caltech.edu


OFFICE HOURS

Martino Lupini: Thursdays at 5pm (260 Sloan) or any other time by appointment (just send me an email to lupini@caltech.edu)   

Jim Tao: Mondays at 10pm (307 Kellogg)


POLICIES

TBA


TOPICS COVERED

TBA


TEXTBOOKS

There will be no official textbook.  The lectures will follow notes that will be posted on this website.

Interested students can consult the following books:

Enderton, A mathematical introduction to logic. Second Edition (2001)

Shoenfield, Mathematical logic. Second Edition (2001)

Manin, A course in mathematical logic for mathematicians. Second Edition (2010)

The following is a book containing a wealth of examples of proofs by induction taken from a variety of mathematical subjects, and aimed at undergraduate students:

David Gunderson, Handbook of Mathematical Induction, CRC Press, 2011   


LECTURE NOTES

Date Description
Tuesday, March 29 Lecture 1
Thursday, March 31 Lecture 2
Tuesday, April 5 Lecture 3
Thursday, April 7 Lecture 4
Tuesday, April 12 Lecture 5    (source)
Thursday, April 14 Lecture 6    (source)
Tuesday, April 19 Lecture 7    (source)
Thursday, April 21 Lecture 8    (source)
Tuesday, April 26 Lecture 9    (source)
Thursday, April 28 Lecture 10  (source)
Tuesday, May 3 Lecture 11
Thursday, May 5 Lecture 12 (source)
Tuesday, May 10 Lecture 13 (source)
Thursday May 12 Lecture 14 (source)
Tuesday, May 17
Thursday, May 19
Lecture 15 and 16
Tuesday, May 24
Thursday, May 26
Lecture 17 and 18

PRACTICE PROBLEMS   

Lecture number Description
Lecture 7 and 8 Practice set 1
Lecture 8 Practice set 2
Lecture 9 Practice set 3
Lecture 10 Practice set 4
Lecture 12 Practice set 5
Lecture 13 and 14 Practice set 6
Lecture 15 and 16 Practice set 7
Lecture 17 and 18 Practice set 8

HOMEWORK

Due Date Homework Solutions
Tuesday, April 12 Homework 1  
Tuesday, April 19 Homework 2  
Tuesday, April 26 Homework 3  
Tuesday, May 10 Homework 4  
Tuesday, May 24 Homework 5  
Tuesday, May 31 Homework 6  

EXAMS

There will be no final exams. The grade will be based on 6 written assignments.


READING