Current students

COMP202P - Logic and Database Theory

This database contains 2016-17 versions of the syllabuses. For current versions please see here.

Code COMP202P
Year 2
Prerequisites Theory I (102P) and Theory II (104P). Students will be required to implement a program in C, so some programming experience is desirable.
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 a number of logical inference methods for classical logics.
Learning Outcomes Students should understand how axiomatic systems can be used for propositional and predicate logic and they should understand the notions of soundness and completeness. They should also understand how propositional and predicate tableaus work. They should have familiarity with other logics, including modal and temporal logics. They should be able to analyse relational databases.

Content:

Propositional and Predicate logic
Review of syntax and semantics.
Deduction and Inference.
Truth tables. 
Decidability of propositional logic.

Mathematical proofs
Proof by contradiction.
Induction and structured induction.
Hilbert systems.
Axioms and inference rules for propositional logic.
Axioms and inference rules for predicate logic.
Tableau.
Tableau construction for propositional logic and predicate logic.
Soundness and completeness theorems for first order logic.
Semi-decidability of first order logic.

Finite computation methods
Finite state machines.
Regular languages.
Kleene's theorem.
Finite state machines with stacks.

Databases
1. Database management systems (DBMS) and the relational database:  essential concepts, data model, architecture and primary functions of the DBMS.
2. SQL: use of SQL as a language for database construction and data manipulation
3. Database design: a structured method for designing relational databases through data modelling, schema specification, validation and normalisation.

Method of Instruction:

Lecture presentations with associated courseworks.

Assessment:

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 components combined;
  • Obtain a minimum mark of 30% in each component worth ≥ 30% of the module as a whole.

Resources:

J. Truss, Discrete mathematics for computer scientists, Addison-Wesley, 2nd edition, 1999.

 

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