Follow Bryant's reduction of a three-variable tree and name the rule that removes one node.
It applies the three rules in a fixed order. R1 comes first and keeps one terminal of each value. Then each level is processed from the bottom up: R2 removes every node whose two edges lead to the same node, then R3 merges each node into an earlier one on the same variable with the same two children. Children are compared as they are once the levels below are reduced, not as they were in the tree.
Take k = b & c under the order a b c. Its tree has a node on a, two on b and four on c, though k does not depend on a.
k = b & c
a b c
a
b
c
k
R1 keeps one leaf of each value. On level c, the two nodes with b = 0 have both edges on 0: R2 removes them. The two with b = 1 have the same children, 0 and 1: R3 merges the one at a = 1 into the one at a = 0.
b = 0
b = 1
a = 1
a = 0
On level b, the nodes at a = 0 and a = 1 now have the same children: 0, and the one node left on c. R3 merges the second into the first.
On level a, both edges of the root now lead to the one node on b: R2 removes the root.
R1 removed 6 leaves, R2 3 nodes and R3 2, leaving one node on b, one on c and the two terminals.
Bryant's procedure reduces the decision tree of f = (a | b) & c under the order a b c. When R1 or R3 merges equal nodes, the leftmost one stays, with else edges drawn on the left.
f = (a | b) & c
Which rule removes the node on b reached by a = 1?
R1: merge duplicate terminals.
R2: remove a node whose two edges lead to the same node.
R3: merge a node into another with the same variable and the same children.
None: the node stays in the ROBDD.
Choose one of the four options: the rule that removes the node, or None when the node stays in the ROBDD.
One rule, or none.
Write the function each node on level c of the tree of f computes, then each node on level b, once the level below it is reduced.
f
For the node in question, ask whether its two edges now lead to one node, which is R2, or whether an earlier node on b has the same two children, which is R3.
Step through the example in Explore the example, to check that you apply the rules as the procedure does.
Kata 2.1 of Binary Decision Diagrams with CUDD on formal.org. The site checks the answer when you press Check answer; sign in to keep your progress.