Wir haben zu Beginn dieses Abschnitts die Ausdrucksmächtigkeit des
jeweiligen Formalismus als unser vorherrschendes Ordnungskriterium
erklärt. Der einfachste Formalismus in dieser Hinsicht ist die Termlogik.
In ihr betrachten wir logische Probleme der Form (dh.
das auftretende Prädikat spielt eine triviale Rolle, die man ignorieren
kann) bzw. Varianten hiervon. Das sieht trivialer aus, als es wirklich ist,
kann doch
ein außerordentlich komplexer Term sein, der ein
kompliziertes funktionales (zB. LISP) Programm repräsentiert. Wegen der
in Abschnitt 1.3 genannten Wissensrepräsentationshypothese haben wir
diesen funktionalen Teil nicht als eigenständigen Formalismus innerhalb
unserer Diskussion zugelassen (obwohl er natürlich immer Bestandteil
über die auftretenden Terme ist).
Datenbankformalismen sind aus logischer Sicht in etwa von der Form
, wobei die
Grundatome sind. Anfragen sind Atome, die Variablen enthalten und in
der Liste der Grundatome in instantiierter Form auftreten können (in
welchem Fall die Instantiierung die Antwort liefert).
Bedingungsnetze
sind aus syntaktischer Sicht nur geringfügig komplizierter als Datenbanken, indem sie als Anfragen
Konjunktionen von Atomen (und nicht nur Atome allein) enthalten können, in
denen gemeinsame Variable auftreten können. Diese formulieren
gewissermaßen die (Rand-) Bedingungen, unter denen eine Lösung
gesucht wird. Trotz dieser scheinbar einfachen Gestalt stellt das Lösen
von Bedingungsnetzen bereits ein NP-vollständiges Problem dar.
Bei dem Studium dieses Problemtyps hat sich eine netzartige Darstellung eingebürgert, die in Abbildung 2.36 anhand des in Abbildung 2.35 gezeigten Bedingungsproblems eines Kreuzworträtsels illustriert wird. Die Knoten repräsentieren je eine Variable und ihren Datenbereich, während die Kanten je eine Bedingung zwischen zwei Variablen darstellen. [Ric89] stellt diese Netze allerdings dual dar, dh. die Variablen werden den Kanten und die Knoten den Prädikaten zugeordnet, was ebenfalls möglich, aber ungebräuchlich ist.
Abbildung 2.35: Ein Kreuzworträtsel
Abbildung 2.36: Ein Bedingungsnetz zum Kreuzworträtsel der Abbildung 2.35
Da wir in Abschnitt 1.5.3 gewissermaßen die These aufgestellt haben, daß die Darstellungsform sich aus den durchzuführenden Operationen ergibt, wäre eine diesbezügliche Untersuchung der Bedingungsnetze sehr aufschlußreich, die aber nach Kenntnis des Autors bislang nicht vorliegt. Über die Netze selbst gibt es eine äußerst umfangreiche Literatur, deren Inhalt wir eher zur Deduktion im engeren Sinne rechnen, weshalb wir in diesem Buch nicht ausführlicher darauf eingehen, vielmehr diesbezüglich auf den Abschnitt 4.4.1 in [Bib92] sowie auf den Sonderband [FM92] über ``Constraint-Based Reasoning'' des Artificial Intelligence Journal verweisen wollen.
Christoph Quix, Thomas List, René Soiron