reduced ordered binary decision diagram, ROBDD, ein geordneter binärer EntscheidungsgraphG = (V, E, index), bei dem es keinen Knoten ν ∈ V gibt, dessen low- und high-Nachfolgerknoten (binärer Entscheidungsgraph) identisch sind, und es keine zwei Knoten ν, w ∈ V so gibt, daß der binäre Entscheidungsgraph, der aus allen Knoten und Kanten besteht, die von v aus erreichbar sind, isomorph (isomorphe binäre Entscheidungsgraphen) zu dem binären Entscheidungsgraph ist, der aus allen Knoten und Kanten besteht, die von w aus erreichbar sind.

Die Definition reduzierter geordneter binärer Entscheidungsgraphen impliziert zwei Reduktionsregeln. Sind für einen Knoten v die low- und high-Nachfolgerknoten identisch, so kann der Knoten ν gelöscht werden. Alle in ν einlaufenden Kanten laufen nun in den Nachfolgerknoten von ν ein. Sind die low-Nachfolgerknoten ebenso wie die high-Nach-folgerknoten von zwei Knoten ν und w identisch, so können wir einen der beiden Knoten ν oder w löschen und die in ihm eingehenden Kanten auf den anderen umlenken. Man spricht in diesem Zusammenhang von der Reduktion geordneter binärer Entscheidungsgraphen.

Für eine feste Variablenordnung (geordneter binärer Entscheidungsgraph) sind reduzierte geordnete binäre Entscheidungsgraphen eine kanonische Darstellung Boolescher Funktionen. Die Kosten eines reduzierten geordneten binären Entscheidungsgraphen einer Booleschen Funktion hängen aber in der Regel sehr von der gewählten Variablenordnung ab. Um eine effiziente Darstellung einer Booleschen Funktion f zu erhalten, muß eine Variablenordnung gefunden werden, für die der reduzierte geordnete binäre Entscheidungsgraph von f minimale Kosten hat. Man spricht in diesem Zusammenhang von BDD-Minimierung.