MAT/CSE 371

Class Schedule and Homework Assignments
Spring 2000 last revision: April 24, 2000

Week Topic Homework
All problem numbers are from the 4th edition of the text.

Jan 21 class cancelled due 2/17

1.5, 1.8, 1.11, 1.17, 1.18, 1.19, 1.22, 1.31, 1.31, 1.32, 1.37, 1.43(1.42 in 3rd ed), 1.46(1.44 in 3rd ed)

Jan 25, 27 Introduction.
1.1: Propositional connectives and truth tables.
1.2: Tautologies

Feb 1, 3 1.3: Adequate sets of connectives
1.4: Axiom systems

Feb 8, 10 1.4: Axiom systems (continued), interpretation and many valued logics due 3/2

1.52, 1.57, 1.60(a,b,c), 2.2, 2.8(a-l), 2.9, 2.10, 2.11, 2.14(a-d), 2.15(b,c)
The corresponding problems from Ch.1 in the 3rd edition are: 1.51, 1.56, 1.59(a,b,c). I don't know the corresponding problems in Ch.2

Feb 15, 17 1.5: independence of axioms
1.6: other axiomatizations; intuitionist logic
2.1: quantifiers

Feb 22, 24 2.2: First order languages, satifiability, and models
2.3: First order theories.
2.4: properties of first order theories.

Feb 29, Mar 2 2.4: Properties of first order theories (continued)
2.5: Additional metatheorems and derived rules.
2.6: Rule C
As you've no doubt noticed, grading of homeworks hasn't quite worked out as I had hoped. Consequently, no more problems will be officially assigned.

Instead, I will do any problems I think very important as part of lecture. You should look over the other problems, do most of them, and ask about any you don't understand. Sorry for the confusion.

Mar 7
Mar 9 Exam on sections 1.1-2.2 Go over exam. Rant about how people are confused about basic ideas, have no concept of what a proof is, and so on.

Mar 14, 16 More extended rambling about why logic needs to be so formal, what good it is, etc.
2.6: Rule C (continued)
2.7: Completeness Theorems

Mar 21, 24 Spring Break

Mar 28, 30 2.7: Completeness (continued)
2.8: First-Order Theories with Equality
2.9: Defining New Functions and Constants

April 4, 6 3.1: Formal Number Theory.
3.2: Number Theoretic Functions and Relations

April 11, 13 3.3: Recursive functions

April 18
April 20 3.3: Recursive functions(continued)
No class (Passover) Take-home Exam
due May 4

TYPO in problem 1d fixed on April 29

April 25, 27 3.3: Arithmetization and Gödel Numbers
3.4: The fixed-point theorem and Gödel's incompleteness theorem.

May 2, 4 3.4: Gödel's incompleteness theorem (continued).
3.5: Recursive undecidability and Church's theorem.
Fuzzy Logic (presentation by Gus Crespo)
May 9 (Finals week) Paper on a topic of your choice (related to logic)

Administrivia

Office:	Math 5d-148
Phone:	632-7306
Email:	scott@math.sunysb.edu

Office Hours
Mon 1-2 math 5d-148	Wed 10-12 math P-143	Thu 11-12 math 5d-148
and by appointment

Text: Elliott Mendelson, Introduction to Mathematical Logic, fourth edition.

Grading: Your grade will be based on the following 5 things:

In-class participation (8%)
Homework assignments (23%)
Two exams (23% each)
A paper on a topic of your choice related to logic (23%)
If you prefer, you may give a 20-30 minute lecture instead of writing a paper. Please make arrangements well before the end of the semester if you plan to do this.

Week	Topic	Homework All problem numbers are from the 4th edition of the text.
Jan 21	class cancelled	due 2/17 1.5, 1.8, 1.11, 1.17, 1.18, 1.19, 1.22, 1.31, 1.31, 1.32, 1.37, 1.43(1.42 in 3rd ed), 1.46(1.44 in 3rd ed)
Jan 25, 27	Introduction. 1.1: Propositional connectives and truth tables. 1.2: Tautologies
Feb 1, 3	1.3: Adequate sets of connectives 1.4: Axiom systems
Feb 8, 10	1.4: Axiom systems (continued), interpretation and many valued logics	due 3/2 1.52, 1.57, 1.60(a,b,c), 2.2, 2.8(a-l), 2.9, 2.10, 2.11, 2.14(a-d), 2.15(b,c) The corresponding problems from Ch.1 in the 3rd edition are: 1.51, 1.56, 1.59(a,b,c). I don't know the corresponding problems in Ch.2
Feb 15, 17	1.5: independence of axioms 1.6: other axiomatizations; intuitionist logic 2.1: quantifiers
Feb 22, 24	2.2: First order languages, satifiability, and models 2.3: First order theories. 2.4: properties of first order theories.
Feb 29, Mar 2	2.4: Properties of first order theories (continued) 2.5: Additional metatheorems and derived rules. 2.6: Rule C	As you've no doubt noticed, grading of homeworks hasn't quite worked out as I had hoped. Consequently, no more problems will be officially assigned. Instead, I will do any problems I think very important as part of lecture. You should look over the other problems, do most of them, and ask about any you don't understand. Sorry for the confusion.
Mar 7 Mar 9	Exam on sections 1.1-2.2 Go over exam. Rant about how people are confused about basic ideas, have no concept of what a proof is, and so on.
Mar 14, 16	More extended rambling about why logic needs to be so formal, what good it is, etc. 2.6: Rule C (continued) 2.7: Completeness Theorems
Mar 21, 24	Spring Break
Mar 28, 30	2.7: Completeness (continued) 2.8: First-Order Theories with Equality 2.9: Defining New Functions and Constants
April 4, 6	3.1: Formal Number Theory. 3.2: Number Theoretic Functions and Relations
April 11, 13	3.3: Recursive functions
April 18 April 20	3.3: Recursive functions(continued) No class (Passover)	Take-home Exam due May 4 TYPO in problem 1d fixed on April 29
April 25, 27	3.3: Arithmetization and Gödel Numbers 3.4: The fixed-point theorem and Gödel's incompleteness theorem.
May 2, 4	3.4: Gödel's incompleteness theorem (continued). 3.5: Recursive undecidability and Church's theorem. Fuzzy Logic (presentation by Gus Crespo)
May 9 (Finals week)		Paper on a topic of your choice (related to logic)