このスライドは以下の URL からダウンロード可能です 2

Transcription

1 計算機学 1

2 このスライドは以下の URL からダウンロード可能です 2

3 参考書の紹介 計算機学入門デジタル世界の原理を学ぶ阿曽弘具著共立出版 2,900 以前教科書だった本の改訂版 講義の内容と一致しており 説明は詳しい CPU の創りかた渡波郁著毎日コミュニケーションズ 2,940 個人的おすすめだが講義の前半部分しかカバーしていない ソフトウェアの 20 世紀長谷川裕行著翔泳社 2,400 コンピュータとソフトウェアの歴史 講義と直接の関連はないが面白い コンピュータはなぜ動くのか矢沢久雄著日経 BP 社 2400 一般向け 内容は浅く広く わかりやすい 3

4 講義の流れ (1) イントロダクション ( 今回 ) コンピュータの歴史 2 進法 8 進法 16 進法 ハードウェアの原理 論理関数と論理回路 論理関数の簡単化 論理関数の数学 ブール代数と代数系 論理関数の様々な性質 4

5 講義の流れ (2) ソフトウェアの原理 CPU と機械語 アセンブリ言語と高級言語 データ構造とその操作 計算のモデルと計算量 試験 5

6 計算機 ( コンピュータ ) とは何か 誰が何のために作ったのか 計算機とは ( 原理的に ) 何なのか 現在どのように使われているのか それはどのように実現されているのか 6

7 誰が : 計算機をめぐる年表 17 世紀 ブレース パスカル ( ) 考える葦の人 世界で初めて 計算機 (calculator) を試作 名前は パスカリーヌ 7

8 誰が : 計算機をめぐる年表 17 世紀 ゴットフリート ウィルヘルム フォン ライプニッツ ( ) 2 進法の発明者 自動的に真なる概念を導くための計算方法 を研究 計算機も試作 ニュートンとは永遠のライバル 8

9 誰が : 計算機をめぐる年表 19 世紀 チャールズ バッベジ ( ) 2 つの自動計算機械を設計 階差機関 (Difference Engine) 解析機関 (Analytical Engine) でも完成しなかった 9

10 Babbage の解析機関 世界初の機械式計算機 加減乗除算 あらかじめ決められた順序で計算する 結果の印字 10

11 誰が : 計算機をめぐる年表 世界初のプログラマ (Translator) エイダ オーガスタ ラブレス公爵夫人 ( ) 詩人バイロンの娘 ド モルガンに師事 チャールズ バッベジを支援した 不遇な晩年 11

12 誰が : 計算機をめぐる年表 20 世紀 アラン チューリング ( ) 自動機械による証明についての理論的考察 実際に計算をする 機械 を想定 ( チューリングマシン ) 計算の可能性についての理論を構築 暗号解読器 コロッサス の開発に参加 不遇な晩年 12

13 誰が : 計算機をめぐる年表 20 世紀 エッカート & モークリー (UPENN) 世界初の ( 実用化された ) 電子式コンピュータ ENIAC を開発 弾道計算に特化した計算機 モークリー氏 13

14 これが ENIAC だ 真空管 本 コンデンサ 個 スイッチ 6000 個 ケーブルの接続で実行を制御 14

15 何のために? 正しい推論のため ( ライプニッツ ) 数表を作るため ( バッベジ ) 計算 とは何かを考えるため( チューリング ) 弾道計算のため ( エッカート & モークリー ) 15

16 原理的に何なのか? 計算モデル : 原理的に何が計算できるかを考えるための数学モデル コンピュータを抽象化したもの 速度やメモリ容量などの制約を考えない さまざまな計算モデル チューリングマシン (TM) ランダムアクセスマシン (RAM) 帰納的関数 どれも 計算可能 なものは同じ ( すなわち どれか 1 つで別な 1 つのエミュレータを書くことができる ) 16

17 チューリングマシン 仮想的な計算機械 by Alan Turing 状態 ヘッド A = 1 0 ; B = A + 2 ; F テープ 17

18 ランダムアクセスマシン 現在のコンピュータに近い 計算部とメモリがある メモリは必要に応じていくらでも大きい どのメモリにアクセス ( 読み書き ) するときにもかかる時間は同じ ( ランダムアクセス ) 計算部 無限に大きいメモリ 番目のメモリの値と 番目のメモリの値を足す 基本的な計算はどれも一定時間で計算される 18

19 現在どのように使われているのか? 汎用の何でも機械として 電話 ごはんの炊け具合を監視する お部屋の温度をいい具合に調節する 大きいお友達のゲーム テレビを録画する あるいはテレビそのもの 19

20 どのようにして実現されるのか? コンピュータの実現のための階層 ソフトウェア アプリケーション MS-Wordとか プログラミング言語 C, C++, Java, Ruby, Python,... OS Windows, MacOS, ios, Linux, Android,... ハードウェア CPU IA32, x86-64, ARM, MIPS, PowerPC, PIC,... 論理回路 機能ブロック レジスタ ALU メモリ... 論理ゲート AND, OR, NOT,... 電子回路 トランジスタ 真空管 リレー... 階層間は ( ほぼ ) 独立 論理回路の階層には ( 現在のところ )alternative はない 20

21 この講義では何をするのか 1. 計算機の動作原理を理解するための論理回路の理解 ( 主に組み合わせ論理回路 ) ( 進んだ内容は ディジタルコンピューティング の範疇 ) 2. それに伴う論理演算 論理関数の理解 3. 計算機のネイティブな動作 ( 機械語 ) の理解 4. 抽象的な計算機としての計算モデルの理解と 計算量についての初歩的な理解 21

22 あらゆる計算が 1 と 0 で実現できる 10 進法の数字 2 進法の数字 (1と0) 文字 数字 文字列 数字列 = 数字 画像 数字 音声 数字 その他のデータ 数字 計算機が行うすべての処理は 1 と 0 の列に対する処理である 22

23 10 進法 2 進法 8 進法 16 進法 10 進 2 進 8 進 16 進 10 進 2 進 8 進 16 進 A B C D E F 23

24 10 進 2 進 16 進数の変換 例題 108 (10) を 2 進法で表せ 解答 ある数 x を 2 進数で表したとき それが偶数ならば下 1 桁は 0 奇数ならば 1 になる したがって 2 で割った余りを計算すれば 2 進数の最下桁が求まる 以下同様 2 ) ) ) ) ) ) (2) 24

25 10 進 2 進 16 進数の変換 例題 (2) を 10 進法で表せ 解答 2 進数の n 桁目だけが 1 である数は 2 n-1 である したがって = = = = =50 (10) 25

26 10 進 2 進 16 進数の変換 例題 (2) を 16 進法で表せ 解答 16 進数の 1 桁は 2 進数の 4 桁にそのまま対応する ただし下から割り当てていく B 2 5B2 (16) ちなみに 8 進数 1 桁は 2 進数 3 桁に対応する 26

27 演習 次の 2 進数を 8 進数と 16 進数で表せ 次の 10 進数を 2 進数と 16 進数で表せ

28 2 進数の演算 加算 0+0=0, 0+1=1+0=1, 1+1=10 減算 0-0=0, 0-1=-1, 1-0=1, 1-1=0 乗算 0 0=0 1=1 0=0, 1 1=1, 1 10=10 1=10, 10 10=100, 10 11=11 10=110,... これらは 算術演算 と呼ばれる 28

29 2 進数の演算 どんなデータも0と1で表せる すべての計算は01の列に対する関数で表現で きる f ( )= 例 f (00)=0 f (01)=1 f (10)=1 f (11)=1 入力の桁数が有限ならば入力のパターンも有限 すべての入力に対して出力を決めれば関数が定義できる 29

30 基本的な論理関数 ( 論理演算 ) AND 演算 ( 論理積 ) 0 0=0 0 1=0 1 0=0 1 1=1 OR 演算 ( 論理和 ) 0+ 0=0 0+ 1=1 1+ 0=1 1+ 1=1 x y, x y, x y 2 つの引数の両方が 1 の場合だけ 1 x+ y, x y 2 つの引数の両方が 0 の場合だけ 0 30

31 基本的な論理関数 ( 論理演算 ) NOT 演算 ( 否定 ) 0=1 1=0 x, x XOR 演算 ( 排他的論理和 ) 0 0=0 0 1=1 1 0=1 1 1=0 ~ x y, x y 2 つの引数が異なる場合だけ 1 実は AND,OR,NOT で作れる x y= x y+ x y 31

32 組み合わせて作れる論理演算 NAND 演算 x y 0 0=1 0 1=1 1 0=1 1 1=0 NOR 演算 0+ 0=1 0+ 1=0 1+ 0=0 1+ 1=0 x+ y 32

33 論理演算の基本的性質 交換則 ( 交換律 ) x y= y x x+ y= y+x 結合則 ( 結合律 ) 分配則 ( 分配律 ) x ( y z)=( x y) z x+ ( y+ z)=(x+ y)+ z x ( y+ z)=(x y)+ ( x z) x+ ( y z)=( x+ y) (x+ z) ド モルガン則 ( ド モルガン律 ) x y=x+ y x+ y=x y 33

34 論理演算の記述の優先順位 通常は AND 演算を OR 演算より優先して書く ( 算術演算の記述法と同じ ) a b+ c d=(a b)+ (c d ) 紛らわしい場合はカッコを使う 34

35 論理関数 ( 論理演算 ) は何種類あるか 論理関数の引数の数を固定する 入力 出力ともに有限のパターンしかないので 論理関数は有限個しかない 例 :1 変数論理関数は 4 種類 f 0 (0)=0 f 0 (1)=0 f 1 (0)=0 f 1 (1)=1 f 2 (0)=1 f 2 (1)=0 f 3 (0)=1 f 3 (1)=1 f 0 (x)=0 f 1 (x)=x f 2 (x)= x f 3 ( x)=1 35

36 論理関数 ( 論理演算 ) は何種類あるか n 変数関数の場合 入力のパターンは 2 n 通り それぞれに対して 出力のパターンは 0 か 1 入出力のパターン数 = 2 2n 36

37 真理値表 すべての入力パターンに対して出力を定義すれば論理関数が定義できる 表にするとわかりやすい 真理値表 (truth table) AND OR NOT x y x y x y x+y x x

38 真理値表 注意事項 引数 ( 入力 ) のパターンは その並びを 2 進数と見たときに だんだん増えていく 順番に記述するのが普通 対応関係が同じでも 思いついた順番に並べるのはよくない! x y x y GOOD BAD x y x y

39 真理値表による証明 真理値表によってド モルガン則を確かめてみよう x y x y x y x+y x y x+y x y x+y

40 基本論理演算と論理関数 AND, OR, NOT 演算の組み合わせだけでどんな論理関数でも作ることができる 証明 : 引数の数に関する数学的帰納法 引数 1 つの時 引数 1 つの論理関数は前述の通り 4 種類しかない f 0 ( x)=0=x x f 1 (x)=x f 2 ( x)= x f 3 ( x)=1=x+ x 成立 40

41 基本論理演算と論理関数 引数 n 個のとき 引数 n-1 個では成立を仮定 任意の n 変数論理関数 次の n-1 変数論理関数を考える f (x 1, x 2,, x n ) g 0 ( x 1, x 2,, x n 1 )= f (x 1,, x n 1,0) g 1 ( x 1, x 2,, x n 1 )= f ( x 1,, x n 1,1) ここで次の式を考える : x=0 なら a x=1 なら b x a+ x b x a b xa xb xa+ab x a b xa xb xa+ab

42 基本論理演算と論理関数 xn の値によって関数を切り替える x n =0 x n =1 f ( x 1,, x n 1, x n )=g 0 ( x 1,, x n 1 ) f ( x 1,, x n 1, x n )=g 1 ( x 1,, x n 1 ) 前ページの考察により f ( x 1,, x n 1, x n )=x n g 0 ( x 1,, x n 1 )+ x n g 1 ( x 1,, x n 1 ) 仮定より g 0 と g 1 は AND,OR,NOT のみで表せるの で f も AND,OR,NOT のみで表せる 42

43 演習 分配律が成立していることを真理値表で確かめよ x ( y+ z)=( x y)+ ( x z) x+ ( y z)=(x+ y) (x+ z) x y z xy xz y+z x(y+z) xy+xz

44 論理演算と論理素子 ある論理演算を実現するための電子回路 ( 論理ゲート ) AND ゲート OR ゲート MIL 記号 NOT ゲート XOR ゲート 44

45 論理演算と論理素子 ゲートの端にある が 反転 を表す NOT ゲート NAND ゲート NOR ゲート 45

46 等価な論理ゲート ド モルガン律などによる = A B C D AB+CD = = 46

47 NAND ゲートは万能 NAND ゲートですべてのゲートの代用ができる = x x= x = x y= x y = x y=x+ y 47

48 NAND ゲートの実現例 Diode-Transistor Logic (DTL) 簡略化した回路図 ( 実際はもう少し複雑 ) DTLは遅くて消費電力が大きいので 実際にはあまり使われない V+ V+ L V+ H H L V+ V+ V+ IN1 IN2 OUT L L H L H H H L H H H L 48

49 半導体でなくても論理ゲートは作れる リレーで作る論理ゲート コイルに電流を流すと隣にあるスイッチが ON/OFF S1 S2 S1 と S2 の両方が ON のときだけ OFF になる 49

50 論理演算と論理回路 論理式 論理回路 例 Z= AB BC CA A B C Z 50

51 演習 次の論理式に基づく論理回路を描け S= X Y X Y C= X Y X Y? C S 51

52 半加算器 さっきの論理式の真理値表 X Y C S C: Carry ( 桁上げ ) S: Sum ( 和 ) X, Y を 1 桁の 2 進数 CS を 2 桁の 2 進数と見ると CS は X と Y の算術加算になっている 半加算器 (Half Adder) 52

53 桁の多い加算 2 桁以上の 2 進数の加算をするにはどうする? 桁上げを考慮 3 つの 2 進数の和を計算しなければならない 3 つの 1 桁の 2 進数 a,b,c を加算 2 桁の 2 進数 CS a b c C S

54 全加算器 (full adder) 半加算器の組み合わせで作れる 54

55 発展 前ページの回路の入出力関係がその前の真理値表と同じになっていることを確かめよう 2 ページ前の真理値表を直接表現する論理式を考えてみよう C= f (a, b, c) S=g (a,b, c) 55

56 桁の多い加算器 筆算と同じ要領 ( 下から順に桁上げ )

57 論理関数の設計 これまでは論理式から論理回路を描いていた 本当にやりたいこと 要求仕様 ( 欲しい入出力関係 ) を実現する論理回路 やるべきこと 要求仕様 ( 真理値表 ) 論理式 ( 関数 ) 論理回路 問題点 どうやって真理値表を満たす論理式を作るか 真理値表を満たす論理式は1つではない どういう論理式を作ればいいか 57

58 真理値表から論理関数へ 次の真理値表で表される論理式 ( 論理関数 ) は? x y z f(x,y,z)

59 真理値表から論理関数へ 次の真理値表で表される論理式 ( 論理関数 ) は? x y z f(x,y,z) 答えは唯一ではない f = x y ẕ+ x y z+ x y ẕ f = y ẕ+ x y z f = (x+ y+ z)( x+ y+ ẕ) (x+ y+ ẕ)( x+ y+ z) ( x+ y+ ẕ) 59

60 真理値表から論理関数へ 論理関数への変換の考え方 できるだけ機械的に変換できたほうがいい 真理値表から標準形論理式への変換 できるだけ論理演算が少ないほうがいい 論理回路として実現した時の素子数が少ない 低コスト 高速 演算数が最小の論理式 : 最簡形論理式 最簡形論理式の導出 カルノー図 クワイン マクラスキ法 60

61 基礎的な概念 基本的に積和形 ( 論理積の論理和 ) で考える y z+ x y ẕ 項 ( 積項 ) リテラル : 変数または変数の否定 y z+ x y ẕ リテラル リテラル リテラル 61

62 標準形論理式 積和標準形 ( 主加法標準形 ) Sum-of-product リテラルの論理積の論理和 すべての項がすべての変数を含む 同じ項は1 回しか出てこない 積和標準形の例 f ( x, y, z)= x y z+ x y z+ x y ẕ 積和標準形でない例 f ( x, y, z)= y z+ x y ẕ f ( x, y, z)= y (x+ z)+ x y ẕ f ( x, y, z)= x y z+ x y z+ x y ẕ+ x y z 62

63 標準形論理式 和積標準形 ( 主乗法標準形 ) Product-of-sum リテラルの論理和の論理積 すべての論理和がすべての変数を含む 同じ論理和は1 回しか出てこない 和積標準形の例 f ( x, y, z)=( x+ y+ z)(x+ y+ ẕ)( x+ y+ z) 和積標準形でない例 f ( x, y, z)=( x+ z)( x+ y+ z) f ( x, y, z)=( x+ z)( x y+ z) f ( x, y, z)=( x+ y+ z)(x+ y+ ẕ)(x+ y+ z) 63

64 2 つの標準形の関係 どんな論理式でも 積和標準形と和積標準形の両表で表現できる 証明 ( 変数の数による数学的帰納法 ) 1 変数の場合は自明 k 変数の場合に成立を仮定 任意の k+1 変数論理関数を考える f (x 1, x 2,, x k+ 1 ) 次の k 変数関数を考える g 0 (x 1,, x k )= f ( x 1, x 2,, x k, 0) g 1 ( x 1,, x k )= f (x 1, x 2,, x k,1) 64

65 2 つの標準形の関係 g をそれぞれ積和と和積標準形で表した論理式 g 0 0 ( x 1,, x k ) g SOP g 1 1 (x 1,, x k ) g SOP 以前と同じ議論により 0 ( x 1,, x k ), g POS 1 ( x 1,, x k ), g POS (x 1,, x k ) (x 1,, x k ) f (x 1, x 2,, x k, x k+ 1 )=x k + 1 g 0 ( x 1,, x k )+ x k+ 1 g 1 ( x 1,, x k ) 0 1 =x k + 1 g SOP ( x 1,, x k )+ x k+ 1 g SOP ( x 1,, x k ) これを分配律によって展開すれば f も積和標準形で表せる 65

66 2 つの標準形の関係 和積標準形の場合 まず次の関係を考える x=0ならa x=1ならbとなる論理式 したがって (x+ a)( x+ b) x=0 ( x+ a)( x+ b)=(0+ a)(1+ b)=a 1=a x=1 ( x+ a)( x+ b)=(1+ a)(0+ b)=1 b=b f ( x 1, x 2,, x k, x k+ 1 )=( x k g 0 ( x 1,, x k ))( x k g 1 (x 1,, x k )) 0 =( x k g POS 1 ( x 1,, x k ))( x k g POS これを分配律によって展開すれば f も和積標準形で表せる ( x 1,, x k )) 66

67 標準形論理式と論理回路設計 ある標準形は 1 つの仕様 ( 真理値表 ) に対して基本的に 1 つしか存在しない 真理値表一対一標準形論理式 一対一 論理回路 x y f(x,y) x y+ x y 67

68 真理値表から積和標準形へ 最小項 : すべての変数のリテラルを含む積項 ある入力の組み合わせの時だけ 1 になり それ以外の組み合わせでは 0 になる x y x y x y x y x y x y f(x,y) 実現したい真理値表のうち 1 になる組み合わせの最小項だけを OR でつなぐと積和標準形になる f (x, y)= x y+ x y 68

69 真理値表から和積標準形へ 最大項 : すべての変数のリテラルを含む論理和 ある入力の組み合わせの時だけ 0 になり それ以外の組み合わせでは 1 になる x y x+y x+y x+y x+y x y f(x,y) 実現したい真理値表のうち 0 になる組み合わせの最大項だけを AND でつなぐと和積標準形になる f (x, y)=(x+ y)( x+ y) 69

70 演習 次の真理値表による論理関数を積和標準形と和積標準形で表せ x y z f(x,y,z)

71 論理式の簡単化 標準形で表現した論理式は一般に冗長 x y f(x,y) x y+ x y+ x y x y 同じ x y+ x y+ x y= x y+ x y+ x y+ x y =( x+ x) y+ x( y+ y)=1 y+ x 1=x+ y x y どうすれば同じ関数を表現するときの論理演算の数を最小にできるのか? 71

72 基礎的な概念 論理関数の順序 値の順序 :0 0, 0 1, 1 1 論理関数の順序 :f(x),g(x) について x(f(x) g(x)) f g 例 : 確かめてみよう xy x x+y ( 真理値表を書き 左辺が 1 のところが右辺でも必ず 1 になっているな らば が成立 ) 72

73 基礎的な概念 系 論理関数 a,b,c,d について a c, b d ならば a+b c+d a c, a d ならば a c+d a c, b c ならば a+b c 73

74 基礎的な概念 論理式 f の主項とは リテラルの論理積 t のうち 次の条件を満たすもの t f であり tからそれ以上リテラルを取り除くと t f でなくなる 例 x y z f x y z x y x f x y ẕ f x y f x これが主項 74

75 主項と論理式 ある論理式 f の主項を全部列挙し その論理和をとれば それは f と一致する ただし一般には冗長 x y z f x y x z y z f = x y+ x ẕ+ y z= x ẕ+ y z 75

76 必須主項 ある論理式を構成するために必ず必要な主項 f =x y+ x ẕ+ y z=x ẕ+ y z x y z f x y x z y z 必須主項 76

77 最簡形論理式とは 次の条件を満たす論理式 : ある論理関数を実現する論理式のうち 積項の数が最小で かつ式全体のリテラルの数が最小のもの 論理式を簡単化するときの目標 論理関数の仕様 ( 真理値表 ) に対して最簡形が一意に決まるとは限らない 77

78 最簡形を求めるには 次のような手順を踏む 1. 与えられた論理関数の主項をすべて求める 2. 求まった主項のなかの必須主項を調べる 3. すべての必須主項と それ以外の主項のうちできるだけリテラルの少ない主項を組み合わせて元の論理関数を表現する これらの求め方でいくつかの方法がある カルノー図 クワイン マクラスキ 法 78

79 最簡形を求める方法 カルノー図 (Karnaugh map) 真理値表に似た表と四角形でできた図を使う 人間向き 変数の数はふつう 4 個ぐらいまで クワイン マクラスキ 法 (Quine-McClusky alg.) 文字列処理 計算機向き ( 人間にはつらい ) 変数の数は多くてもよいが 変数が多いと時間がかかる 79

80 カルノー図 2 次元の真理値表をもとに主項を発見する 3 変数 (x,y,z) 4 変数 (x,y,z,w) の表の例 0,1 の並びに注意 xy\z xy\zw

81 カルノー図 カルノー図では積項は長方形になる z y xy\zw x

82 カルノー図 カルノー図は表の上下左右がつながっている y xy\zw w

83 カルノー図 リテラルの多い積項の例 x z x y z w xy\zw z w x y w y z w 83

84 カルノー図による論理式の簡単化 カルノー図の表を描き 目標となる論理式が 1 となるマス目に 1 を記入 1 を囲む できるだけ大きい長方形 (= 主項 ) を探す 辺の長さは 2 の n 乗のみ 上下左右が連続していることを忘れずに すべての 1 をカバーする できるだけ少ない数の できるだけ大きい長方形の組み合わせを探す その長方形の組み合わせに対応する論理式が最簡形になっている 84

85 カルノー図の例 カルノー図の表を描き 目標となる論理式が 1 となるマス目に 1 を記入 xy\zw

86 カルノー図の例 1 を囲む できるだけ大きい長方形 (= 主項 ) を探す 辺の長さは2のn 乗のみ 上下左右が連続していることを忘れずに xy\zw

87 カルノー図の例 すべての 1 をカバーする できるだけ少ない数の できるだけ大きい長方形の組み合わせを探す xy\zw この 2 つは必須ではない 大きいほうを選ぶ ある 1 を 1 つの四角だけが囲んでいるなら その四角は必須主項 87

88 カルノー図の例 その長方形の組み合わせに対応する論理式が最簡形になっている x w+ y w+ z w+ x y w xy\zw 使わない z w x y w y w x w 88

89 演習 次のカルノー図を使って最簡形論理式を求めよ xy\z xy\zw

90 部分論理関数とカルノー図 入力のすべてのパターンを考えなくてよい場合 例 :7 セグメント LED に 0~4 の数字を表示 x 1 x 2 LED エンコーダ b x 3 b 6 3 x 1 x 2 x 3 =

91 部分論理関数とカルノー図 b1~b6 の真理値表 下 3 行の入力は想定しなくてよい 部分論理関数 x1 x2 x3 b0 b1 b2 b3 b4 b5 b N/A N/A N/A 91

92 部分論理関数とカルノー図 b0 の論理関数の設計 想定外の入力に対して 0 を出力 x1x2\x 想定外の入力に対して何を出力してもよい x1x2\x * * 1 0 * x 1 x 3 + x 1 x 2 x 1 x 3 + x 2 92

93 部分論理関数とカルノー図 演習 :b6 に対応する論理関数を設計しよう x1 x2 x3 b N/A N/A N/A 93

94 クワイン マクラスキー法 機械的に最簡形を求める方法 文字列処理によって主項を発見する 手順 すべての最小項を文字列で表現する 組み合わせ表を使って文字列をまとめていく ( 主項の発見 ) 主項表を作り 必須主項を発見する 必須主項以外の主項を発見する 94

95 クワイン マクラスキ 法 項を文字列化する例 ( 変数 xyzw の場合 ) x y z w 1111 x y z w 0101 x y z 111- x z w 1-00 x z と 1 が 1 か所だけ違う文字列をまとめる = = =0--1 x y z w+ x y z w=x y z (w+ w)=x y z x y ẕ w+ x y z w= x y (z+ ẕ)w= x y w x y w+ x y w= x( y+ y)w= x w 95

96 クワイン マクラスキー法 表を使った主項の発見 1. すべての最小項の組み合わせ表を作り 第 0 表とする n 0 とする 2. まとめられる文字列はまとめる まとめられなかった項に印をつける 3. 文字列をまとめることができた場合は それらを集めて第 (n+1) 表を作る 2. へ 4. 印のついた項が主項である 96

97 表を使った主項の発見 g x, y, z, w = x y w x y z w y z w x y z w x y z w x z 最小項は 第 0 表

98 第 1 表 表を使った主項の発見

99 表を使った主項の発見 第 2 表 まとめられる組み合わせはない 発見された主項は -0-1, -01-, --11, 1-1-, 11-0 次にこの中から必須主項を探す 主項表 99

100 主項表 ある主項がどの最小項をカバーするか記入する x x x x -01- x x x x --11 x x x x 1-1- x x x x 11-0 x x 100

101 主項表 最小項のうち印が 1 個しかついてないものをチェック x x x x -01- x x x x --11 x x x x 1-1- x x x x 11-0 x x 101

102 主項表 その印がある行の主項が必須主項 x x x x -01- x x x x --11 x x x x 1-1- x x x x 11-0 x x -0-1, -01-, --11, 11-0 は必須主項 1-1- は必須主項でない 102

103 主項表 必須主項がカバーする最小項をチェック x x x x -01- x x x x --11 x x x x 1-1- x x x x 11-0 x x 必須主項だけですべての最小項がカバーできる 必須主項だけで最簡形が構成される g ( x, y, z,w)= ȳ w+ ȳ z+z w+x y w 103

104 第 0 表 カルノー図による QM 法の理解 xy \ zw 第 1 表 xy \ zw

105 カルノー図による QM 法の理解 第 2 表 xy \ zw 最適な組み合わせ xy \ zw

106 必須主項以外が必要な例 g ( x, y, z)= x y z+ x y z+ x y ẕ+ x y z+ x y ẕ 第 0 表 第 1 表

107 必須主項以外が必要な例 主項表 * * -11 * * 11- * * 1-0 * * 必須 必須 必須主項でカバーされる最小項 * * -11 * * 11- * * 1-0 * * どちらでもよいことがわかる 107

108 演習 クワイン マクラスキー法を使って x y z x y z x y z x y z x y z を簡単化せよ 108