[The University of Leicester]

Department of Mathematics & Computer Science



Next: CO1015 Information Systems Up: Year 1 Previous: CO1006 Software Engineering and Professional Practice

CO1011 Logic and Discrete Structures

CO1011 Logic and Discrete Structures

Credits: 20 Convenor: Dr. Stefan Dantchev Semester: 2
Prerequisites:
Assessment: Coursework: 30% Three hour exam in June: 70%
Lectures: 48 Problem Classes: 12+24(voluntarily)
Tutorials: none Private Study: 78
Labs: none Seminars: none
Project: none Other: none
Surgeries: 12 Total: 150

Subject Knowledge

Aims

This module teaches the basic concepts from Discrete Mathematics and Logic that are needed in the study of Computer Science.

Learning Outcomes

Students should be able to give an account of, and solve problems, in logic and discrete mathematics; to apply this knowledge to estimate the efficiency of some simple algorithms; and to gain some basic insight in the formal specification of programs.

Methods

Class sessions together with course notes, surgeries, class tests worksheets, voluntary problem classes, some additional hand-outs and web support.

Assessment

One marked coursework, eight class tests, traditional written examination.

Subject Skills

Aims

To teach students scientific writing and problem solving skills.

Learning Outcomes

Students will be able to: to read and write phrases in formal language and to translate back and forth between plain English and a formal language; to analyse the validity of simple arguments with help of truth tables and semantic tableaux; to write short, clear, note based, summaries of logical/mathematical knowledge; to solve abstract and concrete problems (both routine seen, and simple unseen), including numerical/algebraic data.

Methods

Class sessions together with course notes, surgeries, class tests worksheets, voluntary problem classes, some additional hand-outs and web support.

Assessment

One marked coursework, eight class tests, traditional written examination.

Explanation of Pre-requisites

There is no prerequisite knowledge required for this module apart from some topics from GCSE Mathematics.

Course Description

The main purpose of this course is to teach the basic concepts from Discrete Mathematics and Logic that are needed in the study of Computer Science. While the main purpose is to learn the necessary Mathematics, the course is taught from a Computer Science viewpoint throughout. It is divided into two relatively independent parts.

The first one, Logic, is motivated by Formal Specifications. We start by giving a (somewhat informal) idea of a mathematical argument and then go on to cover several topics from Propositional and Predicate Logic such as the syntax, truth tables, tautologies, semantic tableaux, quantifiers, models, predicate tableaux. We then introduce some topics which are useful in describing computational systems such as sets, relations, functions, and finish with Formal specifications by introducing a subset of a real specification language, VDM .

The second part, Discrete Mathematics, is motivated by Analysis of Algorithms. We start by revising some fundamental concepts such as number systems, polynomials, solving simple equations. We then introduce more advanced topics such as induction (both inductive definitions and inductive proofs), graphs, matrices, equivalence relations (including modular arithmetic), counting. We finish by using all these to analyse some simple sorting and searching algorithms.

This material will be described in the lectures (four per week); there will also be weekly problem classes (for sorting out problems, including difficulties with the assessed work) and a surgery session (for going through the previous worksheet). The course is based on a textbook. Few topics, which are not covered by the textbook, can be found in the handouts we will distribute.

Syllabus

Part 1. Logic and Formal Specification.

  1. An introduction to reasoning. The notion of proof and examples of proofs. Direct proofs. Proofs by contradiction and contraposition.

  2. Propositional logic. Syntax. Debracketing. Main connectives. Turning English statements into formal logic. Truth tables and valuations. Logical equivalence. Interdefinability of connectives. Valid arguments and tautologies. Satisfiability. Semantic tableaux: tableaux rules, open and closed tableaux.

  3. Predicate logic. Predicates and names. Quantifiers. Models and counter-examples. Predicate tableaux: tableaux rules, open and closed tableaux.

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

  5. 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. Use in specifications. Ordered pairs, Cartesian products. Relations. Functions: partial and total functions. Use in specifications. Non-determinism and determinism. Sequences. Concatenation and other operations. Use in specifications.

Part 2. Discrete Structures and Algorithm Analysis.

  1. Number systems (integers, rationals, reals). Polynomials (including addition, subtraction and multiplication of polynomials). Solving linear and quadratic equations.

  2. Inductive definitions. Proof by induction. Summation of arithmetic series.

  3. Graphs. Paths, trees and branches. Composition of relations. Matrices (including adjacency matrices of graphs) and matrix operations.

  4. Equivalence relations. Partitions and equivalence classes. Modular arithmetic. Composition of functions. Injections, surjections and bijections. The identity map. Inverse of a function.

  5. Factorials. Exponentials, logarithms and their properties. Counting: permutations and combinations. Pascal's triangle. Elementary probability. Simple recurrence relations and their solution. Summation of geometric series.

  6. Basic concepts of algorithm analysis applied to some simple sorting and searching algorithms.

Reading list

Essential:

Kenneth H. Rosen, Discrete Mathematics and Its Applications, 5th edition, McGraw-Hill.

Resources

Textbook, web page, study guide, worksheets, class tests, handouts, past examination papers; lecture rooms with white/blackboards, two OHPs and data projector, tutorial rooms with assistants; and a marked assignment system.

Module Evaluation

Course questionnaires, course review.

Next: CO1015 Information Systems Up: Year 1 Previous: CO1006 Software Engineering and Professional Practice

[University Home] [MCS Home] [University Index A-Z] [University Search] [University Help]

Author: N. Rahman, tel: +44 (0)116 252 3902
Last updated: 2003-09-23
MCS Web Maintainer
This document has been approved by the Head of Department.
© University of Leicester.