Reduced Ordered Binary Decision Diagram
Reduce a Boolean decision graph and see how variable order affects its size.
Free theory articleReduce a Boolean decision graph and see how variable order affects its size.
Concept & interpretation
A Binary Decision Diagram (BDD) is a data structure that represents a Boolean function. When the diagram is ordered (variables appear in the same order on all paths) and reduced (isomorphic subgraphs are merged, and nodes with identical children are eliminated), it becomes a canonical Reduced Ordered Binary Decision Diagram (ROBDD).
Interactive Experiment
You can experiment with different variable orders and functions using the interactive module athttps://riano.app/module/reduced-ordered-binary-decision-diagram.
- Set Function to "Multiplexer".
- Set Variable order to "xyz". Observe that the graph has 3 nonterminal nodes.
- Change the Variable order to "zxy". Observe that the number of nonterminal nodes increases to 4.
- Set Function to "Parity" and observe the symmetric structure.
- Change Assignment mask to "3" (which sets x=false, y=true, z=true in xyz order depending on binary representation) and follow the highlighted path to the terminal node.