論理式の表現を数学的に取り扱いやすくするために代数学の助けを借りる.

Presentation on theme: "論理式の表現を数学的に取り扱いやすくするために代数学の助けを借りる."— Presentation transcript:

1 論理式の表現を数学的に取り扱いやすくするために代数学の助けを借りる.
第３章　　ブール代数 論理式の表現を数学的に取り扱いやすくするために代数学の助けを借りる.

2 第３章の概要 公理 ブール代数としての論理関数 双対性 ブール代数の定理 集合論 ー ブール代数の例 簡単化の例
ｎ変数ブール代数と拡大ブール代数

3 ブール代数系 代数学 ブール代数 元の集合、演算子の組み、少数の公理系 その上に定理を組み立てて行く。 有限集合 K
二つの演算　＋、・　を定義 ６つの公理系

4 ブール代数の公理系 二つの演算 恒等元の存在 交換法則 分配法則 補元の存在 K の大きさ ＞１

5 演算子の定義 (a) K は演算子＋に関して閉じている。 (b) K は演算子 ・ に関して閉じている。

6 恒等元の存在 (a) K は演算子＋に関する恒等元をもつ。 (b) K は演算子 ・ に関する恒等元をもつ。

7 交換法則 (a) 演算子＋は可換である. (b) 演算子 ・ は可換である.

8 分配法則 (a) 演算子＋は分配法則を満たす. (b) 演算子 ･ は分配法則を満たす.

9 補元の存在 　　　　　　 にたいして を満たす　　　　　が必ず存在する. K の大きさ ＞１ Ｋ の中には相異なる元が存在する.

10 注意 Ｋ の要素については不問 通常の整数の演算と異なる。 ＋が分配する 　　　の存在 逆演算が存在しない.

11 ２元ブール代数 この系が公理１,２,３,６ を満たすことは、定義から 明らかである. 　　 ２.恒等元、３.交換法則、６.相異なる元の存在

12 ブール代数としての論理関数

13 双対性 Huntington の公理系は(a), (b) の対になっている. の変換をすれば、一方から他方が得られる

14 ブール代数の定理 補題3.4.１　恒等元０,１はそれぞれひとつしかない. 証明

15 証明終り

16 補題3.4.2　冪等（単一化） 証明

17 補題3.4.3 証明　

18 補題3.4.4 証明　

19 また、 である.双対性により

20 補題3.4.5 証明 意味が明白であれば ・ を省略することができる. 表記法としては ・ は＋に優先する.　

21 証明 いま a の補元が のように２つあるとすれば、補元の定義より、
補題3.4.6 証明　いま a の補元が　　　　　　のように２つあるとすれば、補元の定義より、 となる。したがって、 から　　　　　　をうる.よって補元は単一である.

22 証明 とおく. は の補元であるから、公理５より、
補題3.4.7　すべての　　　　　　について 　　　　　　である. 証明　　　　　　　　　　　とおく.　　は　 の補元であるから、公理５より、 　は　　の補元であるから、公理５より、 となり、交換法則から　　も　　もともに　　の補元 である.　よって補題3.4.6から　　　　である.

23 補題3.4.8 証明　　省略 定理3.4.1　結合法則

24 定理3.4.2 証明

25 定理3.4.3 (De Morgan’s law) 　　　　　ドモルガンの定理

26 証明 分配 定理１補題３ 恒等元 したがって　　　と　　　とは互いに単一の補元である.

27 集合論　･･･　ブール代数の例 全集合　　　空集合 ただし　　　　　　　　　とする.　　　の上にブール 代数を定義する. 全集合 空集合

28 例題 この代数が下の対応をつけることによって，ブール代数になることを示せ.
union, 和集合 intersection, 積集合 complement, 補集合 二つの集合　　と　　とが等しいとは、 例題　この代数が下の対応をつけることによって，ブール代数になることを示せ. （ブール代数公理の成立することを示す）

29 Venn図 and or not

30 簡単化の例 例題 3人の古書のコレクターがいた．それぞれが集めている書籍は， であるという．競合の起きる書籍はどんなものか？
例題　3人の古書のコレクターがいた．それぞれが集めている書籍は， Ａ氏　日本の歴史物と外国小説 Ｂ氏　日本の小説を除く歴史ものと小説以外の日本の作品 Ｃ氏　ノンフィクションただし日本の作品か外国の歴史もの であるという．競合の起きる書籍はどんなものか？ 本の集合を記号で表す． Ｊ　日本の作品　　　　　　Ａ　Ａ氏の収集本 Ｎ　小説　　　　　　　　　Ｂ　Ｂ氏の収集本 Ｈ　歴史物　　　　　　　　Ｃ　Ｃ氏の収集本

31 求めたい本の集合　は 一方 ABC は これを Z に代入すると複雑な式となるが，ブール代数を 用いることにより簡単化されて，（プリント参照） をうる．

32 ブール代数の表記法にしてみる．

33

34 定理3.6.1 証明 　（プリントを参照）

35 例題　下図の論理回路を簡単化せよ

36

37 例題　次の関数を簡単化せよ． 分配法則

38 別解

39 ｎ 変数論理関数 3変数論理関数はいくつあるか？ n 変数では 　通り 通り

40 関数の表現はさまざまでも種類は　　 だけ． はいずれも同じ真理値表になる． 真理値表が等しければ 二つの関数は等価である．

41 拡大ブール代数 n 変数論理関数の集合　Ｋ この上にブール代数を定義する． Ｖｅｎｎ図を使うことができる．

42 論理関数の問題 　　　　個あるn変数論理関数の一つが与えられた時に、この関数と等価な、無数にある式の表現のうちで，何かある基準のもとで最も簡単なものを求めることにある．