Using the encoding of symbols in Example 12.28, develop a BDD that represents the relation consisting of the tuples (b,b), (c,a), and (b,a). You may order the boolean variables in whatever way gives you the most succinct BDD.
As a function of n, how many nodes are there in the most succinct BDD that represents the exclusive-or function on n variables. That is, the functions is true if an odd number of the n variables are true and false if an even number are true.
For each variable, we put it on one layer. Their is only two possible arrangement left 0 or left 1. So for each variable, we need at most two nodes for it. And we need only one node for the first variable. So the answer is:
2n-1
For example, when n is 4:
Modify Algorithm 12.29 so it produces the intersection (logical AND) of two BDD's.
There are two places to modify:
a. BASIS: Zero variables. The BDD's must both be leaves, labeled either 0 or 1. The output is the leaf labeled 1 if both
input are 1, or the leaf labeled 0 if either
is 0.
b. INDEUCTION 2. ...The first of these BDD's represents the function that is true for all truth assignments that have y_{1} = 0 and that make both
of the give BDD's true.