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 can therefore be represented as:

• Solid Edge:
• Dashed Edge:

Example:

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

Production Rules

Deletion Rule

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

Example:

Merging Rule

If we have two copies of ​ that refer exactly to ​ and ​, we can merge (combine) the copies of ​.

Example:

Examples

Simple Example