Binary Decision Diagram

A rooted, directed acyclic graph with two types of vertices, terminal vertices and nonterminal vertices.

A binary decision diagram with root $v$ determines a boolean function $f_v(x_1,\dots ,x_n)$ in the following manner:

1. If $v$ is a terminal vertex:

   1. If $value(v)=1$ then $f_v(x_1,\dots ,x_n)=1$.
   2. If $value(v)=0$ then $f_v(x_1,\dots ,x_n)=0$.

2. If $v$ is a nonterminal vertex with $var(v)=x_i$ then $f_v(x_1,\dots ,x_n)$ is given by

   $$\overline{x_i}\cdot f_{low(v)}(x_1,\dots ,x_n)+x_i\cdot f_{high(v)}(x_1,\dots ,x_n)$$

Canonical Form

Ordered Binary Decision Diagram

• OBDD

Links

• Boolean Algebra
• Graph Theory
• Decision Tree