二分決定図
BDDのサイズは、表現しようとする関数とその変数(引数)の順序をどうするかで決定される。BDDのサイズは変数の個数に対して、線形のオーダーから指数のオーダーまで様々である。 f ( x 1 , ... , x n ) {\displaystyle f(x_{1},\ldots ,x_{n})} というブール関数があったとき、これを二分決定図に表現する際に、根となるノードからどういう順番で変数を対応させるかによって、そのサイズは指数オーダー(2)にも線形オーダー(n)にもなる。例えば、 f ( x 1 , ... , x 2 n ) = x 1 x 2 + x 3 x 4 + ⋯ + x 2 n − 1 x 2 n {\displaystyle f(x_{1},\ldots ,x_{2n})=x_{1}x_{2}+x_{3}x_{4}+\dots +x_{2n-1}x_{2n}} という形式のブール関数を考える。変数の順序付けを x 1 < x 3 < ⋯ < x 2 n − 1 < x 2 < x 4 < ⋯ < x 2 n {\displaystyle x_{1}<x_{3}<\dots <x_{2n-1}<x_{2}<x_{4}<\dots <x_{2n}} とすると、この関数を表現する BDD のノード数は 2 n + 1 {\displaystyle 2^{n+1}} となる。
従って, f ( x 1 = 0 , x 2 = 1 , x 3 = 1 ) {\displaystyle f(x_{1}=0,x_{2}=1,x_{3}=1)} の値は 1 ということになる。
開始ノードから降りていったときに現われる変数の順序が(どの経路でも)同じである二分決定図を順序付き(ordered)BDDと呼ぶ。また、特定の規則によって簡約した二分決定図を既約(reduced)BDDと呼ぶ。左の図に示した二分決定木は、簡約することで既約な右の図へと変換される。簡約のための規則は以下のとおりである。
あるノード A {\displaystyle A} が子ノード A 1 {\displaystyle A_{1}} と A 2 {\displaystyle A_{2}} を持つ時、同様に A 1 {\displaystyle A_{1}} と A 2 {\displaystyle A_{2}} を子ノードに持つような、機能的に重複したノードは存在しない。
2つの子ノードが同じノードであるような、決定に関して意味のないノードは存在しない。