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

972 questions

1.1k answers


469 users

+1 vote
Sept 2022 1d

Consider the set representation : { },{a },{ c},{a,c },{ a,b,c}

1. CDNF : (!a&!b&!c)|(a&!b&!c)|(!a&!b&c)|(a&!b&c)|(a&b&c)

2. RMNF on simplifying b ⊕ b&c ⊕ a&b&c ⊕ true

3. Using SNF: I couldn't get the ZDD in the solution

Please help me spot the mistake.
in # Study-Organisation (Master) by (850 points)

1 Answer

+1 vote

To construct a ZDD, recall that a ZDD is a data structure to store a set of sets of some elements. For instance, the set of sets of integers {{2}, {3}, {2,3}} is stored this way:

For the ZDD of a propositional logic formula, we want to store the minterms. For the minterms which are represented as set of sets of variables {{a,b,c},{a,c},{a},{c},{}} and to this end, we first decompose the set of sets of states by variable a (see page 142 of the related chapter): 

  • a=1: {{b,c},{c},{}}
    • b=1: {{c}}
    • b=0: {{c},{}}
  • a=0: {{c},{}}
    • b does not matter
and so on so get the ZDD

by (147k points)
here, when a=1, and b=1, why isn't the {} part of b=1? why is it part of b=0?

The way I understand is:
a=1: {{b,c}, {c},{}}
       b=1: {{1&c}, {c}, {}} => {{c}, {c}, {}} => {{c}, {}}

but why is is just {{c}}?
Imprint | Privacy Policy