Database Reference
In-Depth Information
9.5
Erweiterte logische Programme
Das klassische logische Programmieren verdankt seinen Erfolg im Wesentlichen zwei
typischen Besonderheiten, namlich einer klaren, deklarativen Semantik in Form des
kleinsten Herbrandmodells und der SLD-Resolution, die aussagekraftige Antwort-
substitutionen e zient berechnet. Seine Ausdrucksfahigkeit ist jedoch beschrankt
dadurch, dass Atome nur in positiver Form in den Regeln auftreten durfen. Zwar
stellt Prolog einen not -Operator zur Verfugung, der eine Aussage als wahr annimmt,
wenn ihre Ableitung scheitert ( negation as failure ), doch wird negative Information
hier rein prozedural behandelt. Zudem mochte man die Moglichkeit haben, auch die
strenge, logische Negation zur Modellierung von Problemen benutzen zu konnen.
Beispielsweise konnte dann eine angemessene Darstellung des Pinguin-Problems mit
Default-Negation not und logischer Negation
¬
wie folgt aussehen:
Vogel (x)
Pinguin (x).
Fliegt (x)
Vogel (x), not
¬
Fliegt (x).
¬
Fliegt (x)
Pinguin (x).
Die Losung des Negationsproblems ruhrt an die Grundlagen des logischen Pro-
grammierens, denn ein Auftreten von Negation hat im Allgemeinen zur Folge, dass
nicht mehr ein eindeutiges Modell die Semantik eines logischen Programms be-
stimmt. Logische Programme mit Negation haben moglicherweise mehrere Modelle
oder auch gar kein sinnvolles Modell. Hier sind nicht nur technische Modifikationen
notwendig, sondern eine echte Erweiterung des Paradigmas des logischen Program-
mierens.
Erste, grundlegende Ansatze zur Erarbeitung einer deklarativen Semantik fur
logische Programme mit Default-Negation wurden von Clark [41] und Reiter [190]
unternommen und brachten prinzipielle Gemeinsamkeiten zwischen dem logischen
Programmieren und nichtmonotonen Formalismen ans Licht. Unter den in den Fol-
gejahren vorgeschlagenen Ansatzen wie z.B. der wohl-fundierten Semantik ( well-
founded semantics )wardie stabile Semantik ( stable model semantics ) [81] besonders
erfolgreich. Wir werden sie daher als geeignete Semantik fur logische Programme
mit Default-Negation vorstellen. Fur logische Programme mit beiden Arten der Ne-
gation ist die Antwortmengensemantik ( answer set semantics , [80]) eine passende
Erweiterung der stabilen Semantik. Im Unterschied zur klassischen logischen Se-
mantik ist eine Antwortmenge nun nicht mehr ein durch das logische Programm
eindeutig spezifiziertes Objekt, sondern eine von moglicherweise mehreren Losun-
gen eines Problems, das durch das logische Programm beschrieben wird.
Wir werden zunachst die Erweiterung der Syntax logischer Programme festle-
gen und dann die Semantik erweiterter logischer Programme stufenweise definieren.
In Definition 9.1 wurden logische Programme als Mengen definiter Klauseln
eingefuhrt. In den Regeln klassischer logischer Programme durfen daher nur Atome
auftreten. Die folgende Definition erweitert die Syntax logischer Programme, indem
sie sowohl strenge (logische) Negation als auch die Modellierung von fehlendem
Wissen mittels einer Default-Negation zulasst. Wie zuvor werden wir annehmen,
dass zu jedem logischen Programm immer eine passende Signatur Σ gegeben ist.
Search WWH ::




Custom Search