**Phil 151: First Order Logic**

[Teaching Staff | Overview | Reading Material | Schedule | Grading | Notes/Handouts]

**Quarter**: Winter

**Instructor**: Eric Pacuit

**Instructor's Office Location**: Room 92B, Building 90

**Office Hours**: Wednesday, 3:00PM - 4:30PM

**Meeting Times**: Monday, Wednesday and Friday, 10:00AM - 10:50AM

**First Class**: Wednesday, January 7, 2009

**Location**: Building 260, Rm 113

**Class Email**: philosophy151@lists.stanford.edu (messages will reach the instructor and all TAs)

## Final Grades

I hope you enjoyed the course! Your final grades will be available in the next few days.

# Teaching Staff

Marcello di Bello

**Section Times**: Thursday, 2:15PM - 3:05PM

**Section Location**: Building 200, Room 32

**Office Hours**: Tuesday, 2:00PM - 4:00PM

**Office**: Building 90, Room 92C

Wes Holliday

**Section Times**: Tuesday, 4:15PM - 5:05PM

**Section Location**: Educ 130

**Office Hours**: Thursday, 3:15PM - 4:15PM (and by appointment)

**Office**: Building 100 Room 102K

Thomas Icard

**Section Times**: Monday, 2:15PM - 3:05PM

**Section Location**: Building 80, Room 115

**Office Hours**: Wednesday, 2:00PM - 3:00PM

**Office**: Building 100, Room 102K

# Overview

**Course Description**:The aim of the course is to introduce you to the kinds of questions logicians ask about logics, the meta-theory of logic. To illustrate these questions, we will use propositional logic, modal logic and first-order logic. All these logics are important in philosophy, computer science, AI, linguistics and mathematics.

**Course Material**: Topics to be covered include syntax & semantics of propositional logic, modal logic and first-order logic; logical consequence; axiomatics systems; compactness; definability; completeness and computatability.

**Prerequisites**: The formal prerequisites are Phil 150, or consent of the instructor.

# Reading Material

The course is based on the following textbook.
The following texts are recommended for further reading:

- H. Enderton,
**A Mathematical Introduction to Logic**, Academic Press, 2nd Edition, 2001 - Chapters from a draft of a textbook by Johan van Benthem (will be made available in class)

- R. Smullyan, First-Order Logic, Dover, 1995 (first edition: 1968)
- H.-D. Ebbinghaus, J. Flum, and W. Thomas, Mathematical Logic, Springer, 1995

# Schedule

Below is a schedule which will be updated as the course proceeds. The reading refers to sections
from

*A Mathematical Introduction to Logic*by Herbert Enderton. `vB' refers to the chapters from Johan van Benthem's new textbook on modal logic.Date | Lecture Topic | Reading | Notes |
---|---|---|---|

1/7 | Introduction and Motivation | ||

1/9 | The Language of Sentential Logic | 1.1 | HW 1 |

1/12 | The Semantics of Sentential Logic | 1.2 | |

1/14 | Induction and Recursion | 1.4 | |

1/16 | Truth Functional Completeness | 1.4,1.5 | HW 1 Due; HW 2 |

1/19 | No Classes (Martin Luther King Day) | ||

1/21 | Compactness and Introduction to Modal Logic | 1.7, vB Sections 2.1-2.4 | |

1/23 | Semantics of Modal Logic, Bisimulation | vB Chapter 3 | HW 2 Due; HW 3 |

1/26 | Definability | vB Chapter 3 | Modal Logic Notes |

1/28 | Definability | vB Chapter 3 | |

1/30 | Modal Deductions and Soundness | vB Chapter 5 | HW 3 Due |

2/2 | Completeness of ML | vB Chapter 5 | |

2/4 | Completeness of ML | vB Chapter 5 | |

2/6 | Syntax and Semantics of FOL | 2.1, 2.2 | Midterm Exam |

2/9 | Syntax and Semantics of FOL | 2.1,2.2 | |

2/11 | Definability in FOL | 2.2 | |

2/13 | Homomorphism Theorem, Definiability in FOL | 2.2 | Midterm Exam Due, HW 4 |

2/16 | No Classes (President's Day) | ||

2/18 | Deductions in FOL | 2.4 | |

2/20 | Deductions and Metatheorems | 2.4 | HW 4 Due, HW 5 |

2/23 | Deductions and Metatheorems | 2.4 | |

2/25 | Soundness of FOL | 2.5 | |

2/27 | Soundness and Completeness of FOL | 2.5 | HW 5 Due, HW 6 |

3/2 | Completeness of FOL | 2.5 | |

3/4 | Completeness of FOL | 2.5 | |

3/6 | Completeness of FOL, Theories | 2.5,2.6 | HW 6 Due Final Exam |

3/9 | Elementary Model Theory | 2.6 | |

3/11 | Elementary Model Theory | 2.6 | |

3/13 | Concluding Remarks |

# Grading

Homework assignments count for 50%, midterm 20% and final exam 30%.
The lowest homework assignment will be dropped from the final tally, and you may hand in one
homework assignment one class late. Otherwise, late homework will not be accepted. Midterm and
final exam are take-home. Homeworks and the midterm are due at the beginning of class on Friday.
Solutions will be made available at Tanner Library the following Monday or Wednesday after the
assignment is due.

For the midterm and final exams, you may NOT collaborate with others in any way. For the homework assignments, you are encouraged to work in small groups. You may discuss the problems with one another or with me or the TAs as much as you want.

((HW1+HW2+HW3)/170)*30 + ((MID/100)*20)

So, if you have received perfect scores on all homeworks and the midterm, you would have a score of 50. The following table gives the number of students in each of the ranges:

For the midterm and final exams, you may NOT collaborate with others in any way. For the homework assignments, you are encouraged to work in small groups. You may discuss the problems with one another or with me or the TAs as much as you want.

*But you must always do the final write-up completely on you own.*A good strategy when working together is to use a blackboard and erase it completely before writing up your (separate) answers. Please write the name of your discussion partners on the front page of your homework assignments.**Midway Grades**: Many students have asked about how to determine their current score for the course. In order to take into account the fact that the midterm and homeworks are weighted differently, use the following formula to calculate your score (out of 50):So, if you have received perfect scores on all homeworks and the midterm, you would have a score of 50. The following table gives the number of students in each of the ranges:

Range | Number of Students |
---|---|

48 - 49 |
5 |

39.5 - 47.5 |
19 |

34 - 39.5 |
10 |

28 - 32 |
9 |

13.5 - 27 |
7 |

*Note that this score does not reflect the fact that the lowest homework score will be dropped, so for those you received a 0 for one of the homeworks, your current score which be significantly lower than what you can expect.*

# Notes/Handouts

- Course Information (pdf)

- Homework 1 (pdf)

*The solutions are available in Tanner Library*

- Homework 2 (pdf)

*The solutions are available in Tanner Library*

- Homework 3 (pdf)

*The solutions are available in Tanner Library*

- Modal Logic Study Guide (pdf)

- Midterm Exam (pdf)

*The solutions are available in Tanner Library*

- Homework 4 (pdf)

*The solutions are available in Tanner Library*

- Homework 5 (pdf)

*The solutions are available in Tanner Library*

- Homework 6 (pdf)

*The solutions are available in Tanner Library*

- Final Exam (pdf)

*The solutions are available in my office*