Department of Mathematics & Computer Science

MC111 Logic and Discrete Structures

Explanation of Pre-requisites

Course Description

There is no specific pre-supposed knowledge required for this module (other than some elementary topics from Mathematics GCSE or the equivalent) and so the course will start from a fairly basic level. The topics will generally be motivated by examples from Computer Science (and other areas), although no actual knowledge of Computer Science will be assumed.

The course covers both Discrete Mathematics and Logic. In the first half, we start by giving a (somewhat informal) idea of a mathematical argument and then go on to cover topics which are useful in describing computational systems (such as sets, relations, graphs and functions). We next investigate some special functions and their properties (which occur, amongst other places, when analysing the performance of algorithms), and contine this theme by solving certain simple types of recurrence relations (equations where the value of the function at a number is defined in terms of its values at smaller numbers). We then go on study of formal logic; we want to be able to reason about computer systems (for examples, statements like `if we replace ths component then the system will run faster' or `for all possible values of the input my program will terminate'). We will introduce the notation for modelling such statements and then describe the rules for drawing conclusions. We finish the course by drawing many of these strands together by considering formal specifications (i.e. precise mathematical descriptions of what a system is supposed to do).

This material will be described in the lectures (four per week); there will also be a weekly surgery session (for sorting out problems, including difficulties with the assessed work) and a problem class (for going through the previous worksheet). A full set of printed lecture notes for the module is also available.

Aims

The aim of this course is to provide a basic knowledge of some of the Mathematics required for the study of Computer Science. By the end of the module, the students should be able to think abstractly and have some appreciation of the role of Mathematics in Computer Science. In particular, they should understand how Mathematics provides an elegant and efficient framework for modelling (and inferring properties of) computational systems and processes.

Objectives

Transferable Skills

Apart from the use of Mathematics in Computer Science, the study of the material in this course should help students develop their general ability to think abstractly and, consequently, provide them with the ability to be adaptable in a fast-changing subject area. In addition, the module should make a contribution to the general development of problem-solving skills.

Syllabus

Sets. Elements, subsets and proper subsets. Operations on sets (union, intersection, difference). Basic properties of these operations (including De Morgan's laws). Power sets. Orders of sets. Inductive definitions. Proof by induction. Summation of arithmetic series.

Ordered pairs, Cartesian products. Relations. Composition of relations. Graphs. Paths, trees and branches. Matrices (including adjacency matrices of graphs) and matrix operations. Equivalence relations. Partitions and equivalence classes. Modular arithmetic. Partial and total orders. Functions: partial and total functions. Composition of functions. Non-determinism and determinism. Injections, surjections and bijections. The identity map. Inverse of a function.

Factorials. Polynomials (including addition, subtraction and multiplication of polynomials). Exponentials, logarithms and their properties. Counting: permutations and combinations. Pascal's triangle. Elementary probability. Simple recurrence relations and their solution. Summation of geometric series.

Propositional logic. Connectives and bracketing. Main connectives. Turning English statements into formal logic. Syntax versus semantics. Truth tables. Logical equivalence. Validity. Interdefinability of connectives. Proof theory. Soundness and completeness. Theorems and tautologies. Satisfiability. Semantic tableaux: tableaux rules, open and closed tableaux.

Predicate logic. Predicates, function symbols and names. Quantifiers. Free and bound variables. Terms. Atomic formulae, formulae and sentences. Interpretations and models. Substitution. Predicate tableaux: tableaux rules, open and closed tableaux.

Introduction to formal specifications. The idea of a specification. Basic constructs: types, attributes, initializations, invariants and methods. Pre-conditions and post-conditions. Sets, mappings and sequences.

Basic concepts of algorithm analysis; big O notation, asymptotic analysis; algorithm analysis applied to algorithms already introduced elsewhere in the course.

Reading list

Background:

D. F. Stanat and D. F. McAllister, Discrete Mathematics in Computer Science, Prentice Hall, 1977 (out of print but in the Library).

D. J. Velleman, How to Prove It, Cambridge University Press, 1995.

J. Kelly, The Essence of Logic, Prentice Hall, 1997.

J. Truss, Discrete Mathematics for Computer Scientists, Addison Wesley, 1999.

S. Reeves and M. Clarke, Logic for Computer Science, Addison Wesley, 1990 (out of print but in the Library).

W. Hodges, Logic, Pelican, 1977.

A. Galton, Logic for Information Technology, Wiley, 1990 (out of print but in the Library).

R. Johnsonbaugh, Discrete Mathematics, Prentice Hall, 1997.

A. B. Shiflet, Discrete Mathematics for Computer Science, West Publishing Company, 1987.

Details of Assessment

The written May/June examination will contain six questions. These are equally weighted; any number of questions may be attempted, but only the best four answers will be taken into account.

Author: S. J. Ambler, tel: +44 (0)116 252 3884
Last updated: 2001-09-20
MCS Web Maintainer
This document has been approved by the Head of Department.
© University of Leicester.