Here you can ask questions and find or give answers to organizational, academic and other questions about studying computer science.

1.1k questions

1.2k answers

1.6k comments

529 users

0 votes

I confused myself while trying to convert zdd to fdd

Sept 2022, 1d

1) Can you help me write ¬ba&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.

in # Study-Organisation (Master) by (850 points)

1 Answer

0 votes

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!

by (166k points)
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)).

Related questions

0 votes
1 answer
0 votes
1 answer
asked Feb 14, 2023 in * TF "Emb. Sys. and Rob." by obeng (260 points)
0 votes
2 answers
0 votes
1 answer
asked Aug 31, 2022 in * TF "Emb. Sys. and Rob." by ss (160 points)
Imprint | Privacy Policy
...