## [Reduktion Binärer Entscheidungsdiagramme](/de/node/60056) Definition Eine graphbasierte Technik zur Darstellung boolescher Funktionen als gerichtete azyklische Graphen (Binary Decision Diagrams, BDDs) zusammen mit Reduktionsregeln (Zusammenführen isomorpher Teilgraphen und Eliminieren redundanter Tests), die für eine feste Variablenordnung eine kanonische reduzierte Form (ROBDD) erzeugen können und so effiziente Äquivalenz- und Erfüllbarkeitsprüfungen ermöglichen. ## Prinzip Prinzip Die Funktion als Entscheidungsgraph darstellen und zwei Kernreduktionsregeln anwenden: (1) isomorphe Teilgraphen zusammenführen (Unique-Table/Sharing) und (2) Knoten entfernen, deren low- und high-Nachfolger identisch sind; mit fester Variablenordnung liefern diese Reduktionen eine kanonische Form der booleschen Funktion. ## Demonstration Demonstration Gegeben sei eine boolesche Funktion f über Variablen x1 < x2 < x3; konstruieren Sie den vollständigen Entscheidungs-DAG und wenden Sie Reduktion an: identische Teilgraphen zusammenführen und Knoten mit identischen low/high-Nachfolgern entfernen, sodass eine kompakte ROBDD entsteht, die mittels Pointer-Gleichheit auf Äquivalenz mit einer anderen Funktion unter derselben Ordnung geprüft werden kann. ## Fehlanwendung Fehlanwendung Die Annahme, BDD-Reduktion liefere stets eine kompakte Darstellung unabhängig von der Variablenordnung — tatsächlich können ungünstige Ordnungen zu exponentieller Aufblähung führen; ebenso ist der Einsatz von BDDs für Funktionen, die andere Zerlegungsstrategien benötigen (z. B. arithmetische Übertragsketten), ohne Alternativen zu prüfen, fehlleitend. ## Konsequenz Konsequenz Bei gut gewählter Variablenordnung liefert die Reduktion eine kanonische Form, die polynomiellen Äquivalenztest erlaubt und viele symbolische Boolesche Operationen effizient implementierbar macht; sie bildet auch die Grundlage für Model Checking und symbolische Manipulationstools. ## Umkehrung Umkehrung Im Gegensatz zu CNF-SAT oder expliziter Wahrheitswertextension: Diese Methoden enumerieren Belegungen oder Klauseln, während reduzierte BDDs eine geteilte strukturelle Darstellung bieten; die Umkehrung empfiehlt sich, wenn die BDD-Größe unbeherrschbar wird und enumeration-basierte Algorithmen günstiger sind. ## Abgrenzung Abgrenzung Gilt für boolesche Funktionen und hängt entscheidend von einer festen Variablenordnung ab; sie vermeidet nicht die worst-case-exponentielle Größe für manche Funktionen und ist nicht direkt für nichtboolesche oder hochgradig arithmetische Objekte geeignet ohne Zerlegung. ## Semantische Spannung Semantische Spannung Spannung zwischen OBDD (geordnet, reduziert) und anderen Repräsentationen wie FBDD (freie BDDs), SDDs oder CNF-Kodierungen: Abwägungen betreffen Kanonizität, Ordnungsabhängigkeit und welche Klassen von Funktionen kompakt darstellbar sind. ## Synthese Synthese Die BDD-Reduktion wandelt einen Entscheidungsprozess für eine boolesche Funktion in einen kanonischen geteilten Graphen um, indem isomorphe Teilgraphen zusammengeführt und Redundanzen unter einer festen Variablenordnung entfernt werden; die resultierende ROBDD unterstützt bei kleiner Größe effiziente Äquivalenztests und symbolische Operationen.