Code

COMP2008

Year

2

Prerequisites

Theory I (1002) and Theory II (1004)

Term

1

Taught By

Robin Hirsch (67%)
John Dowell (33%)

Aims

To introduce and familiarise students with logical and mathematical inference and with database theory, the latter having an emphasis on the fundamentals of relational database systems and SQL. Students learn syntax and semantics of first-order logic, various proof methods and elementary models of computation.

Learning Outcomes

Students should be able to use first-order proof techniques to derive valid conclusions from premises, but they should be aware of the limitations of these techniques. They should be able to analyse relational database

Predicate logic

Syntax - variables and quantifiers. Free and bound variables, and scope of a variable.
Semantics, Validity and satisfiability in a model. Validity and satisfiability in general.
Proof theory - tableau systems and Hilbert systems.
Translating from natural language to predicate logic and vice versa.
Main theorems: soundness and completeness of tableau method, Herbrand models; Godel's incompleteness theorem

Mathematical proofs

Proof by contradiction
Induction and structured induction

Finite computation methods

Finite state machines
Regular languages
Kleene's theorem
Finite state machines with stacks

Applications of predicate logic

Case studies of using predicate logic in information technology, including relational databases, software engineering, and artificial intelligence

Databases

What is a database and a database system?
Data Models
The Entity-Relationship Model
The Relational Model and SQL
New Technologies

Lecture presentations with associated courseworks.

The course has the following assessment components:

• Written Examination (2.5 hours, 95%)
• Coursework Section (2 pieces, 5%)

To pass this course, students must:

• Obtain an overall pass mark of 40% for all sections combined

The examination rubric is:
Answer all three questions

J. Truss, Discrete mathematics for computer scientists,

Addison-Wesley, 2nd edition, 1999.

W. Hodges, Logic: an introduction to elementary logic,

Penguin, 1977.

Web resources