Write a function whose BDD is large under one stated order and small under another.
An order is good for a function when the variables the function combines are near each other, so that few different functions remain below each level. Which variables those are depends on the function. So the order that makes one function small can make another large, and the same function can be small under one order and large under another.
Take k = (w | y) ^ (x | z). It combines w with y, and x with z.
k = (w | y) ^ (x | z)
w
y
x
z
Under the order w y x z, each pair is together: k has 5 nodes with complement edges.
w y x z
k
Under the order w x y z, each pair is split, and the diagram must remember w while it reads x: 7 nodes.
w x y z
So k is small under the order that keeps its pairs together. A function that combines other variables is small under another order.
Given: order: x1 y1 x2 y2 x3 y3;
order: x1 y1 x2 y2 x3 y3;
Write a function f of x1, x2, x3, y1, y2 and y3 whose BDD has at least 11 nodes under the order x1 y1 x2 y2 x3 y3, and at most 7 nodes under the order x1 x2 x3 y1 y2 y3, counting nodes with complement edges.
f
x1
x2
x3
y1
y2
y3
x1 y1 x2 y2 x3 y3
x1 x2 x3 y1 y2 y3
One definition, f = expression;, in the six variables, with any operator of the language. For example, a function of other variables might read m = (s | t) & ~u;.
f = expression;
m = (s | t) & ~u;
At least 11 nodes under the order x1 y1 x2 y2 x3 y3.
At most 7 nodes under the order x1 x2 x3 y1 y2 y3.
With complement edges, terminal included.
Watch the conditions: they show your function's node count under each of the two orders, as you type.
The diagram is drawn under the order x1 y1 x2 y2 x3 y3: a level with one node there is one where your function lets the diagram forget what it read above.
Decide which variables your function combines, and check that the second order keeps them together while the first splits them.
Kata 4.3 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.