システム開発実験No.７ 　　　　　　　解　説 　　　　　　“論理式の簡略化方法”.

Presentation on theme: "システム開発実験No.７ 　　　　　　　解　説 　　　　　　“論理式の簡略化方法”."— Presentation transcript:

1 システム開発実験No.７ 　　　　　　　解　説 　　　　　　“論理式の簡略化方法”

2 真 or 偽 => 常に真 => 結果に影響を与えないので省略
【0】 簡略化で用いる基本的な規則 高速である A 高速でかつ（大容量か　または大容量でない） A ( B B ) A B A B 高速で大容量であるか　 　　　または　高速で大容量でない （例） 　　A: 高速である 　　B:　大容量である 真　or　偽 => 　 常に真　=> 　結果に影響を与えないので省略

3 論理式の各項を座標空間内に配置されたトークンとして捉える
【1】 簡略化アルゴリズムの考え方 　　　　論理式の各項を座標空間内に配置されたトークンとして捉える 《例1》 A B A B A B 入力論理式： 座標値：　（０　０）　（１　０）　（１　１） 0,0 座標空間に配置する 1,0 1,1 B 1 簡略化可能なので移動 　　変数が異なるので 　　もはや簡略化できない 1, -1 －1は，この変数に関して簡略化したことを意味する -1, 0 A 0　　　　　　　　 1 B　　　　　+　　　A

4 《例2》 A B C + A B C + A B C + A B C + A B C + A B C C (1,0,1) B A
入力論理式： 座標値に変換する 座標値 ： 1,0, ,1, ,1, ,1, ,0, ,1,1 3次元空間の各座標番号で示される位置にトークンを配置する 3 1 4 2 6 7 A B C 1,0,0 1,1,0 0,0,1 1,1,1 0,1,0 0,1,1 5 (1,0,1) 座標番号とは，空間の各点の 座標値を2進数のビット列と解釈し 10進数に変換したものである

5 AC B AC 第２回目の移動 簡略結果へ変換 第1回目の移動 例２の簡略化動作 C 1 3 0,-1, 1 0,0,1 0,1,1 5 7
移動可能な方向へすべて動いたら移動元のトークンを消す 例２の簡略化動作 1 3 第２回目の移動 簡略結果へ変換 第1回目の移動 0,-1, 1 0,0,1 0,1,1 AC 5 7 -1,1,1 (1,0,1) 0, 1, -1 -1,1,-1 1,1,1 -1,1,-1 0,1,0 1,1,-1 B -1, 1, 0 1,-1, 0 1,0,0 2 B 1,1,0 AC A 4 6

6 【２】データ構造の設計 ① 簡略化されたトークンを含め どんなトークンが存在するかを 識別するためのデータ
　　　　　　　　アルゴリズムを実現するにはどんなデータ構造が必要か！ ①　簡略化されたトークンを含め 　　　　　　どんなトークンが存在するかを 　　　　　　識別するためのデータ 　　　　　　（テーブルCoord） p.126参照 C 1 -1,1,1 0,0,1 0,1,1 3 ②　存在するトークンの 　　　　移動可能な軸方向を示すデータ 　　　　　（テーブル　pair_tbl) 　p.127参照 5 7 (1,0,1) 1,1,1 0,1,0 ③　各座標点にどんなトークンが 　　 あるかを記録しておくデータ （テーブル　reduce_tbl) p.128参照 4 2 B 1,0,0 1,1,0 A 1,1,-1 6

7 < 配列coord > (1) 各トークンは，001や010のような値を識別子としてもつ．
(1)　各トークンは，001や010のような値を識別子としてもつ．　 　　　配列coordは，どのようなトークンが存在するかを格納しておく配列である． 　　　簡略化された結果，変数値がｰ1になったトークンも，この配列に格納される． < 配列coord > 座標番号位置(=配置されたトークンの識別番号でもある) 1 2 3 4 5 6 7 8 9 10 11 12 13 初期配置されたトークンの識別子 　　　　nPoint 初期配置されたトークンの数 新たに生成された（簡略化された） トークンの識別子 nCoord 簡略化されたトークンも含めた 　 トークンの最大数 図3-17 座標番号に置かれたトークンと識別子を管理するテーブル

8 < 配列pair_tbl > (2) 存在するトークンの移動可能な軸方向を示す配列 始端座標番号(from)
(2) 存在するトークンの移動可能な軸方向を示す配列　　　　　 < 配列pair_tbl > 始端座標番号(from) 終端座標番号(to) 移動可能な軸(axis)方向 を示したもの．例えば，０ならば変数Aの軸方向, 1なら変数Bの軸方向,２なら変数Cの軸方向へ移動可能である． 　 3 1　　　6 1 2 fromとtoの差が2のべき乗でないものは移動可能な軸方向を示す配列から削除する． なぜなら，座標点は2進点の値と解釈している｛例えば座標（110)や座標(010)等｝． そこでトークンが進める方向を２つの座標点の差で表すと，その間には上記の例で言うと(100)（＝２3）の差がある． したがって，トークンが移動可能な軸方向は，始端座標番号（２進数を10進数に置き換えたもの）と終端座標番号の間には，２のべき乗の差がなくてはいけない． nPair (辺の数 + 1)

9 (3) 各座標点にどんなトークンが存在しているかを記録しておく配列 p.132参照
(3)　各座標点にどんなトークンが存在しているかを記録しておく配列 　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　p.132参照 各座標番号に存在しているトークン数 ⑥もはやトークンが動けなるなるまでこの操作を繰り返す 座標番号 reduce_tbl reduce_tbl 1 2 3 4 5 6 7 ９ ８ 1 7 ⑤ すべてのトークンを移動したら簡略化に使用されたトークンを消す 1 2 3 4 5 6 7 1 13 1 ９ 1 10 1 ８ reduce_tbl 1 2 3 4 5 6 7 1 　1 1 　2 1 　3 1 　4 1 　 6 1 　7 ②２つのノードを接続する辺の両端にトークンが存在するときのみ調べる ④ 簡略化に使用されたトークン であることを示す丸印を付ける ③簡略化の結果，生成したトークンの識別番号を置く ① 初期配置として各座標位置に 座標番号をもったトークンを置く

10 《 簡略化の基本的なアルゴリズム 》 関数 do_reduce ( ) Yes No Yes No
《　簡略化の基本的なアルゴリズム　》 関数　do_reduce　( ) 各座標点に入力された項に対応するトークンを初期配置する 移動可能な軸方向にもはやトークンが移動できなくなる（簡略化できなくなる）まで繰り返す 移動可能な軸の数だけ繰り返す 　　　　　　　　　　　移動可能な辺の両端にトークンが存在するか Yes No 　　　　　　　　　両端にあるトークンは簡略化が可能か matchToken(… ) Yes No 簡略化した結果を示す新たなトークンを簡略化の移動先に置く 　　　　 moveToken（トークンID，到着ノード，軸方向） 両端のトークンに簡略化されたことを示す印を付ける 簡略化に使用したトークンを座標点から消去する

11 【課題】 欠損論理変数の個所を補い，あたかも標準形が入力されたかのようにデータを生成せよ A C (例1） A （ B ＋ B ） C
このように変形しても結果には影響ない． 　A　（　B　＋　B　）　C　　 　A　B　C　＋　A 　B　C このような標準形式の論理式が入力さ れたかのように変数データを生成する A　　　D　　 (例2） 　A　（　B　＋　B　）　（　C　＋　C　）　D　 このような標準形式の論理式が入力さ れたかのように変数データを生成する 　A　B　C　D　 ＋　A 　B　C　D　 ＋　A 　B　C　D　　＋　A 　B　 C　D　　

12 （1）欠損変数を補う方法について 　　　　　　　　　　生成する変数のパターンを見てみると… 　A　B　C　D　 ＋　A 　B　C　D　 ＋　A 　B　C　D　　＋　A 　B　 C　D　　 1　　０ 1　　1 ０　　1 ０　　０ ２進数のビットパターンになっている 欠損変数の数ｎが２なら， 　　ｎの２乗（＝４）個のビットパターンを 　　あたかも入力されたかのように生成すればよい！！

13 （２） 具体的なプログラミングに必要なデータ
（２）　具体的なプログラミングに必要なデータ ①　論理式の中の各項を格納しておくterm_tblとは！ （例）入力された論理式 　Ｂ　 Ｃ 　Ｄ 　 ＋ 　 Ｂ 　Ｅ minBit(Bより前の変数はない) maxBitSize(Eより後の変数はない) A 　 B C D E F 配列 term_tbl O 1 2 3 第1項目 この変数が入力されなかった欠損変数であることを示している.これらの変数をあたかも入力されたかのように生成する 第2項目 nTerm False True 　 True True 　 True False 配列 exist 項の中で出現した変数＝True

14 ２２ 例えば，Term_tblの２行目を取り出したとき ●このようなビットパターンを欠損個所に 埋め込んだ入力変数データを作成する
配列 exist False True 　 True True 　 True False A 　 B C D E F 配列 term_tbl [ 1 ] -1は欠損変数; 欠損変数の個数=2 ●このようなビットパターンを欠損個所に 　埋め込んだ入力変数データを作成する 1 = ２２ 欠損変数の個数 j＝ bit_pat = ０ j＝ bit_pat = 1 j＝ bit_pat = 2 j＝ bit_pat = 3

15 欠損変数を生成する手順の概要 【 関数translate_to_point 】
カウンタを　i 　として,　入力された項の数ｎTermだけ繰返す 　すべての項に現れた変数が配列existに記録されている. それらを参照しながら 　term_tblの　i行目に格納された i番目の項に含めれる欠損変数の個数を見出す 欠損変数の個数　＞　０　 Ｎｏ Ｙｅｓ 　　　生成する変数のビットパターン数ｎGenTerm　＝ 　　　　　　　　　　　　　　　　　　　pow　(2,　欠損変数の個数）　 term_tblのi行目のデータを，一旦一次元配列termにコピーする． カウンタを n として, 生成する変数のビットパターン数nGenTerm だけ繰返す 関数store_to_coord(term)を呼出し，termを座標空間に配置する 欠損変数以外の変数は，そのまま用いるので，term_tblの i行目のデータを，一次元配列termにコピーする． // ビットパターンはtermに埋め込むものとする カウンタ n を 生成用のビットパターン(bit_pat)として用いる termの中の欠損変数の位置を探し出し,　ビットパターンの１ビットをtermの欠損変数位置に次々と埋め込む この部分を作成する 関数store_to_coord(term)を呼出し，termを座標空間に配置する

16 【ヒント】 ビットパターンの最下位１ビットを取り出し，その値を埋め込む．
　ビットパターンのそれぞれの１ビットを 　　　　　　　　　　　　　　変数位置に次々に埋め込むには 【ヒント】　ビットパターンの最下位１ビットを取り出し，その値を埋め込む． bit_pat >> = 1； １ビット右シフト演算　 ビットをシフトする演算 ０　０　０　０　０　０　０　１　 １ビットシフト後のビットパターン(bit_pat) ０　０　０　０　０　０　１　０ ビットパターン（bit_pat) ＆　演算 ０　０　０　０　０　０　０　１ マスク(=1) ＆　演算 ０　０　０　０　０　０　０　１ マスク(=１) ０　０　０　０　０　０　０　０ 演算結果 X　＝　bit_pat &　１; Xには０が入る ０　０　０　０　０　０　０　１ 演算結果 X　＝　bit_pat & 1; Xには１が入る