Formal Logic: Course Outline#

This outline provides a comprehensive introduction to formal mathematical logic, guiding students from the foundational principles of symbolic reasoning to the profound metatheoretical results that define the scope and limits of formal systems.

Course Description#

This course is a rigorous introduction to the principles of deductive reasoning using symbolic techniques. We will begin with propositional logic, developing skills in translating natural language arguments into a formal language and evaluating their validity using truth tables and natural deduction. We will then advance to the more expressive system of first-order predicate logic, which allows for the formalization of arguments involving objects, properties, and quantifiers. The course will culminate in a study of the properties of these logical systems themselves, exploring the foundational concepts of soundness, completeness, and the philosophical implications of Gödel's incompleteness theorems.

Prerequisites#

There are no formal prerequisites beyond a readiness for abstract, mathematical-style reasoning. The course is suitable for students in philosophy, mathematics, computer science, and linguistics.

Core Learning Objectives#

Upon successful completion of this course, students will be able to:

• Identify the logical structure of arguments in natural language.
• Translate sentences and arguments into the formal languages of propositional and first-order logic.
• Use truth tables to determine logical properties and relations (e.g., tautology, contradiction, equivalence, validity).
• Construct formal proofs using a system of natural deduction.
• Understand the semantics of first-order logic through the use of models and interpretations.
• Comprehend the major metatheoretical results, including soundness and completeness, and articulate their significance.

Part I: Propositional Logic (PL) - The Logic of Sentences#

Foundations of Logic#

Topics: What is logic? Arguments, premises, and conclusions. The concepts of validity and soundness. Introduction to formal languages.

The Language of Propositional Logic (PL)#

Topics: Atomic sentences and logical connectives (negation, conjunction, disjunction, conditional, biconditional). Well-formed formulas (WFFs). Translation from English into PL.

Skills: Symbolization of complex English sentences.

Semantics of PL#

Topics: Truth tables for connectives. Using truth tables to classify sentences (tautology, contradiction, contingency). Testing for logical equivalence and validity.

Skills: Construction of full and partial truth tables.

Natural Deduction in PL (Part 1)#

Topics: The concept of a formal proof. Introduction to natural deduction. Rules for conjunction ($\land I$, $\land E$), conditional ($\to I$, $\to E$), and negation ($\lnot I$, $\lnot E$), including proof by contradiction.

Skills: Constructing simple formal proofs.

Natural Deduction in PL (Part 2)#

Topics: Rules for disjunction ($\lor I$, $\lor E$) and the biconditional ($\leftrightarrow I$, $\leftrightarrow E$). Derived rules. Proving theorems.

Skills: Constructing more complex proofs involving all connectives.

Part II: First-Order Logic (FOL) - The Logic of Objects and Properties#

The Language of First-Order Logic (FOL)#

Topics: Limitations of PL. Introduction to predicates, names, and variables. The quantifiers: universal ($\forall$) and existential ($\exists$).

Skills: Translating sentences with quantifiers from English to FOL.

Semantics of FOL#

Topics: The concept of a model (or interpretation). Domains, interpretation functions, and variable assignments. The idea of satisfaction. Proving invalidity in FOL by finding a counter-model.

Skills: Constructing small models to test the truth of FOL sentences.

Natural Deduction in FOL (Part 1)#

Topics: Universal quantifier rules ($\forall E$, $\forall I$). Existential quantifier rules ($\exists I$, $\exists E$).

Skills: Building proofs involving quantifiers. Understanding the restrictions on quantifier introduction rules.

Natural Deduction in FOL (Part 2)#

Topics: Quantifier negation equivalences (e.g., $\lnot\forall x P(x) \Leftrightarrow \exists x \lnot P(x)$). Strategy for proofs in FOL.

Skills: Combining quantifier rules with propositional rules in complex proofs.

Identity#

Topics: The identity predicate ($=$). Rules for identity (reflexivity, $=E$). Translation of definite descriptions ("the king of France") and numerical statements ("at least two", "exactly one").

Skills: Constructing proofs with the identity relation.

Part III: Metatheory and Beyond#

Introduction to Metatheory & Set Theory#

Topics: The distinction between syntax and semantics. Basic concepts of naive set theory (sets, subsets, union, intersection, power sets, relations, functions) needed for metatheory.

Skills: Understanding the formal tools used to prove results about logic systems.

Soundness#

Topics: The concept of soundness: "If you can prove it, it must be true." Sketch of the soundness proof for PL and FOL (proof by induction).

Skills: Articulating the importance of a sound deductive system.

Completeness#

Topics: The concept of completeness: "If it's true, you can prove it." Sketch of the completeness proof for PL and FOL (Henkin-style proof).

Skills: Understanding the deep relationship between syntactic provability and semantic truth.

Limits of Logic#

Topics: Computability and the Halting Problem. Gödel's Incompleteness Theorems: discussion of their statements and profound philosophical implications for mathematics and logic.

Skills: Appreciating the established boundaries of formal systems.