Nächste Seite: 3.10.2 ATMS Vorige Seite: 3.10 Begründungsverwaltungssysteme

3.10.1 Klauselverwaltungssysteme

Wir haben im vorangegangenen zweimal gesehen, daß der deduktive Mechanismus in natürlicher Weise auf Problemstellungen stößt, die seine Kompetenz überschreiten. Dabei sind wir von der Vorstellung ausgegangen, daß an dieser Stelle der Benutzer gefragt wird. Wenn man an ein Gesamtsystem denkt, das sich ähnlich intelligent wie ein Benutzer verhalten soll, dann tritt an die Stelle des Benutzers eben das System selbst, was bei einer strukturierten Architektur eine spezielle Systemkomponente bedeuten würde. Und in der Tat geht man bei einem BVS-basierten System von zwei grundsätzlich voneinander getrennten Komponenten aus, dem eigentlichen BVS, das die deduktive und abduktive Arbeit leistet, wie sie am Beispiel soeben beschrieben wurde, und dem Problemlöser, der das BVS mit dem Wissen und der Auswahl der Annahmen versorgt. Diese Architektur ist in Abbildung 3.5 dargestellt.

Abbildung 3.5: Eine Problemlöserarchitektur

Die Problemlöserkomponente versorgt die BVS-Komponente mit einer Weltbeschreibung . Wie immer können wir annehmen, daß aus einer Menge von Klauseln besteht. Da es bei der Abhängigkeit von Annahmen um eine Abhängigkeit rein aussagenlogischer Struktur geht, können wir der Einfachheit halber zudem annehmen, daß nur Grundliterale auftreten, die gesamte Problemstellung also aussagenlogischer Natur ist. In dieser Form werden wir die Problemstellung nun präzisieren [RdK87].

Wir sagen, die Klausel stützt die Klausel auf der Basis einer Klauselmenge , wenn (dh. ist erfüllbar) und (bzw. ). Weiter heißt eine minimale Stütze von auf der Basis von , wenn es keine echte Untermenge von gibt, so daß die Klausel in bezug auf stützt.

Die erste der beiden Eigenschaften einer Stütze gewährleistet die Konsistenz, da sonst alles ableitbar wäre; die zweite besteht in der Eigenschaft, die wir oben bei der Abduktion bereits kennengelernt und erläutert haben. Der Begriff einer Stütze ist eng verwandt mit dem eines Primimplikanten [RdK87], der bei der Minimierung von Booleschen Schaltungsfunktionen eine wichtige Rolle spielt, was wir kurz erläutern wollen.

Ein Primimplikant einer Menge von Klauseln ist eine Klausel , die die folgenden beiden Eigenschaften erfüllt.

1. .
2. Es gibt keine echte Teilmenge von , für die gilt.

Als Beispiel sei . Die Primimplikanten sind in diesem Fall die beiden gegebenen Klauseln sowie die vier tautologischen Klauseln in den vier Variablen wie zB. .

Sei eine Klauselmenge und eine Klausel. Ist eine minimale Stütze für auf der Basis von , dann gibt es einen Primimplikanten von , so daß und gilt.

Die Umkehrung gilt nicht ohne Einschränkung, wie unser eben gegebenes Beispiel zusammen mit der Klausel zeigt. Der Primimplikant hat zwar einen nichtleeren Durchschnitt mit , jedoch ist keine minimale Stütze für auf der Basis von , da bereits auf der Basis von stützt. Jedoch gilt die Umkehrung in einem wichtigen eingeschränkten Fall.

Sei eine Menge von Klauseln und eine nichtleere Klausel. Ist ein Primimplikant von mit , dann ist eine minimale Stütze für auf der Basis von .

Als einfache Folgerung ergibt sich eine vollständige Charakterisierung der minimalen Stützklauseln für den Spezialfall von Einerklauseln als Anfragen.

Sei eine Klauselmenge und eine Einerklausel. Dann ist eine minimale Stütze für auf der Basis von genau dann, wenn es einen Primimplikanten von gibt, so daß und gilt.