Tableaukalk¨ul f¨ur Aussagenlogik · Deduktion, SS 04, Folien Ded−Aussagen, Seite 33 27. April2004. Quellen des Nichtdeterminismus • Welche Variable wird zur Fallunterscheidung

Tableaukalkul fur Aussagenlogik

Tableau:

• Test einer Formel auf Widerspruchlichkeit• Fallunterscheidung baumformig organisiert• Keine Normalisierung, d.h. alle Formeln sind erlaubt• Struktur der Formel wird beachtet• Verallgemeinerbar fur Modallogik, Pradikatenlogik

Deduktion, SS 04, Folien Ded−Aussagen, Seite 1 27. April2004

Tableaukalkul: Grundbegriffe

• α-Formeln (konjunktive Formeln)• β-Formeln (disjunktive Formeln)

Zerlegungen:

α α1 α2X ∧ Y X Y¬(X ∨ Y ) ¬X ¬Y¬(X ⇒ Y ) X ¬Y(X ⇔ Y ) X ⇒ Y Y ⇒ X

β β1 β2X ∨ Y X Y¬(X ∧ Y ) ¬X ¬YX ⇒ Y ) ¬X Y¬(X ⇔ Y ) ¬(X ⇒ Y ) ¬(Y ⇒ X)


Tableau: Definition

Idee beim Tableau-Kalkul:Zeige, dass die eingegebene Aussage inkonsistent ist.

Definition

Ein aussagenlogisches Tableau ist ein markierter Baumdie Knoten sind mit Formeln markiert.Die Eingabeformel ist an der Wurzel

Ein Pfad ist geschlossen, wenn 0 oder ¬1 vorkommt,oder gleichzeitig F und ¬F auf dem Pfad

Ein Pfad ist (atomar) geschlossen, wenn 0 oder ¬1 vorkommt,oder Atom A und ¬A auf diesem Pfad ist

Ein Tableau ist (atomar) geschlossen, wenn alle Pfade (atomar) ge-schlossen


Tableau-Aufbau-Regeln

• Eingabe ist eine Formel F• Initial: nur Knoten F• Danach Expansionsregeln:

¬¬X

X

α

α1α2

β

β1 | β2

¬0

1

¬1

0

Beachte: Die expandierte Formel muss kein Blatt sein.Einschrankung: Formel pro Pfad nur einmal expandieren

Ein Formel F ist bewiesen, wenn aus dem Tableau mit einem Knoten

und der Formel ¬F ein geschlossenes Tableau erzeugt worden ist.


Strategien

Aufbau-Regeln sind nicht-deterministisch

D.h. Reihenfolge ist nicht vorgeschrieben.

Effizient: moglichst wenig verzweigen

d.h. bevorzuge α-Regeln


Beispiel

Tableau fur X ∧ ¬X:

X ∧ ¬X|X|

¬X

geschlossen


Beispiel

Tableau fur ¬(X ∧ Y ⇒ X):

¬(X ∧ Y ⇒ X)|

X ∧ Y|

¬X|X|Y

geschlossen


Optimierung fur Aquivalenzen

Neue Tableau-Expansionsregeln

A ⇔ B

A ¬AB ¬B

¬(A ⇔ B)

A ¬A¬B B


Beispiel: Aquivalenzen

¬((P ⇔ Q) ⇔ (Q ⇔ P ))

ggggggggggggggggggggg

WWWWWWWWWWWWWWWWWWWW

(P ⇔ Q) ¬(P ⇔ Q)

¬(Q ⇔ P )

ooooooooooooooQ ⇔ P

gggggggggggggggggggggggggggggg

P ¬P ¬Q Q

Q

xxxxxxxxx¬Q P ¬P

¬Q Q . . . . . . . . .

P ¬P


Beispiel

Zeige, dass P ⇒ (Q ⇒ P ) eine Tautologie ist:

¬(P ⇒ (Q ⇒ P ))

P

¬(Q ⇒ P )

Q

¬P

geschlossen, da P und ¬P auf dem Pfad liegen.


Beispiel

Zeige ((P ⇒ Q) ∧ (Q ⇒ R)) ⇒ (P ⇒ R):

Dazu starte mit ¬(((P ⇒ Q) ∧ (Q ⇒ R)) ⇒ (P ⇒ R)):


(P ⇒ Q)

(Q ⇒ R)

¬(P ⇒ R)

P

¬R

iiiiiiiiiiiiiiiiiiiiiiii

PPPPPPPPPPPPPPP

¬P Q

oooooooooooooooo

OOOOOOOOOOOOOOOOO

geschlossen ¬Q R

geschlossen geschlossen

Algorithmische Korrektheit des Tableaukalkuls

Nachweis von:

1. Korrektheit (Soundness): Der Kalkul erzeugt geschlossene Table-

aus nur fur unerfullbare Formeln.

2. Vollstandigkeit (Completeness): Fur jede unerfullbare Formel kann

der Tableaukalkul ein geschlossenes Tableau erzeugen.

Zusatzliche gute Eigenschaften:

• Tableaukalkul fur Aussagenlogik terminiert immer• Liefert Information auch wenn er fehlschlagt.


Korrektheit des Tableaukalkuls (2)

Definition

• Ein Pfad eines Tableaus ist erfullbar, wenn die Kon-

junktion aller Formeln auf dem Pfad erfullbar ist.• Ein Tableau ist erfullbar, wenn es einen Pfad gibt,

der erfullbar ist.

Beachte: Wenn eine Menge von Formeln 0 oder ¬1 enthalt, dann ist

sie nicht erfullbar.

Es gilt: Ein geschlossenes Tableau ist nicht erfullbar.


Korrektheit des Tableaukalkuls (3)

Satz Wenn T → T ′ mit einer Transformationsregel, dann gilt:

T ist erfullbar gdw. T ′ ist erfullbar

Mittels Fallunterscheidung uber mogliche Expansionen:


Fundierte Ordnungen

Ziel: Terminierung

fundierte (well-founded) Ordnung:

ist eine partielle Ordnung ≥ auf einer Menge M ,

ohne unendlich absteigende Ketten a1 > a2 > . . .

zB. Naturliche Zahlen: 5 > 4 > 2 > 1.

Es gilt: Die lexikographische Kombination von fundierten Ordnungen

ist wieder eine fundierte Ordnung.


Fundierte Ordnungen: Multimengenordnung

(M, >) Menge mit fundierter Ordnung

Mult(M) endliche Multimengen uber M

Z.B. Multimengen uber IN:

{3,3,2,1}, ∅, {1,1,1,1,1,100}


Fundierte Ordnungen: Multimengenordnung

Seien A und B Multimengen uber M

A >> B, gdw ∃X, Y mit X 6= ∅, B = (A \X) ∪ Y undzu jedem Element von Y existiertein echt großeres Element in X

Z. B in Mult(IN):

{3,3,2,1} >> {3,2,2,2},denn {3,2,2,2} = {3,3,2,1} \ {3,1} ∪ {2,2,2}.

Es gilt: Die Multimengenordnung >> ist eine partielle Ordnung.>> ist fundiert, gdw. > fundiert ist.


Terminierung des Tableaukalkuls

Lemma Der Tableaukalkul fur Aussagenlogik terminiert, wenn man jede

Formel auf jedem Pfad hochstens einmal expandiert.

Beweis:

Benutze Multimengenordnung . . .


Korrektheit des Tableaukalkuls

Zusammen ergibt sich bis jetzt:

• Wenn F erfullbar:Der Tableaukalkul terminiert,Das Endtableau ist nicht geschlossen

• Wenn F unerfullbar:Der Tableaukalkul terminiert,Das Endtableau ist nicht erfullbarFrage? ist es auch geschlossen?



Betrachte: Endtableau, das nicht geschlossen istDarin einen nicht geschlossenen Pfad.

Es gilt: Die Formelmenge H auf dem Pfad ist abgeschlossen und hat

folgende Eigenschaften:

• A ∈ H und ¬A ∈ H geht nicht.• 0 6∈ H,¬1 6∈ H• ¬¬X ∈ H ⇒ X ∈ H• α ∈ H ⇒ α1 ∈ H und α2 ∈ H• β ∈ H impliziert β1 ∈ H oder β2 ∈ H

D.h.: H ist eine (aussagenlogische) Hintikka-Menge

Es gilt: Hintikka-Mengen sind erfullbar



Zusammenfassend ergibt sich jetzt:

• Wenn F erfullbar:Der Tableaukalkul terminiert,Das Endtableau ist nicht geschlossen

• Wenn F unerfullbar:Der Tableaukalkul terminiert,Das Endtableau ist geschlossen

D.h. der Tableaukalkul fur Aussagenlogik terminiert und ist korrekt.


Quantifizierte Boolesche Formeln

Quantifizierte Boolesche Formeln (QBF) sind

Boolesche Formeln mit Quantoren.

Syntax:

Q := 0 | 1| P ( Boolesche Variable)| (Q1 ∧Q2) | (Q1 ∨Q2) | (Q1 op Q2)| (¬ Q)| ∀P.Q | ∃P.Q

Die Quantifizierung ist nur uber die zwei Wahrheitswerte.

Die Gultigkeit ist nur fur geschlossene QBFs definiert.


QBF: Komplexitat

Gultigkeit von QBF ist PSPACE-vollstandig.

D.h. alle bekannten Algorithmen sind EXPTIME.

Ziel: Untersuchung und Optimierung der Entscheidungsalgorithmen

Hoffnung: großer Anteil praktisch relevanten Probleme effizient ent-

scheidbar


Aussagenlogik in QBFs:

• Erfullbarkeit einer aussagenlogischen Formel F= Gultigkeit der QBF ∃p1, . . . , pn.F ,wobei pi die Variablen in F sind.

• aussagenlogischen Formel F ist Tautologie= Gultigkeit der QBF ∀p1, . . . , pn.F ,wobei pi die Variablen in F sind.


Normalformen fur QBFs:

• Pranex-FormAlle Quantoren im Prafix der Formel,der Rumpf ist eine aussagenlogischen Formel.

• Pranexe KlauselformQuantorenprafix und KlauselmengeDas ist effizient durchfuhrbar: P.F [G] → P.∃X.(X ⇔ G ∧ F [X])

• Annahme: Tautologie-Klauseln sind entferntSimplifikationen ¬0 → 1 und ¬1 → 0 sind durchgefuhrt


Nochmal: CNF-Herstellung in der Aussagenlogik

Zur Frage: Warum wird Aquivalenz von schneller CNF-Herstellung

nicht erhalten:

• Erhaltung der Erfullbarkeit: ok, da man nur eine existenzquantifi-

zierte Variable hinzufugt.

• Erhaltung der Tautologie-Eigenschaft: nicht klar,

da man zu einer allquantifizierten Formel existenzquantifizierte Va-

riable hinzufugt.

Danach hat aber die Formel einen gemischten Prefix.


Gultigkeit von QBF-Formeln

Naiver Algorithmus und gleichzeitig Def der Gultigkeit von F

Transformiere F durch Quantorenelimination:

1. ∀P.F → F [1/P ] ∧ F [0/P ]

2. ∃P.F → F [1/P ] ∨ F [0/P ]

Resultat nach Simplifikation: 0 oder 1

Nachteil: Zwischenergebnisse konnen exponentiell groß sein


Beispiel

F = ∀x∃y.x ⇔ y.

Quantorenelimination ergibt:

1. (∃y.1 ⇔ y) ∧ (∃y.0 ⇔ y).

2. ((1 ⇔ 1) ∨ (1 ⇔ 0)) ∧ ((0 ⇔ 1) ∨ (0 ⇔ 0))

3. Resultat: 1


Klassifizierung von Klauseln

Gegeben: QBF in pranexer Klauselform.

Klassifikation von Klauseln:

1. Eine Klausel ist wahr, wenn sie ein Literal 1 enthalt, oder eine

Variable sowohl positiv als auch negativ (Tautologie).

2. Eine Klausel ist falsch, wenn 1. nicht gilt und wenn die Klausel

keine existenziell quantifizierte Variable enthalt.

Z.B. eine Klausel mit nur allquantifizierten Variablen ist falsch,

wenn sie keine Tautologie ist.

3. Andere Klauseln nennt man offen.


Ein Beispiel

∃x1∀x2∃x3∃x4.((¬x1 ∨ x2 ∨ ¬x3)︸︷︷︸c1

∧ (x3 ∨ ¬x4)︸︷︷︸c2

∧ (x3 ∨ x4)︸︷︷︸c3

∧ (x1 ∨ ¬x2 ∨ ¬x3)︸︷︷︸c4

)

Diese Formel ist nicht gultig:

·x1xxxxxxxxxx ¬x1

BBBB

BBBB

B

·¬x2||

||||

|||

||||

||||

|

x2

·x2

¬x2BB

BBBB

BBB

BBBB

BBBB

B

·x3

}}}}

}}}} ¬x3

· ·x3

}}}}

}}}} ¬x3

·

c1 ·x4��

��

�� ¬x4??

????

??c4 ·

x4��

�� ¬x4

????

????

c2 c3 c2 c3


Entscheidungsprozedur semantischer Baum

Eingabe: Pranexe KlauselformDatenstruktur: UND-ODER-Baum,

ALL ↔ UNDEX ↔ ODERKnoten sind Formeln


Semantischer Baum: Erzeugung

• Wurzel = Input-Formel in pranexer Klauselform• Am Knoten K erste Variable des Quantorenprafix von FK analysieren:

1. ∀x, dann UND-Knoten.Die beiden Tochterknoten sind:FK[1/x] und FK[0/x]

2. ∃x, dann ODER-Knoten.Die beiden Tochterknoten sind:FK[1/x] und FK[0/x]

• Knoten ist Blatt, wenn FK aussagenlogisch zu 1 oder 0 auswertbarunter Benutzung der Def. wahre / falsche Klauseln

• Auswertung des Ausgabe-Baums:Auswertung entsprechend der UND, bzw ODER-Strukturund Werten an den Blattern.

• Ergebnis: 0 oder 1.

Optimierungsmoglichkeit: Vertauschen von gleichartig quantifizierten

benachbarten Variablen


Quellen des Nichtdeterminismus

• Welche Variable wird zur Fallunterscheidung verwendet?

• Welcher Fall wird zuerst untersucht pro Variable?


Beispiel

∀x, ∃y.x ⇔ y:

∀x∃y.x ⇔ y

ffffffffffffffffffffffff

ffffffffffffffffffffffff

SSSSSSSSSSSSSS

SSSSSSSSSSSSSS

∃y.1 ⇔ y

mmmmmmmmmmmm

QQQQQQQQQQQQ∃y.0 ⇔ y

jjjjjjjjjjjjjjj

QQQQQQQQQQQQ

1 ⇔ 0 1 ⇔ 1 0 ⇔ 1 0 ⇔ 0

Der Wert an der Wurzel ist 1.

> dpll "ALL x EX y: (x <=> y)"

"Formel ist Tautologie"


Optimierungen:

Vermeiden von Fallunterscheidungen:

• Wenn aktuelle Variablen nicht in der Klauselmenge enthalten ist,

dann streiche die aus dem Prafix.


Optimierungen: Unit-Propagation

Situation: Formel am Knoten

Eine Klausel c ist eine Unit, gdw. c hat genau ein existenzielles Literal

(x oder ¬x) und

fur alle anderen (universellen) Literale y oder ¬y,

y ist rechts von x im Quantorenprafix

Aktion :

Nur ein Tochterknoten:

F [1/x], wenn x das Literal ist und

F [0/x], wenn ¬x das Literal ist.

Beachte: x muss nicht die Top-Variable sein


Optimierungen: Isoliertes Literal

Definition Ein Literal in einer Klauselmenge ist isoliert (pur),

wenn das Komplement nicht in der Klauselmenge vorkommt.

Aktion:

Sei x die Variable im isolierten Literal.

1. Wenn x Ex-quantifiziert ist,

Tochterknoten: F [1/x], wenn x das Literal ist und

Tochterknoten: F [0/x], wenn ¬x das Literal ist.

2. Wenn x All-quantifiziert ist,

Tochterknoten mit F [0/x], wenn x das Literal ist und

F [1/x], wenn ¬x das Literal ist.


Documents

Tableaukalk¨ul f¨ur Aussagenlogik · Deduktion, SS 04, Folien Ded−Aussagen, Seite 33 27. April2004. Quellen des Nichtdeterminismus • Welche Variable wird zur Fallunterscheidung