Embed Size (px)
Citation preview
Resolutionskalkul
Mit dem Begriff Kalkul bezeichnet man eine Menge von syntaktischenUmformungsregeln, mit denen man semantische Eigenschaften derEingabeformel herleiten kann.
Fur den Resolutionskalkul:
• Syntaktische Umformungsregeln: Resolution, Stopp bei Erreichen derleeren Klausel
• Semantische Eigenschaft der Eingabeformel: Unerfullbarkeit
Wunschenswerte Eigenschaften eines Kalkuls:
• Korrektheit: Wenn die leere Klausel aus F abgeleitet werden kann,dann ist F unerfullbar.
• Vollstandigkeit: Wenn F unerfullbar ist, dann ist die leere Klausel ausF ableitbar.
112
Resolutionsalgorithmus
• 1. Version: berechne Res∗(F )if 2 ∈ Res∗(F ) then return
”unerfullbar“
else return”erfullbar“
• 2. (praktische) Version: suche mit Hilfe von Heuristiken kurzeDeduktion von 2 (n ist die Anzahl der atomaren Formeln in F ):
for 1 ≤ i ≤ 4n do
choose K1,K2 ∈ F , Resolvente R von K1 und K2
if R = 2 then return”unerfullbar“
else F := F ∪ {R}return
”erfullbar“
113
Resolutionsalgorithmus
Bemerkungen:
1 Haufig existiert kurze Deduktion von 2, obwohl Res∗(F ) sehr großist. Daher ist Resolution als Unerfullbarkeitstest haufig effizient. Wennkeine Deduktion von 2 existiert, so muß Schleife 4n bzw. |Res∗(F )|mal durchlaufen werden, als Erfullbarkeitstest ist Resolution also nichtsehr effizient.
2 auch als Unerfullbarkeitstest ist Resolution nicht immer effizient:Haken hat 1985 fur jedes n eine Menge von Klauseln Fn angegebenmit:
• Fn ist unerfullbar.• Fn enthalt n · (n + 1) viele atomare Teilformeln.
• Fn besteht aus n3+n
2
2+ n + 1 vielen Klauseln.
• Jede Deduktion der leeren Klausel aus Fn hat Lange mindestens cn fureine feste Konstante c > 1.
114
Anwendung 1 der Resolution: (Un-)Erfullbarkeitstest
geg. aussagenlogische Formel F
Frage: Ist F erfullbar?
Methode: Wandle F in KNF in Mengendarstellung um und wendeResolutionsalgorithmus an.
115
Anwendung 2 der Resolution: Tautologietest
geg. aussagenlogische Formel F
Frage: Ist F Tautologie?
Methode: Wandle ¬F in KNF in Mengendarstellung um und wendeResolutionsalgorithmus an. An Stelle von
”unerfullbar“ gib
”Tautologie“,
an Stelle von”erfullbar“ gib
”keine Tautologie“ aus.
116
Anwendung 3 der Resolution: Folgerungstest
geg. aussagenlogische Formeln F1,F2, . . . ,Fn,F
Frage: Gilt F1,F2, . . . ,Fn |= F?
Methode: Bilde F ′ = F1 ∧ F2 ∧ · · · ∧ Fn ∧ ¬F , wandle F ′ in KNF inMengendarstellung um und wende Resolutionsalgorithmus an. An Stellevon
”unerfullbar“ gib
”F folgt aus F1,F2, . . . ,Fn“, an Stelle von
”erfullbar“
gib”F folgt nicht aus F1,F2, . . . ,Fn“ aus.
117
Beweis einer Folgerung: BeispielWir wollen
(AK ∨ BK ), (AK → BK ), (BK ∧ RL → ¬AK ),RL |= (¬AK ∧ BK )
zeigen.
Betrachte
F ′ = (AK ∨BK )∧ (AK → BK )∧ (BK ∧RL → ¬AK )∧RL → (¬AK ∧BK )
Eine KNF von F ′ ist
(AK ∨ BK ) ∧ (¬AK ∨ BK ) ∧ (¬BK ∨ ¬RL ∨ ¬AK ) ∧ RL ∧ (AK ∨ ¬BK )
In Mengendarstellung:
{{AK ,BK}, {¬AK ,BK}, {¬BK ,¬RL,¬AK}, {RL}, {AK ,¬BK}}
118
Beispiel zur ResolutionEine mogliche Deduktion von 2 aus
{{AK ,BK}, {¬AK ,BK}, {¬BK ,¬RL,¬AK}, {RL}, {AK ,¬BK}} (1)
sieht wie folgt aus:
{AK ,BK} gehort zu (1) (2)
{¬AK ,BK} gehort zu (1) (3)
{BK} aus (2) und (3) (4)
{¬BK ,¬RL,¬AK} gehort zu (1) (5)
{AK ,¬BK} gehort zu (1) (6)
{¬BK ,¬RL} aus (5) und (6) (7)
{RL} gehort zu (1) (8)
{¬BK} aus (7) und (8) (9)
2 aus (4) und (9) (10)
119
Bemerkungen zur Resolution
• Die Resolution ist als Unerfullbarkeitstest fur Formeln in KNF, alsTautologietest fur Formeln in DNF, als Folgerungstest fur Formeln inKNF i.a. sehr effizient (aber nicht immer: Haken 1985). Umallgemeine Formeln zu behandeln, mussen diese in KNF umgewandeltwerden, was sie i.a. exponentiell vergroßert.
• Die Vorlesungsseite enthalt einen Verweis auf ein Java-Applet zumResolutionsalgorithmus.
120
Erfullbarkeitstests
Im folgenden:
• Ein sehr effizienter Erfullbarkeitstest fur eine spezielle Klasse vonFormeln in KNF, sogenannte Hornformeln (vgl.
”Grundlagen und
diskrete Strukturen“)
• Ein fur Formeln in KNF im allgemeinen effizienter Unerfullbarkeitstest(Resolution)
• Ein fur beliebige Formeln im allgemeinen effizienter Erfullbarkeitstest(Tableau)
• Ein (philosophisch) interessanter Erfullbarkeitstest fur beliebigeFormeln (naturliches Schließen)
121
Tableaux (Idee)
Nachteil des Resolutionskalkuls: man muß zunachst KNF herstellen.
Tableaux-Methoden testen beliebige Formeln auf Erfullbarkeit.Sie sind etwas direkter, aber nicht unbedingt effizienter.Idee: Suche systematisch nach einer erfullenden Belegung uber wahreTeilformeln.hier nur fur Formeln in NNF (die ja mit linearem Aufwand aus beliebigerFormel berechnet werden kann)
Definition
Ein Tableau ist ein endlicher Baum, dessen Knoten mit Formeln beschriftetsind.
Ein Ast p in τ ist abgeschlossen, falls es atomare Formel A gibt, so daß Aund ¬A auf p vorkommen.
122
Tableaux und Entwicklung
Definition
”Das Tableau τ wird zum Tableau τ ′ entwickelt“ (τ ⊢ τ ′), falls τ einennicht-abgeschlossenen Ast p enthalt, so daß eine der folgenden Aussagengilt:in p enthalteneFormeln
in p nicht enthalteneFormeln
τ ′ entsteht aus τ durchVerlangerung von p um
(F ∧ G ) F und G F
G
(F ∧ G ),F GG
(F ∧ G ),G FF
(F ∨ G ) F und GF
pppppp
G
OOOOOO
123
Tableaux: Vollstandigkeit (I)
Lemma
Sei τ ⊢ τ ′ ein Entwicklungsschritt und B eine Belegung. Wenn es einenAst p in τ gibt mit B(F ) = 1 fur alle Formeln F auf p, dann hat auch τ ′
einen solchen Ast p′.
Beweis: Wird die Entwicklung von τ zu τ ′ an einem Ast p′ 6= p gemacht,so ist p gewunchter Ast von τ .Werde also der Ast p weiter entwickelt unter Verwendung der FormelF ∧ G (bzw. F ∨ G ). Dann gilt B(F ) = B(G ) = 1 (bzw. B(F ) = 1 oderB(G ) = 1). Die bzw. eine der Verlangerungen von p in τ ′ ist gewunschterAst p′.
124
Tableaux: Vollstandigkeit (II)
Folgerung
Sei τ Tableau mit F ⊢∗ τ (”das aus F entwickelt werden kann“). Ist F
erfullbar, so hat τ einen nicht-abgeschlossenen Ast.
Beweis: Es gilt F ⊢ τ1 ⊢ τ2 · · · ⊢ τn = τ und es gibt eine Belegung B mitB(F ) = 1. Nach dem Lemma hat jedes dieser Tableaux einenabgeschlossenen Ast pi , so daß B(G ) = 1 fur alle Formeln auf pi . Also istpn ein nicht-abgeschlossener Ast in τ .
125
Tableaux: Korrektheit
Definition
Ein Tableau ist vollstandig, wenn es nicht weiter entwickelt werden kann.
Lemma
Sei τ vollstandiges Tableau, das aus F entwickelt werden kann. Ist F nichterfullbar, so ist jeder Ast in τ abgeschlossen.
Beweis: Es gilt wieder F ⊢ τ1 ⊢ τ2 · · · ⊢ τn = τ . Angenommen, τ hatteeinen nicht-abgeschlossenen Ast p. Definiere eine Belegung B durch
B(A) =
{
1 A kommt in p vor
0 sonst.
Sei F = Fm,Fm−1,Fm−2, . . . ,F1 die Folge der Formeln auf dem Ast p.Man zeigt induktiv uber die Große der Formeln Fi , daß B(Fi ) = 1 gilt,insbesondere also B(F ) = B(Fm) = 1, ein Widerspruch zur Annahme.
126
Tableauxverfahren
τ := Fwhile true do
if alle Aste in τ abgeschlossen sindthen stopp mit Ausgabe
”unerfullbar“
if ein Ast nicht-abgeschlossen und nicht-entwickelbarthen stopp mit Ausgabe
”erfullbar“
berechne ein τ ′ mit τ ⊢ τ ′; setze τ := τ ′
endwhile
127
Tableauxverfahren: Beispiel 1
F ∧ ¬H ∧ G ∧ (¬F ∨ ¬G )
F
¬H ∧ G ∧ (¬F ∨ ¬G )
¬H
G ∧ (¬F ∨ ¬G )
G
¬F ∨ ¬G
¬F ¬G
Alle Aste in τ sind abgeschlos-sen, also ist die Formel nichterfullbar.
128
Tableauxverfahren: Beispiel 2
(F ∨ G ) ∧ (F ∨ ¬G )
F ∨ G
F ∨ ¬G
F ¬G
F G
Die zwei nicht-abgeschlossenen und nicht-entwickelbaren Aste fuhrenbeide zu der erfullendenBelegungen B(F ) = 1 undB(G ) = 0 (denn beideenthalten F aber nicht G )
129
Vollstandigkeit und Korrektheit des Tableauxverfahrens
Satz
Das Tableauxverfahren terminiert immer. Er gibt genau dann”erfullbar“
aus, wenn die Formel F erfullbar ist.
Beweis:
Termination folgt aus zwei Beobachtungen:
• Die Knoten der berechneten Tableaux sind Teilformeln von F
• jede Teilformel von F kommt auf jedem Ast eines berechnetenTableaux hochstens einmal vor
Ist F erfullbar, so gibt der Algorithmus”erfullbar“ aus nach Folgerung auf
Folie 125
Gibt der Algorithmus”erfullbar“ aus, so ist F erfullbar nach Lemma auf
Folie 126
130
Erfullbarkeitstests
Im folgenden:
• Ein sehr effizienter Erfullbarkeitstest fur eine spezielle Klasse vonFormeln in KNF, sogenannte Hornformeln (vgl.
”Grundlagen und
diskrete Strukturen“)
• Ein fur Formeln in KNF im allgemeinen effizienter Unerfullbarkeitstest(Resolution)
• Ein fur beliebige Formeln im allgemeinen effizienter Erfullbarkeitstest(Tableau)
• Ein (philosophisch) interessanter Erfullbarkeitstest fur beliebigeFormeln (naturliches Schließen Sequenzenkalkul)
131
Sequenzenkalkul
ein weiterer Kalkul, der”rein syntaktisch“ die Folgerungen erzeugt
Idee: Regeln der Form:”Wenn ich weiß, daß G aus F bewiesen werden
kann, so weiß ich auch, daß G ′ aus F ′ bewiesen werden kann.“Schreibweise: {F1,F2, . . . ,Fn} ⊢ G wird heißen
”Die Formel G kann aus
den Formeln F1, . . . ,Fn bewiesen werden.“
Regeln werden geschrieben als
F1 ⊢ G1 F2 ⊢ G2 . . .Fk ⊢ Gk
F ′ ⊢ G ′
Definition
Eine Sequenz besteht aus einer endlichen Menge von Formeln F und einerFormel G .
132
Sequenzenkalkul
Definition
Die Sequenz (F ,G ) ist gultig (F ⊢ G ), wenn sie sich in endlich vielenSchritten durch die folgenden Regeln erzeugen laßt:
F ∪ {G} ⊢ GF ⊢ G
F ⊢ ¬¬G¬i F ⊢ G1 F ⊢ G2
F ⊢ G1 ∧ G2∧i
F ⊢ G1
F ⊢ G1 ∨ G2∨i1
F ⊢ G2
F ⊢ G1 ∨ G2∨i2
F ⊢ F ∨ G F ⊢ ¬F ∨ GF ⊢ G
∨e
F ⊢ ¬G1 F ⊢ ¬G2
F ⊢ ¬(G1 ∨ G2)deM∨
F ⊢ ¬G1
F ⊢ ¬(G1 ∧ G2)deM∧1
F ⊢ ¬G2
F ⊢ ¬(G1 ∧ G2)deM∧2
F ⊢ H G ⊢ ¬H ∨ GF ∪ G ⊢ G
MPF ∪ {F} ⊢ GF ⊢ ¬F ∨ G
→i
133
Korrektheit
Lemma
Aus F ⊢ G folgt F |= G .
Bemerkung
Auf der linken Seite steht, daß man F ⊢ G herleiten kann. Dies ist einesyntaktische Aussage.Auf der rechten Seite steht, daß jede Belegung B, die alle Formeln aus Ferfullt, auch G erfullt. Dies ist eine semantische Aussage.
134
Korrektheit
Beweis induktiv uber die Lange einer Herleitung (= Anzahl derRegelanwendungen) von F ⊢ GI.A. gilt G ∈ F , so folgt aus B |= F sofort B |= G , also F |= G .
I.V. Gelte F |= G , falls die Gultigkeit der Sequenz F ⊢ G sich in ≤ nSchritten zeigen laßt.
I.S. Sei F ⊢ G eine gultige Sequenz, deren Gultigkeit sich in n + 1Schritten zeigen laßt.
Wir machen eine Fallunterscheidung danach, welche Regel als letztesangewandt wurde.
135
Korrektheit
∨i1 Wurde als letztes die Regel ∨i1 angewandt, so gilt G = G1 ∨ G2 unddie Gultigkeit der Sequenz F ⊢ G1 kann in hochstens n Schrittengezeigt werden. Also gilt nach I.V. F |= G1. Sei nun B Belegung mitB |= F . Dann gilt also B(G1) = 1 und damit1 = B(G1 ∨ G2) = B(G ). Also haben wir F |= G gezeigt.
∧i Wurde als letztes die Regel ∧i angewandt, so gilt G = G1 ∧ G2 unddie Gultigkeit der Sequenzen F ⊢ G1 und F ⊢ G2 kann in hochstens nSchritten gezeigt werden. Also gilt nach I.V. F |= G1 und F |= G2.Sei nun B Belegung mit B |= F . Dann gilt also B(G1) = B(G2) = 1und damit 1 = B(G1 ∧ G2) = B(G ). Also haben wir F |= G gezeigt.
136
Korrektheit
deM∨ Wurde als letztes die Regel deM∨ angewandt, so gilt G = ¬(G1 ∨ G2)und die Gultigkeit der Sequenzen F ⊢ ¬G1 und F ⊢ ¬G2 kann inhochstens n Schritten gezeigt werden. Also gilt nach I.V. F |= ¬G1
und F |= ¬G2. Sei nun B Belegung mit B |= F . Dann gilt alsoB(¬G1) = B(¬G2) = 1 und damit1 = B(¬G1 ∧ ¬G2) = B(¬(G1 ∨ G2)) = B(G ) nach demFundamentalsatz. Also haben wir F |= G gezeigt.
→i Wurde als letztes die Regel →i angewandt, so gilt G = ¬G1 ∨ G2 unddie Gultigkeit der Sequenz F ∪ {G1} ⊢ G2 kann in hochstens nSchritten gezeigt werden. Also gilt nach I.V. F ∪ {G1} |= G2. Sei nunB Belegung mit B |= F . Gilt B(G1) = 0, so erhalten wirB(¬G1 ∨ G2) = 1. Andernfalls haben wir B |= F ∪ {G1} und damitauch B(G2) = 1, also B(¬G1 ∨ G2) = 1.
Die restlichen Falle konnen (und sollten von Ihnen beim Nacharbeiten)analog behandelt werden.
137
