Binary decision diagram

In computer science, a binary decision diagram (BDD) or branching program is a data structure that is used to represent a Boolean function. On a more abstract level, BDDs can be considered as a compressed representation of sets or relations. Unlike other compressed representations, operations are performed directly on the compressed representation, i.e. without decompression. Other data structures used to represent a Boolean function include negation normal form (NNF), and propositional directed acyclic graph (PDAG).

A Boolean function can be represented as a rooted, directed, acyclic graph, which consists of several decision nodes and terminal nodes. There are two types of terminal nodes called 0-terminal and 1-terminal. Each decision node ${\displaystyle N}$ is labeled by Boolean variable ${\displaystyle V_{N}}$ and has two child nodes called low child and high child. The edge from node ${\displaystyle V_{N}}$ to a low (or high) child represents an assignment of ${\displaystyle V_{N}}$ to 0 (resp. 1). Such a BDD is called 'ordered' if different variables appear in the same order on all paths from the root. A BDD is said to be 'reduced' if the following two rules have been applied to its graph:

...
Wikipedia