zdd2fdd conversion

Question

I confused myself while trying to convert zdd to fdd

Sept 2022, 1d

1) Can you help me write ¬b⊕a&b&c to its DNF form?

2) Can you help me draw the set representation to ZDD? I tried snf&davio decompisition but cannot get the graph in the solution provided.

I get the overall idea from the lecture and exercise but couldnt understand rightly.

Answer 1

There is a similar question with an answer that should also help you: see https://q2a.cs.uni-kl.de/3413/fdd-to-zdd-09-2022-1d

But it is not difficult: ¬b⊕a&b&c is almost in DNF:

    ¬b⨁a&b&c
    = b&(¬1⨁a&1&c) | ¬b&(¬0⨁a&0&c)
    = b&(a&c) | ¬b&(1⨁0)
    = a&b&c | ¬b

For the set representation of the ZDD, Davio composition is useless (it is used for FDDs). Instead, you need the full DNF where all minterms are listed. In the above DNF, we just have one minterm a&b&c and a cube ¬b that is to be expanded to four minterms:

      a&b&c | ¬b
    = a&b&c | a&¬b | ¬a&¬b
    = a&b&c | a&¬b&¬c | ¬a&¬b&¬c | a&¬b&c | ¬a&¬b&c

The latter gives us the set representation of the minterms:

    {{a,b,c},{a},{},{a,c},{c}}

And now, we can draw the ZDD!

Comments

I got the clarification for my second question. Thank you.

For my first question. Can you please explain the trick or formula used in this step?
¬b⨁a&b&c = b&(¬1⨁a&1&c) | ¬b&(¬0⨁a&0&c)

in the case of (b⨁a&b&c) = b&(1⨁a&1&c) | ¬b&(0⨁a&0&c) Is it right?

---

The trick was just to use the Shannon decomposition that we usually use for computing SNF or BDDs. It is also very useful for computing DNF and also for CNF (in the dual way).

---

Thank you so much for the tip :)

So when I consider b=1|0 i get (¬1⨁a&1&c) | (¬0⨁a&0&c)
but need to get b&(¬1⨁a&1&c) | ¬b&(¬0⨁a&0&c). I couldn't get this.

---

Any variable is either true or false in 2-valued propositional logic. So, if we consider a formula like ¬b⨁a&b&c and a variable like b, we can consider the cases where b is 1 or 0. In each case the formula simplifies since b is eliminated. However, the original formula ¬b⨁a&b&c is not equivalent to (¬1⨁a&1&c) | (¬0⨁a&0&c) (since b does no occur in the latter). Instead, it is equivalent to b&(¬1⨁a&1&c) | ¬b&(¬0⨁a&0&c) which is nothing else but the Shannon decomposition. If a CNF is needed, you can also decompose it this way (!b|(¬1⨁a&1&c)) & (b|(¬0⨁a&0&c)).