Topics include propositional and predicate logic, natural deduction systems, models, and the syntactic notion of proof versus the semantic notion of truth, including soundness and completeness. The incompleteness theorems are also covered. Math 277 or equivalent. Math 254, or ComSci 315, or consent of instructor. Programming knowledge not required.
Predicate logic is a precise logical system developed to formally express mathematical reasoning.
Prolog is a computer language intended to implement a portion of predicate logic. This course covers both predicate logic and Prolog, presented to complement each other and to illustrate the principles of logic programming and automated theorem proving. Topics include syntax and semantics of propositional and predicate logic, tableaux proofs, resolution, Skolemization, Herbrand's theorem, unification, refining resolution, and programming in Prolog, including searching, backtracking, and cut. Math 250 or 255, and experience with mathematical proofs. Topics include automata theory, regular languages, CFL's, and Turing machines.