3.17 delta : 排他的論理和演算

書式

$obj$ .delta( $zdd1$ ) $\rightarrow$ $zdd2$

説明

ZDDオブジェクト $obj$ に含まれるアイテム集合 $\alpha$ と $zdd1$ に含まれるアイテム集合 $\beta$ の排他的論理和 $\alpha \oplus \beta$ を求め、その結果のZDDオブジェクト $zdd2$ を返す。例えば、アイテム集合abcとbcdの排他的論理和は以下の通り。

abc.delta(bcd) = abc $\oplus$ bcd = ad

複数のアイテム集合間の演算では全組合せについて排他的論理和を求める。

(abc + a).delta(bcd + b) = abc $\oplus$ bcd + abc $\oplus$ b + a $\oplus$ bcd + a $\oplus$ b

= ad + ac + abcd + ab

重みについては、同じアイテム集合を複数に展開して計算すればよい。

(2abc).delta(bcd) = (abc+abc).delta(bcd) = ad + ad = 2ad

ちなみに $\alpha \oplus \beta$ を $\alpha \cap \beta$ (共通集合演算)に変更すればdelta関数となる。

例

例1: 基本例

以下では、アイテムa,b,c、およびアイテム集合2ab + a + 3b、 abc + 2ab + bc + 1、ab+aに関する排他的論理和を求める。

> require 'zdd'
# まずはアイテム集合の定義
> a=ZDD::itemset("a")
> b=ZDD::itemset("b")
> c=ZDD::itemset("c")
> f=2*a*b+a+3*b
> f.show
 2 a b + a + 3 b

(2ab + a + 3b) $\oplus$ a = 3ab + 2b + 1

> f.delta(a).show
 3 a b + 2 b + 1

(2ab + a + 3b) $\oplus$ b = ab + 2a + 3

> f.delta(b).show
 a b + 2 a + 3

(2ab + a + 3b) $\oplus$ ab = 3a + b + 2

> f.delta(a*b).show
 3 a + b + 2

(2ab + a + 3b) $\oplus$ 1 = 2ab+a+3b 定数1は空のアイテム集合なので、それとの排他的論理和を求めると元の集合のままとなる。

> f.delta(1).show
 2 a b + a + 3 b

(abc + 2ab + bc + 1) $\oplus$ (2ab + a)の項別の演算結果は以下の通りとなる。

abc $\oplus$ 2ab = 2c
2ab $\oplus$ 2ab = 4
bc $\oplus$ 2ab = 2ac
1 $\oplus$ 2ab = 2ab
abc $\oplus$ a = bc
2ab $\oplus$ a = 2b
bc $\oplus$ a = abc
1 $\oplus$ a = a

結果をまとめるとa b c + 2 a b + 2 a c + a + b c + 2 b + 2 c + 4となる。

> g=((a*b*c)+2*(a*b)+(b*c)+1)
> h=2*a*b + a
> g.show
 a b c + 2 a b + b c + 1
> h.show
 2 a b + a
> g.delta(h).show
 a b c + 2 a b + 2 a c + a + b c + 2 b + 2 c + 4

3.17 delta : 排他的論理和演算

書式

説明

例

例1: 基本例

関連