Skip to navigation | Skip to main content | Skip to footer
Menu
Menu

Current postgraduate taught students

COMP60162: Knowledge Representation and Reasoning (2007-2008)

This is an archived syllabus from 2007-2008

Knowledge Representation and Reasoning
Level: 6
Credit rating: 15
Pre-requisites: Some knowledge of logic and formal methods
Co-requisites: No Co-requisites
Lectures: 1 day per week (5 weeks)
Course lecturer: not assignedAdditional staff: view all staff
Timetable
SemesterEventLocationDayTimeGroup
Sem 1 w7-11 Lecture 2.15 Wed 09:00 - 17:00 -
Assessment Breakdown
Exam: 40%
Coursework: 60%
Lab: 0%

Introduction

For many applications, specific domain knowledge is required. Instead of coding such knowledge into a system in a way that it can never be changed (hidden in the overall implementation), more flexible ways of representing knowledge and reasoning about it have been developed in the last 10 years. These approaches are based on various extensions of classical logic: modal logic, agents logics, or description logics. They can be used to reason about the terminology of a domain or the behaviour of systems. Computer-based tools can then use this kind of reasoning to support the user. In particular description logics have recently been used as foundational tools for the semantic web.

Aims

This course unit aims to provide an introduction to various extensions of classical logic, how to formalise knowledge and questions about this knowledge in these logics and how to use automated reasoning systems for answering these questions. Students should have some knowledge about logic and will deepen it in the first pre-course week. The course unit aims to:
provide students with an understanding of different kinds of knowledge and the logics developed to represent this kind of knowledge together with the underlying theory necessary for applying automated reasoning systems (based on propositional, first order, modal, and description logic)
study a range of techniques to formalise and represent knowledge within these logics, and, finally,
allow students to use various automated reasoning tools to reason about knowledge represented in these logics.

Learning Outcomes

A student completing this course unit should:
have knowledge and understanding of the syntax and semantics of modal, description, and temporalised description logics, defaults, and formal concept analysis (A)

1. be able to formalise and represent knowledge in these logics and relate questions concerning this knowledge to logical reasoning problems (A and B)

2. have knowledge and understanding of a selection of logic-based applications (A and B)

3. be able to use standard proof systems, in particular Hilbert-style deduction and a translation-based approach for modal logics, subsumption algorithms for description logics (B)

4. be able to use various systems (SPASS, ICOM) and apply them to solve problems (C)

Assessment of Learning outcomes

Learning outcomes (1), (2), (3), (4) will be assessed by exam. All learning outcomes will be assessed via coursework exercises.

Contribution to Programme Learning Outcomes

A1, A2, B2, B3, and C3

Syllabus

The following lists topics to be covered in the pre-course work and taught week. The number of lectures for each topic are given in brackets. If the topic is to be covered in the pre-course work or in the supervised labs, then this is also indicated:

Introduction and motivation.


Including example problems, problem representation via logic, computer assisted reasoning in mathematics.

Elementary set theory.


What is a set, a relation, a function, set operations (intersection, union, etc), properties of binary relations (reflexivity, symmetry, transitivity, etc).

Propositional logic.


Theory, language, models, validity and satisfiability, inference rules, soundness and completeness, reasoning methods: truth tables, proof by contradiction.

First-order logic.


First order logic formulae, their meaning, validity and satisfiability, translating between natural language and first-order logic.

Early knowledge representation formalisms [1].


Nonmonotonic inheritance networks, frame-based systems.

First-Order Logic [2, supervised lab]

.
First order logic formulae, their meaning, reasoning problems, useful normal forms, inference calculus, undecidability and semi-decidability.

Modal Logic: Representation and reasoning on the semantical level [4.5, supervised lab].

Modal logic, possible worlds semantics, model checking, satisfiability and validity, correspondence theory.

Modal Logic: Reasoning calculi, agent applications [4, supervised labs].


Logically omniscience problem, belief logic, epistemic logic, deduction in Hilbert systems, deduction via translation to first-order logic.

Description logics [3.5, supervised labs].


Language of description logics, meaning of description logic statements, reasoning calculi, introduction to the semantic web and ontologies using description logics.

Icom [2, supervised labs].


EER diagrams, relationship between EER diagram and description logic, reasoning about EER diagrams.

Non-standard reasoning services in description logics [2, supervised labs].


Least common subsumers, most specific concepts, and their usage in description logic applications.

Temporal logic [3, supervised labs].


The temporal logic LTL, its extension to temporalised modal and description logics, their applications.

Defaults, in propositional and first order logic [3, supervised labs].


Defaults, motivation for ordered defaults, e.g. in description logics, their applications.

Coursework


Exercises and assignments are of varying difficulty - those in the teaching week are aimed to consolidate the material of the lectures and are thus easier. Some exercises and assignments are to be done with pencil and paper, some will require the use of tools (SPASS for the ML, ICOM for the DL part).

Additional Information


Additional information may be found at the course unit webpage

Reading List

There is no single book covering all the material, but the following gives a good introduction to logical systems and reasoning methods:

Notes will made available to cover the systems (SPASS and ICOM) and all of the various topics presented in the course.

There are many other textbooks available on the topics covered. The following gives a selection of those that would be useful to refer to:

Modal Logic:


Recommended reading is Chapter 3 on modal logic and its applications in the book by M. Huth and M. Ryan, Logic in Computer Science: Modelling and Reasoning about Systems, Cambridge University Press, 2000.

Description logics:


Recommended Reading is the chapter by F. Baader and W. Nutt, Basic Description Logics, in the Description Logic Handbook (edited by F. Baader, D. Calvanese, D.L. McGuinness, D. Nardi, P.F. Patel-Schneider, Cambridge University Press, 2002, pp. 47-100).
Further details will be presented in the taught week.

Supplementary Text
Title: Description Logic Handbook
Author: Franz Baader, Diego Calvanese, Deborah Mcguinness, Daniele Nardi, Peter Patel-Schneider
ISBN: 0521876257
Publisher: Cambridge University Press
Edition: 2nd
Year: 2007


Supplementary Text
Title: Logic in Computer Science: modelling and reasoning about systems (2nd edition)
Author: Michael Huth, Mark Ryan
ISBN: 9780521543101
Publisher: Cambridge University Press
Edition: 2nd
Year: 2004


Supplementary Text
Title: Essence of logic
Author: Kelly, John
ISBN: 0133963756
Publisher: Pearson Education Limited
Edition:
Year: 1997