Mathematical Logic


Code 3.4.3229.6
Semester 6th
Flow M - Mathematics
Category Obligatory by selection
Credits 4
Class Hours - Lab Hours 4 - 0
Lecturers Giorgos Koletsos, Petros Potikas (T & R Associates)

Description

Propositional calculus: Language, unique readability, propositional connectives, truth assignments, semantic concepts, completeness of connectives, disjunctive and conjunctive normal forms, compactness theorem of propositional calculus, applications. First-order predicate calculus: Language, variables, free and bound occurrences of variables, substitution, programming analogies, the concept of structure and interpretation of a language, Tarski’s definition of truth, models. Axiomatization of first-order logic: Formal axiom system, analogies with algorithmic concepts, consistency, soundness and Godel’s completeness theorem, undecidability and incompleteness, compactness and Lowenheim-Skolem theorems. Proof theory of propositional and predicate calculus: Gentzen’s sequent calculus, cut elimination, resolution, semantic tableaux, The completeness theorem for predicate calculus via semantic tableaux. Applications to computer science.