exercise sheet 2 question 2.c

Question

in the example assignment that is provided, in part "apply algorithm" at the end we have:

Apply(→, N_13,N_22) = (b ? Apply(→, N_2,N_1) : Apply(→, N_1,N_2)) = (b ? N_1 : N_2) = N_22

I want to know please how come the final answer of this part is N_22?

Comments

N_22 seems to have been defined as (b ? N_1 : N_2) before.

Answer 1

On slide 13, we defined β as  (b => true | (a => true | false)), and numbered it as N_22 (where (a => true | false) was called N_2, true was N_1, false was N_0).

The root node of N_13 and N_22 is in both cases b. Hence, we add the b node, and propagate the apply-call both on the high- and and the low-edges. We get:
(b ? Apply(→, N_2,N_1) : Apply(→, N_1,N_2))
Node N_1 is the 1-node. This turns Apply(→, N_2,N_1) to N_1 (as anything→true is always true), and it turns Apply(→, N_1,N_2) to N_2 (as true→X always depends precisely on X). Now, we have:
(b ? true : N_2) or (b ? N_1 : N_2) (as we called the true-leaf N_1)
But this exactly what we defined N_22 (the BDD of β) to be. Thus, our result is equal to N_22.

Comments

thanks for explanation

---

Martin is perfectly right. Note that we are not allowed to make copies of BDDs that are already there. So when trying to construct (b ? N_1 : N_2), the BDD package will find in the unique table a node with root b and children N_1 and N_2, and that node is N_22. Thus, this is to be reused and no new node is allowed to be introduced. That is very important to make BDD packages work.

Answer 2

i didn't understand for above question how we got final solution as  N_22? can anyone explain 

Comments

This answer was supposed to be a comment?