Logic and Computation


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. 

Course Information


01:30PM 02:50PM SH214 Tuesday and Thursday


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. 


9-12 units 


60% Homework, 20% Midterm, 20% Final 


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. 


TBA, Closed book


TBA, Closed book


Inductive definitions and proofs, 
Syntax and semantics of propositional logic, 
Syntax and semantics of first-order logic, 
Elementary model theory, 
Higher-order, intuitionistic, and modal logic. 



Teaching Staff




Office Hours




Kevin T. Kelly

BH 152 

Tues 4:30-5:30

Thurs 3:10-4:10




Nick Radcliffe



Sarah Taylor

BH 138

M 4:30-5:30

W 1:00-2:00


By appt.





Academic Administrator

Mauren Antkowski 

BH 135 





Course Assignments and Announcements


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.   

solutions1, solutions2


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. 


  1. van Dalen exercise (i – iv).  
  2. van Dalen exercise 2.3.2.



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, 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.