Binary Decision Diagram

boolean-algebra

Definition

Binary Decision Diagram

Binary decision diagrams are a different method of representing Boolean functions.

Essentially, they are represented as directed graph, where vertices are variables and edges can (but don’t have to) represent negations. An edge $(v_1,v_2)\in V(G)$ can therefore be represented as:

• Solid Edge: $v_1$
• Dashed Edge: $\neg v_1$

Example:

This diagram can be represented as the following disjunctive normal form:

$$f=(a\wedge c)\vee (\neg a\wedge b)$$

Production Rules

Deletion Rule

A vertex $x_i$ can be deleted and its incoming edges from $x_i$ can be moved to $x_k$ if both outgoing edges point from $x_i$ to $x_k$.

Example:

Merging Rule

If we have two copies of $x_i$​ that refer exactly to $x_k$​ and $x_{{}_l}$​, we can merge (combine) the copies of $x_i$​.

Example:

Examples

Simple Example

$$\begin{array}{rl}f& =(a\wedge c)\vee (\neg a\wedge b)\\ & =(\neg a\vee c)\wedge (a\wedge b)\\ & =\mathrm{ITE}(a,\mathrm{ITE}(c,1,0),\mathrm{ITE}(b,1,0))\end{array}$$