Ein binärer Entscheidungsbaum kann durch zwei Vereinfachungsoperationen vereinfacht werden. Erstens können identische Teilbäume zusammengefasst werden und zweitens können Knoten, von denen beide Kanten auf den selben Folgeknoten zeigen, entfernt werden. Führt man darüber hinaus eine feste Reihenfolge für die booleschen Variablen im Entscheidungsgraphen ein, so entsteht ein geordneter Entscheidungsgraph (Ordered Binary Decision Diagram, OBDD). Der OBDD bildet eine kanonische Darstellung einer booleschen Funktion, die gegenüber den bekannten konjunktiven und disjunktiven kanonischen Normalformen oft kompakter und leichter zu manipulieren ist.