| STUDENTS
> Logic and Database Theory
|
Logic and Database Theory
Note:
Whilst every effort is made to keep the syllabus and assessment records correct
for this course, the precise details must be checked with the lecturer(s).
| Code: | 2008 |
| Year: | 2 |
| Prerequisites: | Theory I (1002) and Theory II (1004) |
| Term: | 1 |
| Taught By: | Robin Hirsch (66.6%)
John Dowell (33.3%)
|
| 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 |
Content:
| 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 |
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 sections combined
The examination rubric is:
Answer all three questionsResources:
J. Truss, Discrete mathematics for computer scientists,
Addison-Wesley, 2nd edition, 1999.
W. Hodges, Logic: an introduction to elementary logic,
Penguin, 1977.
Web resources
|
+44 (0)20 7679 7214 - Copyright © 1999-2007
UCL
