Ein rekursives Backtracking-Suchverfahren für die aussagenlogische Erfüllbarkeit, das Variablenteilung, Unit-Propagation (boolesche Konsistenzweitergabe), Eliminierung reiner Literale und systematisches Backtracking zur Entscheidung der Erfüllbarkeit einer CNF-Formel integriert.

Prinzip

Die Suche durch Ableitung erzwungener Belegungen (Unit-Propagation) und Eliminierung offensichtlicher Optionen (pure Literale) reduzieren, nur bei Bedarf auf Variablen verzweigen und bei Widersprüchen zurückspringen, um einen exponentiellen, aber stark beschneidbaren Suchbaum zu erkunden.

Demonstration

Zur Entscheidung der Erfüllbarkeit von (A ∨ B) ∧ (¬A ∨ C) ∧ (¬B ∨ ¬C) führt der Algorithmus Unit-Propagation aus, wenn ein-Einheits-Klauseln erscheinen, wählt ein Verzweigungsliteral (z. B. A), untersucht rekursiv A = wahr und A = falsch und springt bei Widerspruch zurück, bis eine Lösung oder eine Unlösbarkeitsbegründung gefunden ist.

Fehlanwendung

DPLL als rein gierige Suche ohne Pflege und Anwendung von Unit-Propagation oder Klausel-Lernen zu behandeln, führt zu redundanter Exploration und starker Leistungsverschlechterung bei vielen SAT-Instanzen.

Konsequenz

Richtig angewandt kann DPLL viele praktische SAT-Instanzen effizient entscheiden, indem große Teile des Suchraums beschnitten werden; es bildet die Grundlage moderner SAT-Solver und ermöglicht konfliktgesteuerte Erweiterungen.

Umkehrung

Das Konzept umkehren durch blinde, vollständige Aufzählung aller Belegungen ohne Propagation oder Backtracking-Heuristiken; das bleibt korrekt, verliert aber die skalierbare Beschneidung und Strukturausnutzung.

Abgrenzung

Gilt für aussagenlogische Formeln in KNF und für Entscheidungsverfahren, die auf boolescher Struktur beruhen; es behandelt nicht ohne Weiteres Theorien mit interpretierten Funktionen (SMT), außer in Kombination mit theorie-spezifischem Reasoning.

Semantische Spannung

Steht im Spannungsfeld zu rein auf Resolution ausgerichteten Verfahren: Resolution erzeugt global Konsequenzen durch Klauselkombination, während DPLL Suche mit lokaler Propagation und Verzweigungsentscheidungen priorisiert.

Synthese

DPLL verbindet lokale logische Deduktion (Unit-Propagation und Eliminierung reiner Literale) mit systematischer Suche und Backtracking, um SAT-Lösen in eine steuerbare Erkundung eines beschneidbaren Belegungsbaums zu überführen und bildet so das algorithmische Rückgrat moderner propositionaler Entscheidungsmethoden.