Microsoft PowerPoint - LogicCircuits01.pptx

Transcription

1 論理回路 第 回論理回路の数学的基本 - ブール代数 38 号館 4 階 N-4 内線 5459 [email protected]

2 本科目の内容 電子計算機 computer の構成 ソフトウェア 複数のプログラムの組み合わせ オペレーティングシステム アプリケーション等 ハードウェア 複数の回路 circuit の組み合わせ メモリ 演算回路 制御回路等 本科目で学ぶこと 論理回路の働きとその設計手法

3 成績について 課題レポート 3% 中間試験 3% 期末試験 4% 無届欠席禁止 やむを得ず欠席した場合は翌週までに欠席届を提出すること 無届欠席が複数回ある場合は試験の点数に関わりなく不受となる

4 ウェブ教材 URL: 独立行政法人科学技術振興機構 上記のページにてユーザ登録後 研究人材のための e-leaning 教材を選ぶ 電気電子 ディジタル回路コース と辿ってください

5 論理と情報 我々の周囲には様々な情報がある 様々な情報の形態 文字 信号 音声 図形 画像 映像 情報の整理 分析が必要 情報の整理 分析を簡単にするには? 論理 logic を用いる

6 論理と情報 何故論理が必要? 世の中には論理で表現される物事が多い 論理を使えば 物事の曖昧性が無くなりはっきりする 簡単に処理できる 論理を計算機で扱うには? ブール代数を用いる

7 情報の種類アナログとデジタル アナログ情報 : 連続的な値 時間 電圧 気温 質量 大きさ デジタル情報 : 離散的な値 連続的な値を一定周期毎の有限桁の数値で表現 アナログ量 デジタル量

8 計算機アナログ計算機とデジタル計算機 アナログ計算機 : 現在では使われない 数値を電圧 電流等で表現 人間の脳も一種のアナログ計算機 将来はDNA 分子計算機で復活するかも? デジタル計算機 : 現行の計算機 数値を 高電位 と 低電位 の2 値で表現 将来は量子計算機へ進化?

9 論理と論理変数 論理 : 2 つの値で表現されるデジタル情報 と yes と no 真と偽 論理変数 : か のみ を取る変数 n 個並べれば n 桁の 2 進数を表現可能 スイッチの ON - OFF を表現可能 5 : 2: : :

10 論理変数が示す値 論理変数 : か のみを取る変数 2 進値 有限桁の数値を2 進数で表したもの 算術演算を適用 論理値 数値ではない = 偽 = 真 論理演算を適用

11 論理値 公理 論理値 論理変数は か の 2 種の値しか取らない 例 : が論理変数 = または =

12 単項演算子 NOT 定義. 否定 NOT ~ではない 非 ~ 不 ~ を表す 演算記号 公理 2 NOT 真 のNOTは 偽 偽 のNOTは 真

13 2 項演算子 AND 定義.2 論理積 AND ~かつ~ を表す 2 項のうち小さい方を取る 演算記号 公理 3 AND 両方とも のときのみ

14 2 項演算子 OR 定義.3 論理和 OR ~ または ~ を表す 2 項のうち大きい方を取る 演算記号 + 公理 4 OR つでも のとき + +=2 ではない

15 NOT AND OR のベン図 NOT AND OR +

16 論理演算子の優先順位 括弧 否定 論理積 論理和 + 例題 : の実行順は?

17 論理関係と論理式 論理式 : 論理関係を表す式 例題論理関係 A である かつ B でない の両方が成立するか C でない または D である のいずれかが成立する を論理式で表すと? A B C D A B C D

18 論理関数 y = f x x 2 x n 数値関数 y = 2x 2 + 等と同じ ただし y も x i も か の値しか取らない 例 : y f x x x x x x x y f x = x 2 = のとき

19 真理値表 関数値を と の表として表す n 変数ならば組み合わせは 2 n 通り 例 : f の真理値表 f

20 真理値表の例題 例題.4 f 表す真理値表を示せ を f f

21 演習問題 : 真理値表の作成 を表す真理値表を示せ f

22 問題 : 真理値表の作成 真理値表を示せ f を表す f

23 有界則 定理.2 有界則 公理 3より 公理 4より 問題上式を確かめよ でも成立 +

24 有界則の証明 定理.2 有界則 公理 3より 公理 4より 証明 論理変数は か の値しか取らない 公理 ので に を代入すれば公理 34 になり 明らか成立する 注 : 上 2 式は双対 後述 である従って片方が成立すればもう片方も成立する

25 同一則 定理.3 同一則 公理 3より 公理 問題上式を確かめよ 4より +

26 べき等則 定理.4 べき等則 公理 3より 2 ではない 公理 問題上式を確かめよ 4より 2 ではない +

27 べき等則の証明 定理.4 べき等則 公理 3より 公理 4より 証明 二項演算子 は両項の小さい方を取る演算である と の小さい方は であるので = が成り立つ + = も同様である

28 べき等則の系 系.5... 定理.4 より... 定理.4 より 証明 べき等則を繰り返して用いれば明らか

29 相補則 定理.6 相補則 補元則 公理 および公理 3より 問題上式を確かめよ 公理 および公理 4より

30 2 重否定 定理.7 2 重否定対合則 公理 より 問題上式を確かめよ

31 交換則 定理.8 交換則 公理 3より 問題上式を確かめよ 公理 4より + +

32 交換則 数式との比較 定理.8 交換則 公理 3より 数式だと abc : 実数 ABC: 行列 ab = ba 成立 a +b = b +a 成立 A B B A 不成立 A+B = B+A 成立 a-b b-a 不成立 公理 4より

33 結合則 定理.9 結合則 問題上式を確かめよ

34 結合則 数式との比較 定理.9 結合則 数式だと abc: 実数 ABC: 行列 abc = a bc 成立 a +b+c = a +b+c 成立 A B C = A B C 成立 A+B+C = A+B+C 成立 a-b-c a-b-c 不成立

35 分配則 定理. 分配則 問題上式を確かめよ

36 分配則 数式との比較 定理. 分配則 数式だと abc : 実数 ABC: 行列 a b+c = ab + ac 成立 a+bc a+ba+c 不成立 A B+C = A B+A C 成立 A+B C A+B A+C 不成立

37 吸収則 定理. 吸収則 問題上式を確かめよ + +

38 その他便利な規則 系.2 + +

39 系.2 の証明 系.2 証明 同一則相補則分配則

40 系.2 の証明 と を寄せ集める 右辺 : + とき に含まれる つまり は不要なので のみを寄せ集めると良い

41 ド モルガンの定理 定理.3 ド モルガンの定理

42 ド モルガンの定理の証明

43 多変数のド モルガンの定理 系.4 多変数ド モルガンの定理 n 式中の i と i と + と を入れ替え 全体の NOT を取る 証明 ド モルガンの定理を繰り返し用いれば明らか n n n

44 ド モルガンの系 両辺の否定を取って 系.5 AND は NOT と OR で OR は NOT と AND で表せる

45 拡張されたド モルガンの定理 定理.4 拡張ド モルガンの定理 式中の i と i と + と を入れ替える 注 : 演算子の優先順位に注意すること m m m m f L f L : L 例 L

46 拡張ド モルガンの定理の証明 証明 式を積和展開して n 項ド モルガンの定理よりすなわち n m l c c c b b b a a a L n m l n m l c c c b b b a a a c c c b b b a a a L m m m m f f L

47 双対な論理式 論理式 L の双対な論理式 L d L の と と + を入れ替えたもの 例題 : L の d L は? L d = + + 注 : 演算子の優先順位に注意すること

48 双対な論理式の例 L d L L L d L L d L = L d では無いことに注意

49 双対な論理式の関係 L d L L L d 入力の と を入れ替えたときに出力の と が入れ替わる

50 双対性 定理 双対性 P = Q ならば P d = Q d P Q P d Q d Q P 例 Q P d d

51 双対性の証明 定理 双対性 P = Q ならば P d = Q d 証明 ある論理式 L が公理に含まれるとき その双対な論理式 L d も公理に含まれる + = 公理 4 の双対は = 公理 3 従って P に対して P d が一意に決まるよって P = Q ならば P d = Q d となる 注 : 双対性とは P d = P ではない

52 双対性の利点 ある論理式 L を定義すれば それと双対な論理式 L d が存在する 論理代数の定理のほとんどは対になる 定理の証明は片方に対してのみ行えばよい

53 相対な式 有界則 相補則 同一則 交換則 べき等則 吸収則 多くの公式が相対な式の組

54 双対関数 定義.6 双対関数 式中の と + と を入れ替える 例題の双対関数 : f f d m m d m m f f f の双対関数

55 ド モルガンの定理と双対関数 L = f 2 2 m m + ド モルガンの定理 L = f 2 2 m m + 式中の i と i と + と を入れ替える 双対関数 L d = f 2 2 m m + 式中の と + と を入れ替る

56 ド モルガンの定理と双対関数 ド モルガンの定理 双対関数 式中の i と i と + と を入れ替える 式中の と + と を入れ替える f f f d

57 演習問題 : ド モルガンの定理の論理式を求めよ のとき f f f 式中の i と i と + と を入れ替える

58 演習問題 : 双対な論理式の論理式を求めよ のとき f f d f d 式中の と + と を入れ替える

59 問題 : 双対な論理式 f 双対な論理式 f d を書け の f d

60 自己双対関数 定義.6 自己双対関数 f =f d のとき f を自己双対関数と言う 例題 : f f d = = + + = + + = f

61 問題 : 自己双対関数 f 自己双対関数であることを示せ が f d

62 論理式の標準形 論理関数は論理式で表される 論理関数の解析 論理回路の設計 2つの論理関数間の等価性の判定 論理式の標準形があれば便利

63 論理積項 論理和項 論理積項 : AND と NOT のみの式 例 : 論理和項 : OR と NOT のみの式 例 :

64 積和形 和積系 積和形 AND-OR 形 論理積項の和で表される式 例 : 和積形 OR-AND 形 論理和項の積で表される式 例 :

65 最小項 定義.9 最小項 最小項 あるいは極小項 ~ 全ての変数の積 ~ 2... n ~ i は i または i を表す n 変数の式の場合 最小項は2 n 個 ~

66 最小項 例題 f の最小項を全て書け 3 変数なので最小項は 2 3 = 8 通り

67 最小項と真理値表 / カルノー図 最小項は真理値表のある マスに相当 f x y z 最小項

68 最大項 定義. 最大項 最大項 あるいは極大項 ~ 全ての変数の和 ~ 2... n ~ i は i または i を表す n 変数の式の場合 最大項は2 n 個 ~

69 最大項 例題 f の最大項を全て書け 3 変数なので最大項は 2 3 = 8 通り

70 最大項と真理値表 / カルノー図 最大項は真理値表のある マス以外の全てのマスに相当 f x y z 最大項 ++

71 標準積和形 定義. 標準積和形 主加法標準系 最小項表現 n 変数論理関数の標準積和形 f l l 2 l n = となる最小項の和 f = f = f = f = f 例題の標準積和形 : f

72 標準積和形の利用 どんな論理式も 唯一の標準積和形を持つ 標準積和形に変換 展開 できる 形が異なる2つの論理式の異同を調べたい 両者を標準積和形に変形すれば良い

73 標準積和形の例題 例題.: f を標準積和形にせよ f f = f =f = より f

74 標準積和形の例題 f g よって f = g f g が同値であることを示せと例題 :.2 g f

75 問題 : 標準積和系 f を標準積和形にせよ f f =

76 予習問題 : 論理式と論理回路論理式 f f 2 f 3 を表す論理回路 F F 2 F 3 を描け f f f 3 2 F F 2 F 3

77 TkGate TkGate 論理回路のシミュレータ 論理素子やモジュールを使用可能 フリーソフト ただし現在更新停止 第 4 回 4/27 に TkGate を用いた実習を行う予定

78

79 TkGate のインストール ノート PC に TkGate をインストールすること 論理回路のページにインストール方法を記載 最低でもダウンロードはしておくこと

80

81

82 演習問題 : 真理値表の作成 f を表す真理値表を示せ f

83 演習問題 : 有界則 定理.2 有界則 公理 3より 公理 4より でも成立 上式を確かめよ + = += = +=

84 演習問題 : 同一則 定理.3 同一則 上式を確かめよ 公理 3より 公理 4より + = += = +=

85 演習問題 : べき等則 定理.4 べき等則 公理 3より 2 ではない 公理 4より 2 ではない 上式を確かめよ + = += = +=

86 演習問題 : 相補則 定理.6 相補則 補元則 上式を確かめよ 公理 および公理 3より 公理 および公理 4より + = += = +=

87 演習問題 : 2 重否定定理.7 2 重否定対合則 公理 より 上式を確かめよ == ==

88 演習問題 : 交換則定理.8 交換則 公理 3より 公理 4より 上式を確かめよ = = = = = = = = + + += += += += += += += +=

89 演習問題 : 結合則定理.9 結合則 上式を確かめよ = = = = = = = = = = = = = = = =

90 演習問題 : 分配則定理. 分配則 + = + + = + + 上式を確かめよ + + = + = = + = = + = = + = + + = + = = + = = + = = + =

91 演習問題 : 吸収則定理. 吸収則 上式を確かめよ = + = + = + = = = = =

92 演習問題 : ド モルガンの定理の論理式を求めよ のとき f f f 式中の i と i と + と を入れ替える

93 演習問題 : 双対な論理式の論理式を求めよ のとき f f d f d 式中の と + と を入れ替える

94 参考資料 : 標準和積形 定義.2 標準和積形 主乗法標準系 最大項表現 n 変数論理関数の標準和積形 f l l 2 l n = となる最大項の積 f = f = f = f = f 例題の標準和積形 : f

95 参考資料 : 標準和積形の例題 例題.3 : f = + を標準和積形にせよ f f f =f = より f =

96 参考資料 : リテラル 定義.8 リテラル 論理式を構成する論理変数とその否定 ~ 論理変数 のリテラル は と リテラルを使う利点 NOT を気にせず ANDOR のみに着目できる

97 参考資料 : 一般化吸収則 定理.7 一般化吸収則 i + f i n = i + f n i f i n = i f n 証明 i = とのき上式は両辺とも i = とのき上式は両辺ともf n

98 参考資料 : 一般化吸収則の例 定理.7 一般化吸収則 i + f i n = i + f n i f i n = i f n 例 : f = + +f = + f = + + = +

99 参考資料 : 一般吸収則の性質 i + f i n = i + f n i f i n = i f n 下式において i = のとき f i n = f n =f n 上式において i = のとき f i n = + f n =f n

100 参考資料 : 一般吸収則の性質 f i n = f i n i = のとき f i n i = のとき if i then f i n = f n = i f n else f i n = f n = i f n f i n = i f n + i f n

101 参考資料 : シャノンの展開定理 定理.8 シャノンの展開定理 f i n = i f n + i f n f i n = i +f n i +f n シャノンの展開定理の効果 関数 f が i と i で展開される i に関する積和形 和積系 に変形可能

102 参考資料 : シャノンの展開定理による積和形 例題 f = + を に関して展開し積和形にせよ f = f + f = = = +

103 参考資料 : 積和形への変形 全ての変数に対してシャノンの展開を使えばどんな論理関数でも積和形になる f 2 n = f 2 n + f 2 n = 2 f n + 2 f n + 2 f n + 2 f n = = 2 n f +