Mathematical Logic

Syllabus Details

• Unit I: (Classical Propositional Calculus) Syntax: Propositional formulae, height and length of formula, proof by induction on the set of formulae, the decomposition tree of a formula, the unique decomposition theorem, substitution in a formula, Valuations and truth tables, Truth functions, Logical equivalence relation.
• Unit II: (Semantics and Normal Forms) Semantic consequence and satisfiability. Compactness theorem with application. Adequacy of connectives. Normal forms.
• Unit III: (Axiomatic Approach to Propositional Calculus) Sequent calculus, Soundness, consistency, completeness.
• Unit IV: (Classical First Order Logic and First Order Theories) Syntax, Satisfaction, truth, validity in FOL.
• Unit V: (Axiomatic Approach and Completeness) Axiomatic approach, soundness. Consistency of FOL and completeness (sketch), Equality, Examples of first order theories with equality.

Course Learning Objective

1. Get some exposure to the foundations of mathematics.
2. Understand the logic of propositions and analyze various aspects of propositional formulae.
3. Determine the need for axiomatic approach to propositional logic and prove soundness and completeness theorems.
4. Understand the first order logic as generalization of propositional logic and analyze various aspects of the languages associated with structure and formulae.

Recommended Books

1. Cori, R. and Lascar, D., Mathematical Logic, Oxford University Press, 2001.
2. Singh, Arindama., Logics for Computer Science, 2nd ed., PHI Learning, 2018.
3. Chiswell, I. and Hodges, W., Mathematical Logic, Oxford University Press, 2007.
4. Kelly, J., The Essence of Logic, Pearson, 2011.
5. Margaris, A., First Order Mathematical Logic, Dover Publications, 1990.