Kevin T. Kelly
135 K Baker Hall
412 268 8567
This is a standard introduction to formal logic, with an emphasis on syntax and semantics. In philosophy, logic informs discussions in epistemology and foundations of mathematics. In computer science, logic is finding increasing applications in the specification of computer languages, the verification of programs, the theories of uncomputability and NP-completness, natural language processing and data-base update. This course aims to provide secure foundations for branching out into further applications. Topics include inductively defined structures, the syntax and semantics of first-order logic, completeness, compactness, and the Loewenheim-Skolem theorems. Further topics may also include definability, nonstandard models of arithmetic, higher-order, intuitionistic, and modal logic.
Prerequisites: either 80-210, 80-211, 15-251, or consent of the instructor.
Graduate students must complete some extra project approved by the instructor by the last day of class.
|
Lectures |
01:30PM 02:50PM SH214 Tuesday and Thursday |
|
Textbook |
Logic and Structure, Dirk van Dalen, Springer 2004.
Computer science students may also want to consult the first few chapters of John Reynolds’ Theories of Programming Languages for applications to language design and program verification. |
|
Credit |
9-12 units |
|
Grading |
60% Homework, 20% Midterm, 20% Final |
|
Homework |
Weekly homework is assigned weekly and is due in class. Exercises will be discussed in class and turning in the exercises counts toward attendance, so late exercise sets will be penalized by 30 percentage points. Turning in a perfect set is better than not, but you can’t profit from systematically turning them in late. |
|
Midterm |
TBA, Closed book |
|
Final |
TBA, Closed book |
|
Topics |
Inductive definitions and proofs, |
|
Homepage |
http://www.andrew.cmu.edu/user/kk3n/80-310/logic.htm |
|
|
|
Office |
Office Hours |
Phone |
|
|
Professor |
Kevin T. Kelly |
BH 152 |
Tues 4:30-5:30 Thurs 3:10-4:10 |
x8-8567 |
|
|
TAs |
Nick Radcliffe
Sarah Taylor |
BH 138 |
M 4:30-5:30 W 1:00-2:00
By appt. |
x8-9669 |
|
|
Academic Administrator |
Mauren Antkowski |
BH 135 |
|
x8-8568 |
1. Assignment for August 30, due Sept 4: Read van Dalen section 1.1 and Enderton handout (the Appendix mentioned in the previous version of the page is not in the new edition of our textbook, I just learned, so the handout replaces it). Exercise set due Sept 4.
Here are the solutions.
Four questions are required. Three are for extra credit. So divide your score by 40 rather than 70.
2. Assignment for Sept. 4, due Sept 13: Read van Dalen section 1.2 and 1.3. From now on we will be on a Thursday schedule for exercises so this set is due on Sept 13.
Five questions are required. Three are for extra credit. So divide your score by 50 rather than 80.
Here are the solutions.
3. Assignment for Sept 13, due Sept. 20. Do van Dalen Section 1.4, exercises 1, 3, 5, 6, 7.
The solutions are in: solutions1, solutions2, solutions3.
4. Assignment for Sept 20, due Tues, Oct. 2. Do van Dalen Section 1.5, exercise 2 (using proof theory alone, not assuming the completeness theorem). Do exercise 6. You may use any of the lemmas or corollaries leading up to the completeness theorem. Do exercise 7. Something is wrong with exercise 10 (is { _|_ } complete)? State exercise 10 correctly and prove the correct statement.
The solutions are in: solutions1, solutions2.
5. Assignment due Tues, Oct. 9. Do van Dalen Section 1.6, exercises 2, 4, 7. Use the new proof rules instead of the definitions of -, v, <-->. In 4, 7, when it looks bleak, try for a contradiction. When it looks bleak still, try for a contradiction again! That will put assumptions at the top of the proof and allow you to get moving. Don’t fret and stare---just take this advice right away. Try 5 for extra credit. Note that exercise 2 involves the major ideas of this section of the course so pay please pay particular attention to it---it makes a tempting choice as a midterm exam question.
Review Session for midterm: Thurs, Oct 9. Bring your questions. Prior to the review session, memorize the definitions of prop, [phi/q], val, der, |-, |=, consistency, maximal consistency, logical equivalence, logical independence. Know how to do a derivation in the full system and how to compute validity with truth-tables. Know how to state the soundness and completeness theorems. These are the essential ideas that we will build on in the next phase of the course.
Midterm: Oct. 11.
6. Assignment due Thurs. Oct. 18.
Note the revised office hours. Nicholas Radcliffe has shifted his hours to the more accessible time of 4:30-5:30 on Monday. I am discontinuing Wed. office hours due to lack of interest. I may be around on Wed anyway, so send e-mail or stop by to check.
7. Assignment due Thurs. Oct. 25. Do exercises 2.3.4, 2.4.1, 2.4.3, 2.4.5 (be sure to check what |= phi means when phi has free variables). Explain your answer. 2.4.6., first part only. You need to do an induction on TERM. Note that the over-line means the constant for the corresponding domain item. So the over-line of the valuation of t is just a constant denoting the same thing t denotes. It’s pretty obvious that the identity between the constant and the term should be satisfied by the structure. Extra credit: Let the non-logical vocabulary be just the set-theoretic “is an element of” relation. In set theory, “for all” means “for all sets”, so the domain is supposed to cover all sets. Accordingly, let (U, R) be a structure for which U is the set of all sets and R is the element relation over U. What goes wrong? What can you conclude about any structure satisfying set theory whose domain consists only of sets?
8.
Assignment due Thurs. Nov 1.
Do exercise 2.5.2.i. Do it
“algebraically” by chaining equivalences established in sections 2.5 and 2.3.
Do exercise 2.5.3.i. It suffices to make phi :=
P(x) and psi := Q(x). Remember that free variables
are treated as universally quantified according to the definition of |=. Do
exercise 2.5.4 (important). It
suffices to make phi := (x = y). Do
exercise 2.5.5. You will have to
work through the definition of |=, since this is not an equivalence. Look closely at definition 2.2.1 for this
one---a detail is crucial. Do exercise 2.5.6. It suffices to let phi :=
P(x). Do exercise 2.5.7. Do exercise 2.5.9.i. For this one you have to work through the
definition of |=, because you can’t do the whole thing by chaining
equivalences. Do exercise 2.5.14.a. (Extra credit: do exercise 2.5.12---this is the logical
structure of Russell’s paradox discussed at the start of the semester).
9.
I will be
away giving a talk at UC Berkeley on Thursday, Nov 8,
so there is no class.
10. Assignment due
Tues. Nov. 13. I decided in
light of our experience in the first half of the course that it is better for
you to learn the proof theory before applications, so we will skip section 2.7
for now and proceed immediately to sections 2.8, 2.9, and 2.10, which cover
first-order proof theory. The
restrictions on substitution in the proof rules are very important for real
theoretical practice and for automated theorem proving, so pay particular
attention to memorizing them. Do exercise 2.8.3.1(i,
v, vi, vii). Do
exercises 2.9.5, 2.9.6, 2.9.7, 2.9.8, 2.10.4, 2.10.6.
Solutions1, solutions2, solutions3
8. Assignment due Tues. Nov 20. Do exercise 3.1.2. (Hint: remember that a derivation has only finitely many uncanceled hypotheses). Extra credit: In the proof of completeness, Van Dalen mentions that T* may fail to be Henkin, but doesn’t really explain why. This exercise explains his comment. Let T = the set of consequences of Ex Ey phi(x, y). Show that T* is not Henkin. Hint: let psi = Ex Ey (phi(x, c) or phi(x, y)) , where c is not in the language of T. Does there exist c’ in the language of T* such that T* |- (Ex Ey (phi(x, c) or phi(x, y)) --> Ey (phi(c’, c) or phi(c’, x)) for psi? (construct a relational structure for the language of T* in which T* is true but (Ex Ey (phi(x, c) or phi(x, y)) --> Ey (phi(c’, c) or phi(c’, x)) is false).
12 Final assignment: due Nov 29. Do exercise 3.2.1.iii, vi. Show that the converse for vi fails. Note that Gamma and Delta are sets of sentences, rather than theories, which makes the exercise much easier. Do exercise 3.2.6. This is a cool one with an important moral. A set is well-ordered iff it is partially ordered with no infinite descending chain. Follow van Dalen’s recipe and use the compactness theorem. Do exercise 3.2.8. Do exercise 3.2.12. Try the contrapositive. Bonus exercise: 3.2.17. Try the same strategy as for 3.2.6.
December 4: Final review of the course.
December 6: Final exam.
The final will be similar to the
mid-term. Again, the emphasis will be on
concepts and definitions. Expect a few
derivations in first-order logic.