lernzettel_knowledge-representation_30-04-26

Lernzettel: Knowledge Representation I & II

Methods of AI — SoSe 2026 · 1-page exam sheet

For more depth: Description Logics (full reference with all algorithms, Tableaux examples, deep explanations) · quiz_knowledge-representation_30-04-26 (7 practice questions)

Core Ideas

• KR = formal representation of information so machines can reason about it.
• Trade-off: expressivity vs. decidability.
• Description Logics (DL): decidable fragments of FOL focused on concepts (classes) and roles (binary relations).
• A KB = TBox (schema) + ABox (facts) = an ontology.
• All DL reasoning reduces to (un)satisfiability — tested with Tableaux.

Mini-glossary

Term	Meaning
TBox	terminological axioms (general statements about classes)
ABox	assertions about named individuals (facts)
GCI	General Concept Inclusion C ⊑ D — every C is a D
C ⊑ D	subsumption (Cᴵ ⊆ Dᴵ) — direction matters!
C ≡ D	equivalence: C ⊑ D and D ⊑ C
ALC	Attributive Concept Language with Complements — base DL
OWA	Open World Assumption — what’s not stated = unknown (used by DL/OWL)
CWA	Closed World Assumption — what’s not stated = false (databases, STRIPS)
OWL	Web Ontology Language — built on DLs (W3C standard)
Tableaux	model-construction algorithm; tests (un)satisfiability
clash	A(x) and ¬A(x) for some individual — closes a tableau branch
NNF	Negation Normal Form — push ¬ inward to atoms before tableau

⭐ Full glossary + Tableaux walkthrough → Description Logics

ALC constructors (one compact table)

Constructor	Syntax	Meaning
Atomic	A	a named class
Top / Bottom	⊤ / ⊥	universe / empty
Negation	¬C	complement
Intersection	C ⊓ D	both
Union	C ⊔ D	either
Value restriction	∀R.C	every R-filler is C (vacuously true if no R-filler!)
Existential	∃R.C	some R-filler is C

Roles R are atomic binary relations. No role hierarchy in pure ALC — adding it gives ALCH.

Reasoning tasks (all via Tableaux)

Task	Test
Satisfiability of C	TABLEAUX-SAT(C) = SAT
Subsumption C ⊑ D	TABLEAUX-SAT(C ⊓ ¬D) = UNSAT
Equivalence	C ⊑ D and D ⊑ C
Instance check a : C	TABLEAUX-SAT(KB ∪ {a : ¬C}) = UNSAT

Common Exam Traps ⚠️

• TBox ≠ ABox: TBox = class-level schema; ABox = individual facts.
• OWA: in DL/OWL, “not stated” ≠ false. Absence of info = unknown.
• C ⊑ D means every C is a D — direction matters, not the reverse.
• Pure ALC has no role hierarchy — add the H extension → ALCH. (Don’t confuse with SROIQ, which has S, R, O, I, Q on top.)
• ALC = Attributive Concept Language with Complements (slide 31). Don’t write “Attributive Language with Complement”.
• Tableaux tests (un)satisfiability, not truth. Subsumption goes via C ⊓ ¬D unsatisfiable.
• ∀R.C(x) is vacuously true if x has no R-successors — so ∀hasChild.⊥ correctly describes “childless”.
• Allen’s tense logic: 7 base + 6 inverses = 13 relations (EQUAL is symmetric, so its inverse is itself).
• RCC-8 = topological (regions + C(x,y)), not metric.
• OWL Lite / DL / Full is NOT in the lecture slides — the slides only list DL extension letters (U, C, O, E, N, H). Cite letters, not dialect names.
• OWA/CWA itself is NOT in the KR I/II slides — external background; mentioned here because it underlies how DL inference behaves.

Quick comparison (DL vs. FOL)

Aspect	FOL (classical)	DL (ALC)
Focus	arbitrary statements	concepts (classes) + roles
Variables	explicit quantifiers	none in concept syntax
Reasoning	resolution (semi-decidable)	Tableaux (decidable for ALC)
World assumption	varies	OWA (always)
Expressivity	very high (undecidable)	deliberately restricted (decidable)
Typical use	mathematical formalisation	ontologies, semantic web (OWL)

Related Q&A & Notes

Practice quiz

• quiz_knowledge-representation_30-04-26 — 7 questions

Targeted exam questions in Questions for Methods of AI

• Q47–55 (basic: ontology, ALC, TBox/ABox, tableaux, OWL, RDF, SPARQL) · Q101 (ontologies, upper ontologies) · Q102 (TBox vs. ABox) · Q120–122 (deep / exam-trap: TBox vs. ABox unique reasoning tasks, OWA vs. CWA pitfall, ∀R.C vacuous-truth trap)

Atomic notes

• Description Logics · Allen’s Tense Logic · RCC-8

See also

Tags: methods-of-ai lernzettel ai-generated
Full reference: Description Logics
Quiz: quiz_knowledge-representation_30-04-26
Superlink: Methods of AI Lecture
Questions hub: Questions for Methods of AI

Created: 30/04/26