convert bdd to fdd, how to convert rmnf presentation sets to fdd graph?

Question

1)feb 2024 VRS exam, 1g)
2) and same how to convert representation sets to zdd in 1f) ?

Comments

I reached here by 1) calculating dnf using truth table 2) converting dnf to rmnf.
After getting set representation of {{a,b,c},{a,c},{b,c},{}} which is rmnf.
How to convert this sets into FDD graph below??
vrs exam , feb 2024, Q1 part g)

Answer 1

ZDDs and FDDs make use of the interpretation of decision diagrams as sets of sets. While ZDDs store the full minterms of a DNF as sets of sets, FDDs store the monomials of a RMNF as sets of sets. How a set of set is represented by a decision diagram is explained on slides 140-142 of the BDD chapter of VRS.

For example, consider the following sets of sets {{a,b,c},{a,c},{b,c},{}} that represents the monomials of a Reed-Muller normal form. Converting this into a decision diagram with variable ordering c<b<a works as follows: First, we partition the sets into those containing "a", and those not containing "a":

• {a,b,c},{a,c} which yield {b,c},{c} for the positive edge
• {b,c},{} for the negative edge

For the positive edge, we continue with paritioning by "b":

• {b,c} which yield {c} for the positive edge
• {c} for the negative edge

So, we get a node labelled with "b" having two edges for the set representation of {c} which is just a node labelled with c having  positive and negative edges to the 1-leaf and 0-leaf, respectively.

For the negative edge of "a", we also continue with paritioning by "b":

• {b,c} which yield {c} for the positive edge
• {} for the negative edge

So, we get a node labelled with "b" having a positive edge to the c-node that we already have, and a negative edge to the 1-leaf. Note that the 0-leaf is represented by {} and the 1-leaf is represented by {{}}.