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

1.1k questions

1.3k answers

1.7k comments

556 users

0 votes

How is SNF converted or expanded to CDNF in this question? I tried backtracking from the SNF but couldn't get the correct CDNF in the end. I tried getting the set representation of the given BDD (in 1.e ) and converted it into CDNF but I ended up with the FDD (1.g) of the BDD.

How do we expand the SNF to CNDF in the process to find ZDD from BDD?

I have taken this question from the VRS paper on 14th February 2024, Problem 1) e), f) and g).

in * TF "Emb. Sys. and Rob." by (360 points)
edited by

1 Answer

0 votes
 
Best answer

To convert a formula into a ZDD or vice versa, you have to consider the set representation of the minterms, where only the positive variables are listed in the sets, and variables not listed are considered false. These minterms can also be written as a DNF, which is then the maximal DNF that lists a corresponding minterm for each satisfying assignment.

SNFs are essentially formula representations of BDDs. Therefore, we can also get DNFs or CNFs from them. An if-then-else operator (p → f0 | f1) with a variable p and formulas f0 and f1 can be written as

  • (p → f1 | f0) = (!p|f1) & (p|f0) 
  • (p → f1 | f0) = (!p&f0) | (p&f1)

By repeating this, you can create a DNF or CNF from any SNF. For example, consider the following example: 

    a → (c → 0 | 1) | (b → (c → 0 | 1) | 1)
    = a → !c | (b → !c | 1)
    = a → !c | (b&!c | !b)
    = !a&b&!c | !a&!b | a&!c

However, this is only a DNF and not a full DNF, which means that the minterms do not contain ALL variables, and we need a full DNF for the ZDD representation. Therefore, a minterm m that does not list a variable p must be expanded as follows

    m = !p&m | p&m

This way, we obtain the following for the above example:

    = !a&b&!c | !a&!b | a&!c
    = !a&b&!c | !a&!b&!c | !a&!b&c | a&!c
    = !a&b&!c | !a&!b&!c | !a&!b&c | a&!b&!c | a&b&!c

and this corresponds to the set representation that is then listed in the solution to generate the ZDD:

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

by (170k points)
selected by
I get it now, Thank you very much:))!
Imprint | Privacy Policy
...