3. Deduktion in der Pr adik atenlogik...3. Deduktion in der Pr adik atenlogik Wie wir am Beginn des vorangegangenen Kapitels zu erkl ar en ver-suchten, ist es zum Verst andnis der

3. Deduktion in derPradikatenlogik

Wie wir am Beginn des vorangegangenen Kapitels zu erklaren ver-suchten, ist es zum Verstandnis der komplexen Mechanismen der De-duktion erforderlich, eine Reduktion der Problemstellung vorzunehmen.Eine solche reduzierte Fragestellung haben wir im vorangegangenen Ka-pitel ausfuhrlich behandelt, indem wir uns ausschließlich auf die aussagen-logische Struktur von pradikatenlogischen Problemstellungen konzentrierthaben.

Im vorliegenden Kapitel werden wir diese Reduktion nun fallen las-sen und dabei sehen, daß sich alle bisher erzielten Ergebnisse voll auf denunreduzierten Fall ubertragen lassen. In diesem Sinne war die gewahlteReduktion eine vernunftige, da die erzielten Ergebnisse fur den allgemei-nen Fall in entsprechend modifizierter Form Gultigkeit behalten.

Die dazu erforderliche Modifikation ist allerdings nicht vollig trivialund mußte strenggenommen nun fur alle bisherigen Ergebnisse im Detaildurchgefuhrt werden. Ein solches Vorgehen wurde den zur Verfugung ste-henden Rahmen sprengen. Deshalb werden wir die Verallgemeinerung imwesentlichen nur einmal im Detail demonstrieren. Die dabei verwendeteVerallgemeinerungstechnik laßt sich dann in analoger Weise auch fur dieanderen Ergebnisse anwenden. Im Idealfall wurde sich der Leser davondadurch uberzeugen, daß er nach dem Studium des vorliegenden Kapitelsnochmals zum vorangegangenen Kapitel zuruckkehrt und sich die jeweiligeverallgemeinerte Fassung der dortigen Aussagen selbst klarmacht.

3.1 Die Sprache der Pradikatenlogik

Wir wollen nochmals darauf hinweisen, daß diese Darstellung davon Terme undFormelnausgeht, daß sich der Leser mit den Grundbegriffen der Pradikatenlogik

vertraut gemacht hat. Ungeachtet dessen beginnen wir hier zum Zweckeder Normierung der Sprechweise und Notation mit einer Definition der

75

3. Deduktion in der Pradikatenlogik

Formeln. Dabei gilt fur jedes neu eingefuhrte Alphabet immer stillschwei-gend die Vereinbarung, daß seine Elemente verschieden von denen fruhereingefuhrter Alphabete sind.

Definition 3.1.1Die Sprache der Pradikatenlogik basiert auf den folgenden Alphabeten.V Die Menge der (Objekt-) Variablen, die wir mit x, y, z bezeichnen.F Die Menge der Funktionszeichen, die wir mit f, g, h bezeichnen.P Die Menge der Pradikatszeichen, die wir mit P,Q,R bezeichnen.Zu jedem Zeichen aus F und P ist eine Stelligkeit vermoge der Abbil-dung α : F ∪P → IN in die naturlichen Zahlen definiert. Wir verwendendie Bezeichnungen Fn = {f ∈ F | α(f) = n} und Pn = {P ∈ P |α(P ) = n} , wobei n ≥ 0 ist. Die Elemente von F 0 heißen auch Kons-tante und wir bezeichnen sie mit a, b, c .

Die Menge T der Terme (uber V∪P ) ist induktiv wie folgt definiert.(T1) Jede Variable ist ein Term.(T2) Zu jedem n–stelligen Funktionszeichen f und zu n beliebigen Ter-

men t1, . . . , tn ist auch f(t1, . . . , tn) ein Term.Terme bezeichnen wir mit t, s .

Eine Atomformel (auch atomare Formel oder kurz Atom) ist von derGestalt P (t1, . . . , tn) mit einem n–stelligen Pradikatszeichen P . EinLiteral ist ein Atom oder ein negiertes Atom.

Eine pradikatenlogische Formel ist induktiv wie folgt definiert.(F1) Jedes Atom ist eine Formel.(F2) Sind F und G Formeln, so ist auch jedes der folgenden Gebilde

eine Formel:¬F , F ∨ G , F ∧ G , ∃x F , ∀x F

Diese Definition bedurfte einer Fulle von Kommentaren, die aber nichtGegenstand dieser Abhandlung sein konnen, wie mehrfach betont wurde.Wir erwahnen nur die Moglichkeit der Verwendung weiterer logischerZeichen (vgl. Abschnitt 2.5), auch solcher hoherer Stelligkeit; die struk-turelle Ubereinstimmung von Atomen (ja sogar von beliebigen Formeln)mit Termen; die Verwendung von Klammern zur Verdeutlichung der For-melstruktur; die subtilen Details im Zusammenhang mit dem Bindungsbe-reich von Quantoren; den Unterschied zwischen freiem und gebundenemAuftreten von Variablen; die Quantifizierung uber Konstanten; geschlos-sene Formeln, auch Satze genannt; den Begriff des Vorkommens einesZeichens in einer Formel. Wir gehen davon aus, daß all diese und weitereDetails dem Leser gut vertraut sind [Bib87, EFT78, Ric78, Sch87].

Wo immer dies ohne ernstliche Mißverstandnisse durchfurbar ist,Klammerung

werden wir den Gebrauch von Klammern so weit wie moglich einschran-

76

3.1. Die Sprache der Pradikatenlogik

ken (siehe auch die Regeln zur Klammerersparnis in Abschnitt 2.2). Diesgilt insbesondere fur einstellige (Funktions- oder Pradikats-) Zeichen oderfur das Auftreten eines einzigen n–stelligen Zeichens.

Mit der im Abschnitt 3.4 behandelten Skolemisierung laßt sich jede Normalform

Formel durch eine Formel in Skolemnormalform der Gestalt ∃x1 . . . xn F

ersetzen, wobei F keine Quantoren enthalt. Dabei erinnern wir daran,daß wir in diesem Buch der positiven Reprasentation den Vorzug gegebenhaben. Im Fall der negativen Reprasentation treten an die Stelle derExistenzquantoren Allquantoren. Mit den im Abchnitt 2.5 behandeltenTransformationen laßt sich zusatzlich annehmen, daß F aussagenlogischbetrachtet in Normalform ist. Im letzteren Fall sprechen wir dann auchin der Pradikatenlogik von einer Formel in Normalform. In der Regelwerden wir daher nur Formeln in Normalform betrachten. Bei Formelnin Normalform oder in Skolemnormalform verstehen sich die Quantorenvon selbst, so daß sie meist weggelassen werden.

Formeln konnen als Graphen aufgefaßt werden. Es gibt hierfur Formelgraph

mindestens die folgenden drei verschiedenen Formen, je nachdem welcheder Formelstrukturen wir sichtbar machen wollen. Wie bereits erwahnt,konnen Formeln als Terme aufgefaßt und daher als Termbaume reprasen-tiert werden. In diesem Sinne ist die Formel ∀abc ∃xyz [Pxc ∧P (fzb, b)∨¬P (fay, y)] durch den markierten Baum in Abbildung 3.1 reprasentiert.Man beachte, daß durch unsere Bezeichnungsvereinbarungen Quantorenuberflussig werden. Dabei ist es kein Versehen, daß fur allquantifizierteVariable Konstantenbezeichnungen verwendet werden. Wenn dem Le-ser derartige Details nicht wohlvertraut sind, darf ihm noch einmal dieWichtigkeit des obigen Verweises auf die Logikliteratur wie zB. [Bib87]ans Herz gelegt werden.

In den Mechanismen, die wir in den folgenden Abschnitten behan- gaG–Darstellungdeln, ist es wichtig, verschiedene Vorkommen des gleichen Zeichens leicht

zu uberblicken. So tritt in unserer Beispielformel etwa das y an zwei ver-schiedenen Stellen auf. Sogenannte gerichtete, azyklische Graphen (kurzgaG (englisch directed acyclic graph, kurz dag)) erlauben hierfur eine we-sentlich kompaktere Darstellung, wie es in Abbildung 3.2 fur die gleicheFormel illustriert ist.

Oberhalb der oberen gestrichelten Linie befinden sich die zu denQuantoren gehorigen Knoten. Darunter, aber oberhalb der unteren ges-trichelten Linie, befinden sich die den aussagenlogischen Operatoren zu-geordneten Knoten. Darunter sind die auftretenden Atome reprasentiert.

Diese Kompaktifizierung laßt sich noch weiter treiben. So tretenja die Konstanten als Markierungen am obersten Knoten sowie auch alsMarkierungen an Blattern des gaG auf. Durch Ersetzung einer jeden

77


r abc

r xyz

r��∨

r��∧

r�

��

P

r x

r@@@

P

r c

rHHHHHH∧

r�

��

P

r�

��

f

r z

r@@@

f

r b

r@@@

P

r b

rPPPPPPPPP∨

r ¬

r�

��

P

r�

��

f

r a

r@@@

f

r y

r@@@

P

r y

Abbildung 3.1: Markierter Baum der Formel ∀abc ∃xyz [Pxc ∧P (fzb, b) ∨ ¬P (fay, y)]

r abc

r xyz

r��∨

r��∧

r�

��

P

r x

r@@@

P

r c

rHHHHHH∧

r�

��

P

r�

��

f

r z

r@@@

f

r b

r P

rPPPPPPPPP∨

r ¬

r�

��

P

r�

��

f

r a

r@@@

f

r y

r P

Abbildung 3.2: Die Formeldarstellung als gaG

78

3.1. Die Sprache der Pradikatenlogik

Markierung an einem inneren Knoten des gaG durch eine Kante, die inein Blatt fuhrt, laßt sich dieses mehrfache Auftreten vollig unterbinden.Man konnte dies noch weiter treiben und nicht nur Blatter als gemein-same Unterknoten, sondern auch gemeinsame Untergraphen mit mehr alseinem Knoten zulassen; dies wollen wir jedoch nicht tun, da schon derAufwand, eine solche Kompaktifizierung dann zu erreichen, erheblich seinkann.

Die dritte Form der Darstellung betrifft die der Formel zugrunde- Matrix-darstellungliegende Matrixstruktur, die uns aus dem letzten Kapitel bereits gelaufig

ist. Als Matrix lautet unsere Formel wie folgt.

Pxc

P (fzb, b)

¬P (fay, y)

Fur die Zwecke der automatischen Deduktion erweist sich schließlich sogareine Mischung der beiden letztgenannten Formeldarstellungen als beson-ders hilfreich. Hierzu muß man sich einer dreidimensionalen Darstellungbedienen. Dann stellen wir alle aussagenlogischen Informationen der For-mel, in unserem Beispiel in der gaG Darstellung also alles zwischen denbeiden gestrichelten Linien, als Matrix in einer Ebene, alles daruber unddarunter weiterhin in vertikaler Richtung dar. Wir werden in diesemSinne bildlich auch von der Matrixebene und von den Termfußen spre-chen. Wenn man die ohnehin selbstverstandlichen Quantoren weglaßt,dann ergibt dies fur unser Beispiel das in Abbildung 3.3 dargestellte Bild.

Wenn man die dritte Dimension in dieser Darstellung ignoriert, sich Substitution

also nur auf die Matrixebene konzentriert, dann handelt es sich um einekomplementare Matrix im aussagenlogischen Sinne. Vorgreifend konnenwir sagen, daß dies auch pradikatenlogisch dann gilt, wenn zusatzlichalle konnektierten Termfuße durch Substitution der Variablen identischgemacht werden konnen. Im Beispiel mussen wir dazu im Hinblick aufeine der beiden Konnektionen die Variable x durch fac und die Variabley durch c ersetzen. Zu diesem Zweck beschaftigen wir uns zunachstallgemein mit dem Begriff der Substitution.

Definition 3.1.2Eine Substitution ist eine Abbildung σ einer Menge S in eine MengeR , σ : S → R .

Eine Variablensubstitution ist eine Substitution mit S = V , derVariablenmenge, und mit R = T , der Termmenge, die fast uberall (dh.mit Ausnahme von endlich vielen Elementen) die identische Abbildung

79


��

��

��

��

bP��

b f��

bz

DDDDDDDDDDDDD

bb

QQQ

QQQ

bP

��bx

DDDD bc

��

��b¬P

��

b f��

ba

DDDDDDDDDDDD

by

QQQ

QQQ

Abbildung 3.3: Dreidimensionale Matrixdarstellung

ist. Die Menge der Variablen x ∈ V , fur die x 6= σx gilt, heißt derDefinitionsbereich (oder Domain) von σ , kurz DB(σ) . ε bezeichnet dieleere Substitution, also die identische Abbildung. Die Menge der Termeσx mit x aus dem Definitionsbereich heißt der Wertebereich (oder Co-domain) von σ .

Endliche (Variablen–) Substitutionen lassen sich als Mengen von Paarendarstellen. So ist die oben beschriebene Ersetzung definiert als die Sub-stitution σ′ = {x\fac, y\c} . Es gibt viele Varianten der Notierung solcherPaare. Leider uberzeugt auch der in [DJ91] gemachte Versuch einer Ve-reinheitlichung nicht aus logischer Sicht. Die von uns gewahlte Notierungorientiert sich an der naturlichen Vorstellung einer Rampe, dargestellt inForm des Schragstriches, die, sich selbst uberlassen, aufgrund der Schwer-kraft die substituierte Variable zum Verschwinden bringt. Auch die Rei-henfolge, erst die zu ersetzende Variable und dann den Substitutionstermzu nennen, halten wir so fur die naturlichste.

Die Anwendung einer Substitution σ auf einen Term t schreibtSubstitutions-anwendung man in Form eines Postfixoperators, also tσ . Damit wird derjenige Term

bezeichnet, der entsteht, wenn man alle in t auftretenden Variablen desDefinitionsbereichs von σ durch deren Werte unter σ in t ersetzt. Soist fur die soeben gegebene Beispielsubstitution P (x, c)σ ′ = P (fac, c) .

80

3.2. Die Semantik der Pradikatenlogik

Definition 3.1.3Die Komposition τρ zweier Substitutionen τ und ρ ist durch ihre Kom- Komposition

position als Funktionen gegeben; sie ergibt sich als die Substitution

{x\t ∈ ρ | x 6∈ DB(τ)} ∪ {x\tρ | x\t ∈ τ ∧ x 6= tρ}.

Eine Substitution heißt idempotent, wenn keine der Variablen aus demDefinitionsbereich in irgendeinem Term des Wertebereichs von σ auftritt,dh., anders ausgedruckt, wenn σσ = σ .

Da wir es meist mit itempotenten Variablensubstitutionen zu tun haben,werden wir im folgenden unter einer Substitution immer eine idempotenteVariablensubstitution verstehen, wenn nichts Gegenteiliges festgelegt ist.

3.2 Die Semantik der Pradikatenlogik

Bei der Entwicklung der Sprache der Pradikatenlogik hat die naturlicheSprache Pate gestanden. Wie diese sollte sie in der Lage sein, “einen In-halt . . . durch geschriebene Zeichen zum Ausdruck [zu] bringen”, diesaber “in genauerer und ubersichtlicherer Weise . . . als es durch Wortemoglich ist” [Fre82]. Genauigkeit oder Prazision (zB. durch Eliminationvon Zweideutigkeiten, durch Festlegung der Quantoren usw.) auf dereinen und Ubersichtlichkeit (durch uniformen Aufbau, auch auf Kostenhoherer Redundanz) auf der anderen Seite sind es also, was die Pradika-tenlogik von der naturlichen Sprache unterscheidet.

Soweit dem Autor bekannt ist, hat Frege selbst keinen Versuch unter- Semantik

nommen, den “Inhalt” seiner Sprache formal zu fassen. Im Sinne L. Witt-gensteins [Wit58] laßt sich das eigentlich auch gar nicht durchfuhren, daSprache ihre Bedeutung durch den Gebrauch erlangt. Auch spatere he-rausragende Reprasentanten des Gebiets hielten eine Beschaftigung mitder Semantik nicht fur besonders hilfreich oder, wie wohl Herbrand, nichteinmal fur sinnvoll.

Selbst wenn man einen anderen Standpunkt hierzu einnimmt, bleibtdie Tatsache, daß eine Semantik nur dadurch angegeben werden kann,daß man eine weitere formale Sprache angibt und eine Beziehung zwi-schen den beiden herstellt. Genau dies hat A. Tarski [Tar36] fur diePradikatenlogik in einer Weise getan, die heute als Standard angesehenwird. Bezuglich der Details verweisen wir wieder auf Lehrbucher der ma-thematischen Logik [Bib87, EFT78, Ric78, Sch87] und wollen uns nurdarauf beschranken, diese Semantik am Beispiel zu illustrieren.

Nehmen wir an, der Vater von Karl wohnt in der Fregestr. 79. Dannliest sich das in der Sprache der Pradikatenlogik zB. als

Wohnt(vater(karl),fregestr 79)

81


Durch die Normierung der Darstellung wird zweifelsfrei die Rolle derWorte festgelegt. Wohnt spielt die Rolle eines zweistelligen Pradikats,vater die einer einstelligen Funktion und die ubrigen beiden die vonKonstanten. Diese Eindeutigkeit zu erzielen ist der eigentliche Zweckder Pradikatenlogik, nicht etwa die mehr oder weniger zufallig gewahlteSyntax. In der Einschatzung der Rolle der Logik in der Intellektik ist die-ser wichtige Unterschied oft ubersehen worden. Wenn die gleiche AussagezB. in Form eines semantischen Netzes [CM85] dargestellt wird, ist dieSyntax zwar eine andere, aber die syntaktische Funktion der einzelnenWorte bleibt die gleiche. Wenn man es vorzieht, kann man auch sagen,die Semantik bleibt die gleiche.

Fur den Menschen beruht die Semantik auf dem Verstandnis derInter-pretations-funktion

einzelnen Worte im gegebenen Kontext. Wir verstehen karl , indem wirdieses Wort mit einer Person assoziieren. Bezeichnen wir diese Assozia-tion mit dem Zeichen ι , dann konnen wir sagen, ι (karl) sei die Bedeu-tung des Wortes karl , wobei der Wert von ι (karl) eben die Person ist,um die es sich handelt. Wir begegnen hier aber einer Reihe von philo-sophischen Problemen. Meinen wir genauer unsere Vorstellung von derPerson, dh. der Summe aller Kenntnisse, die wir uber sie haben, odermeinen wir die physisch existierende Person in der realen Welt, von deruns die meisten Eigenschaften vollig unbekannt sind.

Die Pradikatenlogik im Sinne von Frege, Herbrand und anderen ent-Struktur

zieht sich diesen und anderen Schwierigkeiten, indem sie auf die Seman-tik nicht wirklich zuruckgreift. Die Tarskische Semantik entzieht sich denSchwierigkeiten, indem sie ein Universum U vorgibt, in dem die Existenzeines Elementes k gefordert wird, das als Bedeutungswert von ι (karl)bezeichnet wird. Offensichtlich heißt dies nichts anderes, als daß wir dieBedeutung des pradikatenlogischen Zeichens karl durch ein anderes Zei-chen k eines anderen Formalismus erklart haben, worauf wir eingangsschon hingewiesen haben. In dieser Weise kann dann jedem pradikatenlo-gischen Zeichen unseres Beispiels ein Bedeutungswert zugewiesen werden,der seine Bedeutung widerspiegelt. So ist der Bedeutungswert ι (vater)eine Funktion f:U → U und der Bedeutungswert ι (Wohnt) eine Rela-tion r∈ U × U . Das Paar bestehend aus dem Universum U und derInterpretationsfunktion ι bezeichnet man auch als eine Struktur .

Der Bedeutungswert der gesamten pradikatenlogischen Aussage

Wohnt(vater(karl),fregestr 79)

ergibt sich durch Einsetzung der Bedeutungswerte ihrer einzelnen Teileund liefert dann einen Wahrheitswert wahr oder falsch je nachdem, obdie sich ergebenden Elemente im Universum in der sich ergebenden Re-lation stehen oder nicht. Der in Abschnitt 2.3 behandelte Spezialfall von

82

3.3. Eine Charakterisierung der Gultigkeit

nullstelligen Pradikatszeichen fugt sich in diese hier erlauterte Form derInterpretation nahtlos ein.

Unter Berucksichtigung des naturlichen Verstandnisses der logischen Formel-interpretationOperatoren laßt sich diese Form einer Semantik auch auf beliebige For-

meln der Pradikatenlogik erweitern, wie wir es fur die Matrixform inAbschnitt 2.3 durchgefuhrt haben. Insgesamt spricht man dann von ei-ner Interpretation einer solchen Formel. Jede Formel laßt sich so aufverschiedenste Weise interpretieren. karl kann demnach genausogut alsein bestimmtes Insekt interpretiert werden. Das mag zunachst sehr un-naturlich erscheinen, hat seinen Sinn aber besonders in dem folgendenSachverhalt.

Die logisch wahren oder gultigen Aussagen, die wir in der Aussa- GultigeFormelngenlogik Tautologien genannt haben, zeichnen sich dadurch von anderen

Aussagen aus, daß sie unabhangig von einer gewahlten Interpretation im-mer den Bedeutungswert wahr annehmen. Bei ihnen kommt es also aufdie Interpretation uberhaupt nicht an, wie fur den Fall der Aussagenlogikaus der Definition 2.3.5 zu ersehen ist. Andererseits handelt es sich beiihnen um genau diejenigen Aussagen, um die es in Deduktionsverfahrengeht, wenn in bestimmten Anwendungen dieser Bereich auch manchmaluberschritten wird (wie in dem in Abschnitt 2.7.9 besprochenen Fall).

Schließlich erwahnen wir noch die folgenden Begriffe aus der Lo-gik. Eine erfullbare Formel hat bei mindestens einer Interpretation denBedeutungswert wahr; eine solche Interpretation nennt man dann auchein Modell der Formel. Eine falsifizierbare Formel hat bei mindestenseiner Interpretation den Bedeutungswert falsch, wahrend sich bei einerunerfullbaren Formel bei jeder Interpretation der Wert falsch ergibt.

3.3 Eine Charakterisierung der Gultigkeit

Fur das Folgende nehmen wir nun an, daß alle Formeln in der in Ab-schnitt 3.1 eingefuhrten Normalform ohne Quantoren vorliegen. Inwie-weit dies eine Einschrankung bedeutet, wird dann im nachsten Abschnitterlautert.

Erinnern wir uns an das einfuhrende Beispiel aus dem Abschnitt 2.1, Liften

das in Normalform ohne Quantoren wie folgt lautet.

Ax ∧ ¬Sx ∨ Sy ∧ ¬Hy ∨ ¬Ac ∨ Hc

Alles was wir in Abschnitt 2.2 eingefuhrt haben, wird nun auf Formelndieser Art ubertragen. Diese Ubertragungsoperation von der Aussagenlo-gik in die Pradikatenlogik ist von großer Wichtigkeit fur das Verstandnisder Literatur der automatischen Deduktion. Wir werden hierfur (wie

83


im Englischen) den Begriff des Liftens gebrauchen. So fuhrt das Liftender Matrixdarstellung angewandt auf unsere Beispielformel zu folgenderMatrix.

Hc

¬Hy

Sy

¬Sx

Ax

¬Ac

Wie im Abschnitt 3.1 bereits illustriert, ist die Situation nur geringfugigverschieden von derjenigen in der Aussagenlogik. Beschrankt man sich inder Betrachtung auf die (dort eingefuhrte) Matrixebene, so ist sie sogarvollig identisch. Nur treten hier nun noch die Termfuße (siehe ebenfallsAbschnitt 3.1) hinzu, die es zusatzlich zu beachten gilt.

Eine hinreichende Bedingung fur die Gultigkeit einer solchen MatrixPaarung

(und damit der von ihr reprasentierten Formel) ist die Existenz einer auf-spannenden Paarung (genau wie im aussagenlogischen Fall) sowie einerSubstitution, so daß nach ihrer Anwendung auf alle Termfuße konnek-tierte Termfuße identisch sind. Betrachten wir die folgende Paarung zuunserem Beispiel.

Hc

¬Hy

Sy

¬Sx

Ax

¬Ac

Jeder der vier moglichen Pfade durch die Matrix enthalt (mindestens)eine der drei Konnektionen. Also ist dies Paarung aufspannend. Zu ihrbetrachten wir nun die Substitution σ = {x\c, y\c} , die alle konnektiertenTermfuße offensichtlich identisch macht. Unsere Matrix ist also in der Tatgultig.

Die genannte Bedingung ist nicht notwendig, wie das Beispiel einergultigen Matrix in Abbildung 3.4, die wir im Abschnitt 3.1 bereits studierthaben, zeigt. Zwar ist die Paarung aufspannend, aber es laßt sich keinegeeignete Substitution fur beide Konnektionen gleichzeitig angegeben.Die Substitution σ = {x\fac , y \ c} macht zwar die von der oberenKonnektion verknupften Termfuße identisch, sie ist aber fur die untereKonnektion unbrauchbar, da durch sie {y\b} erforderlich ware, b undc aber als zwei verschiedene Konstanten nicht gleich gemacht werdenkonnen.

Die Losung beruht darin, daß wir auch mehr als eine Kopie von Klau-Klauselkopien

seln zulassen mussen. Betrachten wir im vorliegenden Fall zwei Kopienvon der zweiten Klausel, so laßt sich die Gultigkeit in der eben beschrie-

84

3.3. Eine Charakterisierung der Gultigkeit

Pxc

P (fzb, b)

¬P (fay, y)

Abbildung 3.4: Beispiel einer gultigen Matrix

benen Weise unter Verwendung der Substitution σ = {x\fac , y1\c , z\a , y2\b} doch nachweisen.

Pxc

P (fzb, b)

¬P (fay1, y1) ¬P (fay2, y2)

Der Grund fur die Notwendigkeit mehrerer Kopien von Klauseln liegt in Kopienindex

dem Auftreten von Existenzquantoren. Erinnern wir uns, daß alle auf-tretenden Variablen existenz-quantifiziert sind, insbesondere also auchy . “Es gibt ein y ” laßt auch nach seiner naturlichen Bedeutung eineoder mehrere Losungen zu. In unserem Beispiel benotigen wir in diesemSinne zwei solcher Losungen, c und b , in anderen Beispielen konnen esbeliebig viele sein. Wie das Beispiel illustriert, unterscheiden wir die ver-schiedenen Losungen durch das Anfugen eines Index an die quantifizierteVariable.

Wegen der beiden fast identischen Kopien ist diese Darstellung ziem- IndizierteMatrixlich redundant. Da der einzige Unterschied eben im Index besteht, defi-

nieren wir die folgende Darstellung als Abkurzung der vorherigen.

Pxc

P (fzb, b)

¬P (fay, y)

1

��2

��Wir sprechen hier von einer indizierten Paarung, bei der Konnektionen-enden mit Indizes versehen sind. Wir konnen der Uniformitat halber auch

85


Pffa

¬Pfx

Px

¬Pa

2

��1

��

2

��1

��Abbildung 3.5: Beispiel einer gultigen, indizierten Matrix

annehmen, daß sogar alle Konnektionenenden indiziert sind, indem wiruns vorstellen, daß nicht-indizierte Enden vereinbarungsgemaß den Index1 erhalten. Eine Matrix mit einer indizierten Paarung nennen wir aucheine indizierte Matrix. Die vorangegangene, erweiterte Form mit denbeiden expliziten Kopien nennen wir die expandierte Form der indiziertenMatrix. Der Ubergang von der expandierten zur indizierten Form einerMatrix und umgekehrt ist immer in eindeutiger Weise moglich, wie manleicht sieht.

Ein Pfad durch eine indizierte Matrix ist demnach definiert als einPfade

Pfad durch ihre expandierte Form. Wie bisher ist eine (indizierte) Paa-rung aufspannend , wenn jeder Pfad mindestens eine Konnektion der Paa-rung enthalt. Dann gilt der folgende fundamentale Satz der Konnektions-methode.

Theorem 3.3.1Eine Formel in Normalform ist gultig, wenn es eine aufspannende in-Charakterisie-

rungstheorem dizierte Paarung und eine Substitution σ gibt, so daß die Anwendungvon σ auf die durch die Paarung konnektierten Termfuße diese identischmacht.

Dies ist die geliftete Form des Theorems 2.4.1. Sein Beweis findet sichin [Bib87] (siehe dort das Korollar III.6.4). Wie gerade im einzelnenerlautert, erfullt unser vorangegangenes Beispiel genau diese Bedingungenund ist daher hiermit als gultig nachgewiesen. Betrachten wir noch dasBeispiel aus Abbildung 3.5.

Diese indizierte Matrix hat vier Pfade, da ja die mittlere Klauselwegen der Indizes doppelt zu sehen ist. Jeder der Pfade enthalt mindes-tens eine der drei Konnektionen, so daß diese Paarung aufspannend ist.

86

3.4. Normalformtransformationen

Die Substitution σ = {x1 \a , x2 \fa} macht uberdies alle konnektier-ten Termfuße identisch. Damit sind alle Bedingungen erfullt, also ist dieMatrix gultig. Zugleich ist leicht zu sehen, daß dies auch fur jede Matrixgilt, die in der ersten Klausel beliebig viele Anwendungen von f , also einLiteral Pfna anstelle von Pffa , enthalt. Der Beweis andert sich nurdahingehend, daß die mittlere Konnektion in n − 1 Instanzen benotigtwird.

Das vorangegangene Theorem ist, wie erwahnt, die geliftete Formdes Theorems 2.4.1. Hinzugetreten ist zur aufspannenden Menge vonKonnektionen zum einen das Erfordernis, daß manche dieser Konnektio-nen in mehrfachen Instanzen (wie in der zuletzt beschriebenen Verallge-meinerung) benotigt werden. Zum andern ist die Existenz der genann-ten Substitution zu prufen. Durch Beachtung dieser beiden zusatzlichenMerkmale konnen nun auch die im zweiten Kapitel besprochenen Verfah-ren zum Nachweis der Gultigkeit einer Formel auf die Stufe der Pradi-katenlogik geliftet werden. Hierzu bedienen wir uns einer fundamenta-len Operation zur Bestimmung der benotigten Substitution, namlich derUnifikation. Sie werden wir nach der Diskussion der im vorangegangenenverwendeten Normalform einfuhren, bevor wir dann zu den Verfahrenkommen.

3.4 Normalformtransformationen

In der Definition 3.1.1 haben wir Formeln beliebig verschachtelterForm eingefuhrt, uns dann aber auf Formeln in Normalform beschrankt.In diesem Abschnitt wollen wir noch die Begrundung nachholen, unterwelchen Umstanden diese Beschrankung moglich ist. Hinsichtlich desaussagenlogischen Teiles ist diese Begrundung in Abschnitt 2.5 bereitsdargelegt, so daß nur noch das Liften notig ist.

All solche Transformationen beruhen auf gultigen Formeln der Ges- Trans-formationentalt A ↔ B . Sie ermoglichen in einer gegebenen Formel die Ersetzung

einer Unterformel der Gestalt A durch eine Unterformel B , ohne denWahrheitswert bei einer beliebigen Interpretation zu andern. Man sprichthier von einer modellerhaltenden Transformation oder auch davon, daßsich die Ausgangsformel in die Endformel aquivalent uberfuhren laßt.Beilaufig erwahnen wir, daß es in diesem Sinne auch gultigkeitserhaltende,erfullbarkeitserhaltende usw. Transformationen gibt. Fur die im Hinblickauf die Normalform erforderlichen Transformationen benotigen wir die

87


folgenden gultigen Formelschemata.

¬∀x F ↔ ∃x ¬F¬∃x F ↔ ∀x ¬F

∀x F ∧ G ↔ ∀x (F ∧ G) x nicht frei in G

∀x F ∨ G ↔ ∀x (F ∨ G) x nicht frei in G

∃x F ∧ G ↔ ∃x (F ∧ G) x nicht frei in G

∃x F ∨ G ↔ ∃x (F ∨ G) x nicht frei in G

Die einfachste Form der Transformation in Normalform laßt sich wie folgtUmformung inNormalform bewerkstelligen. Die gegebene Formel wird nach Bedarf durch Einfuhrung

zusatzlicher Allquantoren abgeschlossen. Dann eliminiere man alle aussa-genlogischen Operatoren bis auf ¬, ∧ , ∨ und alle Negationszeichen mitAusnahme solcher vor Atomen. Neben den aussagenlogischen Gesetzen,die in A4.1 zusammengestellt sind, benotigt man hierbei die ersten beidender obigen Gesetze. Dann bringe man sukzessive unter Verwendung derubrigen vier obigen Gesetze die Formel in pranexe Normalform, so daß dieFormel aus einer Folge von Quantoren und einer quantorenfreien Matrixbesteht. Die Matrix bringe man in Normalform unter Verwendung einesder in Abschnitt 2.5 besprochenen Verfahren. Aus der Folge der Quanto-ren eliminiere man sukzessive im Falle der positiven Reprasentation dieAllquantoren und im Falle der negativen Reprasentation die Existenz-quantoren mit der auf der folgenden Aussage beruhenden Operation derSkolemisierung , die auf [Sko20] zuruckgeht.

Eine Formel der Gestalt ∃x1, . . . , xn ∀c F ist gultig genau dann,Skolemisierung

wenn ∃x1, . . . , xn F{c \ f(x1, . . . , xn)} gultig ist. Die Skolemfunktionf darf dabei nirgends sonst in F auftreten. Analog ist eine Formel derGestalt ∀x1, . . . , xn ∃c F unerfullbar genau dann, wenn ∀x1, . . . , xn F{c\f(x1, . . . , xn)} unerfullbar ist.

Man beachte, daß die Skolemisierung nur gultigkeitserhaltend, nichtaber modellerhaltend ist, was aber fur unsere Zwecke des Beweisens gulti-ger Formeln ausreicht. Bei der Pranexierung lohnt es sich darauf zu ach-ten, daß (in der positiven Reprasentation) Allquantoren gegenuber denExistenzquantoren wenn moglich immer zuerst vorangestellt werden, weilauf diese Weise die Anzahl der Argumente der Skolemfunktionen mini-miert werden kann. Dies kann die Beweissuche und die Lange des resultie-renden Beweises gunstig beeinflussen. Diese Minimierung laßt sich durchBeachtung weiterer aussagenlogischer Gesetze noch weiter treiben, wasim Abschnitt IV.11 in [Bib87] unter dem Stichwort “Antipranexierung”genauer erlautert ist. Die Beweise zu den Aussagen, auf denen die hierbehandelten Transformationen beruhen, findet man im Abschitt III.4 in[Bib87].

Das Ergebnis der oben beschriebenen Transformation ist eine For-Matrix

88

3.5. Unifikation

mel, die aus einer Folge von Existenzquantoren (bzw. von Allquantoren inder negativen Reprasentation) und einer quantorenfreien Matrix in (aus-sagenlogischer) Normalform besteht. Die Folge der Existenzquantorenschreibt man meist mit einem einzigen Quantor gefolgt von der Folge derquantifizierten Variablen. Da es nur noch eine einzige Art von Quantorengibt, versteht sich der Quantor von selbst, so daß man ihn auch entbehrenkann, was in der Regel geschieht. Ubrig bleibt also eine Matrix, die derForm nach von aussagenlogischer Gestalt ist, deren Literale jedoch Pradi-kate mit Termen enthalten. Fur die Darstellung einer solchen Matrix giltalles im Abschnitt 2.5 Gesagte.

Wie bereits im Abschnitt 2.5 erwahnt, ist ein Ubergang zur Nor- Nicht-Normal-Formmalform nicht zwingend geboten, da der Hauptsatz der Konnektionsme-

thode auch fur Formeln in Skolemnormalform gilt. Ein großeres Beispieleines Konnektionsbeweises fur eine gultige Nicht-Normalform–Matrix fin-det der Leser in der Abbildung 5.1, auf die einen Blick zu werfen sich furden Leser vielleicht schon an dieser Stelle lohnen konnte. Selbst die Sko-lemisierung ist uberflussig, worauf wir in Abschnitt 4.3 kurz zu sprechenkommen.

Wenn diese Normierungen auch das Leben der Systementwickler we- Nachteile

sentlich erleichtern, handelt man sich durch sie in jedem Fall Nachteileein. Es herrscht derzeit jedoch die Meinung vor, daß diese Nachteilejedenfalls solange in Kauf genommen werden konnen, als es noch wesent-lich gravierendere Schwachstellen in unseren Systemen gibt. Man solltejedoch nicht aus den Augen verlieren, daß hier noch ein Potential furkunftige Verbesserungen liegt.

3.5 Unifikation

Im vorvorletzten Abschnitt haben wir gelernt, daß zum Beweis einerFormel unter anderem eine Substitution erforderlich ist, die konnektierteTermfuße identisch macht. Im vorliegenden Abschnitt werden wir Ver-fahren zur Bestimmung einer solchen Substitution kennenlernen.

Definition 3.5.1Ein Unifikator einer Menge von Termen ist eine Substitution, die alle Unifikator

Terme der Menge identisch macht. σ heißt ein allgemeinster Unifikatoreiner Menge S von Termen, wenn fur jeden Unifikator τ von S giltτ = στ .

Fur jeden Term t ist zum Beipiel {x\t , y\fgt , z\gt} ein Unifikator von{fgx, y, fz} . Unter diesen Unifikatoren ist {y\fgx , z\gx} der einzigeallgemeinste Unifikator dieser Menge modulo Variablenumbenennung.

89


s f�

��

��

QQQQQs h s g�

��

@@@s x s x s ks y

s fQQ

QQ

Q

��

s k s zs x

q q q q q q q q q q q q

Abbildung 3.6: Die Darstellung von DIFF (f(hx, g(x, ky)), f(kx, z))

Zu jeder unifizierbaren Menge von Termen gibt es immer genau einenallgemeinsten Unifikator (immer modulo Variablenumbenennung). Die-sen zu bestimmen ist die Aufgabe eines Unifikationsalgorithmus. Einensolchen Algorithmus anzugeben ist unser nachstes Ziel. Diesem Ziel di-enen die folgenden Begriffe. Sie lassen sich am besten mit der Vorstellungder Terme als Baume veranschaulichen.

Definition 3.5.2Fur zwei beliebige Terme s, t ist deren Differenz DIFF (s, t) als MengeDifferenz

von ungeordneten Paaren induktiv wie folgt definiert.1. Ist s = t , so ist DIFF (s, t) = ∅ .2. Sind s = f(s1, . . . , sn) und t = f(t1, . . . , tn) , so ist

DIFF (s, t) = DIFF (s1, t1) ∪ . . . ∪DIFF (sn, tn) .3. In allen anderen Fallen ist DIFF (s, t) = {{s, t}} .

Zum Beispiel gilt

DIFF (f(hx, g(x, ky)), f(kx, z)) = {{hx, kx}, {g(x, ky), z}} .

Die Differenz vergleicht analoge Aste zweier Termbaume und sammelt diePaare von Untertermen, in denen sie sich unterscheiden, wie es die Abbil-dung 3.6 an unserem Beispiel illustriert. Die beste Vorstellung macht mansich von der Differenz (und dann auch von der Unifikation), indem man

90

3.5. Unifikation

in Gedanken die beiden Termbaume ubereinanderlegt, um sie dann vonoben nach unten auf Identitat zu prufen. Da dies zweidimensional schwerdarzustellen ist, verwendet unsere Darstellung die Technik der Spiegelungan der waagerechten Linie. Der Leser bilde sich die Vorstellung, den un-teren Teil des Bildes durch Faltung langs dieser Linie hochzuklappen. Dieeingerahmten, ubereinanderliegenden Kasten stellen dann genau diejeni-gen Teile dar, die nicht identisch sind und paarweise in DIFF gesammeltwerden.

Definition 3.5.3DIFF (s, t) heißt verhandlungsfahig, wenn jedes seiner Elemente ein Paar Reduktion

ist, das aus einer Variablen x und einem Term t besteht, der x nichtenthalt. In diesem Fall heißt die Substitution {x\t} eine Reduktion vonDIFF (s, t) .

Im vorangegangenen Beispiel ist DIFF (s, t) nicht verhandlungsfahig, dakeiner der Terme im Paar {hx, kx} eine Variable ist. Im folgenden Bei-spiel ergibt sich jedoch eine verhandlungsfahige Differenz.

DIFF (f(y, g(x, ky)), f(kx, z)) = {{y, kx}, {g(x, ky), z}}

Damit haben wir das Rustzeug zusammen, um den Algorithmus zur Uni- Unifikations-algorithmusfikation zweier Terme s, t in kompakter Form formulieren zu konnen.

Initialisierung Set σ = ε.Reduktion While DIFF (sσ, tσ) ist verhandlungsfahig,

do ersetze σ durch σρ,where ρ eine Reduktion von DIFF (sσ, tσ) ist.

Ergebnis If DIFF (sσ, tσ) ist leer,then {s, t} ist unifizierbar, σ ist der

allgemeinste Unifikator,else {s, t} ist nicht unifizierbar.

Dieser Algorithmus ist eines der bedeutendsten Werkzeuge der automa-tischen Deduktion. Er wurde urspunglich von J. J. Herbrand [Her30]entdeckt und von J. A. Robinson [Rob65b] erneut gefunden. Wenn auchin umstandlicher Form, so ist er dem Effekte nach auch in [Pra60] ver-wendet. Wir nennen ihn Herbrand–Robinson–Algorithmus. Wegen seinergroßen Bedeutung wollen wir ihn an einem Beispiel durchspielen.

Gegeben seien die Atome Beispiel

s = P (x, fgy, fx) und t = P (h(y, z), fz, fh(u, v)) .

Atome sind nicht Terme im eigentlichen Sinne, fur die der Algorithmusformuliert ist. Wenn man aber P als Funktionszeichen liest, so handelt

91


Nr. DIFF (sσ, tσ) σ

0 {{x, h(y, z)}, {z, gy}, {x, h(u, v)}} {}1 {{x, h(y, gy)}, {x, h(u, v)}} {z\gy}2 {{u, y}, {v, gy}} {z\gy , x\h(u, v)}3 {{v, gu}} {z\gu , x\h(u, v) , y\u}

4 {}

{

z\gu , x\h(u, gu) ,y\u , v\gu

}

Tabelle 3.1: Unifikation von P (x, fgy, fx) und P (h(y, z), fz, fh(u, v))

es sich um Terme im Sinne ihrer Definition. Wir dehnen den Begriffdes Terms also nur unwesentlich, wenn wir ihn ausnahmsweise auch aufAtome erweitern.

Die Tabelle 3.1 zeigt die gesamte Berechnung durch Angabe derWerte jeweils vor dem n-ten Durchlauf der Reduktionsschleife. So istvor dem ersten Durchlauf die Substitution leer, was zusammen mit derDifferenz, die sich aus den beiden gegebenen Termen errechnet, in dermit der Nummer 0 versehenen ersten Zeile der Tabelle angegeben ist.

Die Differenz wird nun auf Verhandlungsfahigkeit uberpruft. Zumeinen erfordert dies das Auftreten einer Variablen als Paarelement in je-dem ihrer Paare. Zum anderen darf diese Variable dann nicht in demzugeordneten Paarelement auftreten. Den Test dieser letzteren Eigen-schaft nennt man den occurs-check (deutsch Vorkommenstest). Ist beideserfullt, dann wahlt sich der Algorithmus irgendein Element aus der Dif-ferenz aus; welches Element dies ist, spielt fur das Ergebnis keine Rolle.Hier haben wir willkurlich angenommen, daß es sich um das Element{z, gy} handelt. Dieses Element wird als Substitution mit der bisheri-gen Substitution zusammengefaßt und die so errechnete Substitution aufdie Terme zur Bildung der Differenz angewandt. Das Ergebnis ist inder mit der Nummer 1 versehenen zweiten Zeile der Tabelle angegeben.Man beachte dabei, daß die Differenz nicht jedesmal vollig neu berech-net werden muß, sondern in einfacher Weise aus der vorangegangenenhervorgeht.

Das so beschriebene Verfahren wird nun so lange wie moglich wie-derholt. Im vorliegenden Beispiel geht dies genau dreimal. Wenn dieresultierende Differenz wie hier leer wird, dann laßt sich der allgemeinsteUnifikator in der letzten Zeile rechts ablesen. Wir wissen dann aus derTheorie, daß dies der einzige (modulo Variablenumbenennung) ist, denes gibt. Wenn das Verfahren abbricht, ohne daß die Differenz leer wird,

92

3.5. Unifikation

dann sind die Ausgangsterme nicht unifizierbar. Das Verfahren ist alsoein Entscheidungsverfahren.

Mochte man mehr als zwei Terme unifizieren, so laßt sich dies mitdem eben besprochenen Algorithmus zB. dadurch bewerkstelligen, daßman zunachst zwei der Terme unifiziert, den hieraus resultierenden Unifi-kator auf ein weiteres Paar bestehend aus einem dieser vorher unifiziertenTerme und einem weiteren Term aus der gegebenen Menge anwendet unddas Paar unifiziert usw. Der Gesamtunifikator ergibt sich dann als dieKomposition aller einzelnen Unifikatoren.

Zur Beurteilung der Effizienz des Herbrand–Robinson–Algorithmus Effizienz

fur die Praxis muß man sich folgende Gesichtspunkte vor Augen hal-ten. Der Algorithmus verwendet eine denkbar einfache Datenstrukturzur Reprasentation der zu unifizierenden Terme, was sich auch gunstigauf die Laufzeit auswirkt. Weiter wurde in [ACFZ91] gezeigt, daß dieunifizierbaren Termpaare eine vernachlassigbare Minderheit unter allenTermpaaren bildet. Bei Effizienzvergleichen darf man sich daher nicht aufunifizierbare Terme beschranken. Berucksichtigt man dies, so erweist sichder Herbrand–Robinson Algorithmus tatsachlich als der bestmogliche, daer im Mittel nur eine konstante Zahl von Schritten benotigt [ACFZ91].Andererseits gibt es Termpaare, deren Unifikation einen exponentiel-len Aufwand mit diesem Algorithmus erfordert. Ein solches Paar istf(x1, . . . , xn) , f(g(x0, x0), g(x1, x1), . . . , g(xn−1, xn−1)) . Da solche “pa-thologischen” Falle in der Praxis kaum auftreten, nimmt man diesenNachteil oft in Kauf ungeachtet der Tatsache, daß es weitere Unifika-tionsalgorithmen gibt, deren Komplexitatsverhalten im schlechtesten Fallwesentlich besser ist. Von ihnen soll im folgenden noch die Rede sein.

Die Unifikation laßt sich auch als Gleichheitsproblem auffassen, in Martelli-Montanari-Unifikation

dem es darum geht, eine Losung der Gleichung s.=t zu finden. In dieser

Form haben Martelli und Montanari [MM82] das Problem analysiert undeinen Algorithmus angegeben, dessen Komplexitat (fast) linear ist. Beiihm spielen im Grunde die gleichen Operationen wie oben eine Rolle. DieDifferenzbildung wird durch die Operationen “Termdekomposition” und“Entfernung trivialer Gleichungen” bewerkstelligt, die Reduktion heißt“Variablenelimination”. Wir geben diese Umformungsregeln hier kurzan.

Termdekomposition{f(s1, . . . , sn)

.=f(t1, . . . , tn)} ∪E ; {s1

.=t1, . . . , sn

.=tn} ∪E .

Entfernung trivialer Gleichungen{x

.=x} ∪E ; E .

Umstellung{t.=x} ∪E ; {x

.=t} ∪E , wenn t keine Variable ist.

93


Variablenelimination{x

.=t} ∪E ; E{x\t} , wenn x 6∈ t und x ∈ E .

Am Anfang besteht die Gleichungsmenge lediglich aus {s.=t} . Werden

dann die Regeln solange wie moglich angewendet, dann entsteht schließ-lich im Falle der Unifizierbarkeit der allgemeinste Unifikator in Form einerGleichungsmenge {x1

.=t1, . . . , xk

.=tk} . Unsere Darstellung ist insofern

vereinfachend, als sogenannte Multigleichungen erlaubt werden. Hier-bei kann jede Seite einer Gleichung mehr als ein Element enthalten. Soreprasentiert zum Beispiel {u, v, w}

.=hxy drei Gleichungen gleichzeitig

in kompakter Form. In dieser Datenstruktur liegt der Schlussel fur dasgute Komplexitatsverhalten dieses Verfahrens. Fur weitere Details siehezB. Abschnitt 3.4.1 in [Hol89].

Die Wahl der Datenstruktur ist auch der Grund fur das linearePaterson-Wegman-Verfahren

Verhalten eines Algorithmus von Paterson und Wegman [PW78]. Undzwar werden hier Terme nicht als Baume, sondern als gaGs (gerichtet,azyklische Graphen) reprasentiert, wie wir es im Abschnitt 3.1 bereitsillustriert haben. Die fur die Unifikation notwendigen Manipulationenerfordern hierzu bei der Implementierung jedoch einen ziemlichen Auf-wand, der sich in der Praxis nicht zu lohnen scheint. Jedenfalls ist dieserAlgorithmus in implementierten Systemen selten realisiert.

Ein weiterer, quasi-linearer Algorithmus ist von Huet in [Hue87] an-WeitereAlgorithmen gegeben worden. Robinson selbst hat Verbesserungen seines ursprungli-

chen Algorithmus in [Rob71] angegeben. Auch in [CB83] findet sich einequadratische Variante des Herbrand–Robinson–Algorithmus, der auch furImplementierungen gut handhabbar zu sein scheint.

3.6 Varianten von Deduktionsverfahren

Mit der im letzten Abschnitt behandelten Unifikation steht uns nundas entscheidende Werkzeug zur Verfugung, um die im letzten Kapitelbesprochenen Verfahren von der Aussagenlogik in die Pradikatenlogik zuliften. Wir beginnen wie dort mit dem denkbar einfachsten Verfahren aufder bisher erarbeiteten Grundlage.

3.6.1 Das Extensionsverfahren

Im Abschnitt 2.6.1 haben wir das Extensionsverfahren fur die Aus-Extensions-verfahren sagenlogik besprochen. Fur das Verstandnis des folgenden wird voraus-

gesetzt, daß dem Leser die Details des Verfahrens vertraut sind. Seinepradikatenlogische Form unterscheidet sich davon lediglich dadurch, daßzusatzlich eine Substitution in der folgenden Weise in Betracht zu ziehen

94

3.6. Varianten von Deduktionsverfahren

ist. Zur Illustration verwenden wir das Beispiel, mit dem wir die Diskus-sion im Abschnitt 2.1 eingeleitet haben. Seine durch das im Abschnitt 3.4beschriebene Verfahren erhaltene Matrixform lautet wie folgt.

Hc

¬Hx

Sx

¬Sx

Ax

¬Ac

↑

{} `

Wie fruher haben wir die Startklausel mit einem senkrechten Pfeil mar-kiert. Sie ist so gewahlt, daß sie die letzlich behauptete Aussage, also dasZielliteral enthalt. Die nun mitzufuhrende Substitution wird mit ε (bzw.{}) initialisiert und ist hier und im folgenden bei der Matrix mitangege-ben.

Zur Durchfuhrung eines Extensionsschrittes wahlen wir aus der Extensions-schrittStartklausel ein Literal sowie eine Konnektion aus, die dieses Literal

enthalt. Das Beispiel ist so einfach, daß es hier keine Wahl gibt, so daßder Extensionsschritt eindeutig zu folgender Situation fuhrt.

Hc

¬Hx .

Sx

¬Sx

Ax

¬Ac

↑↗

{x\c} `

Vor der erfolgreichen Durchfuhrung eines solchen Extensionsschrittes muß Unifikation

aber hier nun noch gepruft werden, ob die Atome der beiden konnek-tierten Literale nach Anwendung der bisherigen Substitution unifizier-bar sind. Im vorliegenden Fall muß also der Unifikationsalgorithmus aufdas Paar {Hc ε,Hx ε} angewandt werden. Das Ergebnis ist die bei derMatrix wiederum angegebene Substitution ε {x\c} = {x\c} . Die bi-sherige Substitution wird also mit der durch die Unifikation zusatzlichgewonnenen Substitution durch Komposition vereinigt, was die aktuelleGesamtsubstitution ergibt.

Damit sollte das Verfahren soweit bereits klar sein. Seine weitereAnwendung auf unser Beispiel fuhrt noch zu zwei weiteren Extensions-schritten. Eine Unifikation ist dabei nicht mehr erforderlich, da sichdie Differenzmenge der jeweiligen Terme nach Anwendung der aktuel-len Substitution als leer erweist. Der abschließende Bereinigungsschrittvervollstandigt den erfolgreichen Beweis, dessen Rest in Abbildung 3.7dargestellt ist.

Wir erinnern daran, daß sich die Matrix selbst wahrend der Durch-fuhrung der einzelnen Schritte uberhaupt nicht andert, so daß de factodie in der Abbildung dargestellten mehrfachen Kopien der Matrix nicht

95


Hc

¬Hx.

Sx

¬Sx.

Ax

¬Ac

↑

↗

{x\c} `

Hc

¬Hx.

Sx

¬Sx.

Ax

¬Ac.

↑

{x\c} `

Hc

¬Hx

Sx

¬Sx

Ax

¬Ac

↑

{x\c}

Abbildung 3.7: Restliche Schritte des Extensionsbeweises

wirklich erzeugt und dargestellt werden mussen. Auch die Konnektio-nen sind nur der Anschaulichkeit halber im Bild belassen und mussenvom Verfahren nicht weiter gespeichert werden. Beides dient nur derVeranschaulichung fur den Leser. Vielmehr sind die Markierungen unddie Substitution das einzige, was fur die Durchfuhrung des Verfahrenswirklich gespeichert werden muß.

Die gleichen Bemerkungen treffen auf die Verwendung der Matrix-Darstellungs-varianten darstellung, ja auch der Normalform zu. Die beiden dem Verfahren zu-

grundeliegenden Merkmale, namlich zum einen die Auswahl einer Kon-nektion zur Erledigung einer davon aufgespannten Pfadmenge und zumanderen die Auswahl eines benachbarten Teilziels, lassen sich fur jede For-meldarstellung analog definieren; nur die Anschaulichkeit mag in anderenDarstellungen verloren gehen, ein Gesichtspunkt, dessen Bedeutung auchfur die Systementwicklung jedoch nicht zu unterschatzen ist.

Wir sehen also, daß sich das Extensionsverfahren fur die Aussa-Klauselkopien

genlogik in einfachster Weise auf die Pradikatenlogik liften laßt. Hinzutreten zunachst lediglich die mit der Unifikation zusammenhangendenOperationen. Diese bestehen zum einen aus dem Unifikationstest beijeder betrachteten Konnektion und zum anderen aus der Kompositionund Mitfuhrung der so sich jeweils ergebenden Substitution. Als weitereKomplikation ergibt sich aus der in Abschnitt 3.3 besprochenen Not-

96


¬Pc ¬Pfx1

Px1

¬Pfx2

Px2

Pffy

↑

{} `

¬Pc ¬Pfx1

Px1.

¬Pfx2

Px2

Pffy

↑

↗ {x1\c} `

¬Pc ¬Pfx1

Px1.

¬Pfx2

Px2.

P ffy

↑

↗ {x1\c, x2\fc} `

¬Pc ¬Pfx1

Px1.

¬Pfx2

Px2.

P ffy.

↑

{x1\c, x2\fc, y\c}

Abbildung 3.8: Eine Ableitung mit zwei Klauselinstanzen

wendigkeit der Berucksichtigung mehrerer Instanzen von Klauseln eineErweiterung des Suchraumes. Wahrend in der Aussagenlogik immer nurdie verbleibenden Klauseln fur eine Extension in Frage kommen, gilt dieseBeschrankung in der Pradikatenlogik aus dem genannten Grunde nichtmehr. Dabei sind die Variablen in mehrfach verwendeten Klauseln alsverschieden anzusehen. Diese Komplikation ist an dem bereits in Absch-nitt 3.3 verwendeten Beispiel in Abbildung 3.8 in der gleichen Weise wieim vorangegangenen Beispiel illustriert (nur zeigen wir zur Abwechslungeinen Beweis, der die Aufwartsstrategie benutzt, also mit dem Faktumstartet und beim Zielliteral endet). Das Beispiel demonstriert, daß auchdiese Komplikation mehrfacher Instanzen das aussagenlogische Verfahrenin seiner Struktur unberuhrt laßt. Auch fur diese Komplikation treffendie vorangegangenen Bemerkungen hinsichtlich der Darstellung zu. Siesind hier auch auf die mehrfache Darstellung von Klauseln in verschiede-nen Kopien zu beziehen, was wiederum nur der Anschaulichkeit halber

97


erfolgt und fur die Kodierung des Verfahrens aus den bereits genanntenGrunden nicht erforderlich ist.

Zum Abschluß der Beschreibung des gelifteten ExtensionsverfahrensRucksetzungen

weisen wir darauf hin, daß bei gegebenenfalls erforderlichen Rucksetzun-gen immer auf der Substitution des Rucksetzpunktes (und nicht auf derinsgesamt erreichten Substitution) aufgebaut wird. Mit anderen Worten,alle sich aus einer Sackgasse im Suchprozess ergebenden Substitutionenwerden naturlich im weiteren Verlauf als wertlos ignoriert.

Bei der Transformation zur Normalform einer gegebenen FormelPROLOG

kann man erreichen, daß verschiedene Klauseln keine Varablen gemein-sam haben. Ist dies der Fall, so laßt sich die Propagierung der Sub-stitutionen vereinfachen. Jede aus einer Konnektion resultierende Sub-stitution ist dann lediglich lokal auf die beiden konnektierten Klauselnanzuwenden und kann so Schritt fur Schritt etwas einfacher propagiertwerden. In dieser Form findet das Extensionsverfahren seine Anwendungin vielen Systemen, die die Programmiersprache PROLOG realisieren.Da man in einer solchen Programmiersprache aber nicht nur an einemja/nein–Beweis, sondern auch an Ergebnissen des Berechnungsprozessesinteressiert ist, muß die Komposition der sich ergebenden Substitutionenzumindest fur alle Zielklauselvariablen doch durchgefuhrt werden. DerEinheitlichkeit halber haben wir das Verfahren daher gleich in der allge-meineren Form besprochen.

Es mag manche Leser uberraschen, daß wir soeben PROLOG alsauf dem Extensionsverfahren basierend beschrieben haben. In der Tatist dies das sinnvollste und einfachste Verstandnis des PROLOG zugrun-deliegenden Beweismechanismus. Auf der Hornklausellogik fallt jedochdas Extensionsverfahren in seiner Wirkung mit einer Variante der linea-ren Resolution zusammen, wie wir bereits im Abschnitt 2.6.4 festgestellthaben. Wegen der Popularitat von Resolution wird daher der Beweisme-chanismus von PROLOG meist als eine Form der Resolution dargestellt.Da dies das Verstandnis von PROLOG unnotigerweise erschwert — spieltdoch der komplizierte Mechanismus der Resolution hier uberhaupt keineRolle — sind wir hier nicht dieser Mode gefolgt, sondern haben die durch-sichtigste Form der Darstellung zu geben versucht.

3.6.2 Resolution und Varianten

Das soeben beschriebene Liften des Extensionsverfahrens hat unsLiften

die beiden zusatzlichen Erfordernisse klargemacht: die Unifikation unddie Berucksichtigung mehrfacher Kopien von Klauseln. Beides hat diestrukturellen Merkmale des aussagenlogischen Extensionsverfahrens defacto nicht beeinflußt. Es sollte nach dieser Erfahrung daher den Le-

98


ser nicht uberraschen, wenn wir nun pauschal feststellen, daß sich alleim letzten Kapitel beschriebenen aussagenlogischen Verfahren in volliganaloger Weise liften lassen.

Diese Aussage gilt zB. in offensichtlicher Weise fur das in Abschnitt AllgemeinesExtensions-verfahren

2.7.1 beschriebene allgemeine Extensionsverfahren. Die dort zusatzlichbetrachteten, aus Konnektionen gebildeten Schleifen bedingen lediglich,daß auch bei der Berucksichtigung solcher Konnektionen der Unifikation-salgorithmus eingesetzt und die resultierenden Substitutionen integriertwerden mussen. Weder an dem aussagenlogischen Verfahren noch ander Operation des Liftens andert sich hierdurch irgendetwas Bemerkens-wertes. Da das gleiche fur alle besprochenen Verfahren gilt, wollen wiruns hier nur noch auf die folgenden Bemerkungen beschranken.

Beim Liften des in Abbildung 2.10 dargestellten Verfahrens CP 01

geht die Konfluenz verloren, so daß Rucksetzpunkte eingebaut werdenmussen.

Das im Abschnitt 2.6.2 besprochene Tableau–Verfahren hat aus den Tableau–Verfahrendort erwahnten Grunden fur die Automatisierung keine große Bedeutung

erlangt. Deshalb ist die Einbeziehung der Unifikation erst in jungsterZeit in [Ede91] zu Zwecken von Komplexitatsvergleichen erfolgt.

Wie mehrfach erwahnt, ist unter den im letzten Kapitel besproche- Resolution

nen Verfahren die Resolution das in Systemen am haufigsten verwendete.Wenn sich das Liften auch hierfur in der besprochenen Weise vollzieht, sosei doch auf die folgende Besonderheit hingewiesen, die wir schon im letz-ten Unterabschnitt kurz angesprochen haben. Resolution setzt voraus,daß Klauseln paarweise verschiedene Variablen enthalten. Damit diesauch fur Resolventen zutrifft, werden die Variablen in den Elternklauselneines Resolutionsschlusses vor Durchfuhrung des Schlusses umbenannt.So entsteht der Schluß

{Pxy,Qxy}, {¬Pcfz} ` {Qcfz ′}

dadurch, daß x, y, z zu neuen Variablen x′, y′, z′ umbenannt werden,dann der allgemeinste Unifikator {x′\c, y′\fz′} gebildet, auf die modi-fizierten Elternklauseln angewandt und schließlich die Resolvente wie inder Aussagenlogik gebildet wird. Wie bereits erwahnt, fuhrt dieses Vor-gehen zu einer volligen Lokalisierung der Substitutionsbehandlung, es seidenn, man mochte fur gewisse Antwortvariablen den resultierenden Termals Ergebnis des Beweisprozesses produzieren.

Diese soeben besprochene Besonderheit ist nicht wirklich charakte-ristisch fur die Resolution. Nicht nur ließe sich die Resolution mit einerglobalen Substitution wie beim Extensionsverfahren einfuhren, sondernman konnte auch die Varianten des Extensionsverfahrens in der von der

99


Resolution her bekannten Weise behandeln. Es handelt sich vielmehrum reine Gepflogenheiten, derer man sich je nach Bedarf bedienen kann.Die lokale Behandlung ist technisch einfacher, die globale konzeptuelldurchsichtiger im Hinblick auf den Beweisprozeß als Ganzes und auf dieVerallgemeinerung auf die Nicht-Normalform.

3.6.3 Reduktionen

Im Abschnitt 2.7.3 haben wir eine Reihe von Reduktionsregeln ken-Liften vonReduktionen nengelernt. Auch sie lassen sich in der hier besprochenen Weise liften.

Dabei tritt die Unifikation gegebenenfalls auch in anderem Zusammen-hang als dem von Konnektionen in Erscheinung. Betrachten wir zB. dieReduktion, die wir mit MULT bezeichnet haben. Ubertragen auf diePradikatenlogik besagt sie, daß ein mehrfaches Auftreten des gleichenLiterals in einer Klausel zu einem einfachen Auftreten reduziert werdenkann. Beim Vorliegen einer globalen Substitution {x\c, y\c} hieße dasfur die Klausel {Pcx, Pyc} , daß sie durch MULT zu {Pcc} reduziertwird.

Es tritt naturlicherweise die Frage auf, ob man MULT nicht so ve-MULT-Reduktion rallgemeinern kann, daß die gleiche Reduktion auch ohne das Vorliegen

besagter Substitution moglich ist. Wie beim Bilden von Konnektionenwurde die Substitution sich erst durch Unifikation ergeben. In der Tatist die so verallgemeinerte MULT–Reduktion gleichfalls eine Reduktionin dem in 2.7.3 prazisierten Sinne. Wenn die reduzierte Matrix beweisbarist, so auch die Ausgangsmatrix.

Es kann aber umgekehrt sein, daß die Ausgangsmatrix beweisbar,die reduzierte Matrix jedoch nicht beweisbar ist. Als Beispiel erweiternwir die eben betrachtete Klausel in der folgenden Weise zu einer Matrix.

{{Pcx, Pyc}, {¬Pcd}, {¬Pdc}}

Die beiden erkennbaren Konnektionen sind unifizierbar und spannen dieMatrix auf, also ist sie gultig. Wurde man aber vor Betrachtung derKonnektionen auf die erste Klausel eine in dem genannten Sinne verall-gemeinerte MULT–Reduktion anwenden, so ergabe sich die unbeweisbareMatrix

{{Pcc}, {¬Pcd}, {¬Pdc}}

Daraus ergibt sich die folgende Konsequenz fur Beweissysteme. Erlaubtman die Anwendung der verallgemeinerten MULT–Reduktion und fuhrtdiese zu einer nichtleeren Substitution, so muß an dieser Stelle im Ver-fahren ein Rucksetzpunkt gesetzt werden. Bei Mißlingen der Beweissuche

100


muß dann von diesem Punkt aus eine alternative Beweisrichtung einges-chlagen werden, genauso wie das auch bei alternativen Konnektionen mitder bekannten Rucksetztechnik geschieht.

Was hier anhand der MULT–Reduktion ausgefuhrt wurde, gilt ingleicher Weise fur alle in 2.7.3 besprochenen Reduktionen.

Diese Ausfuhrungen im Zusammenhang mit der MULT–Reduktion Faktorisierung

haben in Form der Faktorisierung eine große Bedeutung fur die Reso-lution, die manchmal sogar mit in den Resolutionsprozeß eingebaut ist.Andererseits sind bei der Resolution zusatzliche Reduktionen in Betrachtzu ziehen. Der Grund liegt in der Generierung von redundantem Mate-rial in diesem Verfahren. Jede Resolvente enthalt ja offensichtlich redun-dante Information, da ihre Literale bis auf die Substitution bereits in denElternklauseln enthalten sind. In manchen Fallen kann man erkennen,welche der Klauseln uberflussig geworden sind, so daß eine entsprechendeReduktion anzuwenden ist. Dies ist ein beachtenswerter Nachteil vonresolutionsartigen Verfahren, dessen Behebung einen enormen Aufwanderfordert [SA90]. Unabhangig davon sind die dynamischen Reduktionenvon Bedeutung, von denen wir in 2.7.3 auch im Zusammenhang von Kon-nektionsverfahren gesprochen haben.

In [Egl91] ist die MULT–Reduktion auf Falle verallgemeinert wor- Lemmabildung

den, in denen zwei nicht unifizierbare Literale mit dem gleichen Pradi-katszeichen zu einem einzigen Literal so verallgemeinert werden, daß derBeweis dieses Literals, wenn er existiert, den der der beiden Ausgangslite-rale impliziert (aber nicht notwendig umgekehrt). Es handelt sich damitum eine Form der Lemmabildung. Mit dieser unvollstandigen Reduk-tionsregel lassen sich Beweise mit exponentieller Lange auf solche linea-rer Lange reduzieren, so daß es sich offenbar um eine essentielle Technikhandelt.

3.6.4 CLIN

Die bisher besprochenen Deduktionsverfahren fur die Pradikatenlo- Klausel-verkettunggik haben ihren Ursprung alle in einem entsprechenden Verfahren fur die

Aussagenlogik. Erst in allerjungster Zeit ist in [LP91] ein Verfahren mitdem Namen “hyper-linking strategy” und ein darauf basierendes SystemCLIN (clause linking (deutsch Klauselverkettung)) entwickelt worden, dasnicht nach diesem Muster vorgeht. Da es sich hierbei um eine aussichts-reiche Idee handelt, wollen wir dieses Verfahren abschließend noch kurzskizzieren.

Zur Illustration verwenden wir wieder das Beispiel, das uns schon Verfahren

aus Abschnitt 3.3 und Abbildung 3.8 bekannt ist. In seiner allgemeinstenForm hat es bei irgendeinem gegebenen n im Aufrufterm die folgende

101


Gestalt.

Pfny

¬Pfx

Px

¬Pa

1

2

3

4

Zur Unterscheidung haben wir seine vier Konnektionen durchnumeriert.CLIN wiederholt die folgenden drei Schritte so oft, bis sich der Beweis ineiner Instanz des dritten Schrittes ergibt.

1. Generiere neue Klauselinstanzen wie nachfolgend beschrieben undfuge sie zu der bisherigen Klauselmenge.

2. Zur Durchfuhrung von Schritt 3 mache eine Kopie der jetzigenKlauselmenge und ersetze darin jede Variable durch eine (einzige)neue Konstante.

3. Teste die aussagenlogische Formel aus Schritt 2 auf Tautologie. ImErfolgsfalle ist die Ausgangsformel gultig; andernfalls fahre fort beiSchritt 1.

Schritt 1 erzeugt im ersten Durchlauf die gegebene Klauselmenge. SchrittBeispiel

2 liefert die folgende aussagenlogische Matrix, die sich in Schritt 3 alsnicht-tautologisch erweist.

Pfnc

¬Pfc

Pc

¬Pa

1

2

3

4

Ware n = 0 und stunde in der Ausgangsmatrix a anstelle von y , sohatte sich ein erfolgreicher Abschluß vermoge der Konnektion 4 schon andieser Stelle ergeben. Andernfalls kommen wir nun zum zweiten Itera-tionsschritt.

Die in Schritt 1 erwahnte Klauselgenerierung geschieht in der folgen-den Weise. Zu jeder in der bisherigen Klauselmenge auftretenden KlauselC wahlen wir zu jedem seiner Literale je eine Konnektion, so daß allegewahlten Konnektionen einen gemeinsamen allgemeinsten Unifikator σ

haben. Die Klausel Cσ gehort zu denjenigen Klauseln, mit denen diebisherige Klauselmenge am Ende des Schrittes 1 zur neuen Klauselmengeerweitert wird. In gleicher Weise wird eine neue Klauselinstanz zu jederanderen derartigen Konnektionenmenge generiert. Durch Variablenum-benennung laßt sich erreichen, daß Klauseln in der neuen Klauselmengepaarweise verschiedene Variablen enthalten. Offensichtlich fuhrt diesesVerfahren fur Klauseln ohne Variablen zu keinen neuen Instanzen, so daßsie dabei von vorneherein ignoriert werden konnen.

102


In unserem Beispiel sind daher im zweiten Iterationsschritt zweiKlauseln nach diesem Verfahren zu behandeln. Betrachten wir zunachstdie Klausel Pfny . Ist n = 0 , so gibt es zwei derartige Konnektionenmen-gen, die in diesem Fall einer Einerklausel je aus einer einzigen Konnektionbestehen. Dementsprechend erhalten wir auch zwei neue Klauselinstan-zen, namlich Pa (mit der Konnektion 1) und Pfx′ (mit Konnektion 2).Im Falle n > 0 ist lediglich die letztere der beiden Konnektionen unifi-zierbar mit Pfnx′ als neuer Instanz. In analoger Weise ergeben sich ausder zweiten Klausel {¬Pfx, Px} die neuen Instanzen

• {¬Pfny′, P fn−1y′} mit den Konnektionen 2 und 3, hier jedoch nurim Fall n > 1 ,

• {¬Pfa, Pa} mit den Konnektionen 2 und 4, hier jedoch nur imFall n = 1 ,

• {¬Pffx′′, P fx′′} mit den Konnektionen 3 und 3, und• {¬Pfa, Pa} mit den Konnektionen 3 und 4.

All diese neuen Instanzen werden nun zu den ursprunglichen drei Klau-seln hinzugefugt und alle auftretenden Variablen durch die neue Kons-tante c ersetzt. Auf das entstehende aussagenlogische Problem wird ir-gendeines der in Kapitel 2 besprochenen Tautologieverfahren angewandt.In den Fallen n = 0, 1 fuhrt es offenbar bereits innerhalb dieses Itera-tionsschrittes zum Erfolg. In den Fallen n = 2, 3 ist der zweite Itera-tionsschritt erfolgreich, in den Fallen n = 4, . . . , 7 der dritte, dann inn = 8, . . . , 15 der vierte usf.

Die Grundidee dieses Verfahrens besteht darin, den Unifikationsteil Grundidee

(Schritt 1) vorweg und unabhangig vom aussagenlogischen Teil (Schritte 2und 3) durchzufuhren. Schritt 1 erweist sich ubrigens als ein Spezialfallder Konsolution des Abschnitts 2.6.3 und ist auf diesem Wege als korrekteinzusehen. In ihm werden alle moglichen Konnektionen in Betracht ge-zogen und die daraus resultierende Substitution berechnet. Ob sich unterihnen eine aufspannende Menge befindet, wird dann nach der moglichenVereinfachung des Schrittes 2 in Schritt 3 getestet.

Dieses Vorgehen ermoglicht zum einen den Einsatz eines schnellen Bewertung

aussagenlogischen Verfahrens, das insbesondere die Vorteile der Fakto-risierung des Abschnittes 2.7.3 voll ausschopft (was ohne die Reduktionauf die Aussagenlogik auf die im vorangegangenen Unterabschnitt bes-prochenen Probleme fuhren wurde). In [LP91] wird hierzu das im Ab-schnitt 2.7.4 erlauterte Davis–Putnam–Verfahren herangezogen, das sichin diesem Sinne vorteilhaft verhalt. Im Abschnitt 2.7.3 sind aber nochweitere Verfahren angegeben, die sich in diesem Sinne mindestens genau-sogut, wenn nicht sogar besser verhalten wurden.

Ein weiterer Vorteil ist durch unser Beispiel illustriert. Bei ihm

103


wachst die Anzahl der in jedem Iterationsschritt erfolgreichen Falle inexponentieller Weise an, die zB. mit dem Extensionsverfahren alle schritt-weise durchgespielt werden mußten. Letzteres ist also in diesem Beispielexponentiell schlechter bezuglich der Anzahl der erforderlichen Schritte.Der gleiche Vorteil ist jedoch auch im Rahmen der Konnektionsmethodemit dem im Abschnitt 4.3 besprochenen Konnektionsstrukturkalkul er-reicht worden.

Schließlich verknupft CLIN eine Abwarts– zugleich mit einer Auf-wartsstrategie, da alle Konnektionen einer jeden Klausel in Betracht ge-zogen werden. Damit nimmt es eine Verbesserung vorweg, die wir imRahmen der Konnektionsmethode in Abschnitt 4.4.2 behandeln werden.

Das Attraktive an diesem Verfahren ist, daß all diese Vorteile in ei-ner relativ einfachen Weise erzielt werden. Der Preis fur diese Einfachheitist jedoch eine exzessive Generierung einer Unmenge neuer Klauseln (inunserem Beispiel sind es n Stuck), die bei den zum Vergleich genann-ten Verbesserungen auf der Grundlage der Konnektionsmethode nicht indieser Weise auftritt.

104

Documents

3. Deduktion in der Pr adik atenlogik...3. Deduktion in der Pr adik atenlogik Wie wir am Beginn des vorangegangenen Kapitels zu erkl ar en ver-suchten, ist es zum Verst andnis der