システム開発実験No.７解説 “論理式の簡略化方法” 【0】簡略化で用いる基本的な規則 A B + A B A ( B + B ) A （例） A: 高速である B: 大容量である高速で大容量であるかまたは高速で大容量でない高速でかつ（大容量かまたは大容量でない）高速である真 or 偽 => 常に真 => 結果に影響を与えないので省略【1】簡略化アルゴリズムの考え方論理式の各項を座標空間内に配置されたトークンとして捉える《例1》入力論理式：座標値： A B + A B + A B （００）（１０）（１１） B 1 1,1 座標空間に配置する簡略化可能なので移動変数が異なるのでもはや簡略化できない 1,0 1, -1A 0,0 0 -1, 0 B 1 + A －1は，この変数に関して簡略化したことを意味する《例2》入力論理式： ABC + ABC +ABC + ABC + ABC + ABC 0,0,1 1,1,1 座標値に変換する座標値： 1,0,0 0,1,1 0,1,0 1,1,0 3次元空間の各座標番号で示される位置にトークンを配置する C 1 座標番号とは，空間の各点の座標値を2進数のビット列と解釈し 10進数に変換したものである 0,0, 1 5 (1,0,1) 7 1,1,1 0,1, 0 2 4 A 1,0, 0 0,1, 1 3 1,1, 0 6 B C 移動可能な方向へすべて動いたら移動元のトークンを消す例２の簡略化動作 1 簡略結果へ変換第２回目の移動第1回目の移動 3 0,-1, 0,0,1 1 5 0,1,1 7 (1,0,1) -1,1,1 1,1,1 0, 1, -1 -1,1,-1 0,1,0 A 1,0,0 1,-1, 0 4 2 1,1, 0 6 AC -1,1,-1 -1, 1, 0 AC 1,1,-1 B B 【２】データ構造の設計アルゴリズムを実現するにはどんなデータ構造が必要か！ ① 簡略化されたトークンを含めどんなトークンが存在するかを識別するためのデータ（テーブルCoord） p.126参照 C 1 0,0, 1 5 (1,0,1) A ② 存在するトークンの移動可能な軸方向を示すデータ（テーブル pair_tbl) p.127参照 7 1,1,1 0,1, 0 2 4 1,0, 0 1,1,1 0,1, 3 1 1,1, 0 1,1,6 1 B ③ 各座標点にどんなトークンがあるかを記録しておくデータ（テーブル reduce_tbl) p.128参照 (1) 各トークンは，001や010のような値を識別子としてもつ．配列coordは，どのようなトークンが存在するかを格納しておく配列である．簡略化された結果，変数値がｰ1になったトークンも，この配列に格納される．座標番号位置(=配置されたトークンの識別番号でもある) nPoint 初期配置されたトークンの数 < 0 1 2 3 4 5 6 7 8 9 10 11 12 13 配列coord 0 0 0 1 0 1 1 0 1 0 1 0 1 1 1 -1 1 -1 0 0 1 1 1 1 -1 1 1 -1 0 1 -1 1 0 0 -1 1 > 初期配置されたトークンの識別子新たに生成された（簡略化された）トークンの識別子 nCoord 簡略化されたトークンも含めたトークンの最大数図3-17 座標番号に置かれたトークンと識別子を管理するテーブル (2) 存在するトークンの移動可能な軸方向を示す配列 < 配列pair_tbl > 始端座標番号(from) 終端座標番号(to) 1 1 1 2 2 2 3 4 4 6 nPair (辺の数 + 1) 3 6 7 3 6 7 7 6 7 7 1 2 0 0 1 2 移動可能な軸(axis)方向を示したもの．例えば，０ならば変数 A の軸方向, 1なら変数 B の軸方向,２なら変数Cの軸方向へ移動可能である． fromとtoの差が2のべき乗でないものは移動可能な軸方向を示す配列から削除する．なぜなら，座標点は2進点の値と解釈している｛例えば座標（110)や座標 (010)等｝．そこでトークンが進める方向を２つの座標点の差で表すと，その間には上記の例で言うと(100)（＝２3）の差がある．したがって，トークンが移動可能な軸方向は，始端座標番号（２進数を 10進数に置き換えたもの）と終端座標番号の間には，２のべき乗の差がなくてはいけない． (3) 各座標点にどんなトークンが存在しているかを記録しておく配列 p.132参照各座標番号に存在しているトークン数座標番号 0 1 2 3 4 5 6 7 ⑥もはやトークンが動けなるなるまでこの操作を繰り返す reduce_tbl 1 1 1 1 1 2 3 4 1 1 6 7 reduce_tbl ②２つのノードを接続する辺の両端にトークンが存在するときのみ調べる 0 1 2 3 4 5 6 7 2 3 2 2 1 2 3 4 2 1 6 7 13 11 ９ 10 12 ８ reduce_tbl 0 1 2 3 4 5 6 7 1 2 1 1 13 11 ９ 10 1 ８ 12 ③簡略化の結果，生成したトークンの識別番号を置く ① 初期配置として各座標位置に座標番号をもったトークンを置く ④ 簡略化に使用されたトークンであることを示す丸印を付ける ⑤ すべてのトークンを移動したら簡略化に使用されたトークンを消す《簡略化の基本的なアルゴリズム》関数 do_reduce ( ) 各座標点に入力された項に対応するトークンを初期配置する移動可能な軸方向にもはやトークンが移動できなくなる（簡略化できなくなる）まで繰り返す移動可能な軸の数だけ繰り返す移動可能な辺の両端にトークンが存在するか Yes Yes No 両端にあるトークンは簡略化が可能か matchToken(… ) No 簡略化した結果を示す新たなトークンを簡略化の移動先に置く moveToken（トークンID，到着ノード，軸方向）両端のトークンに簡略化されたことを示す印を付ける簡略化に使用したトークンを座標点から消去する欠損論理変数の個所を補い，あたかも標準形が入力されたかのようにデータを生成せよ【課題】 (例1） A C Bが何であっても必ず真なので，このように変形しても結果には影響ない． A （ B ＋ B ） C A B C ＋ A B C (例2） A このような標準形式の論理式が入力されたかのように変数データを生成する D A （ B ＋ B ）（ C ＋ C ） D このような標準形式の論理式が入力さ A B C D ＋ A B C D ＋ A B C D れたかのように変数データを生成する＋ A B C D （1）欠損変数を補う方法について生成する変数のパターンを見てみると… A B C D ＋ A B C D ＋ A B C D 1 1 1 ００＋ A B C D 1 ０２進数のビットパターンになっている欠損変数の数ｎが２なら，ｎの２乗（＝４）個のビットパターンをあたかも入力されたかのように生成すればよい！！０（２）具体的なプログラミングに必要なデータ ① 論理式の中の各項を格納しておくterm_tblとは！（例）入力された論理式ＢＣＤ＋ minBit(Bより前の変数はない) 配列 term_tbl 0 1 nTerm A B C O 1 2 -1 1 1 -1 ＢＥ maxBitSize(Eより後の変数はない) D E F 3 4 5 1 1 -1 -1 第1項目 -1 -1 1 -1 第2項目 2 3 この変数が入力されなかった欠損変数であることを示している.これらの変数をあたかも入力されたかのように生成する配列 exist False True True True True 項の中で出現した変数＝True False 例えば，Term_tblの２行目を取り出したとき配列 False exist True A 配列 term_tbl [ 1 ] True True C D B -1 1 -1 True E -1 F 1 -1 -1は欠損変数; 欠損変数の個数=2 ●このようなビットパターンを欠損個所に埋め込んだ入力変数データを作成する欠損変数の個数 False 1= 0 0 00 0 1 -1 1 0 0 1 -1 j＝ bit_pat = ０ -1 1 0 1 1 -1 j＝ bit_pat = 1 -1 1 1 0 1 -1 j＝ bit_pat = 2 -1 1 1 1 1 -1 j＝ bit_pat = 3 ２２欠損変数を生成する手順の概要【関数translate_to_point 】カウンタを i として, 入力された項の数ｎTermだけ繰返すすべての項に現れた変数が配列existに記録されている. それらを参照しながら term_tblの i行目に格納された i番目の項に含めれる欠損変数の個数を見出す欠損変数の個数＞０Ｎｏ term_tblのi行目のデータを，一旦一次元配列termにコピーする．関数 store_to_coord(term )を呼出し，termを座標空間に配置するＹｅｓ生成する変数のビットパターン数ｎGenTerm ＝ pow (2, 欠損変数の個数）カウンタを n として, 生成する変数のビットパターン数nGenTerm だけ繰返す欠損変数以外の変数は，そのまま用いるので，term_tblの i行目のデータを，一次元配列termにコピーする． // ビットパターンはtermに埋め込むものとするカウンタ n を生成用のビットパターン(bit_pat)として用いる termの中の欠損変数の位置を探し出し, ビットパターンの１ビットをtermの欠損変数位置に次々と埋め込むこの部分を作成する関数store_to_coord(term)を呼出し，termを座標空間に配置するビットパターンのそれぞれの１ビットを変数位置に次々に埋め込むには【ヒント】ビットパターンの最下位１ビットを取り出し，その値を埋め込む．ビットパターン（bit_pat) ００００００１０＆演算マスク(=１) bit_pat >> = 1；０００００００１１ビット右シフト演算ビットをシフトする演算０００００００１＆演算マスク(=1) ０００００００１演算結果演算結果００００００００ X ＝ bit_pat & １; １ビットシフト後のビットパターン (bit_pat) ０００００００１ Xには０が入る X ＝ bit_pat & 1; Xには１が入る