## MATH2040 Mathematical Logic 1

### 10 creditsClass Size: 200

Taught: Semester 1 View Timetable

Year running 2005/06

This module is approved as an Elective

### Objectives

To describe the fundamental notions of mathematical logic, including the distinction between syntax and semantics. To present a proof of the completeness theorem in the propositional case and introduce a first order predicate calculus. On completion of this module, students should be able to: (a) express logical arguments in a formal language, and thereby to analyse their correctness; (b) find disjunctive normal form for a propositional formula and prenex normal form for a first order formula; (c) distinguish between syntax and semantics, and give simple formal proofs in a natural deduction system.

### Syllabus

Mathematical logic means both the mathematics of logic, that is, the mathematical study of all forms of reasoning, and also the logic of mathematics, that is studying the particular methods of reasoning used in mathematics. The common approach is to focus attention on the language which is used to express arguments, and study formal languages whose syntax is precisely defined. Mathematical logic is useful because it throws light on mathematics itself, and because it can be applied to problems in philosophy, linguistics, and other areas. In recent times some fruitful applications of logic have been to theoretical computer science. This should not deter those who do not like practical computing. Indeed, one of the main achievements of mathematical logic has been to prove that there are precisely defined mathematical problems that computers cannot solve - a comforting thought. This course is an introduction to mathematical logic and will concentrate on the definition of formal languages which can be used to express mathematical ideas, leaving many of the topics just mentioned for further development in later courses. Topics covered include: 1. Propositional Calculus; Semantics. Notion of formula (well-formed formula). Algorithms for parsing expressions. Syntax of a standard propositional calculus. Semantics via truth-tables. The notion of semantic (logical) consequence. Tautologies, contradictions, satisfiability, models. Disjunctive and conjunctive normal form. Finite Boolean algebras. 2. Formal Proofs. Formal proofs in a natural deduction proof system. Deductions and theorems. Soundness. A proof of the completeness of propositional logic. Decidability of satisfiability. Use of propositional logic to formalize everyday reasoning. 3. Predicate Logic. Introduction to predicate logic. The notion of a first order structure and Tarski's definition of truth. Manipulations of the quantifiers and prenex form. Formal proofs in predicate logic.

### Teaching methods

Lectures (22 hours) and examples classes (11 hours).

### Methods of assessment

2 hour written examination at end of semester (100%).