二分決定図（にぶんけっていず、Binary Decision Diagram、BDD）とは、ブール関数を表現するのに使われるデータ構造である。二分決定グラフあるいは（基本的には二分木のような構造であることから）二分決定木と呼ぶこともある。ビット(0あるいは1)の列を入力として、最終的に1つの 0/1 を返すような関数、すなわちブール関数は、環状構造を持たない有向グラフで表現できる。ノードのうちの大部分は決定ノードと呼ばれ、それぞれの決定ノードは2つの行き先、つまり2つの子ノードを持つ。決定ノードには「入力の何ビット目を読め」というラベルが与えられている。従って、与えられたブール関数の答えを得るには、指示に従って入力のビット列を読みながら、ビットが0か1かによって、分岐点ごとに2つの行き先のどちらかを選べば良い。さらに、このような決定を十分な回数行うと、2つの終端ノード、0終端あるいは1終端のどちらかに行き当たる。その場合には、どちらの終端が得られたかを、ブール関数の答えとして返す。例えば下の左図は、ブール関数 formula_1 を表す二分決定木と真理値表を示している。この木構造で、引数群の値の組み合わせに対応した関数の値はグラフを上から順にたどっていけば決定できる。従って、 formula_2 の関数値は、まず formula_3 から点線(formula_4)をたどって formula_5 ノードに行き、続いて実線(formula_6) をたどって formula_7 へ、最後に実線(formula_8)により1終端ノードにたどり着く。従って, formula_9 の値は 1 ということになる。開始ノードから降りていったときに現われる変数の順序が（どの経路でも）同じである二分決定図を「順序付き; ordered」BDDと呼ぶ。また、特定の規則によって簡約した二分決定図を「既約; reduced」BDDと呼ぶ。左の図に示した二分決定木は、簡約することで規約な右の図へと変換される。簡約のための規則は以下のとおりである。一般的に、BDDと言えば「既約な順序付き二分決定図」を指すのが普通である（既約で順序付きであることを強調する場合は ROBDD と記されることもある）。ROBDD の利点は特定の関数を最も簡単に表現している点にある。この特徴から、ブール関数を論理回路化するのに使われたり、機能の等価性の判定に使われたりする。根のノードから1終端ノードまでの経路は、そのBDDが表現しているブール関数が真(1)となる変数群の値を経路で表している（経路上に現われない変数の真理値は関数の値に影響しない）。このとき、あるノードから HIGH （子）ノードへの経路を通る場合、そのノードに対応する変数の値が 1 であることを示し、LOW ノードの場合は 0 であることを示す。このデータ構造を生み出すきっかけとなった考え方はシャノン展開である。スイッチング関数（ブール関数）は、1つの変数に着目した2つの部分関数に分割できる。そのような部分関数を部分木とみなせば、これを二分決定木で表現できる。二分決定図(BDD)は、Lee （1959年）が最初に紹介し、Akers （1978年）や Boute （1976年）でさらに研究が行われ、広まっていった。このデータ構造を使った効率的アルゴリズムの可能性を見出したのはカーネギーメロン大学の Bryant である。彼の行った拡張は（簡約表現のための）固定変数順序の使用と（圧縮のための）部分グラフの共有である。これらを適用することで、集合や関係を表現するための効率的なデータ構造とアルゴリズムができる。複数のBDDを共有するよう拡張することにより（1つの部分グラフを複数のBDDで利用する）、共有ROBDDというデータ構造が定義された。これを単に BDD と称するのが一般的となっている。より抽象的なレベルでは、BDD は集合や関係の圧縮表現とみなすことができる。他の圧縮との違いは、具体的な操作をその圧縮表現上で行うことができ、伸張する必要がない点である。BDDのサイズは、表現しようとする関数とその変数（引数）の順序をどうするかで決定される。BDDのサイズは変数の個数に対して、線形のオーダーから指数のオーダーまで様々である。formula_15 というブール関数があったとき、これを二分決定図に表現する際に、根となるノードからどういう順番で変数を対応させるかによって、そのサイズは指数オーダー（2）にも線形オーダー（n）にもなる。例えば、formula_16 という形式のブール関数を考える。変数の順序付けを formula_17 とすると、この関数を表現する BDD のノード数は formula_18 となる。しかし、formula_19 という順序付けにすると、ノード数は formula_20 で済む。従って、このデータ構造を実際に利用する際には変数の順序付けが非常に重要となる。最良の順序付けを見つける問題はNP困難であることが分かっている。任意の1より大きい定数 c について、最適な解の c 倍のサイズを持つOBDDを生成する順序付けを探す問題もNP困難である。ただし、最適な順序付けを探すための効率的なヒューリスティックが存在する。 (Topological Sort, MinFillなど)変数の順序をどう変えても常に指数オーダーとなる関数（変数順序付けに依存しない関数）も存在する。例えば、二進数の乗算がそのような関数の例である。BDD から派生したグラフ構造として、二分モーメント図(BMD)やゼロサプレス決定図(ZDD)がある。

出典:wikipedia