二分決定図
ビット(0あるいは1)の列を入力として、最終的に1つの 0/1 を返すような関数、すなわちブール関数は、閉路のない有向非巡回グラフで表現できる。ノードのうちの大部分は決定ノードと呼ばれ、それぞれの決定ノードは2つの行き先、つまり2つの子ノードを持つ。決定ノードには「入力の何ビット目を読め」というラベルが与えられている。従って、与えられたブール関数の答えを得るには、指示に従って入力のビット列を読みながら、ビットが0か1かによって、分岐点ごとに2つの行き先のどちらかを選べば良い。さらに、このような決定を十分な回数行うと、2つの終端ノード、0終端あるいは1終端のどちらかに行き当たる。その場合には、どちらの終端が得られたかを、ブール関数の答えとして返す。
例えば下の左図は、ブール関数 f ( x 1 , x 2 , x 3 ) {\displaystyle f(x_{1},x_{2},x_{3})} を表す二分決定木と真理値表を示している。この木構造で、引数群の値の組み合わせに対応した関数の値はグラフを上から順にたどっていけば決定できる。従って、 ( x 1 = 0 , x 2 = 1 , x 3 = 1 ) {\displaystyle (x_{1}=0,x_{2}=1,x_{3}=1)} の関数値は、まず x 1 {\displaystyle x_{1}} から点線( x 1 = 0 {\displaystyle x_{1}=0} )をたどって x 2 {\displaystyle x_{2}} ノードに行き、続いて実線( x 2 = 1 {\displaystyle x_{2}=1} ) をたどって x 3 {\displaystyle x_{3}} へ、最後に実線( x 3 = 1 {\displaystyle x_{3}=1} )により1終端ノードにたどり着く。
しかし、 x 1 < x 2 < x 3 < x 4 < ⋯ < x 2 n − 1 < x 2 n {\displaystyle x_{1}<x_{2}<x_{3}<x_{4}<\dots <x_{2n-1}<x_{2n}} という順序付けにすると、ノード数は 2 n {\displaystyle 2n} で済む。
従って、このデータ構造を実際に利用する際には変数の順序付けが非常に重要となる。最良の順序付けを見つける問題はNP困難であることが分かっている。任意の1より大きい定数 c について、最適な解の c 倍のサイズを持つOBDDを生成する順序付けを探す問題もNP困難である。ただし、最適な順序付けを探すための効率的なヒューリスティックが存在する。 (Topological Sort, MinFillなど)
変数の順序をどう変えても常に指数オーダーとなる関数(変数順序付けに依存しない関数)も存在する。例えば、二進数の乗算がそのような関数の例である。BDD から派生したグラフ構造として、二分モーメント図(英語版)(BMD)やゼロサプレス型二分決定グラフ(英語版)(ZDD)がある。