Binary Decision Diagramm

Binary Decision Diagramm (BDD)

Binary Decision Diagramms, verkürzt BDD, sind reduzierte Funktionsgraphen und dienen zur Veranschaulichung von Wahrheitswerten: ”Wann wird wo etwas falsch bzw. wahr?”

Die Vorteile von BDDs sind ein häufig wesentlich geringerer Platzbedarf und eine endliche Anzahl von Rechenschritte. Es werden sogar höchstens so viele Rechenschritte benötigt, wie es Eingaben gibt.

Wenn man sich an die Wahrheitstabellen zurückerrinnert, so konnten diese auch zur Herleitung von Wahrheitswerten benutzt werden. Jedoch ist der Rechenaufwand hier exponentiell. In der Praxis können BDDs genau dasselbe wie Wahrheitstafeln, und versprechen eine geringere Komplexität.

Bei vorgegebener Variablenreihenfolge ist ein BDD eindeutig. Ist die Variablenreihenfolge innerhalb des BDD jedoch beliebig, so ist der BDD nicht unbedingt eindeutig und kann deshalb auch unterschiedlich viele Knoten enthalten. BDD sind bzgl. der Konstruktion etwas aufwendiger.