A binary decision diagram (BDD) is a data structure that is used to represent a Boolean function. A Boolean function can be represented as a rooted, directed, acyclic graph, which consists of decision nodes and two terminal nodes called 0-terminal and 1-terminal. Each decision node is labeled by a Boolean variable and has two child nodes called low child and high child. The edge from a node to a low (high) child represents an assignment of the variable to 0 (1). Such graph is called BDD if the variables occur in the same ordering on all paths and it is reduced according to two rules:

* Merge any isomorphic subgraphs.
* Eliminate any node whose two children are isomorphic.

A path from the root node to the 1-terminal represents a variable assignment for which the represented Boolean function is true. If the path descends to a low child (high child) from a node, then the node’s variable is assigned to 0 (1).

desenho de 9li