Quelltext der Seite Resolution (Logik)

Die '''Resolution''' ist ein Verfahren der [[Formale Logik|formalen Logik]], um eine logische [[Formel]] auf Gültigkeit zu testen.

Das Resolutionsverfahren, auch Resolutionskalkül genannt, ist ein [[Reductio ad absurdum|Widerlegungsverfahren]]: Statt direkt die [[Tautologie (Logik)|Allgemeingültigkeit]] einer Formel zu zeigen, leitet es einen logischen Widerspruch aus deren Verneinung ab.

Diese Herleitung geschieht mittels eines [[Algorithmus]] auf rein formalem Weg und kann deshalb von einem Computerprogramm durchgeführt werden. Die Resolution ist eine der bekanntesten Techniken des [[Maschinengestütztes Beweisen|Maschinengestützten Beweisens]].

== Das Resolutionsverfahren in der Aussagenlogik ==

=== Resolvente (auch: Resolvent) ===

Seien <math>C_1</math>, <math>C_2</math> [[Disjunktionsterm|Klauseln]] einer [[Aussagenlogik|aussagenlogischen]] Formel, die in [[Konjunktive Normalform|konjunktiver Normalform]] vorliegt. Gibt es ein [[Literal]] <math>L</math>, welches in <math>C_1</math> positiv und in <math>C_2</math> negativ vorkommt, ist die Vereinigung beider Klauseln ohne das positive und negative Literal <math>L</math> eine Resolvente (auch: der Resolvent) <math>C_R</math>. Das heißt insbesondere: Gibt es '''kein''' komplementäres Literal, so gibt es auch keine Resolvente.

:<math>L \in C_1</math>
:<math>\overline{L} \in C_2</math>

<math>C_R = (C_1 \setminus\{L\}) \cup (C_2 \setminus \{\overline{L}\})</math>

Es darf immer nur '''genau ein''' Literal resolviert werden. Je nach Ausgangsklauseln ist die Bildung verschiedener Resolventen möglich.

Anders notiert: Aus
: <math>(A_1 \vee A_2 \vee \dots \vee A_n) \wedge (B_1 \vee B_2 \vee \dots \vee B_m \vee \neg A_1)</math>
wird auf die Resolvente
: <math>A_2 \vee \dots \vee A_n \vee B_1 \vee \dots \vee B_m</math>
geschlossen.

Die Resolvente ist ''nicht äquivalent'' zu den Ausgangsklauseln. Die Bedeutung der Resolvente liegt vielmehr darin, dass die Ausgangsklauseln nur dann ''beide gleichzeitig erfüllbar'' sind, wenn auch die Resolvente erfüllbar ist ([[notwendige Bedingung]]). Gelingt es, die leere Klausel zu resolvieren, die stets unerfüllbar ist, ist somit die Unerfüllbarkeit der gesamten Formel gezeigt.

=== Beweis ===

Da die Resolvente <math> C_R </math> eine [[notwendige Bedingung]] für die Ausgangsklauseln <math> C_1 </math> und <math> C_2 </math> ist, gilt
: <math> (C_1 \wedge C_2) \rightarrow C_R </math>.
Man sagt <math> C_R </math> folgt aus <math> C_1 </math> und <math> C_2 </math>. Hieraus folgt der Beweis zur Korrektheit der Resolution:
: <math>\begin{align} & [(A_1 \vee A_2 \vee \dots \vee A_n) \wedge (B_1 \vee B_2 \vee \dots \vee B_m \vee \neg A_1)] \rightarrow (A_2 \vee A_3 \vee \dots \vee A_n \vee B_1 \vee B_2 \vee \dots \vee B_m)\\
&\equiv \neg [(A_1 \vee A_2 \vee \dots \vee A_n) \wedge (B_1 \vee B_2 \vee \dots \vee B_m \vee \neg A_1)] \vee (A_2 \vee A_3 \vee \dots \vee A_n \vee B_1 \vee B_2 \vee \dots \vee B_m)\\
&\equiv  (\neg A_1 \wedge \neg A_2 \wedge \dots \wedge \neg A_n) \vee (\neg B_1 \wedge \neg B_2 \wedge \dots \wedge \neg B_m \wedge A_1) \vee (A_2 \vee A_3 \vee \dots \vee A_n) \vee (B_1 \vee B_2 \vee \dots \vee B_m)\\
&\equiv (\neg A_1 \vee A_2 \vee A_3 \vee \dots \vee A_n) \vee (A_1 \vee B_1 \vee B_2 \vee \dots \vee B_m)\\
&\equiv \neg A_1 \vee A_1\\
&\equiv 1
\end{align}</math>

=== Res-Operator ===

Das Ausführen eines einzelnen Resolutionsschrittes wird mit dem Res-Operator notiert:
:<math>\operatorname{Res}(F) = F \cup \{R\}</math>, wobei <math>R</math> eine Resolvente zweier Klauseln aus <math>F</math> ist

Mit <math>\operatorname{Res}^\star(F) = \bigcup_{n \in \mathbb{N}} \operatorname{Res}^n(F)</math> bezeichnet man die Vereinigung aller möglichen Resolutionsschritte auf <math>F</math>.

Somit sind folgende Aussagen möglich:
# ist die leere Klausel Element von <math>\operatorname{Res}^\star(F)</math>, ist <math>F</math> unerfüllbar und
# ist die leere Klausel Element von <math>\operatorname{Res}^\star(\neg F)</math>, ist <math>F</math> eine [[Tautologie (Logik)|Tautologie]]

== Resolution und Prädikatenlogik ==

=== Problemstellung ===

Für interessantere Problemstellungen ist das Instrumentarium der Aussagenlogik nicht ausreichend. Das Prinzip der Resolution sollte von der einfachen Aussagenlogik auf die [[Prädikatenlogik]] erster Stufe ausgeweitet werden können. Neben logischen Literalen sind dabei zu berücksichtigen:

* ''[[Variable (Logik)|Variablen]]'' (beispielsweise Zahlenvariablen), üblicherweise mit Symbolen wie <math>x</math> und <math>y</math> bezeichnet
* die ''[[Quantor]]en'' <math>\exists</math> (''der Existenzquantor'') und <math>\forall</math> (''der Allquantor''),
* ''[[Konstante (Logik)|Konstanten]]'', beispielsweise <math>0, 1, \pi \,</math>
* ein- und mehrwertige ''[[Funktion (Mathematik)|Funktionen]]'', üblicherweise mit Symbolen wie <math>f(x)</math> oder <math>g(x,y)</math> bezeichnet.

Ein durchaus typisches Beispiel für eine prädikatenlogische Aussage ist:

{|cellpadding="15"
|-valign="top"
|'''1)'''
|<math>\forall x \exists y \forall z K(g(a,z),y) \implies K(g(f(a),f(z)),x) </math>
|}

(Anmerkung: Setzen wir <math> g(t, u) = \vert t-u \vert \,</math> und <math> K(v, w) \equiv (v<w) \,</math>, so liefert uns die obige Formel die formal-logische Definition der [[Stetige Funktion|Stetigkeit]] der Funktion <math> f \,</math> im Punkt <math> a \,</math>.)

Damit auf solche Aussagen die Resolution angewendet werden kann, müssen sie umgeformt und das oben beschriebene Verfahren erweitert werden.

=== Normalisierung ===

Die ersten Schritte bestehen darin, die zu widerlegende Aussage in eine Form zu bringen, die der konjunktiven Normalform der Aussagenlogik ähnelt.

# Man bringt die zu widerlegende Formel in die [[Pränexform]]. Nach dieser Umformung stehen die Quantoren alle am Anfang der Formel, und der Rest der Formel hat die Gestalt einer konjunktiven Normalform.
# Durch die Anwendung von ''Skolemfunktionen'' eliminiert man alle Existenzquantoren <math>\exists</math> aus der Formel und bringt sie in die [[Skolemform]].
# Nun sind alle Variablen in der Funktion an Allquantoren <math>\forall</math> gebunden. Trifft man die Übereinkunft, Konstanten und Variablen unterschiedlich zu bezeichnen, beispielsweise Konstanten mit <math>a, b, c, a_1, a_2, a_3, \dotsc \,</math> und Variablen mit <math>x, y, z, x_1, x_2, x_3, \dotsc \,</math>, dann kann auch auf die explizite Notation des Allquantors verzichtet werden. Man lässt ihn ebenfalls weg und erhält die [[Klauselform]] der Aussage.<ref>Davis, Martin: ''Eliminating the Irrelevant from Mechanical Proofs.'' in: ''Journal of Symbolic Logic'', {{ISSN|0022-4812}}, Vol. 32, No. 1 (Mar., 1967), pp. 118–119</ref>

Beispielsweise lautet die Klauselform der Formel '''1)''' aus dem vorigen Abschnitt:

{|cellpadding="15"
|-valign="top"
|'''2)'''
|<math>\neg K(g(a,z),s(x)) \vee K(g(f(a),f(z)),x) </math>
|}

=== Substitution und Vereinheitlichung ===

Die Formeln

{| cellpadding="15"
|-valign="top"
|<math>P(x) \,</math>
|und 
|<math>\neg P(a) \,</math>
|}

scheinen auf den ersten Blick nicht resolvierbar zu sein, da sie sich in <math>x \,</math> und <math>a \,</math> unterscheiden. Da die freie Variable <math>x \,</math> jedoch implizit ein Stellvertreter für alle <math>x \,</math> ist, darf (unter anderem) <math>a \,</math> für <math>x \,</math> eingesetzt werden.

Man erhält also die beiden Terme

{| cellpadding="15"
|-valign="top"
|<math>P(a) \,</math>
|und 
|<math>\neg P(a) \,</math>
|}

die sich offensichtlich miteinander resolvieren lassen.

Folgende Ersetzungen sind möglich:

{| cellpadding="15"
|-valign="top"
|'''3a)'''
|Ersetze Variable durch Konstante:
|<math>P(x) \,</math>
|<math>\rightarrow</math>
|<math>P(a) \,</math>
|-valign="top"
|'''3b)'''
|Ersetze Variable durch eine andere Variable:
|<math>P(x) \,</math>
|<math>\rightarrow</math>
|<math>P(y) \,</math>
|-valign="top"
|'''3c)'''
|Ersetze Variable durch Funktion einer Variablen:
|<math>P(x) \,</math>
|<math>\rightarrow</math>
|<math>P(f(y)) \,</math>
|}

Die Ersetzung von Variablen in einem Literal muss in konsistenter Weise durchgeführt werden: Wird eine Variable an einer Stelle durch einen Term ersetzt, so muss dies innerhalb des Literals überall geschehen:

{| cellpadding="15"
|-valign="top"
|'''4a)'''
|Korrekte Ersetzung:
|<math>P(x, f(x)) \,</math>
|<math>\rightarrow</math>
|<math>P(a, f(a)) \,</math>
|-valign="top"
|'''4b)'''
|Verbotene Ersetzung:
|<math>P(x, f(x)) \,</math>
|<math>\nrightarrow</math>
|<math>P(a, f(x)) \,</math>
|}

Sei <math>\lbrace x_1, x_2, \dotsc, x_n \rbrace \,</math> eine Menge von Variablen. Sei <math>\lbrace t_1, t_2, \dotsc, t_n \rbrace \,</math> eine Menge von Termen, die aus Funktionen, Variablen oder Konstanten zusammengesetzt sein können.

* Ein System <math>S \,</math> von Ersetzungen <math>\lbrace x_1 \rightarrow t_1, x_2 \rightarrow t_2, \dotsc, x_n \rightarrow t_n \rbrace \,</math> heißt eine ''Substitution''.

Seien <math>L_1 = P(t_1, t_2, \dotsc, t_n), L_2 = P(u_1, u_2, \dotsc, u_n), \dotsc, L_m = P(v_1, v_2, \dotsc, v_n)\,</math> Literale über demselben Prädikat <math>P\,</math>, wobei die <math>t_i, u_i, \dotsc, v_i \,</math> wiederum Terme sind.

* Eine Substitution <math>S \,</math> heißt eine ''Vereinheitlichung'' (oder auch Unifikator) von <math>L_1, L_2, \dotsc, L_m \,</math>, wenn durch die Anwendung von <math>S \,</math> die Argumente aller Literale zur Übereinstimmung gebracht werden, das heißt, wenn <math>S(L_1) = S(L_2) = \dotsb = S(L_m) \,</math>.

Zwei Literale über demselben Prädikat haben nicht notwendigerweise eine Vereinheitlichung. Beispielsweise lassen sich <math>P(a) \,</math> und <math>P(b) \,</math> nicht vereinheitlichen, wenn <math>a \,</math> und <math>b \,</math> unterschiedliche Konstanten sind.

* Eine Vereinheitlichung <math>S \,</math> von Literalen heißt ''allgemeinste Vereinheitlichung'', wenn es für jede andere Vereinheitlichung <math>T \,</math> dieser Literale eine Substitution <math>V \,</math> gibt, so dass <math>T = S \circ V \,</math>.

Wenn eine Menge von Literalen eine Vereinheitlichung besitzt, dann besitzt sie eine allgemeinste Vereinheitlichung. Diese kann mit Hilfe eines relativ einfachen Algorithmus<ref>Chang, Chin-Liang; Lee, Richard Char-Tung: ''Symbolic Logic and Mechanical Theorem Proving'', Academic Press, 1973, ISBN 0-12-170350-9, S. 77ff</ref> ermittelt werden.

=== Resolution prädikatenlogischer Klauseln ===
Mit diesem Instrumentarium kann das Resolutionsverfahren auf Aussagen der Prädikatenlogik ausgeweitet werden.
* Seien <math>C_1, C_2 \,</math> zwei Klauseln einer normalisierten prädikatenlogischen Aussage. [[Ohne Beschränkung der Allgemeinheit]] darf vorausgesetzt werden, dass diese keine übereinstimmenden Variablen enthalten (da sie durch einen Allquantor gebunden sind, können wir gleichnamige Variablen in einer Klausel umbenennen, auch wenn der Allquantor nicht mehr explizit geschrieben wird).
* Seien <math>L_1 \,</math> und <math>L_2 \,</math> positive bzw. negiert vorkommende Literale in <math>C_1 \,</math> bzw. <math>C_2 \,</math>, die eine allgemeinste Vereinheitlichung <math>S \,</math> besitzen.
Dann heißt
* <math>C_R = S(C_1 \cup C_2) \setminus\{S(L_1), \neg S(L_2)\}</math> ein ''binärer Resolvent'' von <math>C_1 \,</math> und <math>C_2 \,</math>.
* Sei ferner <math>C \,</math> eine Klausel mit einer Teilmenge von Literalen, die eine allgemeinste Vereinheitlichung <math>S \,</math> besitzt.

Dann heißt
* <math>S(C) \,</math> ein ''Faktor'' von <math>C \,</math>.
Ein ''Resolvent'' zweier Klauseln <math>C_1, C_2 \,</math> ist
* entweder ein binärer Resolvent von <math>C_1 \,</math> und <math>C_2 \,</math>.
* oder ein binärer Resolvent von <math>C_1 \,</math> und einem Faktor von <math>C_2 \,</math>.
* oder ein binärer Resolvent eines Faktors von <math>C_1 \,</math> und <math>C_2 \,</math>.
* oder ein binärer Resolvent eines Faktors von <math>C_1 \,</math> und eines Faktors von <math>C_2 \,</math>.
Das Resolutionsverfahren für prädikatenlogische Aussagen besteht darin, so lange solche Resolventen zu erzeugen, bis die leere Klausel erzeugt und damit der Widerspruchsbeweis erbracht ist.<ref>Chang, Chin-Liang; Lee, Richard Char-Tung: S''ymbolic Logic and Mechanical Theorem Proving'', Academic Press, 1973, ISBN 0-12-170350-9, S. 80–81</ref>

== Beispiel ==

=== Ein logisches Rätsel ===

Wir wollen das Prinzip am Beispiel eines kleinen, nicht wörtlich zu nehmenden logischen Rätsels illustrieren:

Seit dem Altertum ist bekannt, dass alle Athener klug (1) und alle Spartaner heldenmütig (2) sind. Außerdem ist bekannt, dass ein profundes Misstrauen zwischen beiden Städten herrscht, so dass doppelte Stadtbürgerschaften ausgeschlossen sind (3). Unser nach Griechenland entsandter Forscher war neulich zu Gast bei einer Konferenz. Mit Ausnahme unseres Forschers stammte jeder der Anwesenden aus einer der beiden Städte (4).

Der Forscher kam ins Gespräch mit den Herren Diogenes, Platon und Euklid. Mit ihren berühmten Vorbildern hatten diese nur den Namen gemein. Die Herren zogen kräftig übereinander vom Leder. Euklid sagte: „Wenn Platon Spartaner ist, dann ist Diogenes feige!“ (5) – Platon behauptete: „Diogenes ist eine Memme, wenn Euklid Spartaner ist!“ (6) „Wenn Diogenes allerdings Athener ist, dann ist Euklid ein Waschlappen!“ (7) – Worauf sich Diogenes den Bart glatt strich und postulierte: „Wenn Platon Athener ist, dann ist Euklid ein Dummkopf!“ (8)

Bei aller Spitzzüngigkeit blieben die drei Herren mit ihren Behauptungen bei der Wahrheit. Wer kommt aus welcher Stadt?

=== Das Rätsel in Klauselform ===

Wir setzen p für Platon, d für Diogenes, e für Euklid. Die Prädikate „ist Athener“, „ist Spartaner“, „ist heldenmütig“ und „ist klug“ bezeichnen wir mit A, S, H und K. Wir übersetzen die oben genannten Aussagen in die Klauselform und erhalten:

{|
|-
!width="120"| 
!width="450"| 
!width="50"| 
|-
|¬A(x) v K(x)
|
|(1)
|-
|¬S(x) v H(x)
|
|(2) 
|-
|¬A(x) v ¬S(x)
|
|(3)
|-
|A(x) v S(x)
|
|(4)
|-
|¬S(p) v ¬H(d)
|
|(5)
|-
|¬S(e) v ¬H(d)
|
|(6)
|-
|¬A(d) v ¬H(e)
|
|(7)
|-
|¬A(p) v ¬K(e)
|
|(8)
|}

=== Die Auflösung ===

Wir nehmen an, Platon sei Athener:

{|
|-
!width="120"| 
!width="450"| 
!width="50"| 
|-
|A(p)
|{Annahme}
|(9)
|}

Nun wenden wir das Resolutionsprinzip an und erhalten:

{|
|-
!width="120"| 
!width="450"| 
!width="50"| 
|-
|¬K(e)
|{aus Resolution von (9) mit (8)}
|(10)
|-
|¬A(e)
|{aus Substitution von e für x und Resolution (10,1)}
|(11)
|-
|S(e)
|{Subs. (e:x), Res. (11,4)}
|(12)
|-
|¬H(d)
|{Res. (12,6)}
|(13)
|-
|¬S(d)
|{Subs. (d:x), Res. (13,2)}
|(14)
|-
|A(d)
|{Subs. (d:x), Res. (14,4)}
|(15)
|-
|¬H(e)
|{Res. (15,7)}
|(16)
|-
|¬S(e)
|{Subs. (e:x), Res. (16,2)}
|(17)
|-
|leere Klausel
|{Res. (17,12)}
|(18)
|}

Somit ist die Annahme (9) zum Widerspruch geführt. Sie ist mitsamt den aus ihr abgeleiteten Klauseln (10) bis (18) zu verwerfen. Wir erhalten stattdessen:

{|
|-
!width="120"| 
!width="450"| 
!width="50"| 
|-
|¬A(p)
|{da (9) falsch ist}
|(19)
|-
|S(p)
|{Subs. (p:x), Res. (19,4)}
|(20)
|}

Nehmen wir nun an, Diogenes sei Spartaner, und wenden wir weiterhin das Resolutionsprinzip an:

{|
|-
!width="120"| 
!width="450"| 
!width="50"| 
|-
|S(d)
|{Annahme}
|(21)
|-
|H(d)
|{Subs. (d:x), Res. (21,2)}
|(22)
|-
|¬S(p)
|{Res. (22,5)}
|(23)
|-
|leere Klausel
|{Res. (23,20)}
|(24)
|}

Somit ist die Annahme (21) widerlegt und mitsamt den aus ihr abgeleiteten Klauseln (22) – (24) zu verwerfen. Wir erhalten stattdessen:

{|
|-
!width="120"| 
!width="450"| 
!width="50"| 
|-
|¬S(d)
|{da (21) falsch ist}
|(25)
|-
|A(d)
|{Subs. (d:x), Res. (25,4)}
|(26)
|}

Nehmen wir an, Euklid sei Spartaner. Wir erhalten:

{|
|-
!width="120"| 
!width="450"| 
!width="50"| 
|-
|S(e)
|{Annahme}
|(27)
|-
|H(e)
|{Subs. (e:x), Res. (27, 2)}
|(28)
|-
|¬A(d)
|{Res. (28, 7)}
|(29)
|-
|leere Klausel
|{Res. (29,26)}
|(30)
|}

Also ist (27) falsch und samt (28) – (30) zu verwerfen. Wir erhalten stattdessen:

{|
|-
!width="120"| 
!width="450"| 
!width="50"| 
|-
|¬S(e)
|{da (27) falsch ist}
|(31)
|-
|A(e)
|{Subs. (e:x), Res. (31,4)}
|(32)
|}

Platon ist Spartaner (20). Diogenes ist Athener (26), ebenso Euklid (32).

== Terminierung und Komplexität ==

Im Falle der Aussagenlogik [[Terminiertheit|terminiert]] das Verfahren: Es liefert in endlicher Zeit ein Ergebnis, ob eine vorgelegte Aussage erfüllbar ist. Die Rechenzeit wächst im allgemeinen Fall und mit den derzeit bekannten Verfahren exponentiell mit der Anzahl der Literale. Das Problem ist [[NP-Vollständigkeit|NP-vollständig]].<ref>Haken, A. "The Intractability of Resolution", Theoretical Computer Science 39 (1985), pp. 297–308.</ref>

Im Falle der Prädikatenlogik terminiert das Verfahren stets mit dem korrekten Ergebnis, wenn es auf eine unerfüllbare Formel angewendet wird. Bei einer erfüllbaren Formel kommt es jedoch vor, dass das Verfahren kein Ende findet. Man spricht von [[Semi-Entscheidbarkeit]]. Wäre es anders, dann wäre das Resolutionsverfahren ein Algorithmus, um prädikatenlogische Formeln allgemein zu entscheiden – was unmöglich ist, da das Gültigkeitsproblem in der Prädikatenlogik nicht [[Entscheidbarkeit|entscheidbar]] ist.

== Andere Kalküle im logischen Einsatz ==

* [[Baumkalkül]]: in gewisser Weise unter den Kalkülen der nächste Verwandte des Resolutionskalküls
* [[Hilbert-Kalkül|axiomatische Kalküle]]
* [[Systeme natürlichen Schließens]]
* [[Sequenzenkalkül]]
* [[Existential Graphs]]

== Quellen ==

<references/>

== Literatur ==
* Chang, Chin-Liang; Lee, Richard Char-Tung: ''Symbolic Logic and Mechanical Theorem Proving'', Academic Press, 1973, ISBN 0-12-170350-9

== Weblinks ==
* [http://www.informatik.uni-hamburg.de/WSV/teaching/vorlesungen/FGI1SoSe09/PL_Resolution.pdf Vorlesungsskript von Habel und Eschenbach], 2009, Fachbereich Informatik, Universität Hamburg, mit anschaulichen grafischen Darstellungen (PDF-Datei; 410&nbsp;kB)
* [http://userpages.uni-koblenz.de/%7Ebeckert/Lehre/Logik/12PraedikatenlogikResolution.pdf Vorlesungsskript von Bernhard Beckert], 2006, Universität Koblenz-Landau (PDF-Datei; 197 kB)
* [http://en.wikibooks.org/wiki/Logic_for_Computer_Scientists/Propositional_Logic/Resolution Logic for Computer Scientists], von [[Ulrich Furbach]], Universität Koblenz-Landau

[[Kategorie:Mathematische Logik]]
[[Kategorie:Logikkalkül]]