二分決定図
一般的に、BDDと言えば「既約な順序付き二分決定図」を指すのが普通である(既約で順序付きであることを強調する場合は Reduced Ordered Binary Decision Diagram(ROBDD)と記されることもある。なお、BDDのうち、一部のみ簡約されているものを ROBDD と呼ぶのも間違いではないが、そのようなBDDは扱いにくく、通常は2つの簡約化規則を適用してこれ以上簡約化規則を適用できない状態のROBDDを一般的に使用されるROBDD、さらに単にBDDと呼ぶのが通常である。なお、既約でも順序付きでもないBDDはUnordered BDDであるが、特にUnorderedであることに関する研究対象としてはともかく、BDDとしてのコンパクト性やROBDDの生成アルゴリズムの処理時間等の実学的観点からは、あまり重要なBDDではないといえる)。ROBDD の利点は特定の関数を最も簡単に表現している点にある。この特徴から、ブール関数を論理回路化するのに使われたり、機能の等価性の判定に使われたりする。
根のノードから1終端ノードまでの経路は、そのBDDが表現しているブール関数が真(1)となる変数群の値を経路で表している(経路上に現われない変数の真理値は関数の値に影響しない)。このとき、あるノードから HIGH (子)ノードへの経路を通る場合、そのノードに対応する変数の値が 1 であることを示し、LOW ノードの場合は 0 であることを示す。