Write a four-variable function whose ROBDD has exactly 8 nodes under a stated order.
The nodes on a level are the different functions that remain there once the variables above are fixed, counting only those that depend on the level's variable. To reach a target, decide first how many functions each level must leave, then choose a function that leaves them. A level can hold no more nodes than there are assignments of the variables above it.
Suppose a task asks for a function of p, q and r with one node on p, one on q and two on r, under the order p q r. Level r must then leave two different functions that depend on r: the only two are r and ~r.
p
q
r
p q r
~r
Try k = (p | q) ^ r. Level q: with p = 0, k is q ^ r; with p = 1, it is ~r, which does not depend on q. So level q has one node.
k = (p | q) ^ r
p = 0
k
q ^ r
p = 1
Level r: with p and q both 0, k is r; otherwise it is ~r. Those are two functions that depend on r: two nodes.
So k meets that smaller task: 1, 1 and 2 nodes on its levels and the two terminals, 6 nodes with two terminals.
Given: order: a b c d;
order: a b c d;
Write a function f of a, b, c and d that depends on all four variables and whose ROBDD under the order a b c d has exactly 8 nodes with two terminals, terminals included.
f
a
b
c
d
a b c d
One definition, f = expression;, in the variables a, b, c and d, with any operator of the language. For example, a function of other variables might read m = s & t | ~u & v;.
f = expression;
m = s & t | ~u & v;
f depends on exactly a, b, c and d.
Under the order a b c d, its ROBDD, drawn with two terminals, has exactly 8 nodes, terminals included.
Watch the conditions: they show the variables f depends on and its node count with two terminals under the order a b c d, as you type.
In the diagram, count the nodes on each level, and decide which level needs one more or one fewer.
For that level, fix the variables above it and list the functions that remain, as in the example, to see which of them make its nodes.
Kata 2.4 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.