Default-Logiken - Methoden Wissensbasierter Systeme - page 246

Reiter schlug die folgende iterative Charakterisierung von Extensionen vor:

Theorem 8.10 Sei E eine Menge geschlossener Formeln, und sei T =(W, Δ) eine
Default-Theorie. Definiere eine Folge von Formelmengen E i ,i ≥ 0, in der folgenden

Weise:

E 0 = W

und fur i ≥ 0

χ

E

ϕ : ψ 1 ,...,ψ n
χ

E i+1 = Cn (E i ) ∪ | ∈ Δ,ϕ ∈ E i and ¬ ψ 1 ,..., ¬ ψ n / ∈

Dann ist E eine Extension von T genau dann, wenn

E = ∞ E i

i=0

gilt.

Ein Beweis dieses Theorems findet sich in [191].
Auch hiermit ist keine konstruktive Bestimmung von E moglich, da E selbst in
der Definition der E i vorkommt (!), praktisch also zunachst geraten werden muss,
bevor man es als Extension bestatigen kann.
Die obigen Definitionen stellen die Umsetzung des Begriffs einer Extension in
einer formal korrekten und eleganten Weise dar. Im nachsten Abschnitt werden wir
dagegen eine konstruktive Methode zur Berechnung von Extensionen vorstellen.

8.1.4 Ein operationaler Zugang zu Extensionen

“ Operational ” bedeutet hier die Einbettung des Begriffs der Extension in einen
Prozess. Wir werden ein Verfahren beschreiben, mit dem sich Extensionen explizit
berechnen lassen. Die grundlegende Idee dabei ist, Defaults so lange wie moglich
anzuwenden. Kommt es dabei zu Inkonsistenzen (was bei der unsicheren Natur
von Defaults nichts Ungewohnliches ist), so muss eine Rucksetzung ( backtracking )
erfolgen, und andere Alternativen mussen verfolgt werden. Wir werden hier im
Wesentlichen der Darstellung von [4] folgen.
Sei also T =(W, Δ) eine Default-Theorie. Mit Π = (δ 0 ,δ 1 ,...) bezeichnen wir
eine eventuell leere, endliche Folge von Defaults aus Δ ohne Wiederholungen. Π
reprasentiert eine gewisse Ordnung , in der die Defaults aus Δ angewendet werden
sollen. Da die wiederholte Anwendung eines Defaults nicht zu neuen Erkenntnissen
fuhrt, schließen wir Wiederholungen aus. Mit Π[k] bezeichnen wir die Teilfolge der
ersten k Elemente von Π, wobei immer angenommen wird, dass die Lange von Π
mindestens k betragt. Es gilt also Π[k]=(δ 0 ,δ 1 ,...,δ k−1 ), wobei Π[0] = () die leere
Folge ist.
Da wir nur endliche Defaultmengen Δ betrachten werden, wird auch jedes Π
endlich sein. Es ist jedoch notationsmaßig einfacher, die tatsachliche Lange von Π
nicht immer explizit aufzufuhren.