Set representation to ZDD

Question

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.

Answer 1

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

Comments

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}}?