2005/06 Undergraduate Module Catalogue

MATH2040 Mathematical Logic 1

10 creditsClass Size: 200

Taught: Semester 1 (Sep to Jan) 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%).

Reading list

The reading list is available from the Library website

Last updated: 13/05/2005

Disclaimer

Browse Other Catalogues

• Undergraduate module catalogue
• Taught Postgraduate module catalogue
• Undergraduate programme catalogue
• Taught Postgraduate programme catalogue

Errors, omissions, failed links etc should be notified to the Catalogue Team.PROD