# 2019/20 Undergraduate Module Catalogue

## 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 View Timetable

**Year running** 2019/20

### 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

Delivery type | Number | Length hours | Student hours |

Workshop | 10 | 1.00 | 10.00 |

Class tests, exams and assessment | 1 | 2.00 | 2.00 |

Lecture | 22 | 1.00 | 22.00 |

Practical | 5 | 2.00 | 10.00 |

Tutorial | 5 | 1.00 | 5.00 |

Private study hours | 101.00 | ||

Total Contact hours | 49.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

**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 |

Standard exam (closed essays, MCQs etc) | 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.

### Reading list

There is no reading list for this moduleLast updated: 30/09/2019

## 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