2.3 演算

ZDDには四則演算を始めとして様々な演算が定義されており、それらを組み合わせることで、ZDDオブジェクトを自由に加工することが可能となる。以下に、いくつかの例を示す。一般的な多項式と同様に展開されるものもあれば、そうでないものもある。

> (a+a).show # 同じアイテム集合の足し算により重みが足しこまれる。
2 a
> (2*a).show # 定数を掛けても同様の結果になる。
2 a
> (a*b).show # 異なるアイテムの掛け算でアイテム集合にアイテムが追加される
a b
> (a*a).show # 同じアイテムの掛け算は、アイテムが2つになるので重みが2になる。
2 a
> (2*a-a).show # 引き算
a
> ((a*b*c+b*d+c)/b).show # 割り算
a c + d
> ((a+b)*(c+d)).show
a c + a d + b c + b d 
> ((a+1)*(a+1)).show # 最後の項の"1"は空アイテム集合の重み。
3 a + 1
> ((a+1)*(a-1)).show
a - 1

演算の例として、最後にアイテム集合{a,b,c,d}の全ての部分集合を列挙してみよう。以下にそれを実現する式とその結果を示す。

> f=(a+1)*(b+1)*(c+1)*(d+1)
> f.show
a b c d + a b c + a b d + a b + a c d + a c + a d + a + b c d + b c +
  b d + b + c d + c + d + 1

式の展開方法は、上記のケースにおいては、一般的な多項式の展開方法と同様に考えれば良い。右辺の演算結果として構築されたZDDオブジェクトがruby変数fに代入されている。そして結果、16( $=2^4$ )のアイテム集合が列挙されていることがわかる。式の最後の項である1は、空のアイテム集合の重みであることに注意する。