Logik und wissensbasierte Systeme: Vorwärts- und Rückwärtsverkettung, Resolution und Expertensysteme

Wissensbasis, Folgerung und Modellprüfung, Hornklauseln, Vorwärts- und Rückwärtsverkettung, Resolution, Prolog und Expertensysteme von MYCIN bis zu Wissensgraphen — an einem kleinen System, das ein Tier erkennt.

15 Minuten Matěj Žalmánek 2026-10-15

Serie KI-Grundlagen Teil 24 von 52

Der ganze Lehrplan der Serie 52 von 83 Themen fertig

Was du mitnimmst

Was es heißt, dass aus einer Wissensbasis etwas folgt, und warum das Prüfen aller möglichen Welten unbrauchbar langsam ist.
Wie Vorwärts- und Rückwärtsverkettung aus „Wenn–dann“-Regeln Schlüsse ziehen und wann man welche verwendet.
Warum Expertensysteme erfolgreich waren und an Grenzen stießen und wo handgeschriebenes Wissen bis heute weiterlebt.

Vorher gut zu wissen: Logik und Beweise: die Regeln, nach denen KI schließt

Bevor Maschinen anfingen, aus Daten zu lernen, versuchte man, künstlicher Intelligenz Wissen von Hand beizubringen: aufschreiben, was eine Expertin weiß, als „Wenn–dann“-Regeln, und den Computer daraus Schlüsse ziehen lassen. So entstanden die Expertensysteme der Siebziger- und Achtzigerjahre, die Infektionen diagnostizierten oder Computer nach Auftrag konfigurierten. Dann stießen sie an ihre Grenzen, und es kam ein KI-Winter. Ihre Ideen sind aber nicht verschwunden — sie leben im Prolog weiter, in den Wissensdatenbanken hinter Suchmaschinen und in der Überprüfung dessen, was Sprachmodelle behaupten.

Dieser Teil knüpft an Logik und Beweise an, wo du Junktoren, Implikation und Modus ponens findest.

1. Wissensbasis und Inferenzmaschine

Definition — Wissensbasis

Eine Wissensbasis KB ist eine Menge von Sätzen einer formalen Sprache (hier der Aussagenlogik), die das System für wahr hält. Das System kann mit ihr zwei Dinge tun: mitteilen — einen neuen Satz zu KB hinzufügen — und fragen — herausfinden, ob ein Satz α aus KB folgt.

Einfach gesagt

Eine Wissensbasis ist ein Heft, in das du schreibst, was gilt: „Jedes Tier mit Fell ist ein Säugetier“, „dieses Tier hat Fell“. Die Inferenzmaschine ist diejenige, die im Heft blättert und Fragen beantwortet, auch wenn die Antwort nicht direkt im Heft steht.

Dieser Ansatz heißt deklarativ. Du programmierst nicht das Verfahren, wie man zur Antwort kommt — du schreibst nur auf, was gilt, und das Verfahren ist immer dieselbe Inferenzmaschine. Soll das System etwas Neues lernen? Du fügst einen Satz hinzu und schreibst nichts um.

Durch den ganzen Teil begleitet uns ein kleines Expertensystem nach dem Vorbild von Patrick Winstons Lehrbuchsystem ZOOKEEPER: zwölf Regeln, mit denen man ein Tier an seinen beobachteten Eigenschaften erkennt. Wir haben ein Tier beobachtet, das Fell, scharfe Zähne und Krallen hat, gelbbraun ist und schwarze Streifen hat. Was ist es?

2. Folgerung und Modelle

Definition — Modell und Folgerung

Ein Modell eines Satzes ist eine Belegung der Aussagensymbole, in der der Satz wahr ist. Die Menge der Modelle eines Satzes α bezeichnen wir mit M(α).

Aus KB folgt α, geschrieben KB ⊨ α, genau dann, wenn M(KB) ⊆ M(α) — in jedem Modell der Wissensbasis gilt auch α.

Einfach gesagt

Ein Modell ist eine „mögliche Welt“ — eine Kombination dessen, was wahr ist und was nicht. Folgerung heißt: Wie auch immer die Welt aussieht, wenn in ihr alles aus dem Heft gilt, gilt in ihr auch α. Es geht nicht darum, was wahrscheinlich ist, sondern was unausweichlich ist.

KB ⊨ α ⇔ M(KB) ⊆ M(α)

KB ⊨ α: das, wonach wir fragen: Folgt α aus der Basis? Das Symbol ⊨ spricht über Wahrheit in Welten, nicht darüber, ob wir etwas ableiten können
M(KB): die Welten, die die Basis zulässt — Belegungen, in denen alle ihre Sätze zugleich gelten (die Basis ist ihre Konjunktion); andere Welten interessieren uns nicht, von ihnen behauptet die Basis, dass sie nicht eingetreten sind
⊆: Inklusion: In keiner zugelassenen Welt darf α fehlen; ein einziges Gegenbeispiel würde genügen, damit α nicht folgt
M(α): die Welten, in denen α gilt; es kann viel mehr davon geben — α darf auch dort gelten, wo die Basis nicht gilt

Je mehr die Basis weiß, desto weniger Welten lässt sie zu und desto mehr folgt aus ihr. Eine leere Basis lässt alle Welten zu, deshalb folgen aus ihr nur Tautologien.

Der direkteste Weg, eine Folgerung zu prüfen, ist die Modellprüfung (model checking): alle Belegungen durchgehen, diejenigen auswählen, in denen die ganze Basis gilt, und nachsehen, ob in ihnen auch die Anfrage gilt. Unsere Basis hat 24 Aussagensymbole („hat Fell“, „Säugetier“, „Tiger“…), es gibt also 2²⁴ = 16 777 216 Belegungen. Davon sind 13 440 Modelle der Basis — und in allen gilt „Tiger“. Die Antwort lautet ja, aber um den Preis von sechzehn Millionen Zeilen einer Wahrheitstafel. Mit jedem weiteren Symbol verdoppelt sich die Zahl; bei einer Basis mit Hunderten von Symbolen würde das nie fertig.

Beispiel — Modellprüfung mit drei Symbolen

Basis KB = {regnet ⇒ nass, nass ⇒ glatt, regnet}, Anfrage α = glatt. Drei Symbole ergeben 2³ = 8 Belegungen (1 = wahr, 0 = falsch); die Implikation p ⇒ q ist nur für p = 1, q = 0 falsch.

regnet	nass	glatt	regnet ⇒ nass	nass ⇒ glatt	`KB`
0	0	0	1	1	0
0	0	1	1	1	0
0	1	0	1	0	0
0	1	1	1	1	0
1	0	0	0	1	0
1	0	1	0	1	0
1	1	0	1	0	0
1	1	1	1	1	1

Die ganze Basis gilt nur in der letzten Zeile, also |M(KB)| = 1. In dieser Zeile gilt auch „glatt“ — M(KB) ⊆ M(glatt), und deshalb KB ⊨ glatt. Der Algorithmus ging 8 Zeilen durch und wertete in jeder die 3 Sätze der Basis aus; allgemein kostet die Modellprüfung O(2ⁿ · |KB|).

Beispiel — woher die 13 440 Modelle kommen

In jedem Modell der Basis gelten die fünf beobachteten Fakten, und die Regeln R1, R6 und R9 erzwingen dann „Säugetier“, „Raubtier“ und „Tiger“. Diese 8 Symbole sind fest wahr. Die übrigen 16 zerfallen in Gruppen, die über die Regeln nicht miteinander zusammenhängen, und die Anzahlen ihrer Belegungen multiplizieren sich:

„gibt Milch“ (R2 ist erfüllt, Säugetier gilt) und „frisst Fleisch“ (R5 ist erfüllt, Raubtier gilt): beliebig, 2 · 2 = 4;
„hat dunkle Flecken“, „Gepard“ mit Regel R8: drei Belegungen — Flecken ohne Gepard sind nicht erlaubt;
„hat Hufe“, „Huftier“, „hat langen Hals“, „Giraffe“, „Zebra“ mit R7, R10, R11: Ist Huftier falsch, müssen auch Hufe falsch sein, und die übrigen drei Symbole sind frei (8 Möglichkeiten); ist es wahr, muss Zebra gelten, Hufe sind frei und Hals mit Giraffe haben 3 Möglichkeiten (2 · 3 = 6); zusammen 14;
die Vogelgruppe „hat Federn“, „fliegt“, „legt Eier“, „Vogel“, „fliegt nicht“, „schwimmt“, „Pinguin“ mit R3, R4, R12: Ohne Vogel dürfen weder Federn noch zugleich fliegt und Eier gelten (3 Möglichkeiten), und die letzten drei Symbole sind frei (8): 24; mit Vogel sind Federn frei (2), fliegt und Eier frei (4), und von den acht Belegungen von „fliegt nicht, schwimmt, Pinguin“ ist nur 1, 1, 0 verboten (7): 56; zusammen 80.

Insgesamt 4 · 3 · 14 · 80 = 13 440 — genau so viele, wie die Modellprüfung gezählt hat. Und in jedem von ihnen gilt Tiger, weil es zu den fest wahren Symbolen gehört.

3. Ableitung: korrekt und vollständig

Statt Welten durchzugehen, kann man mit Sätzen hantieren: aus vorhandenen Sätzen nach Ableitungsregeln wie dem Modus ponens neue erzeugen. So macht es auch der Mensch.

Definition — Ableitung, Korrektheit, Vollständigkeit

Wir schreiben KB ⊢ α, wenn sich α aus KB durch endlich viele Anwendungen von Ableitungsregeln gewinnen lässt.

Ein Ableitungsverfahren ist korrekt, wenn aus KB ⊢ α folgt KB ⊨ α — es leitet nur ab, was wirklich folgt.

Es ist vollständig, wenn aus KB ⊨ α folgt KB ⊢ α — es leitet alles ab, was folgt.

Einfach gesagt

Das Symbol ⊨ heißt „es ist so“, das Symbol ⊢ heißt „ich kann es ableiten“. Eine korrekte Maschine erfindet nie etwas Falsches. Eine vollständige Maschine übersieht nichts. Wir wollen beides — und für die allgemeine Logik ist das teuer, für eine einfachere Form von Regeln dagegen billig.

Definition — Hornklausel

Eine Hornklausel ist eine Disjunktion von Literalen, von denen höchstens eines positiv ist. Eine Klausel mit genau einem positiven Literal ist definit und lässt sich als Regel schreiben

p₁ ∧ p₂ ∧ … ∧ p_k ⇒ q,

wobei p₁, …, p_k die Prämissen sind und q die Konklusion. Für k = 0 ist es ein Fakt q.

Einfach gesagt

Eine Hornklausel ist eine Regel „wenn dies und dies und dies gilt, dann gilt jenes“. Kein „oder“ in der Konklusion, kein „nicht“ in den Prämissen. Das klingt nach einer großen Einschränkung, aber die meisten Fachregeln haben genau diese Form — und das Ableiten aus ihnen ist schnell.

Warum ist „eine Disjunktion mit höchstens einem positiven Literal“ dasselbe wie eine Regel? Die Implikation A ⇒ q ist äquivalent zu ¬A ∨ q, und nach dem De-Morgan-Gesetz ist ¬(p₁ ∧ … ∧ p_k) dasselbe wie ¬p₁ ∨ … ∨ ¬p_k:

¬p₁ ∨ … ∨ ¬p_k ∨ q ≡ (p₁ ∧ … ∧ p_k) ⇒ q

¬p₁ ∨ … ∨ ¬p_k: die negativen Literale der Klausel; zusammen sagen sie „irgendeine Prämisse gilt nicht“ — und das ist genau die Negation der Konjunktion der Prämissen
(p₁ ∧ … ∧ p_k): die Prämissen der Regel — aus der Disjunktion negativer Literale wurde dank De Morgan eine Bedingung; keine von ihnen darf negativ sein, sonst stünde in der Regel „wenn … nicht gilt“
q: das einzige positive Literal, die Konklusion; wären zwei positiv, bekämen wir „dann q oder r“, und die Inferenzmaschine wüsste nicht, welches sie hinzufügen soll
⇒: die Klausel ist wahr, wenn irgendeine Prämisse nicht gilt oder die Konklusion gilt — das ist die Definition der Implikation; die Regelform liest nur dieselbe Disjunktion anders

Zum Beispiel ist R6, Säugetier ∧ hat scharfe Zähne ∧ hat Krallen ⇒ Raubtier, die Klausel ¬Säugetier ∨ ¬hat scharfe Zähne ∨ ¬hat Krallen ∨ Raubtier.

4. Vorwärtsverkettung

Algorithmus — Vorwärtsverkettung

Jede Regel merkt sich, wie viele ihrer Prämissen noch nicht bekannt sind. Lege alle Fakten auf die Agenda.
Nimm ein Symbol von der Agenda. Wurde es schon verarbeitet, mach mit dem nächsten weiter.
Verringere bei jeder Regel, die es unter ihren Prämissen hat, den Zähler um 1. Fällt er auf 0, feuert die Regel: Füge ihre Konklusion zur Agenda hinzu.
Wiederhole, bis die Agenda leer ist.

Satz. Für eine Basis aus definiten Hornklauseln ist die Vorwärtsverkettung für Aussagensymbole korrekt und vollständig: Sie leitet genau diejenigen ab, die aus KB folgen. Sie läuft in Zeit linear in der Größe der Basis.

Einfach gesagt

Du gehst von dem aus, was du weißt, und schaust, welche Regel dadurch „freigeschaltet“ wurde. Jede neue Konklusion kann eine weitere Regel freischalten — wie Dominosteine. Du hörst auf, wenn nichts Neues mehr fällt. Man nennt das datengetriebene Ableitung.

Vorwärtsverkettung: Fakten in der Reihenfolge der Verarbeitung, abgeleitete grün Schritte: 8

Gleich die erste Beobachtung „hat Fell“ schaltet Regel R1 frei, die „Säugetier“ ans Ende der Agenda setzt. Die übrigen vier Beobachtungen lösen vorerst nichts aus, verringern aber die Zähler. Wenn Säugetier an der Reihe ist, schaltet es R6 frei (scharfe Zähne und Krallen kennen wir schon) — es entsteht „Raubtier“. Raubtier schaltet R9 frei, und wir haben einen Tiger. In acht Schritten, keine Millionen Zeilen. Regel R5 („ein Säugetier, das Fleisch frisst, ist ein Raubtier“) hat nie gefeuert: Dass das Tier Fleisch frisst, wissen wir nicht — und müssen es auch nicht wissen.

def dopredne(fakta, pravidla):
    chybi = {r.id: len(r.kdyz) for r in pravidla}
    zname, agenda = set(), list(fakta)
    while agenda:
        p = agenda.pop(0)
        if p in zname:
            continue
        zname.add(p)
        for r in pravidla:
            if p in r.kdyz:
                chybi[r.id] -= 1
                if chybi[r.id] == 0:          # alle Prämissen sind bekannt
                    agenda.append(r.pak)
    return zname

Das Herz des Algorithmus ist der Zähler jeder Regel r mit den Prämissen P(r):

fehlt(r) = |P(r)| − |P(r) ∩ Bekannt|

fehlt(r): wie viele Prämissen wir noch nicht kennen; bei fehlt(r) = 0 feuert die Regel — dank der Zahl merkt die Maschine das, ohne die Liste der Prämissen durchzugehen
|P(r)|: der Anfangswert: Zu Beginn wissen wir nichts, alle Prämissen fehlen
|P(r) ∩ Bekannt|: Prämissen, die schon verarbeitet sind; jedes verarbeitete Symbol verringert den Zähler jeder Regel, in der es vorkommt, um 1 — und es wird nur einmal verarbeitet, deshalb wird nichts doppelt gezählt

Jedes Symbol wird höchstens einmal verarbeitet, und jedes Vorkommen einer Prämisse verringert einen Zähler höchstens einmal — daher die lineare Zeit: Die Zahl der Schritte ist proportional zur Summe der Regellängen.

Wie die Zähler während unseres Laufs fallen (nach der Verarbeitung des Symbols in der jeweiligen Zeile; fett die Null, also das Feuern):

Schritt	verarbeitetes Symbol	R1	R5	R6	R9	R8
0	—	1	2	3	3	3
1	hat Fell	0	2	3	3	3
2	hat scharfe Zähne	0	2	2	3	3
3	hat Krallen	0	2	1	3	3
4	ist gelbbraun	0	2	1	2	2
5	schwarz gestreift	0	2	1	1	2
6	Säugetier	0	1	0	1	2
7	Raubtier	0	1	0	0	1
8	Tiger	0	1	0	0	1

R5 bleibt bei eins stehen (es fehlt „frisst Fleisch“) und R8 für den Geparden ebenfalls (es fehlt „hat dunkle Flecken“). Die übrigen Regeln stehen nicht in der Tabelle; ihre Prämissen tauchten im Lauf entweder gar nicht oder nur teilweise auf.

Satz — Vorwärtsverkettung ist korrekt und vollständig (Beweis)

Korrektheit. Jedes abgeleitete Symbol entstand durch das Feuern einer Regel, deren Prämissen alle schon bekannt waren. In jedem Modell der Basis gelten die Fakten und (durch Induktion über die Reihenfolge der Ableitung) auch die zuvor abgeleiteten Symbole, also gilt nach der Regel auch die neue Konklusion — das ist Modus ponens.

Vollständigkeit. Nach dem Ende nehmen wir die Belegung m: wahr für die abgeleiteten Symbole (und Fakten), falsch für alle anderen. Das ist ein Modell der Basis: Würde irgendeine Regel p₁ ∧ … ∧ p_k ⇒ q in m nicht gelten, wären alle p_i abgeleitet und q nicht — dann wäre aber der Zähler der Regel auf null gefallen und q abgeleitet worden. Folgt also q aus der Basis, gilt es im Modell m und wurde somit abgeleitet. ∎

Das Modell m ist das „bescheidenste“: Es glaubt nur, was es muss. Für unsere Basis ist es die Belegung, in der genau die 5 Beobachtungen, Säugetier, Raubtier und Tiger gelten.

5. Rückwärtsverkettung

Algorithmus — Rückwärtsverkettung

Beweist das Ziel q:

Ist q ein bekannter Fakt, ist es bewiesen;
sonst versuche für jede Regel p₁ ∧ … ∧ p_k ⇒ q nacheinander alle p_i zu beweisen; gelingt das bei irgendeiner Regel, ist q bewiesen;
hat keine Regel Erfolg, ist der Beweis gescheitert.

Für definite Hornklauseln ist die Rückwärtsverkettung korrekt und vollständig und untersucht nur Symbole, die mit dem Ziel zusammenhängen.

Einfach gesagt

Du beginnst mit der Frage „Ist es ein Tiger?“ und fragst, was das bestätigen würde: Ein Tiger ist ein gelbbraunes Raubtier mit schwarzen Streifen. Ist es ein Raubtier? Ein Raubtier ist ein Säugetier, das Fleisch frisst, oder ein Säugetier mit scharfen Zähnen und Krallen. Ist es ein Säugetier? … Bis du bei dem ankommst, was du weißt. Man nennt das zielgetriebene Ableitung.

def zpetne(cil, fakta, pravidla, cesta=()):
    if cil in fakta:
        return True                           # wir wissen es direkt
    if cil in cesta:
        return False                          # Zyklus: das Ziel beweist sich selbst
    for r in pravidla:
        if r.pak == cil:                      # ODER: eine Regel genügt
            if all(zpetne(p, fakta, pravidla, cesta + (cil,))
                   for p in r.kdyz):          # UND: alle Prämissen müssen gelingen
                return True
    return False                              # wir wissen nicht, wie man es beweist

Die Funktion all hält bei der ersten Prämisse an, die nicht gelingt — deshalb wird bei R5 nach dem Misserfolg mit „frisst Fleisch“ nichts weiter untersucht. Die Liste cesta (Pfad) sorgt dafür, dass Regeln wie „a ⇒ b, b ⇒ a“ keine Schleife bilden.

Rückwärtsverkettung für das Ziel „Tiger“: Unter den Knoten stehen die Regeln

Der Algorithmus hat 11 Ziele untersucht. Raubtier versuchte er zuerst mit Regel R5 zu beweisen — Säugetier bewies er, aber bei „frisst Fleisch“ blieb er hängen: Das wissen wir nicht, also gab er R5 auf und versuchte R6, die gelang. Hier ist die Rückwärtsverkettung stark: Sie weiß, was ihr fehlt. Ein Expertensystem fragt in so einem Moment den Benutzer: „Frisst das Tier Fleisch?“ Das ganze Gespräch mit einem Expertensystem ist also eigentlich laut ausgesprochene Rückwärtsverkettung.

Wann was verwenden? Vorwärtsverkettung eignet sich, wenn Daten hereinkommen und du wissen willst, was aus ihnen folgt — etwa bei der Überwachung einer Produktion. Rückwärtsverkettung, wenn du eine konkrete Frage hast — eine Diagnose, eine Datenbankabfrage. Würden wir fragen „Ist es ein Zebra?“, würde die Rückwärtsverkettung das nach der Untersuchung von nur 5 Zielen widerlegen: Ein Zebra ist ein Huftier, und Hufe hat unser Tier nicht.

6. Resolution: Ableitung für die ganze Logik

Hornklauseln reichen nicht für alles. Der Satz „das Tier ist ein Säugetier oder ein Vogel“ hat in der Konklusion ein „oder“, und als Regel lässt er sich nicht schreiben. Für beliebige Aussagen gibt es eine einzige Regel, die für alles reicht.

Definition — Resolution

Sätze werden in die konjunktive Normalform umgeformt — eine Konjunktion von Klauseln, von denen jede eine Disjunktion von Literalen ist. Resolutionsregel: Aus den Klauseln (A ∨ ℓ) und (B ∨ ¬ℓ) leite (A ∨ B) ab.

Widerspruchsbeweis: KB ⊨ α genau dann, wenn KB ∧ ¬α unerfüllbar ist. Die Resolution leitet aus KB ∧ ¬α neue Klauseln ab; leitet sie die leere Klausel ab, ist ein Widerspruch gefunden. Dieses Verfahren ist korrekt und vollständig (Robinson, 1965).

Einfach gesagt

Wenn „es regnet oder es ist trocken“ gilt und zugleich „es ist nicht trocken oder es weht Wind“, dann gilt „es regnet oder es weht Wind“ — das Trockene hebt sich auf. Die Resolution beweist durch Widerspruch: Sie nimmt das Gegenteil dessen an, was sie beweisen will, und kürzt Klauseln so lange, bis eine leere übrig bleibt — ein Widerspruch. Das Gegenteil gilt also nicht.

( A ∨ ℓ ), ( B ∨ ¬ℓ ) ⊢ ( A ∨ B )

ℓ, ¬ℓ: komplementäre Literale — in jeder Welt ist genau eines von ihnen wahr, also erfüllt es eine der Klauseln nicht; diese muss durch ihren Rest erfüllt sein. Deshalb fehlt ℓ im Ergebnis
A: der Rest der ersten Klausel: gilt immer dann, wenn ℓ falsch ist (dann hält nur A die erste Klausel wahr)
B: der Rest der zweiten Klausel: gilt immer dann, wenn ℓ wahr ist (dann gilt ¬ℓ nicht, und B hält die zweite Klausel wahr)

Wie auch immer ℓ ist, einer der Reste muss gelten — das ist der ganze Beweis, dass die Resolution korrekt ist. Aus (ℓ) und (¬ℓ) entsteht die leere Klausel, die nichts erfüllt: ein Widerspruch.

Algorithmus — Umformung in konjunktive Normalform

Äquivalenzen entfernen: α ⇔ β durch (α ⇒ β) ∧ (β ⇒ α) ersetzen.
Implikationen entfernen: α ⇒ β durch ¬α ∨ β ersetzen.
Negationen bis zu den Symbolen nach innen schieben: ¬¬α ≡ α, ¬(α ∧ β) ≡ ¬α ∨ ¬β, ¬(α ∨ β) ≡ ¬α ∧ ¬β (De Morgan).
∨ über ∧ ausmultiplizieren: α ∨ (β ∧ γ) ≡ (α ∨ β) ∧ (α ∨ γ).

Beispiel: (regnet ∨ schneit) ⇒ nass

Schritt 2: ¬(regnet ∨ schneit) ∨ nass

Schritt 3: (¬regnet ∧ ¬schneit) ∨ nass

Schritt 4: (¬regnet ∨ nass) ∧ (¬schneit ∨ nass) — zwei Klauseln, beide sogar Hornklauseln.

Das Ausmultiplizieren im 4. Schritt kann die Formel exponentiell verlängern; Solver verwenden deshalb in der Praxis die Tseitin-Transformation mit Hilfssymbolen, die ein nur linear längeres Ergebnis liefert (erfüllbar genau dann, wenn die ursprüngliche Formel es ist).

Beispiel: die Basis {regnet ⇒ nass, nass ⇒ glatt, regnet}, Anfrage „glatt“. In Normalform und mit hinzugefügter Negation der Anfrage:

(¬regnet ∨ nass), (¬nass ∨ glatt), (regnet), (¬glatt)

(regnet) und (¬regnet ∨ nass) ergeben (nass); (nass) und (¬nass ∨ glatt) ergeben (glatt); (glatt) und (¬glatt) ergeben die leere Klausel. Ein Widerspruch — „glatt“ folgt aus der Basis.

Die Resolution ist universell, aber im Allgemeinen teuer: Für die Aussagenlogik ist das Erfüllbarkeitsproblem (SAT) NP-vollständig. Moderne SAT-Solver bewältigen trotzdem Millionen von Variablen — von ihnen war im Teil über Constraint Satisfaction die Rede.

7. Regeln mit Variablen und Prolog

Die Aussagenlogik hat einen Mangel: „Rex ist ein Säugetier“ und „Micka ist ein Säugetier“ sind für sie zwei unzusammenhängende Symbole. Eine Regel über alle Säugetiere müsste man für jedes Tier einzeln abschreiben. Die Prädikatenlogik aus dem Teil über Logik und Beweise löst das mit Variablen: ∀x : hat_fell(x) ⇒ säugetier(x).

Definition — Unifikation

Ein Unifikator zweier Ausdrücke ist eine Ersetzung der Variablen, nach der beide Ausdrücke identisch sind. Zum Beispiel werden rodič(jan, Y) und rodič(X, petr) (rodič = Elternteil) durch die Ersetzung {X / jan, Y / petr} unifiziert. Der Unifikationsalgorithmus findet den allgemeinsten Unifikator, falls es einen gibt.

Einfach gesagt

Unifikation heißt „finde, was man einsetzen muss, damit es passt“. Wenn eine Regel von irgendeinem x spricht und du nach Rex fragst, setzt die Unifikation x = Rex, und die Regel lässt sich anwenden. Das Verketten funktioniert dann genauso wie in der Aussagenlogik, nur mit Einsetzen.

def unifikuj(a, b, s):                    # s: bisher gefundene Ersetzung (Wörterbuch)
    if s is None:
        return None                           # schon vorher gescheitert
    a, b = dosad(a, s), dosad(b, s)           # anwenden, was wir schon wissen
    if a == b:
        return s
    if je_promenna(a):
        return None if vyskytuje_se(a, b) else {**s, a: b}
    if je_promenna(b):
        return None if vyskytuje_se(b, a) else {**s, b: a}
    if slozeny(a) and slozeny(b) and a.jmeno == b.jmeno and len(a.args) == len(b.args):
        for x, y in zip(a.args, b.args):      # Argumente einer nach dem anderen
            s = unifikuj(x, y, s)
        return s
    return None                               # verschiedene Konstanten oder Prädikate

Am Beispiel rodič(jan, Y) und rodič(X, petr): Die Prädikate stimmen überein, also werden die Argumente verglichen. jan und X ergeben {X / jan}, Y und petr fügen Y / petr hinzu. Dagegen unifizieren rodič(jan, Y) und rodič(petr, eva) nicht — jan und petr sind verschiedene Konstanten. Der Test vyskytuje_se (Occurs-Check) verhindert eine Ersetzung wie X / f(X), die zu einem unendlichen Ausdruck führen würde. (Prolog lässt ihn aus Geschwindigkeitsgründen standardmäßig weg.)

Auf Rückwärtsverkettung mit Unifikation beruht Prolog (Alain Colmerauer, Marseille, 1972) — eine Sprache, in der das Programm eine Wissensbasis ist und das Ausführen des Programms eine Anfrage (rodic = Elternteil, prarodic = Großelternteil, kdo = wer):

rodic(jan, petr).
rodic(petr, eva).

prarodic(X, Z) :- rodic(X, Y), rodic(Y, Z).

?- prarodic(jan, Kdo).
Kdo = eva.

Prolog arbeitet sich zum Ziel prarodic(jan, Kdo) genau wie unser Baum beim Tiger vor: Es findet die Regel, unifiziert X = jan, beweist rodic(jan, Y), findet Y = petr und dann rodic(petr, Z) mit dem Ergebnis eva.

8. Expertensysteme

Ein Expertensystem ist eine gemeinsam mit einer Fachperson aufgeschriebene Wissensbasis und eine Inferenzmaschine, meist mit Rückwärtsverkettung und der Möglichkeit zu erklären, warum es zu einem Schluss gekommen ist — es genügt, den Baum zu lesen, den wir oben gezeichnet haben. Am bekanntesten waren drei:

DENDRAL (Stanford, ab 1965) bestimmte die Struktur von Molekülen aus Daten eines Massenspektrometers — das erste System, das die Arbeit von Wissenschaftlern nach deren eigenen Regeln erledigte.
MYCIN (Stanford, 1970er-Jahre) diagnostizierte bakterielle Blutinfektionen und empfahl Antibiotika. Es hatte rund sechshundert Regeln, und in einer Bewertung von 1979 schnitten seine Vorschläge genauso gut ab wie die von Stanforder Fachärzten oder besser. Im Krankenhaus wurde es trotzdem nie eingesetzt.
XCON (Firma DEC, ab 1980) stellte Konfigurationen von VAX-Rechnern nach Bestellung zusammen. Es hatte Tausende von Regeln und sparte nach Angaben der Firma jährlich zig Millionen Dollar.

Die Medizin kennt aber selten Gewissheit. MYCIN versah deshalb jede Regel mit einer Zahl, die angibt, wie sehr ihr die Fachperson vertraut:

Definition — Sicherheitsfaktor

Der Sicherheitsfaktor CF ∈ [−1, 1] drückt das Maß des Vertrauens in eine Konklusion aus: 1 gilt sicher, −1 gilt sicher nicht, 0 unbekannt. Stützen zwei Regeln mit positiven Faktoren CF₁ und CF₂ dieselbe Konklusion, ist der resultierende Faktor

CF = CF₁ + CF₂ · (1 − CF₁).

Einfach gesagt

Ein Hinweis überzeugt dich zu 0,6, ein zweiter, unabhängiger zu 0,5. Zusammen 0,6 + 0,5 · 0,4 = 0,8 — der zweite Hinweis nimmt die Hälfte der verbleibenden Unsicherheit weg. Sicherheitsfaktoren sind keine Wahrscheinlichkeiten und erfüllen nicht den Satz von Bayes; später wurden sie durch Bayes-Netze ersetzt, die im Lehrplan einen eigenen Teil haben.

CF = CF₁ + CF₂ · (1 − CF₁)

CF₁: das Vertrauen aus der ersten Regel; die zweite Regel kann es nicht senken, nur ergänzen
CF₂: welchen Teil der verbleibenden Unsicherheit die zweite Regel beseitigt; würde man einfach addieren, ergäben zwei Hinweise zu je 0,6 unsinnige 1,2
1 − CF₁: die Unsicherheit, die nach der ersten Regel übrig blieb; nur von ihr lässt sich noch etwas wegnehmen, und deshalb überschreitet das Ergebnis nie 1

Äquivalent 1 − CF = (1 − CF₁) · (1 − CF₂): Die verbleibenden Unsicherheiten multiplizieren sich. Deshalb spielt die Reihenfolge der Regeln keine Rolle.

Beispiel — drei Hinweise und eine Regel mit unsicheren Prämissen

Drei Hinweise 0,6, 0,5 und 0,5: zuerst 0,6 + 0,5 · (1 − 0,6) = 0,8, dann 0,8 + 0,5 · (1 − 0,8) = 0,9. Probe über die Unsicherheiten: 1 − 0,4 · 0,5 · 0,5 = 0,9.

Unsichere Prämissen. In MYCIN (Shortliffe und Buchanan, 1975) bekommt eine Konjunktion von Prämissen den Faktor ihres schwächsten Glieds und die Konklusion einer Regel den Faktor der Regel mal diesen minimalen Faktor (die Regel wird dabei nur angewendet, wenn das Minimum 0,2 übersteigt): CF(Konklusion) = CF(Regel) · min_i CF(p_i). Eine Regel mit dem Faktor 0,7, deren Prämissen die Faktoren 0,9 und 0,6 haben, trägt so 0,7 · min(0,9; 0,6) = 0,42 zur Konklusion bei.

Ende der Achtzigerjahre zeigten sich die Grenzen. Die Wissensakquisition war der Engpass: Fachleute können ihr Know-how oft nicht als Regeln aussprechen, und jede Regel kostete Stunden an Gesprächen. Die Systeme waren spröde: Einen Schritt außerhalb ihres Gebiets wussten sie nichts und wussten nicht einmal, dass sie nichts wissen. Und Tausende von Regeln ließen sich schlecht pflegen — eine neue Regel konnte stillschweigend einer alten widersprechen. Der Markt für Expertensysteme brach zusammen, und es kam der zweite KI-Winter. Die Antwort, die danach kam, ist das Gegenteil: Wissen nicht aufschreiben, sondern aus Daten lernen.

9. Wissen in der heutigen künstlichen Intelligenz

Wissensgraphen. Google beantwortet seit 2012 viele Anfragen aus seinem Knowledge Graph — einem Netz von Fakten wie (Prag, Hauptstadt, Tschechien). Das frei verfügbare Wikidata hat über hundert Millionen Einträge. Es ist eine Wissensbasis, nur überwiegen statt Regeln die Fakten.
Regeln dort, wo sich alles überprüfen lassen muss. Steuerberechnungen, Versicherungsbedingungen, Kreditgenehmigungen oder Sicherheitsrichtlinien werden bis heute als Regeln geschrieben: Jede Entscheidung lässt sich erklären und verteidigen.
Sprachmodelle und Wissen. Ein Sprachmodell enthält riesige Mengen an Wissen, aber verteilt über die Gewichte des Netzes — es lässt sich weder Stück für Stück lesen noch korrigieren, und das Modell erfindet manchmal selbstsicher etwas. Deshalb schließt man es an die Suche in einer Wissensbasis (RAG) oder an Werkzeuge und Inferenzmaschinen an, die das Ergebnis überprüfen.
Neurosymbolische KI verbindet beides: Das Netz erkennt, was es sieht, und die Logik leitet daraus ab, was folgt. Beispiele sind Systeme, die mathematische Beweise suchen: Das Modell schlägt einen Schritt vor, und ein formales Werkzeug prüft ihn mechanisch.

10. Zusammenfassung

Eine Wissensbasis ist eine Menge von Sätzen; KB ⊨ α bedeutet, dass α in allen Modellen der Basis gilt. Die Modellprüfung prüft das, aber um den Preis von 2ⁿ Belegungen.
Ableitung (⊢) arbeitet mit Sätzen statt mit Welten. Wir wollen, dass sie korrekt (erfindet nichts) und vollständig (übersieht nichts) ist.
Für Hornklauseln genügt Vorwärtsverkettung (von den Fakten aus, datengetrieben) oder Rückwärtsverkettung (vom Ziel aus, von der Frage getrieben); die Vorwärtsverkettung läuft in linearer Zeit, die Rückwärtsverkettung untersucht nur, was mit dem Ziel zusammenhängt.
Für die ganze Aussagenlogik gibt es die Resolution und den Widerspruchsbeweis; für Regeln mit Variablen die Unifikation und Prolog.
Expertensysteme haben die Stärke und die Grenzen von handgeschriebenem Wissen gezeigt — und den Boden für das Lernen aus Daten bereitet.

Möchtest du es selbst ausprobieren? Lass einen KI-Agenten ein Expertensystem mit Rückwärtsverkettung schreiben, das nach fehlenden Fakten fragt — und denk dir eigene Regeln für etwas aus, worin du dich auskennst.

Siehst du das anders? Schreib an support@coden-app.com.

Logik und wissensbasierte Systeme: Vorwärts- und Rückwärtsverkettung, Resolution und Expertensysteme

1. Wissensbasis und Inferenzmaschine

2. Folgerung und Modelle

3. Ableitung: korrekt und vollständig

4. Vorwärtsverkettung

5. Rückwärtsverkettung

6. Resolution: Ableitung für die ganze Logik

7. Regeln mit Variablen und Prolog

8. Expertensysteme

9. Wissen in der heutigen künstlichen Intelligenz

10. Zusammenfassung

Ein Agent auf deinem Rechner, vom Telefon aus gesteuert