Question

exercise sheet 3 question 2.b:

would you please give a hint how it works? I read a lot but couldn't understand how to solve this problem!!!

Answer 1

So you are looking for hints on how to convert a ZDD to Reed-Muller-Normal-Form. There you go:

1. Use Davio-Decomposition to build a FDD and read the RMNF from that.
2. Non-overlapping-DNF-to-RMNF:

The Non-overlapping-DNF-to-RMNF conversion works like this:

1. Read the DNF from the ZDD/ROBDD
2. Make sure that the DNF is non-overlapping (e.g. containing no pair of co-clauses that can be satisfied by the same assignment)
3. Since the co-clauses don't overlap, you the disjunctions are here the same as excluseive-or. Hence, replace all the OR by XOR.
4. Now the formula consists of XOR, conjunction, and negation. RMNF doesn't allow negation. Replace ¬X by (1 XOR x)
5. Multiply the inner XOR-terms out.