In the last lecture, we saw that every Boolean function can be uniquely represented by a reduced ordered BDD if we fix an order on the variables. In this lecture, we will see some examples and basic properties of this kind of representing Boolean functions. Let's start by a simple example. Consider the formula p and q or r. This represents the Boolean function that yields true if either both p and q are true or r is true. Now we want to look at the unique reduced ordered BDD, ROBDD of this function and we fix an order. Let's fix the order, p is less than q, is less than r. Well, then we get p on top and it depends on p. If p is true, we still should look at q and then also look at r. If p is false, we only need to look at r. If you consider all cases, you can figure out that this is the resulting reduced ordered BDD. We saw its unique. So it cannot be the case that you get something else. This is the only reduced ordered BDD representing this Boolean function. In such a reduced ordered BDD and in general, in every BDD, every node itself represents also a Boolean function. How can we think of that? Well, we could consider the ROBDD simply take the part of the original ROBDD that is reachable from this particular node, and this particular node is chosen as the root. Again, we have an ROBDD and that represents a Boolean function. So it's good to think of every node in the ROBDD is a Boolean function itself. All nodes of a reduced ordered BDD represent distinct Boolean functions. Since if two would represent the same, then they can be shared by applying merge and elimination steps, contradicting the property of being reduced. The next example deals with a by implication operator. So let's figure out some properties of the by implication. Well, what's the definition? P by implication q yields true if and only if p and q are equivalent. That is, they are both true or both false. If that's the case, it yields true. If they are different, then it yields false. One can check that this property is associative. That means if I write down p by implication, q by implication r, I can put the parenthesis in two different ways, but they show equivalent formulas. So we can simply leave out the parenthesis since for the Boolean function, it doesn't matter how we put them. Now again, we fix an order on the variables. Again, p less than q, less than r, and now we build the ROBDD of this function. It turns out to be we get this picture. How can we think about it? Well, a property of this function is that it yields true if and only if the number of variables that is false is even. Since if we look at the function, it has the property if we take an arbitrary variable p, q, or r and if we swap its value, then we swap its results. So if all of them are true, then clearly the result will be true. But if we swap one of them, the result will be false. If swap one more, the result will be true again and that is the argument for this observation. From this observation, we can build this ROBDD. We get to the one if we always go to the left or we go to the right twice. So an even number of times, it is false and we go to zero if we go to the right an odd number of times. Sometimes in literature, you see an alternative notation. If you look at this picture, you see quite curved arrows and some people try to avoid that. A standard way to do that is to use solid arrows for the true branch and dashed arrows for the false branch. If you do that, instead of this picture, you can write exactly the same in this way where you do not need curved arrows. Let's consider this example in some more detail. We can see that sharing really helps. If we take the same Boolean function but we do not do sharing, so we only have the unique reduced ordered decision tree, then instead of this BDD, we get this tree and this is not yet very convincing. But if we don't do this for three variables with four n variables, so we take the Boolean function represented by p_1 by implication p_2 by implication 2, and so on until the p_n, then by the same approach for the shared version, the reduced ordered BDD, we get 2n minus 1 nodes. While if we do the tree version, nothing can be shared. So then we get 2 to the power n minus 1 nodes, and there is an exponential gap in between. So this convincingly showed that the step of sharing for BDDs really helps to get an efficient representation. The next example we consider is the following Boolean function. Now we have six Boolean variables: p_1, p_2, p_3, and q_1, q_2, and q_3. The formula is p_1 or q_1, and p_2 or q_2, and p_3 or q_3. Now we will consider two different orders. The first order we consider is p_1 is less than q_1 is less than p_2 is less than q_2 less than p_3 less than q_3. Then we get the following reduced ordered BDD. We want p_1 on top. In case p_1 and q_1 both are false, we get zero since then the first conjunct is false and the whole formula is false. But no matter whether p_1 is true or q_1 is true, we should look at p_2 and this node is shared, that is a p_2 node. From p_2 on, we do exactly the same. In that way, we get this reduced ordered BDD. Instead, we could chose another order. For instance, p_1 less than p_2 less than p_3, and then less than q_1 less than q_2 less than q_3. If you do this, again we get a unique reduced ordered BDD, but it looks completely different. We get the following pattern. We get p_1 on top center. That's the smallest. On the next level, we get p_2. The level below, we get p_3. Now the observation is, all these eight nodes we get below the p_3 all represent distinct Boolean functions. The leftmost one is just true. The next one depends on q_3. The next one depends on q_2 and q_3, and so on. So you can argue that all of these eight question marks represent distinct Boolean functions. So no sharing is possible at all. More general, if we generalize this to n nodes, 2n variables rather than the 2 times 3 we saw in this example, we get exactly the same phenomenon. In the one order, we get a BDD which is very efficient and having exactly two n-nodes since every variable occurs exactly once as a node. If we do the other order, then we get an exponentially big BDD since at the level of q_1, there are 2 to the power n-distinct nodes. So on top part, nothing can be optimized. Maybe below the q_1, something can be optimized, but we know for sure that there are 2 to power n distinct nodes on the level of q_1. So distinct orders may have addresstict result on the size of the ROBDDs that can be an exponential gap in-between. So the question now is, how to choose an order if you look at the formula and we give a general heuristic. Choose the order in such a way that variables close to each other in the formula are also close in the order. In the formula we see, p_1 and q_1 are close to each other, p_2 and q_2 are close to each other. In the first order, indeed in the order they are close to, and in the second one, they are far apart. So following this heuristic, then often we get feasible ROBDDs. Concluding, Boolean functions of n-variables described by a formula, can always be uniquely represented as a reduced ordered BDDs. In many cases, it has a feasible size, the size is much smaller than 2 to the power n. This strongly depends on choosing a suitable order on the variables. In the next lecture, in fact, the next two lectures, we will give an algorithm to compute such reduced ordered BDDs. But for getting a feeling of what's going on and what the BDDs are, it's recommended first to do some quizzes. Thank you.
