SAT-Engines Seminar

WS 2000/2001

Albert-Ludwigs-Universität FreiburgFakultät für angewandte WissenschaftenLehrstuhl für Rechnerarchitektur

Jochen Römmler

15. Dezember 2000

Themen der Vortrags

Historisches Notationen Idee des ursprünglichen DP-Algorithmus Regeln des DP-Algorithmus & Beispiele dazu Der komplette DP-Algorithmus DP-Algorithmus in heutiger Implementation

I. Davis & Putnam Algorithmus:

Definitionen Klassisches Unit Propagation Unit Propagation von Crawford und Auton Unit Propagation von Zhang und Stickel

II. Effiziente Unit Propagation:

I. Davis & Putnam Algorithmus

Historisches Notationen Idee des ursprünglichen DP-Algorithmus Regeln des DP-Algorithmus & Beispiele dazu Der komplette DP-Algorithmus DP-Algorithmus in heutiger Implementation

Martin DavisHillary PutnamJACM, 1960,„A Computing Procedure for Quantification Theory”.

HistorischerHintergrund (1)• Hoffnung: mittels Methoden der formalen Logik kann man rein berechenbare Methoden fürmath. Theoreme erhalten.

• Hilbert: klassische Mathematik in Quantifizierungstheorie formalisierbar. Zentrales Problem der mathematischen Logik:

„Entscheidungsalgorithmus finden, der über die Gültigkeit von Formeln der Prädikatenlogik (PL) entscheidet“

HistorischerHintergrund (2) Ernüchterung durch Church & Turing:

„So einen Algorithmus wird es nie geben!“(„Satz von der Unentscheidbarkeit der Logik erster Stufe“1) ) => Krise

...Erkenntnis: kein ultimativer Entscheidungs-Algorithmus, aber viele computertaugliche (semi-entscheidbare) Beweis-Algorithmen; d.h. Algorithmen, die gültige Formeln in jedem Fall beweisen können, und unendliche Laufzeit haben bei ungültigen Formeln

Das Paper von Davis & Putnam entstand in der „Steinzeit“ der Informatik (1960), nachdem man erkannt hatte, dass die computerbasierte Beweisführung beliebiger logischer Theoreme i.A. nicht möglich ist. Trotzdem wollte man sich den Computer als unterstützendes Mittel bei einer Beweisführung zu Nutze machen.

1) vgl. H.-D. Ebbinghaus / J. Flum / W. Thomas: Einführung in die mathematische Logik. S.181, 4. Auflage, Spektrum Akademischer Verlag, Heidelberg/Berlin/Oxford 1996.

HistorischerHintergrund (3) Es gibt schon Ansätze von H. Wang und

P.C. Gilmore, welche abereine zu hohe Laufzeit haben, obwohl sie schneller sind als Methoden, die auf Wahrheitstabellen beruhen(bereits für einfache Beispiele unbrauchbar).

Veröffentlichung des Papers vonM.Davis & H.Putnam im JACM 1960,Original-Titel:„A computing procedure for quantification theory”. (Sponsor: US-Air Force)

Die Ansätze, die es bisher gab, waren bereits für kleine Beispiele und Anwendungen derart langsam, dass sie nur von geringem praktischen Nutzen waren. Deshalb präsentieren M. Davis und H. Putnam ihre „Berechnungsprozedur für die Quantifizierungstheorie“ (DP-Algorithmus), also einen Algorithmus, der (in der Originalversion) Formeln der Prädikatenlogik erster Stufe (PL1) beweist bzw. widerlegen kann. Man beachte, dass es hier zunächst nicht um aussagenlogische Formeln geht. Der DP-Algorithmus, wie man ihn heute weit verbreitet findet, bezieht sich meist nur auf das Auffinden eines Modells einer Formel der Aussagenlogik.

Notationen (1)

Begriffe aus der Prädikatenlogik: Quantorenfreiheit, freie/gebundene Variablen Interpretation :=

Interpretationsfunktion + Universum Prädikate, Funktionssymbole, Terme

Begriffe aus der Aussagenlogik: Erfüllbarkeit := Es gibt eine Interpretation der

Formel, die sie erfüllt (wahr macht) SAT := Frage nach der Erfüllbarkeit Konjunktive/Disjunktive Normalform (KNF/DNF) Literale, Klauseln

Diese Begriffe sind für das weitere Verständnis des Algorithmus essentiell:Eine PL1-Formel heißt quantorenfrei, wenn in ihr keine All- oder Existenzquantoren auftreten.Eine Variable in einer PL1-Formel ist gebunden, wenn sie quantifiziert ist und innerhalb des Gültigkeitsbereichs des entsprechenden Quantors auftritt, frei sonst. Eine PL1-Formel, in der alle Variablen gebunden sind, heißt geschlossen.

Notationen (2)

Pränex-Normal-Form (PNF) :=Quantoren vorziehen, wobei jede Variable nur einmal quantifiziert werden darf (ggf. umbenennen), und der „Rest“ bildet die sog. quantorenfreie Matrix. Die PNF kann immer effizient gewonnen werden. Beispiele:

y[P(y) -> x Q(x)] wird: yx[P(y) -> Q(x)] y[P(y) -> y Q(y)] wird: yx[P(y) -> Q(x)]

( Umbenennung [y in x] )

Bei der Bildung der Pränexnormalform (PNF) geht man in drei Schritten vor:

1. Eliminierung von und

2. Negation ~ nach innen ziehen

3. Quantoren nach außen ziehen (ggf. unter Berücksichtigung von Namenskonflikten, denn jede Variable darf nur einmal quantifiziert werden)

Bei der PNF handelt es sich um eine Äquivalenzumformung.

Notationen (3)

Skolem-Normal-Form2) (SNF) :=PNF ohne Existenzquantoren.In geschlossener Formel in PNF werden alle Existenzquantoren entfernt und an die Stellen der entsprechend quantifizierten Variablen neue Funktionssymbole geschrieben, deren Stelligkeit von der Anzahl der zuvor allquantifizierten Variablen abhängt. Diese Funktionen sollen uns das „richtige Element“ liefern. Die SNF kann man effizient gewinnen.

Beispiele:

1. xy P(x,y) wird zu y P(f0,y)2. yxz P(x,y,z) wird zu yz P(f(y),y,z)

Diese Vorgehensweise ist aber keine Äquivalenztransformatin, sondern ist nur erfüllbarkeitsäquivalent, d.h. dass jede erfüllende Belegung einer Formel auch deren SNF erfüllt.

Die DNF einer geschlossenen Formel kann immer effizient gewonnen werden.

2) vgl. H.-D. Ebbinghaus / J. Flum / W. Thomas: Einführung in die mathematische Logik. S.143f, 4. Auflage, Spektrum Akademischer Verlag, Heidelberg/Berlin/Oxford 1996.

Notationen (4)

QFL Generator (Herbrandexpansion) Grundtermmenge := Menge aller

Grundterme, die sich aus Symbolen der PL1-Formel in SNF bilden lassen.Beispiel:Symbole = {x1,x2,f1} =>GTM = {x1,x2,fx1,fx2,ffx1,ffx2,fffx1,...}=> i.A. ist die Menge unendlich groß (!)

Eine Instanziierung der Matrix der Formel mit Elementen aus der Grundtermmenge liefert eine aussagenlogische Formel, die wir in KNF bringen...

Der folgende DP-Algorithmus macht von einem QFL-Generator Gebrauch. Das ist eine Vorschrift, mittels der man aus einer PL1-Formel in SNF eine stetig wachsende Formel in propositionaler (=Aussagen-) Logik erhält. Pro Aufruf, gibt uns der QFL-Generator eine Instanz der PL1-Formel zurück, welche wir in Konjunktion mit den bereits erhaltenen Instanzen setzen. Die Instanzen gewinnt man, indem man die Herbbrand-Expansion der PL1-Formel bildet. Der Hintergrund dabei ist, dass wir keine allgemeinen Aussagen über die Erfüllbarkeit von PL1-Formeln machen können, jedoch können wir das Erfüllbarkeitsproblem auf die Erfüllbarkeit von propositionalen Formeln reduzieren.

Notationen (5)

Jeder Aufruf des QFL-Generator liefert uns eine neue Zeile, die wir mit den bisherigen Zeilen in Konjunktion setzen. (constraints nehmen zu)

Beispiel QFL-Output für F=P(x,y,z):1. Zeile: P(x1,x1,x1)2. Zeile: P(x1,x1,x2)...i. Zeile: P(f(x1),f(x1),f(x1))...j. Zeile: P(ff(x1),f(x2),f(x1))...

Das Problem dabei ist, dass der QFL-Generator unendlich viele Zeilen liefern kann, falls es in der Grundtermmenge ein Funktionssymbol mit einer und mehr Stellen gibt. Aufgrund dieser Tatsache wird der folgende DP-Algorithmus auch ggf. unendliche Laufzeit haben (genau dann, wenn die zu beweisende PL1-Formel ungültig war).

Davis&Putnam-Algorithmus Idee (1)

Wir beweisen F, indem wir ~F widerlegen!(Widerlegungs-Algorithmus)

Prüfe iterativ, ob die Konjunktion der ersten n (n=1,2,3,...) „QFL-“Zeilen erfüllbar ist.

Falls Ergebnis: „unerfüllbar“ lautet, dann ist auch ganz ~F unerfüllbar, d.h. F ist erfüllbar; denn die Unerfüllbarkeit einer endlichen Teilmenge genügt schon, um die Unerfüllbarkeit der gesamten Klauselmenge zu zeigen.

...der Algorithmus terminiert i.A. also nur, wenn ~F unerfüllbar ist,

d.h. wenn F eine gültige Formel war!

Davis&Putnam-AlgorithmusIdee (2) Ziel: Entscheidungsverfahren für PL1 Formeln Weg: Reduktion von Erfüllbarkeit von PL1 Formeln

auf Erfüllbarkeit von aussagenlogischen Formeln.

Frage: Wie kann man dies effizient gestalten?

Davis&Putnam-Algorithmus Regeln (1) Regel 1: Löschen von unit-clauses

a) F = …&(p)…&(~p)… Resolution ergibt leere Klausel (!) setze F  0.Die Formel ist widerspruchsvoll und damit unerfüllbar

Sobald in der KNF-Formel F eine Klausel mit nur einem einzigen Literal p und eine weitere Klausel mit demselben Literal negiert auftaucht, kann man keine erfüllende Belegung mehr für F finden. Die Antwort „F unerfüllbar“ steht fest und wir brauchen nicht mehr weiter zu testen.

b) Wenn a) nicht zutrifft:F = …&(p)&… streiche alle Klauseln, in denen p positiv vorkommt. Streiche p aus den Klauseln, in denen es negiert vorkommt. Erhalte F' mit:

> F unerfüllbar F' unerfüllbar

> F' = F erfüllbar Sobald in der KNF-Formel F eine Klausel mit nur einem einzigen positiven Literal p vorkommt, kann man für p true einsetzen und daher alle Klauseln streichen, in denen p positiv vorkommt. Außerdem streicht man p aus denjenigen Klauseln, die p negativ enthalten. Diese Vorgänge nennt man auch „unit resolution“ und „unit subsumption“.

Davis&Putnam-Algorithmus Regeln (2) Regel 1 (Fortsetzung):

c) Wenn a) nicht zutrifft: (analog zu 1.b)F = …&(~p)&… streiche alle Klauseln, in denen p negiert vorkommt. Streiche p aus den Klauseln, in denen es positiv vorkommt. Erhalte F' mit:

> F unerfüllbar F' unerfüllbar

> F' = F erfüllbar

Verfahre bei der Regel 1.c) analog zu der vorherigen Regel 1.b): statt p einfach ~p einsetzen.

Davis&Putnam-Algorithmus Regeln (3) Regel 2: Positiv-Negativ Regel

F enthält Literal p nur positiv oder nur negativ (fixed polarity)

streiche alle Klauseln, die p enthalten

Erhalte F' mit: > F unerfüllbar F' unerfüllbar> F' = F erfüllbar

Wenn in einer Formel F ein Literal p nur mit einer festen Polarität (nur positiv oder nur negativ) vorkommt, so können wir p eine p erfüllende Belegung zuweisen:

• p positiv => weise p true zu

• p negativ => weise p false zu

und daher alle Klauseln streichen, die p enthalten; denn diese werden dann automatisch auch erfüllt.

Unsere Aussage nach diesem Schritt ist: F ist unerfüllbar gdw. die so erhaltene Formel F‘ unerfüllbar ist.

Davis&Putnam-Algorithmus Regeln (4) Regel 3: Lösche atomare Formeln

Sei F = (A v p)&(B v ~p)&Rmit A,B,R frei von p.

F' = (A v B)&R F unerfüllbar F' unerfüllbar

Davis&Putnam-Algorithmus Regel-BeispieleDie folgenden Beispiele sollen die 3 Regeln verdeutlichen:

Beispiele (Regel)

1. F = {p,q,~r},{p,~q},{~p},{r} (1.b, r=1) F' = {p,q},{p,~q},{~p} (1.c, p=0) F'' = {q},{~q} (1.a) F''' = 0 (leere Klausel)

2. F = {p,q},{~q},{~p,q,~r} (1.c, q=0) F' = {p},{~p,~r} (1.b, p=1) F'' = {~r} (1.c od. 2) F'' erfüllbar

3. F = {p,~q},{~p,q},{q,~r},{~q,~r} (2, ~r) F' = {p,~q},{~p,q} (3, p) F'' = {~q,q} (1.a) F'' = 1 erfüllbar.

Davis&Putnam-Algorithmus komplett (1)Voraussetzungen für die Anwendung des Algorithmus

1. F ist PL1-Formel in Pränexnormalform2. F skolemisiert (Existenzquantoren eliminiert)3. Die entstandene Matrix muss in KNF sein

Der komplette DP-Algorithmus hat 4 Punkte:

Step 1:Generiere eine oder mehrere QFLs und teste die Konjunktion alle bisher generierten Zeilen auf Erfüllbarkeit wie folgt:

Step 2:Regel 1 anwenden, sofern unit-clauses existieren (wdh. ggf. Step 2, bis keine mehr da sind)- Antwort: unerfüllbar => fertig.- Antwort: erfüllbar => Gehe zu Step 1- sonst: Gehe zu Step 3

Davis&Putnam-Algorithmuskomplett (2) Step 3:

Regel 2 anwenden bis jede Variable nur noch positiv und negativ auftaucht. (ggf. iterieren).Sind nun neue unit-clauses aufgetaucht, Goto Step 2

- Antwort: unerfüllbar => fertig.- Antwort: erfüllbar => Gehe zu Step 1- sonst: Gehe zu Step 4

Step 4:Regel 3 anwenden: eliminiere die erste atomare Formel p aus der ersten Klausel minimaler Länge. Ist Resultat wieder in KNF zu bringen, dann tue das und gehe zu Step 2.Sonst*) fertig mit Ausgabe „erfüllbar“.

Step 4 ist derjenige Teil des DP-Algorithmus, der für die exponentielle Laufzeit verantwortlich ist, denn das Zurückführen in KNF kann u.U. sehr lange Laufzeit haben. Dass man hierbei die Regel 3 auf Literale/Formeln aus den Klauseln minimaler Länge nimmt, hat den Vorteil, dass die most-constrained Variablen zuerst belegt werden. Diese Heuristik sorgt dafür, dass der Suchbaum möglichst weit oben „beschnitten“ wird und somit möglichst viele Möglichkeiten entfallen.

Davis&Putnam-AlgorithmusKNF vs. DNF

Erfüllbarkeit nicht direkt „ablesbar“

KNF erhalten wir automatisch, sofern QFL-Generator mit einer Formel in KNF gestartet ist!

=> DP-geeignet

Erfüllbarkeit leicht „ablesbar“

Erstellung zu komplex bei zu vielen quantoren-freien Zeilen (QFLs)

=> DP-ungeeignet

KNF DNF

Davis&Putnam-AlgorithmusEigenschaften (1) ...für endliche Herbrandexpansionen gilt:

Vollständig, korrekt und terminierend i.A. exponentielle Laufzeit

(SAT ist NP vollständig) Laufzeit schlecht, falls die

Erfüllbarkeitswahrscheinlichkeit einer Klauselmenge bei 50% liegt

polynomiell auf Horn-Klauseln(Klauseln mit nur einem positiven Literal)

Im Mittel O(n2), falls die Wahrscheinlichkeit eines Literals in einer Klausel positiv:negativ:überhaupt aufzutreten 1:1:1 ist.

...für unendliche Herbrandexpansionen gilt: DP terminiert nur für gültige Formeln F,

d.h. die Prozedur muss für ~F „unerfüllbar“ liefern.

Trotzdem ist DP anderen Algorithmen sogar „zu Fuß“ überlegen.

Davis&Putnam-AlgorithmusHeutige Implementationfunction DP(set-of-clauses D) : boolean {

// leere Klauselmenge D: erfüllbar if (D=={}) return true;// leere Klausel in D: unerfüllbarif (leere-Klausel in D) return false;// unit propagation rule if (unit-clause c in D) { c := c erfüllenden Wahrheitswert {true, false}; D' := vereinfachen(D); DP(D');}// splitting rule:a := select_unassigned_variable(D);a := true;D' := vereinfachen(D);if (DP(D')==true)return true else {

a := false;

D'' := vereinfachen(D);return DP(D'')

}

}

Wenig später (1962) veröffentlichten M.Davis, G. Logemann und D. Loveland ein Paper, in welchem die Implementierung des DP-Algorithmus auf einem Rechner im Vordergrund stand. Dabei schlugen sie Veränderungen des DP-Algorithmus, u.a. der Regel 3, vor -- in obigem Pseudo-Code „splitting rule“ genannt. Hier erkennt man noch besser den exponentiellen Charakter der Laufzeit.

II. EffizienteUnit Propagation

Hantao ZhangMark E. StickelSymp. On AI & Mathematics, 1996,„An Efficient Algorithm for Unit Propagation”.

Definitionen Klassisches Unit Propagation Unit Propagation von Crawford und Auton Unit Propagation von Zhang und Stickel

Definitionen

Unit Propagation (UP):Solange es unit clauses gibt, wende unit subsumption und unit resolution an.

Unit subsumption: eine Klausel wird erfüllt, weil ein Literal 1 ist.

Unit resolution: eine Klausel wird vereinfacht, weil ein Literal 0 ist.

Viele heutige SAT-Solver setzen unit propagation ein - auch der DP-Algorithmus!

Pro Fallunterscheidung im DP: 2 UPs (!)viele Millionen UPs können nötig sein

=> Jeder kleinste Vorteil zählt!

Warum ist Unit Propagation so wichtig?

Klassisches Unit Propagation

Klassisches Unit propagation:Sei S eine aussagenlogische Klauselmenge, v Literal.

Teile S in 3 Teilmengen auf:

• P={{v,P1},...,{v,Pn}} enthalten v

• Q={{~v,Q1},...,{~v,Qm}} enthalten ~v

• R={R1,...,Rn} enth. kein v Unit clause {v} tritt auf:

Q -> Q‘={Q1,...,Qm} (=Unit resolution)P wird gelöscht (=Unit subsumption) S=Q‘R

weit

ere

unit

cla

use

s?

Unit Propagation vonCrawford & AutonIdee: S‘ wird nicht explizit erzeugt!Jede Variable v: Speichere 2 Listen

1. Klauseln, die v positiv enthalten

2. Klauseln, die v negativ enthalten

Jede Klausel c erhält einen Zähler, der die Anzahl der unbelegten Variablen in c speichert, oder inactive ist, falls c erfüllt ist. Eine Klausel ist active, wenn der Zähler nicht inactive ist.

So funktioniert eine Variablen-Zuweisung von v:a) true:

1. verringere Zähler aller aktiven Klauseln, die v negativ enthalten um 1Zähler=0? leere Klausel => unerfüllbarZähler=1? neue unit-clause

2. Setze Zähler aller Klauseln, die v positiv enthalten, auf inactive

b) false (analog)

=> Laufzeit: O(n), n Anzahl Klauseln

Unit Propagation von Zhang & Stickel (1) Laufzeit: immer noch O(n), aber ein speed-up von

2 ist möglich durch folgende Verbesserungen:

1. Verzögere Klausel-Erfüllungstest2. Resolution nur auf dem ersten und letztem

aktiven Literal einer Klausel

Wie sieht die Datenstruktur aus?1. Literale einer Klausel in zusammenhängendem

Speicher-Array ablegen.2. Eine Klausel wird repräsentiert durch je einen

Pointer auf das erste & letzte Literal einer Klausel3. Verzicht auf Zähler an den Klauseln4. Zu jeder Variable v: halte 4 dynamisch

strukturierte Listen:1. clauses_of_pos_head(v): startet mit v2. clauses_of_neg_head(v): startet mit ~v3. clauses_of_pos_tail(v): endet mit v4. clauses_of_neg_tail(v): endet mit ~v

Unit Propagation vonZhang & Stickel (2)

So funktioniert die Variablen-Zuweisung von v:a) true:

1. Ignoriereclauses_of_pos_head(v) und clauses_of_pos_tail(v).(Verzögerte Subsumption)

2. Suche für alle Klauseln c in clauses_of_neg_head(v) das erste unzugewiesene Literal l und addiere c in clauses_of_pos_head(l) bzw. clauses_of_neg_head(l) (je nachdem, ob l positiv oder negativ ist.), außer ...

1. Ein Literal mit true wurde bei der Suche gefunden (d.h. c ist erfüllt). Addiere c in keine Liste.

2. Alle Literale in c sind false=> leere Klausel => unerfüllbar

3. l ist das letzte Literal in c=> neue unit clause entdeckt=> sammeln auf einem „stack of unit clauses“

...Analog behandeln: clauses_of_neg_tail(v),sowie den Fall, falls v := false.