Find an order under which a six-variable function's BDD has at most 9 nodes, down from 20.
A function has one ROBDD for each variable order. On each level, the diagram needs one node for each different function that remains once the variables above are fixed. When two variables that the function combines are far apart in the order, the diagram must remember the first one's value until it reads the second, and more functions remain on the levels between them.
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 x y z, each pair is split. On level y, fixing w and x leaves y & z, y, z or 1: two of these depend on y, so level y has 2 nodes. In all, k has 7 nodes with complement edges.
w x y z
y & z
k
Under the order w y x z, each pair is together. Once w and y are read, what remains is 0 or x | z, so the levels below need one node each: 5 nodes in all.
w y x z
x | z
Bringing together the variables that k combines took it from 7 nodes to 5.
Given: order: p q r s t u; f = (p ^ s) & (q ^ t) | r & u;
order: p q r s t u; f = (p ^ s) & (q ^ t) | r & u;
Under the order p q r s t u, the BDD of f = (p ^ s) & (q ^ t) | r & u has 20 nodes with complement edges.
p q r s t u
f = (p ^ s) & (q ^ t) | r & u
Find an order of the six variables under which it has at most 9.
An order of all the variables, top to bottom, in the list: drag a row by its handle, or select it and move it with its arrows or with Alt and an arrow key. The list starts in the order the task gives. For example, an order of other variables might read w y x z.
Each of p, q, r, s, t, u exactly once.
At most 9 nodes, with complement edges.
Watch the conditions: they show that your order holds each variable once, and its node count with complement edges, as you change it.
Read the diagram level by level: a level with several nodes is one where the diagram still remembers a variable read above it.
Move one variable at a time and watch the count, as the example compares two orders.
Kata 4.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.