## MATH2042 Logic with Computation

### 15 creditsClass Size: 160

Module manager: Dr Andrew Brooke-Taylor
Email: a.d.brooke-taylor@leeds.ac.uk

Taught: Semester 2 (Jan to Jun) View Timetable

Year running 2020/21

### Pre-requisites

 MATH2920 Computational Mathematics

### This module is mutually exclusive with

 MATH2041 Logic PHIL2122 Formal Logic

Module replaces

MATH2040 Mathematical Logic 1

This module is not approved as a discovery module

### Module summary

Logic is the study of reasoning itself. Since its origins in ancient Greece, logic has evolved into a wide and vibrant subject, with many important applications to other areas of mathematics and to computer science. A typical application in mathematics is to decide whether a certain statement can be proved from a given set of axioms (e.g. whether the axiom on parallel lines follows from Euclid’s other axioms). In computer science, ever since the pioneering work of Turing, logic has played a fundamental role in describing and analysing algorithms. The module will provide an introduction to logic, with emphasis on its computational applications.

### Objectives

On completion of this module, students should be able...
1. To describe the fundamental notions of mathematical logic, including the distinction between syntax and semantics.
2. To present a proof of the completeness theorem in the propositional case and introduce a first order predicate calculus.
3. To describe the fundamental notions of Computational Logic, including algorithmic proof verification.

Learning outcomes
1. To express logical arguments in a formal language and thereby to analyse their correctness.
2. To distinguish between syntax and semantics, and give simple formal proofs in a natural deduction system.
3. To give a proof by induction on a finite tree.
4. To apply the soundness and completeness theorems to establish whether a formula is derivable from a set of axioms or not.
5. To understand the working of fundamental algorithms in computational logic.

### Syllabus

1. Propositional Logic. Syntax. Semantics. Satisfiability, tautologies, contradictions. Disjunctive and conjunctive normal forms. A formal proof system. Completeness and compactness.
2. Boolean algebras and partially ordered sets.
3. Predicate Logic. Language and syntax. First-order structures. Truth in a structure. Prenex normal form. A formal proof system.
4. Data-types for propositional logic. Algorithms for checking well-formed formulas. Algorithms for constructing parse trees. Algorithms for satisfiability. Construction of formal natural deduction proofs for propositional logic in software.Algorithms for proof-checking.
5. Formal manipulations of Boolean algebras in software.
6. Data-types for first-order formulas and natural deduction proofs for first-order logic. Construction of formal natural deduction proofs for first order logic in software. Algorithms for proof-checking.

### Teaching methods

Due to COVID-19, teaching and assessment activities are being kept under review - see module enrolment pages for information

 Delivery type Number Length hours Student hours Workshop 10 1.00 10.00 Class tests, exams and assessment 1 2.00 2.00 Lecture 11 1.00 11.00 Practical 5 2.00 10.00 Tutorial 5 1.00 5.00 Private study hours 112.00 Total Contact hours 38.00 Total hours (100hr per 10 credits) 150.00

### Private study

Studying and revising of course material. Completing of assignments and assessments.

### Opportunities for Formative Feedback

Regular problem-solving assignments.

### Methods of assessment

Due to COVID-19, teaching and assessment activities are being kept under review - see module enrolment pages for information

Coursework
 Assessment type Notes % of formal assessment Computer Exercise . 30.00 In-course Assessment . 10.00 Total percentage (Assessment Coursework) 40.00

In order to pass the module, students must pass the MATH2041 component (which is at least 40% on exam and in-course assessment combined) and score at least 40% on the Computer Exercises.

Exams
 Exam type Exam duration % of formal assessment Open Book exam 2 hr 00 mins 60.00 Total percentage (Assessment Exams) 60.00

Students who have failed the MATH2041 component will need to resit the exam; students who have failed the computer exercises will need to resubmit these. There is no resit available for the 10% in-course assessment component of this module. If the module is failed, the mark for this component will be carried forward and added to the resit exam and/or computer exercises mark with the same weighting as listed above.