University of Calgary
University of Calgary
Site Navigation
Courses and Teaching
Site Feed
Search
Navigation
Logic II (Phil 379)
Logic II is an introduction to computability and the basic metatheory of first-order logic (undecidability and incompleteness). Official, printable outlines can be found at the end of this page.
Contents
Course Description
This course will introduce you to the basic metatheory of first-order logic and to the relation between computability and logic. We will start with the latter and discuss one precise definition of computablity: Turing machines. We will show that there are problems which are undecidable in the sense that there is no Turing machine which, in a finite amount of time, provides a definite yes-or-no answer. The first example of an undecidable problem is the halting problem, i.e., the problem of deciding, given the description of a turing machine, whether it halts on a given input.
In the second half of the class, we will go on to the basic metatheory of first-order logic. We will prove two important theorems: First, we will show that the decision problem, i.e., the problem of deciding, given a sentence of first-order logic, whether it is valid, is undecidable. Then we will study the relationship between provability and validity in-depth and show that the provable sentences are exactly the valid ones (soundness and completeness). In the course of this, we will also discuss the beginnings of model theory of first-order logic, proving the compactness theorem and the Löwenheim-Skolem Theorem. If there is time, we will cover some advanced topics at the end of the semester, such as second-order logic or solvable cases of the decision problem.
WARNING: This is a course in metalogic. It builds upon the material in Logic I (Phil 279), but is very different in character. In Logic II, we prove theorems about logical systems (and not in logical systems, e.g., there will be be almost no formal proofs). Doing well in 279 is no guarantee that this will come easy to you.
(This disclaimer added on request of some of last year's students, who thought that 379 was going to be just more of 279.)
Prerequisites and preparation
Logic I (PHIL 279) or Elementary Formal Logic (PHIL 377) is a prerequisite for this course.
It can't hurt to review your logic textbook prior to the start of class (although we won't get to logic proper until the second half of the semester). If you've used the Logic Book, review chapters 8 and 11; in Chellas' Elementary Formal Logic, review chapters 7 and 9 and the appendices; in Language, Proof and Logic, review chapters 15, 16, 18.1-18.3.
Required Text
George S. Boolos, John P. Burgess, Richard C. Jeffrey, Computability and Logic, 4th edition, Cambridge University Press
Available at the University of Calgary Bookstore.
Evaluation and course requirements
4 homework assignments (40%), an in-class midterm exam (25%), and a registrar-scheduled final exam (30%). Class participation counts for 5% of your grade. You must submit all four assignments and complete both exams. You must receive a D or better on the final exam to receive a D or better in the course.
On each assignment and exam you will receive a letter grade reflecting the level of mastery of the material shown by the work you submit. According to the Calendar, letter grades are defined as follows:
A Excellent—superior performance, showing comprehensive understanding of subject matter. (A solution to an assigned problem shows that you understand the problem, is complete and rigorously correct, and is reasonably direct and elegant.)
B Good—clearly above average performance with knowledge of subject matter generally complete. (You understand the problem and give a complete solution, although there may be minor gaps in the proof, or the solution is correct but circuitous.)
C Satisfactory—basic understanding of the subject matter. (You understand what the question is asking but your solution contains significant errors or gaps.)
D Minimal pass—marginal performance. (It is not clear that you understand what the question is asking, or your proposed solution goes completely in the wrong direction.)
F Fail—Unsatisfactory performance.
In computing your final grade, your marks will be converted to grade points (A = 4, B = 3, C = 2, D = 1, F = 0; + or − adds/subtracts .3) and averaged according to the weights given above. The final mark is the letter grade corresponding to this average plus a margin of 0.1 (i.e., an average of 3.9 earns an A, an average of 3.6 an A− , etc.).
Assignments and Policies
Late work and extensions
Assignments handed in late will be penalized by the equivalent of one grade point per calendar day. There will be no make-up exams under normal circumstances; for the final exam, university policies for deferral of exams apply.
Collaboration
Collaboration on exercises is encouraged. However, you must write up your own solutions, and obviously you must not simply copy someone else’s solutions. You are also required to list the names of the students with whom you’ve collaborated on the assignment.
Exams
Midterm and final will be closed-book, and the final is cumulative. Be aware that cheating on an exam is a serious academic offence and can result in suspension or expulsion.
Course Website
A course website on U of C's BlackBoard server will be set up. You should be automatically signed up on the first day of class if you're registered in the class. You can find the website at
Log in with your UCS user ID and password. (You have a UCS ID if you have a ucalgary.ca email address. The ID is the part before the @; your password is the same password you use to check your email. If it works on webmail.ucalgary.ca, it should work on the WebCT server.) You must log on at least once before the end of the second week of class.
If you are not registered in the course on the first day of class, you will be added to the website as soon as you register, provided you have a UCS account. If you don't, you have to get one. You can register for one online at
NOTE: an @cpsc.ucalgary.ca account will not work!
If you have forgotten your password and/or user ID, you will have to go to the IT Help Desk on the 7th floor of Math Sciences.
Official Outlines
| Attachment | Size |
|---|---|
| Outline Winter 2003 | 11.79 KB |
| Outline Fall 2003 | 16.02 KB |