Database Reference
In-Depth Information
2. Wahle eine der maximalen Annahmen n
A
∈
MaxAnn(n
⊥
);
wahle einen (
out
-) Knoten n
∗
in der
out
-Liste der stutzenden Begrundung
von n
A
.
n
∗
3. F
¨
ugeeineneueBegrundung der Form
I
⊥
|
O
⊥
→
hinzu, wobei
I
⊥
= Vereinigung der
in
-Listen von
J
⊥
und
O
⊥
= (Vereinigung der
out
-Listen von
n
∗
}
J
⊥
)
−{
.
n
∗
Dann ist I
⊥
⊆
M und O
⊥
∩
M =
∅
,also
I
⊥
|
O
⊥
→
gultig in M .
4. Starte JTMS-Prozedur, Schritte 1 - 5 (n
∗
wird
in
, damit werden die Grund-
lagen der aktuellen stutzenden Begrundung von n
⊥
ungultig), und ermittle
ein neues Modell M
.
5. Ist der Status des Widerspruchsknotens n
⊥
auch im neuen Modell
in
, so wende
DDB auf M
und das erweiterte Netzwerk an.
6. Ist schließlich der Status von n
⊥
out
, so ist das DDB erfolgreich abgeschlossen;
HALT.
Anderenfalls liegt ein unlosbarer Widerspruch vor; HALT.
Dies ist der ursprungliche DDB-Algorithmus, wie er von Doyle in [54] vorgestellt
wurde. Unter dem Schlagwort
dependency directed backtracking
wird manchmal ge-
nerell auch jedes Rucksetzungs-Verfahren verstanden, das logischen Abhangigkeiten
folgt (im Gegensatz zum einfacheren
chronologischen Backtracking
).
Selbsttestaufgabe 7.21 (Widerspruchsknoten und DDB)
Man stelle sich
vor, im obigen Beispiel 7.13 solle die Aussage B nicht langer ohne die Aussage C
akzeptiert werden. Formulieren Sie mit Hilfe eines Widerspruchsknotens die hinzu-
zufugende Begrundung und ermitteln Sie mittels JTMS und DDB ein neues Modell
und uberprufen Sie dieses auf Zulassigkeit. Zeichnen Sie das Diagramm des erwei-
terten TMN.
7.4.3
Anwendungsbeispiele
Wir haben den Begriff eines Truth Maintenance-Netzwerks und sowohl das JTMS-
als auch das DDB-Verfahren bisher nur an sehr formalen Beispielen illustriert. Dies
geschah teilweise aus Grunden der Vereinfachung, teilweise aber auch, um eine klare
Unterscheidung zwischen
Knoten
und
logischer Aussage
zu machen (vgl. die Bemer-
kungen auf S. 212).
Dieser Abschnitt ist einigen kleinen Beispielen gewidmet, die zeigen sollen, wie
die Verwendung der TM-Techniken eine gegenuber der klassischen Logik erweiter-
te Wissensreprasentation und -verarbeitung ermoglicht. Wir beginnen mit Tweety,
dem beruhmtesten Vogel der nichtmonotonen Logiken.
Beispiel 7.22 (Tweety 1)
Es geht (wieder einmal) um die Modellierung der Aus-
sage “
Vogel konnen im Allgemeinen fliegen, aber Tweety der Pinguin nicht, da
Pinguine zwar Vogel sind, aber nicht fliegen konnen
”.
