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)$$