example solutions for assignment 3

Question

in example solutions (https://es.cs.uni-kl.de/teaching/vrs/exercises/03-Solutions.pdf) page 43, while computing the constraint algorithm, the answer to Constrain(N_18,N_24) =  N25 and Constrain(N_15,N_23) = N6 but we didn't have these nodes (N6 and N25) in the ROBDDs that we created for β and ϕ. 

So why do we add these two new nodes?

Answer 1

N_6 and N_25 belongs to the final bdd after apply constrain algorithm. That is mentioned for all to understand, how we got those new nodes.

Adding those nodes is optional, at the end the Shannon normal form and the graph needs to be correct.

Comments

N_6 and N_26 are just names. Since our original BDDs didn't have the particular structure (c?1:0), we didn't have a name for it. Hence, we create a new name N_6. As the said node before, we also didn't have nodes pointing to it. That's why also needed to introduce the new name N_26 (d?1:N_6).

---

Martin has written essentially everything that had to be written. Let me just add how you have to read the function "CreateNode" which is called in the BDD algorithms at the end. By the name, it suggests to just create a node, however, as revealed later in the chapter, currently on slide 112, you can see that first it checks whether such a node already exists by inspecting a unique table. That is very important to make BDDs work correctly. Clearly, if such a node does exist, it is reused, otherwise a new one has to be created.