Description Logic – Second Class Test Revision Notes¶

Target audience: students who missed earlier lectures and are (re)learning Description Logic from scratch.
Goal: cover all DL + Tableau material that is relevant for the second class test, based on lectures and slides.

Part 0. Exam information and suggested study route¶

0.1 What is included / excluded in this class test?¶

From the lecturer’s repeated in-class announcements:

Included in the second class test:

Description Logic (DL) basics:
Concepts, roles, individuals
ABox / TBox, knowledge base \(K = (T, A)\)
Consistency, coherence, entailment: meanings and relations
Tableau method for DL:
The six-step tableau procedure
Preprocessing of TBox and ABox
Applying completion rules
Using tableau to test:
- consistency of a knowledge base,
- coherence of concepts,
- entailment (via reduction to consistency)

Explicitly excluded from this class test:

All Epistemic Logic:
any content about knowledge, belief, multi-agent epistemic logic
DL complexity and extended DL features (27 Nov lecture):
complexity results (e.g. EXPTIME-completeness),
specific named DLs like EL, SHIQ, OWL profiles, etc.
lecturer said this is background for later modules, not examined here
Revision lecture (after the test):
purely for revision and Q&A,
content there does not extend the class test syllabus.

One-sentence summary (as the lecturer phrased it):

“The class test is everything up to Description Logic, up to and including the Tableau method.”
“There is no epistemic logic on the class test.”

0.2 Suggested study route (for starting almost from zero)¶

Recommended reading order for this document:

Part 1: build an intuitive picture of what DL is for.
Part 2: understand ABox, TBox and knowledge bases \(K = (T, A)\).
Part 3 (to be filled): learn the notions of consistency, coherence, entailment and how they relate.
Part 4–5 (to be filled): go through the tableau method step-by-step.
Part 6 (to be filled): look at typical exam-style problems and a last-minute checklist.

注意：Part 3-5 的详细内容参见文档 2_consistency_entailment_tableau.md，Part 6 的详细内容参见文档 3_exam_problems_and_checklist.md。

Part 1. Intuition: what is Description Logic about?¶

This part is not about formal definitions. It is here to give you a mental picture before we introduce syntax and semantics.

1.1 A small “student–course” world¶

Imagine a tiny world with:

People: Alice, Bob, Carol
Courses: Logic, AI
A relation “takes”: e.g. Alice takes Logic.

We want to express statements like:

“Every student is a person.”
“Every student on this module is an undergraduate.”
“Some people do not take any course.”
“Every course has at least one student.”

In Description Logic, we think in terms of:

Concepts (like sets/types):
Student, Person, Course
Roles (binary relations):
takes
Individuals (specific objects):
alice, bob, logic101

DL is designed to help us do two main things:

Represent such structured knowledge clearly:
e.g. “Student is a subclass of Person”
(all students are persons)
define more complex concepts, like “busy student” or “graduate course”.
Reason with this knowledge automatically:
from "Alice is a Student" and \(Student \sqsubseteq Person\) we want to infer
"Alice is a Person".
given a definition like
\( BusyStudent \equiv Student \sqcap (\exists takes.Course \sqcap \exists takes.Course) \)
we want to know whether some individual must be a BusyStudent.

So DL is a family of logics for:

structured representation (like types, classes, ontologies),
and automated reasoning (deriving implicit facts from explicit ones).

1.2 Informal view: concepts, roles, individuals¶

A helpful informal analogy (not fully precise, but good intuition):

Concept:
think “class”, “type”, or “set of individuals”.
examples: Student, Person, Course.
Role:
think “binary relation” or “association between classes”.
examples: takes, teaches, supervises.
Individual:
think “concrete object”, “record”, or “instance”.
examples: alice, bob, logic101.

We will formalise this later, but this picture is enough to continue.

Part 2. ABox, TBox, and knowledge bases¶

From this part onwards, we are firmly inside the exam syllabus.

2.1 Basic DL syntax (ALC-style, simplified)¶

In a basic DL such as ALC, we typically assume:

Atomic concepts (unary predicates):
written with capital letters, e.g.
Student, Person, Course
Atomic roles (binary predicates):
written with lower case, e.g.
takes, teaches, enrolledIn
Individual names:
usually lower case, e.g.
a, b, c (standing for Alice, Bob, Carol),
l (for Logic), etc.

From atomic concepts and roles, we build complex concepts using constructors:

\( \top \) (top):
the concept of “all individuals” (always true).
\( \bot \) (bottom):
the concept of “no individuals” (always false).
\( \neg C \):
complement: individuals that are not in concept \(C\).
\( C \sqcap D \):
conjunction: individuals that are in both \(C\) and \(D\).
\( C \sqcup D \):
disjunction: individuals that are in \(C\) or \(D\).
\( \exists r.C \):
existential restriction: individuals that have at least one \(r\)-successor in \(C\).
\( \forall r.C \):
universal restriction: individuals whose every \(r\)-successor is in \(C\).

Example concepts (you do not need to memorise these; just understand the idea):

“People who take at least one course”:
\( \exists takes.Course \)
“Students all of whose taken modules are passed courses”:
\( Student \sqcap \forall takes.PassedCourse \)

These constructs are what TBox and ABox statements are built from.

2.2 TBox: terminological knowledge (schema / theory level)¶

1) Intuitive view (as explained in lectures)¶

A TBox captures “background knowledge” about the vocabulary:
general, context-independent relationships between concepts.
It is similar to:
a class hierarchy in OOP,
a schema or ontology in databases/semantic web.

It does not talk about specific individuals, only about how concepts relate.

2) Formal style (what you see in slides)¶

Typical TBox statements (axioms) are:

Subsumption (inclusion):
\( C \sqsubseteq D \)
meaning: every instance of \(C\) is also an instance of \(D\).
Example:
- \(Student \sqsubseteq Person\)
Equivalence:
\( C \equiv D \)
meaning: \(C\) and \(D\) denote exactly the same set of individuals.
Example:
- \(Bachelor \equiv Person \sqcap \neg Married\)

A TBox \(T\) is just a finite set of such axioms.

3) How TBox appears in exam-style tasks¶

Typical roles of the TBox in exam questions:

You are given a TBox and asked to reason about concept relationships:
e.g. whether a certain concept is satisfiable or not (coherence).
You use the TBox definitions when preprocessing for the tableau method:
expanding defined concepts,
eliminating subsumptions (using the “star” construction),
ensuring acyclicity is respected.

So you need to:

read and interpret TBox axioms,
apply the preprocessing steps that the lecturer described.

2.3 ABox: assertional knowledge (instance / fact level)¶

1) Intuitive view¶

An ABox contains “facts about particular individuals”:
e.g. “Alice is a Student”,
“Alice takes Logic”.

It is analogous to:

the data rows in a database,
or specific objects in memory with class membership and links.

2) Formal style¶

Typical ABox statements are:

Concept assertions:
\( a : C \)
meaning: individual \(a\) is an instance of concept \(C\).
Example:
- a : Student
Role assertions:
\( (a, b) : r \)
meaning: \(a\) is related to \(b\) via role \(r\).
Example:
- (a, l) : takes

An ABox \(A\) is just a finite set of such assertions.

3) How ABox appears in exam-style tasks¶

In exam questions, typically:

you are given an ABox together with a TBox, forming a knowledge base;
the tableau procedure starts from an ABox (after preprocessing).

You should be able to:

read an ABox and understand what it says in English,
apply the preprocessing steps to it (expanding definitions, NNF, etc.),
follow the tableau rules starting from that ABox.

2.4 Knowledge base \(K = (T, A)\)¶

1) Intuitive picture¶

A knowledge base combines:
a TBox \(T\): general terminological knowledge,
an ABox \(A\): concrete facts about individuals.

So a knowledge base describes:

“what the world is like in general” (TBox),
plus "what is true in this particular situation" (ABox).

2) More formal description¶

A DL knowledge base is written as:

\( K = (T, A) \)

An interpretation (or model) \(\mathcal{I}\) “satisfies” \(K\) if:

\(\mathcal{I}\) satisfies every TBox axiom in \(T\),
and \(\mathcal{I}\) satisfies every ABox assertion in \(A\).

You do not need to reproduce the full formal semantics in the exam, but you do need the key idea:

If there exists at least one interpretation \(\mathcal{I}\) that satisfies \(K\), then \(K\) is consistent.
If no such interpretation exists, then \(K\) is inconsistent.

The notions of consistency, coherence, and entailment will be made precise in Part 3.

3) How knowledge bases are used in the tableau method¶

For the tableau algorithm:

Input: a knowledge base \(K = (T, A)\).
Preprocessing:
rewrite and expand TBox into ABox (Steps 1–3),
convert assertions into Negation Normal Form (Step 4).
After preprocessing:
the tableau runs on a (possibly transformed) ABox,
and tests whether that ABox is satisfiable (i.e. whether the original \(K\) is consistent, or whether an entailment holds, depending on the reduction).