2011年2月13日日曜日

対称関数

TAOCP V4F1にきれいな絵があった. 元の絵はもちろん白黒である.



これは3変数対称関数のBDD(二分決定図)ベースの図である.

そもそも対称関数とは, 変数をとりかえても値が変らないものである.

以下に2変数(xとy), 3変数(xとyとz)の対称関数を示す. 頂点にある色つきの丸は関数値が1の点で, 同じ色は対称の相手を表わす.



上の方の2変数対称関数は, それぞれの図で, 左下がx=0, y=0. 右上がx=1, y=1の点で, 破線は対称軸. 従って対称関数は, 同じ色の丸が対称軸について対称であるものである.

2変数関数が16あるうち, 対称なのはここにある0番から7番の8個である.

3変数のx, y, zは, 左上の0番の図に示す通りで, 3変数の場合も, 同じ色の丸は対称軸について3回対称である.

3変数関数は全部で256あり, 対称なのは0番から15番の16個である.

Boole関数は, こういう図の他, その真理値表で表わすことも出来る. x, y, zの各値に対し, 関数値を並べて書く. 例えば3番は多数決関数で


x 00001111
y 00110011
z 01010101
f 00010111


である. 図からは右下の経路で頂点をたどり1と0を書き取ればよい.


ところで, TAOCP 7.1.4項は, BDDが話題であった. BDDは下に示すような図で, 変数を調べる節点を実線と破線で繋げたものである.

一番上の入口(根)から出発し, 丸で示す変数の値を調べ, 値が1なら実線方向へ, 0なら破線方向へ進み, 次の変数をチェックする. 四角に⊥は, 関数の値が0で確定する, 四角にTは, 1で確定し, BDDの出口である.

下の図は, 3変数の16個の対称関数のうち16個のBDDで, 0番のオール0, 15番のオール1は定数関数なので, 省いてある.




最上段の右端の3番が, 話題の多数決関数で, 根の1番変数(xのこと)の脇に先ほどの真理値表が書いてある. xが0なら左下の2番変数へ進み, yを調べる. ここでyも0ならzと無関係に0なので, 0の出口になる. yが1なら, 決定はzによる. そこで3番へ進む. 上へもどり, xが1なら右下の2番変数へ進み, 2も1なら1の出口. 2が0なら3番の変数をしらべる. BDDはこのような図である.


ところでそれぞれの図の節点の数は, 0と1の出口は1個と数えるので, 1番から順に, 5, 7, 6, 7, 7, 7, 5, 5, 7, 7, 7, 6, 7, 5 で合計88個ある. 1の節点は14個あるが, 1段下の2の節点は6種類, 3の節点は2種類しかない. 同じものをまとめてメモリーにいれれば節約になるといってまとめたのが最初に掲げたBDDベースである. ここには節点は24しかない.

1の節点の左下の青の番号は, 対称関数の3変数の番号と一致している. 一番上の3番は, 実線で左の2へ, 破線で右の2に進むが, それぞれの2の左に青で1と3とあるのは, BDDの2の添字に合っている.

もう一度対称関数の絵で3番をみると, xが1の手前の四角の丸は, 直ぐ上の2変数の3番と同じ. xが0の向こうの四角は, 2変数の1番と同じであり, さきほどの添字はそれを表わしている.

変数の図はyの値で1変数の図に分解できる. 下の図が1変数の(対称)関数の図と, その右が0変数の図である.

0 件のコメント: