Mathematical Logic

Recommended Prerequisites

Basic courses on Analysis, Algebra, Programming.

Teaching Methods

Classes are expository, with presentation of detailed proofs on the blackboard. The lectures include exercises and voluntary homework.

Learning Outcomes

The main goal is to familiarize students with classical mathematical logic (symbolic logic) that aims to formalize propositions of informal language, in particular with respect to mathematical propositions and mathematical reasoning. The ambiguities of informal language led to a more and more symbolic language. It is one of the aims of the course to reflect these developments in the chapters on propositional and predicate logic. The third part of the course is an introduction to topics of the theory of computation.

One hopes that the lectures augments the students aptness to formalize propositions and arguments; augments their aptness to discern between fallacious and correct reasoning in mathematics; clarifies the historic and technical rôles of symbolic logic in mathematics and computer science; and conveys, in particular, knowledge on formal deductive systems and Turing machines.

Work Placement(s)

No

Syllabus

Propositional Logic (CP) 1. Alphabet, valuations, tautologies, contingencies, contradictions. Substitution theorems, associativity, DNF. Boolean algebras and functions 2. Applications: analysis of arguments, electrical and logical circuits 3. Simplification of formulas. Connections with algorithmic complexity 4. Compactness of PC 5. Formal systems of deduction. A formal system (Hilbert) for CP. Deduction and completeness theorems. First Order Logic (FOL) Alphabet, terms, atomic and prime formulas. Applications. Theorems of FOL. Computability, Decidability, Enumerability 1. Algorithms and Turing machine. Computability 2. Computable functions. Quantification of relations. Theorems of composition, recursion and minimum operator. Computability of common functions. Existence of non-computable functions 3. Decidibility of relations (order and equality relations) 4. Algorithmic indecidibility of the halting problem 5. Listability. Listable but indecidable sets.

Head Lecturer(s)

Alexander Kovacec

Assessment Methods

Final assessment
Mini Tests: 30.0%
Exam: 70.0%

Continuous assessment
Mini Tests: 30.0%
Frequency: 70.0%

Bibliography

J. Malitz, Introduction to Mathematical Logic, Springer, 1978.

B. Margaris, First Order Logic, Dover, 1970.

E. Mendelsson, Introduction to Mathematical Logic, v. Nostrand, 1966.

A. Kovacec, Lógica (notas de curso), Departamento de Matemática da FCTUC, 2007.

A.J. Franco de Oliveira, Lógica e Aritmética, Gradiva, 2003.

P.J. Davis, R. Hersh, A Experiência Matemática, Gradiva, 1995.