Computer Science Comprehensive Exam
Logic Syllabus
1997-1998
Topics:
Propositional Logic - Syntax
- Well-formed formulas
- Unique readability
Propositional Logic - Semantics
- Interpretations and satisfaction
- Validity, satisfiability, and unsatisfiability
- Logical implication and material implication
- Completeness of connectives
Propositional Logic - Decision Procedures
- Truth tables
- Complexity (NP-completeness)
- Compactness
First-Order Logic - Syntax and Semantics
- Terms and formulas
- Structures, assignments, and semantics
- Satisfiability, validity, and logical implication
First-Order Logic - Definability
- Preservation under isomorphism
- Elementary equivalence vs. isomorphism
- Definability: classes of structures, relations
- Compactness and applications to definability
First-Order Logic - A Formal System
- Deductions
- Propositional Reasoning
- The Deduction Theorem
- Soundness
First-Order Logic - Completeness and Consequences
- Completeness
- Lowenheim-Skolem Theorm
- Compactness Theorem
- Models and theories
First-Order Logic - Undecidability and Incompleteness
- Recursive enumerability of validity
- Non-recursive enumerability of satisfiability
- Godel's Incompleteness Theorem
Second-Order Logic
- Second-order languages
- Skolemization
References:
- H.B. Enderton: A Mathematical Introduction to Logic,
Academic Press, 1972, Chapters 1,2,4.1-4.2