3Wissens­repräsentation mit Horn-Klauseln (Pure Prolog)

3.1Horn-Klauseln

Klauseln stellen eine normalisierte Darstellung von allgemeinen logischen Aussagen dar. Eine Klausel hat die Form:
 A1 ∨ A2 ∨... ∨ Am ∨ ¬B1 ∨ ¬B2 ∨ ... ∨ ¬Bn,
wobei Ai, Bj atomare Prädikate sind (Prädikate ohne logische Operatoren ∧, ∨ ¬, etc.). Allfällige Variablen werden über die ganze Klausel universell quantifiziert. Ai heissen positive Literale, ¬Bj heissen negative Literale. Eine äquivalente Form der Klausel ist:
  A1 ∨ A2 ∨... ∨ Am ⇐ B1 ∧ B2 ∧ ... ∧ Bn.

Jede logische Aussage kann in eine äquivalente Konjunktion von Klauseln transformiert werden. Eine Horn-Klausel ist eine Klausel mit m ≤ 1.

m, n	m = 1, n = 0
Horn-Klausel	A1.
Bedeutung	Fakt, Assertion
Prolog	A1.
m, n	m = 1, n > 0
Horn-Klausel	A1 ⇐ B1 ∧ B2 ∧ ... ∧ Bn
Bedeutung	Implikation, Regel
Prolog	A1 :- B1, ... Bn.
m, n	m = 0, n > 0
Horn-Klausel	¬B1 ∨ ¬B2 ∨ ... ∨ ¬Bn.
Bedeutung	Frage
Prolog	?- B1, ... Bn.
m, n	m = 0, n = 0
Horn-Klausel	leere Klausel
Bedeutung	"false"
Prolog

m, n	Horn-Klausel	Bedeutung	Prolog
m = 1, n = 0	A1.	Fakt, Assertion	A1.
m = 1, n > 0	A1 ⇐ B1 ∧ B2 ∧ ... ∧ Bn	Implikation, Regel	A1 :- B1, ... Bn.
m = 0, n > 0	¬B1 ∨ ¬B2 ∨ ... ∨ ¬Bn.	Frage	?- B1, ... Bn.
m = 0, n = 0	leere Klausel	"false"

Die Semantik der Horn-Klauseln entspricht vollumfänglich der Logik.

Objekte

Objekte werden durch Terme bezeichnet (benannt): Konstanten, Variablen und Strukturen. Variablen bezeichnen unbestimmte Objekte, resp. stehen für beliebige Objekte. Terme treten als Argumente von Prädikaten auf, sind aber selber semantisch keine Prädikate. Beispiel: Der Term klein( haus) bezeichnet ein bestimmtes Haus, das auch klein_haus heissen könnte. Es ist nicht bekannt, wie gross dieses Haus ist.

Prädikate

Prädikate sind Eigenschaften (Attribute, Merkmale) von Objekten und Beziehungen (Relationen) zwischen Objekten. Prädikate haben den Wahrheitswert 'true' oder 'false'. Im Prolog haben Prädikate und Terme die gleiche syntaktische Form.

Beispiele:

klein( haus):	klein ist die Eigenschaft des Objektes haus
schneller( auto, velo):	schneller ist eine Beziehung zwischen den Objekten auto und velo.
teuer( X):	X ist teuer.

Assertionen (Fakten)

Ein Fakt A1 bedeutet: "A1 ist wahr". Im Prolog können nur wahre Prädikate dargestellt werden.

Beispiele:

klein( haus).	haus ist klein.
schneller( auto, velo).	auto ist schneller als velo.
teuer( X).	Alles ist teuer, d.h. für alle X gilt: teuer( X). Logik: ∀ X teuer( X).

Variablen sind also implizit universell quantifiziert.

Implikationen (Regeln)

Die logische Implikation (Regel)
A1 ⇐ B1 ∧ B2 ∧ ... ∧ Bn
bedeutet:
Falls B1 und B2 ...und Bn wahr sind, dann ist A1 wahr.
A1 ist wahr, wenn B1 und B2 ...und Bn wahr sind.

Beispiel:
enkel( E, G) ⇐ kind( M, G) ∧ kind( E, M).

Alle Variablen sind implizit universell quantifiziert (über die ganze Regel):
Für alle E, G, M gilt: E ist Enkel von G, wenn M Kind von G, und E Kind von M ist.
∀ E, G, M [ enkel( E, G) ⇐ kind( M, G) ∧ kind( E, M) ].

Eine äquivalente Bedeutung ist, dass Variablen, die nur im Body vorkommen, existentiell, alle anderen universell quantifiziert sind:
Für alle E, G gilt: E ist Enkel von G, wenn ein M existiert, sodass M Kind von G ist, und E Kind von M ist.
∀ E, G [ enkel( E, G) ⇐ ∃ kind( M, G) ∧ kind( E, M) ] ]

Ziele, Fragen

Die Klausel
¬B1 ∨ ¬B2 ∨ ... ∨ ¬Bn (universell quantifiziert)
ist äquivalent zu:
¬ (B1 ∧ B2 ∧ ... ∧ Bn) (existentiell quatifiziert)

Die Variablen sind implizit universell quantifiziert (über die ganze Klausel).

Die logische Bedeutung ist: Die Aussage (B1 und B2 und ... und Bn) ist falsch. Bei der Problemlösung in Logik versucht man eine Aussage der Form (B1 ∧ B2 ∧ ... ∧ Bn) aus den gegebenen Assertionen und Implikationen zu beweisen. In dieser Formel sind die Variablen existentiell quantifiziert. Die obige Horn-Klausel ist die Negation dieser Aussage. Der Resolutionsalgorithmus basiert auf dem Beweis durch Widerspruch. Es wird angenommen, dass (B1 ∧ B2 ∧ ... ∧ Bn) falsch ist. Falls diese Annahme zum Widerspruch führt, ist (B1 ∧ B2 ∧ ... ∧ Bn) wahr.

Beispiel:

Problem:	Welche Autos sind schnell?
Prolog: :	?- auto( X), schnell( X).

Der zu beweisende Satz: Es existiert ein X, sodass X ein Auto und X schnell ist.

Logik:	∃ X [auto( X) ∧ schnell( X)]
Negation:	∀ X ¬ [auto( X) ∧ schnell( X)]

Die Problemlösung mit Horn Klauseln ("logic programming" im engen Sinne) bedeutet:

1. Darstellung des Bekannten durch Fakten und Regeln. Diese Horn Klauseln, die genau ein positives Literal haben (m = 1), heissen auch Definite Clauses oder Programmklauseln (Pi).
2. Darstellung des Gesuchten als G = G1 ∧ G2 ∧ . . . ∧ Gm. (G = Goal).
3. Beweis der Formel
   P1 ∧ P2 ∧ . . .∧ Pn ⇒ G (äquivalent zu ¬P1 ∨ ¬P2 ∨ . . . ∨ ¬Pn ∨ G)
   durch Resolution (Beweis durch Widerspruch). Die Formel wird negiert zu:
   P1 ∧ P2 ∧ . . .∧ Pn ∧ ¬ G,
   und durch Widerspruch bewiesen. Es ist
   ¬ G = ¬ G1 ∨ . . . ∨ ¬ Gn,
   d.h. ¬ G ist eine Horn Klausel ( m = 0, n > 0).

Horn-Klauseln und Prolog

Die Ausführung eines Programms mit Horn-Klauseln sollte die allgemeine Resolution verwenden (s. 2.9, Bemerkung d). Das im Kapitel 2 behandelte Prolog ("pure" Prolog) entspricht den Horn-Klauseln bis auf die Ausnahme der speziellen Ausführungsstrategie. Es kann also vorkommen, dass ein Prolog-Programm nicht terminiert ("Linksrekursion"), obwohl das entsprechende Programm mit Horn Klauseln eine Lösung ("yes") liefert (logische Unvollständigkeit von Prolog). Dieses Problem muss vom Prolog-Programmierer durch richtiges Anordnen der Klauseln angegangen werden. Falls das Prolog-Programm ein Resultat liefert, dann ist es identisch mit dem Resultat der Horn-Klauseln (logische Korrektkeit von Prolog). Pure Prolog und Horn-Klauseln werden meistens gleichbedeutend verwendet.

Horn-Klauseln und Logik

Horn-Klauseln sind eine echte Teilmenge der Prädikatenlogik 1. Ordnung. Sätze können mit Horn-Klauseln viel effizienter als in der vollen Prädikatenlogik bewiesen werden. Horn-Klauseln stellen einen universellen Berechnungsformalismus dar, d.h. alle berechenbaren Funktionen sind mit Horn-Klauseln formulierbar und durch Resolution berechenbar. Horn-Klauseln haben jedoch nicht die volle Darstellungsmächtigkeit der Prädikatenlogik, z.B. kann A ∨ B nicht dargestellt werden.

Prolog

Folgende Aussagen können in (pure) Prolog nicht formuliert werden:

¬ A. (eine Horn Klausel, aber keine Prolog Programm-Klausel)
A ∨ B.
A ⇐ ¬ B. (äquivalent zu A ∨ B)
¬ A ⇐ B. (äquivalent zu ¬ A ∨ ¬ B)
(A ∨ B) ⇐ C (äquivalent zu A ∨ B ∨ ¬ C)
?- A ∨ B.
?- ¬ A.

Eine Prolog Programm-Klausel enthält genau ein positives Literal. Alle Klauseln im Programm sind wahr (alle gelten). Es ist nicht möglich (im Unterschied zur vollen Logik), einen Fakt darzustellen, der nicht wahr ist. Analog kann auch eine Implikation mit negativer Konklusion nicht dargestellt werden.

Alle Klauseln im Programm sind implizit durch "und" (Konjunktion) verbunden (alle gelten). Es ist nicht möglich (im Unterschied zur vollen Logik), eine Disjunktion von Fakten ("oder") darzustellen. Z.B. "er heisst Peter oder Paul": "name( person1, peter) ∨ name( person1, paul)" kann in Logik, aber nicht in Prolog dargestellt werden. Die Darstellung durch zwei Fakten:
name( person1, peter).
name( person1, paul).
bedeutet: "Er (person1) heisst Peter und er heisst Paul", was nicht beabsichtigt ist.

In der Prämisse einer Implikation (d.h. im Körper einer Regel) kann die Disjunktion "oder" dargestellt werden. "Wenn A oder B, dann C" ist nämlich äquivalent zu "Wenn A, dann B" und "Wenn B, dann C":
C ⇐ A ∨ B ist äquivalent zu: (C ⇐ A) ∧ (C ⇐ B).

Beispiel

"Ein Mensch ist ein Mann oder eine Frau". Dieser Satz ist eine Definition von Mensch:
mensch( X) ⇔ mann( X) ∨ frau( X)
und kann so nicht in Prolog dargestellt werden. Üblicherweise wird
mensch( X) ⇐ mann( X) ∨ frau( X)
dargestellt, und zwar als:
mensch( X) :- mann( X).
mensch( X) :- frau( X).
d.h. "Ein Mann oder eine Frau sind ein Mensch". Eine äquivalente Darstellung ist:
mensch( X) :- mann( X) ; frau( X).
Der Operator ';' bedeutet "oder". Er bindet schwächer als ','.

3.2Methoden der Wissens­repräsentation

Terme und Klauseln

Das Wissen wird durch Terme und Klauseln dargestellt. Terme repräsentieren Objekte der Welt; Klauseln repräsentieren Eigenschaften von Objekten und Beziehungen zwischen Objekten.

Beispiel: Turm: c auf b, b auf a

1) Term - Darstellung

Der Turm wird durch einen Term (z.B. die Liste [ c, b, a]) repräsentiert, der von einem Prolog-Programm verarbeitet wird.

Das N-te Element (von oben):

element( 1, [ X| Xs], X).
element( N, [ X| Xs], Y) :- 
    N > 1, N1 is N - 1, 
    element( N1, Xs, Y).

Der Zugriff geschieht durch Rekursion: elegant aber ineffizient bei tief geschachtelten Strukturen. Beliebige Manipulation (z.B. update) sind möglich, z.B. lege Block X auf Turm Y:

stack( X, Y, [X | Y]).
/* [ X| Y] ist der resultierende Turm */

Daten ("Wissen") werden nicht im Programm gespeichert, sondern durch Parameterübergabe zwischen Prädikaten übermittelt.

2) Klauseln - Darstellung (Fakten und Regeln)

Der Turm wird durch Fakten und Regeln repräsentiert; das Wissen wird also im Programm gespeichert. Gewisse Manipulationen werden direkt durch den Prolog-Beweiser (z.B. unter Ausnützung von Backtracking) ausgeführt.

turm( 1, c).
turm( 2, b).
turm( 3, a).
hoehe( 3).
element( N, X) :- turm( N, X).

Der Zugriff geschieht direkt durch den Prolog-Prover; er ist effizient, aber oft nicht flexibel genug. Die Struktur ist nicht einfach veränderbar. Praktisch wird dies durch Programmmodifikation zur Laufzeit (s. assert, retract) gelöst.

Eine andere, häufig verwendete Darstellung ist:

on( c, b).
on( b, a).
on( a, table).

Objekt-Attribut Paare

Beispiel:

klein( haus).	"haus ist klein"; klein ist das Attribut des Objektes haus
Was ist klein?:	?- klein( X). => X = haus
Wie gross ist das Haus?:	?- X( haus) . => Syntax error. Dies geht nicht in der Logik 1. Stufe (erst 2. Stufe). Mögliche Abhilfe: objekt( haus, klein). Objekt - Attribut - Paar (symmetrische Darstellung): ?- objekt( haus, X) => X = klein

Ein Objekt hat oft mehrere Attribute, die Werte haben. Dies kann auf verchiedene Arten dargestellt werden:

/* Objekt - Attribut */
farbe( auto, rot).
preis( auto, 28).
marke( auto, opel).

/* Objekt-orientiert */
auto( farbe, rot).
auto( preis,  28).

/* Objekt - Attribut - Wert  - Tripel */
objekt( auto, farbe, rot).
objekt( auto, preis, 28). 

/* Listen */
objekt( auto, [ farbe (rot), preis( 28)]).

Die Darstellung hängt vom Verwendungszweck ab. Die objektorientierte Darstellung ist sehr übersichtlich und oft zweckmässig (s. auch Frames in AKI II).

Beispiel: Repräsentation von digitalen Schaltkreisen mit Klauseln

Die abgebildete Schaltung stellt ein xor-Element dar:

Fig. 3.1: xor-Schaltung

Die Repräsentation durch Klauseln ist:

xor( X, Y, Z) :- 
    nand( X, Y, A), 
    nand( X, A, B), 
    nand( Y, A, C), 
    nand( B, C, Z).
nand( 0, 0, 1).  
nand( 0, 1, 1).  
nand( 1, 0, 1).  
nand( 1, 1, 0).

Die Schaltung kann sofort auch simuliert werden und zwar unter Ausnutzung der Invertibilität der Argumente: Inputs und Outputs können bei der Abfrage beliebig instantiiert werden.

Beispiel: Repräsentation von natürlichsprachlichen Aussagen

1) Alle roten Pilze sind giftig

Ein (misslungener) Versuch:

giftig( rot_pilz).  /* FALSCH ! */
giftig :- rot( pilz).  /* FALSCH ! */

Richtig ist: Alle Objekte, die Pilz sind und rot sind, sind giftig:

giftig( X) :- pilz( X), rot( X).
pilz( fliegenpilz).
rot( fliegenpilz).

2) Pilze sind giftig, nur wenn sie rot sind

Bedeutung: "Wenn ein Pilz nicht rot ist, dann ist er nicht giftig". Äquivalent ist: "Wenn ein Pilz giftig ist, dann ist er rot".
(Logik: "A ⇒ B" ist äquivalent zu "¬ B ⇒ ¬ A").

rot( X) :- pilz( X), giftig( X).

3) Kein roter Pilz ist giftig.

¬ giftig( X) ⇐ pilz( X), rot( X).
Dies kann nicht direkt in Prolog formuliert werden. Die oft sinnvolle positive Formulierung:
ungiftig( X) ⇐ pilz( X), rot( X).
ist nicht logisch äquivalent.

4) Es gibt genau einen Pilz.

∃ X { pilz( X) ∧ [ ∀ Y ( Y ≠ X ⇒ ¬ pilz( Y) ) ] }
Dies wird in Prolog formuliert, indem dieser eindeutige Pilz benannt wird, z.B. der_pilz:

pilz( der_pilz).

Diese Formulierung ist äquivalent mit der obigen logischen Formel unter Closed World Assumption (s. 4.2).

5) Jeder Pilz ist essbar oder giftig.

essbar( X) ∨ giftig( X) ⇐ pilz( X).
Kann nicht direkt in Prolog formuliert werden. Die äquivalente Formulierung:
giftig( X) ⇐ pilz( X) ∧ ¬ essbar( X).
geht in Pure Prolog (Horn Klauseln) auch nicht. In Prolog oft:

pilz( X) :- essbar_pilz( X) ; giftig_pilz( X).

mit der Bedeutung "Essbare Pilze und giftige Pilze sind Pilze". Beachten Sie auch, dass das natürlichsprachliche "und" hier die logische Bedeutung von "oder" hat.