Sum an ADD over all its variables, and choose the result.
A multi-terminal BDD, or algebraic decision diagram (ADD), has terminals that are numbers rather than 0 and 1, and represents a function from assignments to numbers. Cudd_BddToAdd turns a BDD into the ADD with terminals 0 and 1. Cudd_addExistAbstract abstracts variables by summing: for each assignment of the other variables, it adds the function's values over every value of the abstracted ones.
Cudd_BddToAdd
Cudd_addExistAbstract
Take the ADD of 2·a + b, the value of the 2-bit number with bits a and b. Its terminals are 0, 1, 2 and 3.
2·a + b
a
b
Sum out b. With a = 0, the values for b = 0 and b = 1 are 0 and 1, which add to 1; with a = 1, they are 2 and 3, which add to 5.
a = 0
b = 0
b = 1
a = 1
The result is an ADD over a alone, with terminals 1 and 5: the function 4·a + 1.
4·a + 1
Each value left is a sum of the function's values over the variable abstracted.
Cudd_addExistAbstract abstracts variables from an ADD by summing over their values. f is a Boolean function of x0 to x3, and A is its ADD with terminals 0 and 1, from Cudd_BddToAdd.
f
x0
x3
A
What is A with all four variables summed out?
The number of assignments that satisfy f, as a constant.
The constant 1 when f is satisfiable, and 0 otherwise.
The number of nodes of f's BDD.
The largest terminal of A, which is 1.
Choose one of the four options.
One answer.
Sum out one variable at a time, as the example does: after x0, what does each remaining assignment of x1 to x3 carry?
x1
Try it on a function you can count by hand, such as x0 & x1 over x0 and x1: sum out both variables, and see which option the constant left matches.
x0 & x1
Kata 8.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.