CMSC 450 ELEMENTARY LOGIC AND ALGORITHMS

Catalog Description

This is the same course as MATH 444. An elementary development of propositional logic and predicate logic with an introductory treatment of Turing machines, recursive functions, unsolvable problems, and applications of logic in artificial intelligence.

Prerequisites

MATH 141 or CMSC 251.

Topics

  1. Sentential logic\\ The formal language, truth assignments, induction and recursion, completeness, compactness and effectiveness.
  2. First order logic\\ The formal language, truth assignment and models, deduction, completeness and soundness, models of theories, resolution theorem proving.
  3. Undecidability\\ Representability, decidability, computability; Godel numbering; incompleteness and undecidability; recursive funtions.

Course Text

H.B. Enderton, A Mathematical Introduction to Logic, Academic Press, 1972.

Typical Grading and Workload