There is no required text. We will use Semantic Tableaux so the texts below have been selected because they emphasize this method. I strongly recommend any of the three supplemental texts. Raymond Smullyan's texts are the best treatment of the subject. Alternatively, the first four chapters of Simpson's course notes are an excellent introduction to tableaux in propositional and first-order logic.
- Supplemental Texts
- Raymond Smullyan, First-Order Logic.
- Raymond Smullyan, Logical Labyrinths
- Stephen Simpson, Course Notes for Mathematical Logic
- Alternative Texts
- Mordechai Ben-Ari, Mathematical Logic for Computer Science.
- Melvin Fitting, First-Order Logic and Theorem Proving
- Jean Gallier, Logic for Computer Science
- Anil Nerode and Richard Shore, Logic for Applications
Formal logic is concerned with the systematic study of the principles of valid inference. There is a broad audience interested in the methods of formal logic: philosophers, computer scientists and mathematicians. This course is intended to be broad, elementary and rigorous. Our aim is to study the relationship between truth and proof in propositional logic and first-order logic. We deal with the mathematical foundations of these formal systems in several stages:
- Semantics, the appropriate notions of truth in an interpretation, validity and consequence
- Proof, formal methods of deduction and inference. Our primary proof system is semantic tableaux, but we will consider other proof systems as well.
- The fundamental theorems connecting proof and truth: soundness, completeness and compactness. Our focus will be to develop general methods for establishing these properties.
As time permits, we will prove the Craig Interpolation Theorem, Robinson Consistency Theorem and Beth Definability Theorem for first-order logic. These are not usually presented in an introductory mathematical course, but their proofs are elementary using the method of tableaux.
The following components will determine the final grade.
- Total points: 600 points.
- Homework: 250 points (five assignments).
- First Midterm Exam: 100 points. (October 23, covering propositional logic)
- Second Midterm Exam: 100 points.(November 20, covering first-order logic)
- Final Exam: 150 points.