コンピュータアーキテクチャI #2 論理数学の基礎

Presentation on theme: "コンピュータアーキテクチャI #2 論理数学の基礎"— Presentation transcript:

1 コンピュータアーキテクチャI #2 論理数学の基礎
平成30年4月20日 教科書p.12～p.23

2 本日の講義内容 2進数と10進数（復習） 論理とは？ 論理表現と演算 基本的な論理演算 まとめ 組み合わせ論理，順序論理，２値論理
真理値と真理値表 基本的な論理演算 論理和，論理積，否定 ベン図による論理の表現 双対性 まとめ

3 2進-10進変換 10進数→2進数 2進数→10進数 2で割って余りを求める これを余りが０か１になるまで続ける
最後に求めた余りから最初の方に向かって余り（０か１）を並べれば変換終了 2進数→10進数 2進数の第𝑘桁目は 2 𝑘 を表す 𝑘桁目の値 𝑎 𝑘 に 2 𝑘 をかけた値を各桁で求める これをすべて加えれば変換終了

4 論理とは ろんり（logic）＜広辞苑＞ 「論理回路」の世界では，論理変数と論理演算を組み合わせ，「命題」を表現する手立て．
思考の形式・法則。また、思考の法則的なつながり。 実際に行われている推理の仕方。論証のすじみち。 比喩的に、事物間の法則的なつながり。 「論理回路」の世界では，論理変数と論理演算を組み合わせ，「命題」を表現する手立て．

5 命題(Proposition) 正しいか，正しくないかの判定ができる文章や数式のこと ある命題が正しい： 真（True，１）
「２０１7年度セントラルリーグ優勝はカープだった」 「２０１7年度セントラルリーグ優勝チームは？」 「赤い色の果物はイチゴである」 「いちごは赤い色の果物である」 ある命題が正しい：　真（True，１） ある命題が正しくない：　偽（False，０）

6 論理変数 ある物事を表すのに用いる「変数」．2値しかとりえない変数を用いるときは「2値論理」と呼ぶ． (例)論理変数𝑋：そば粉が使われている
「そば」や「そばがき」など：𝑋=1 「うどん」や「パスタ」など：𝑋=0 (例）論理変数𝑌：海苔がのっている 「ざるそば」，「親子丼」など：𝑌=1 「ハンバーグ」など：𝑌=0

7 独立変数と従属変数 𝑃=𝑋∩𝑌 𝑄=𝑋∩ 𝑌 独立変数 従属変数 他に束縛されることなく値を決定できる 先の例では論理変数𝑋,𝑌が該当する
他の論理変数の値により，値が決まる変数 「ざるそば」を論理変数𝑃とすれば，𝑃は従属変数であり，以下のように表される 「もりそば」を論理変数𝑄とすれば，𝑄は従属変数であり，以下のように表される 𝑃=𝑋∩𝑌 𝑄=𝑋∩ 𝑌

8 真理値と真理値表 すべての独立変数がとりうる値に対して，従属変数がどのような値をとるかを一覧表にしたもの 論理変数がとる値 𝑋 𝑌 𝑃 1
変数𝑋：そば粉 変数𝑌:海苔 変数𝑃:ざるそば 論理変数がとる値 論理値と呼ぶ 𝑋 𝑌 𝑃 1

9 例題：真理値表を作ってみる ２つの２進数１桁を加算したときの和と桁上がりの関係
講義が休講であり，霧島，秋月，雪風の急速修理が完了していれば遠征に出す 宮崎県内で生まれ畜養された黒毛和種であり，肉質等級が4等級以上，かつ県内種雄牛，もしくは家畜改良のため指定された種雄牛を一代祖にもつものであれば，「宮崎牛」である（2017年4月改訂）

10 命題の否定 𝑈 𝑋 𝑋 𝑋=1のとき 𝑋 =0 𝑋=0のとき 𝑋 =1 ある論理変数𝑋に対し，その値を否定（反転）すること
論理変数𝑋の否定： 𝑋 　 𝑋=1のとき 𝑋 =0 𝑈 𝑋 𝑋 𝑋=0のとき 𝑋 =1

11 論理積 𝑋⋅𝑌 ある命題𝑋と𝑌があり，ともに｢真」のときのみ成り立つ命題𝑍 𝑋 𝑌 𝑍 1 𝑍は𝑋と𝑌の「論理積」である，という
𝑍=𝑋⋅𝑌=𝑋𝑌 𝑍=𝑋∩𝑌 𝑍=𝑋 𝑎𝑛𝑑 𝑌 𝑋 𝑌 𝑍 1 𝑋⋅𝑌 𝑈 𝑌 𝑋

12 論理和 𝑋+𝑌 ある命題𝑋と𝑌があり，どちらか一方が｢真」であれば成り立つ命題𝑍 𝑋 𝑌 𝑍 1 𝑍は𝑋と𝑌の｢論理和」である，という
𝑍=𝑋+𝑌 𝑍=𝑋∪𝑌 𝑍=𝑋 𝑜𝑟 𝑌 𝑋 𝑌 𝑍 1 𝑋+𝑌 𝑈 𝑌 𝑋

13 2変数のAND,OR,NOTと真理値表 論理変数𝑋,𝑌によるAND，OR，𝑌に対するNOT演算をまとめて書きなさい 𝑋 𝑌 AND OR
𝑁𝑂𝑇 𝑌 1 1 1 1 1 1 1

14 ３変数のAND,ORと真理値表 論理変数𝐴,𝐵,𝐶に対するANDとORをまとめて書きなさい 𝐴 𝐵 𝐶 AND OR 1 1 1

15 論理式（関数）とは 𝑍= 𝐴+𝐵 ⋅𝐶⋅ 𝐷 ある命題を，論理変数とその演算を組み合わせて表現したもの
命題Z：「翌日が土曜日か日曜日であり，天気予報が晴れであり，かつ所持金が3千円以下でなければ海水浴にいく」 翌日が土曜日：　A（真ならば１） 翌日が日曜日：　B（真ならば１） 天気予報が晴れ：　C（真ならば1） 所持金が3千円以下：　D（真ならば１） 𝑍= 𝐴+𝐵 ⋅𝐶⋅ 𝐷

16 真理値表と論理式 𝑍= 𝐴 𝐵 𝐶 + 𝐴 𝐵𝐶+𝐴 𝐵 𝐶 +𝐴𝐵𝐶 論理式 1 𝑍 𝐶 𝐵 𝐴
𝑍= 𝐴 𝐵 𝐶 + 𝐴 𝐵𝐶+𝐴 𝐵 𝐶 +𝐴𝐵𝐶 論理式 ある論理変数について，真となる条件のみを独立変数の論理演算の形で表したもの 真理値表が与えられたとき， 論理式が１となる場合の， 各場合の論理変数の値を調べ， 論理変数の値が１ならそのまま， 論理変数の値が０なら変数を否定し， 結果の論理積をとり， すべての場合の5を論理和で結ぶ 1 𝑍 𝐶 𝐵 𝐴

17 ブール代数 ブールさん ブール代数 論理変数に対する演算を体系化した人 論理変数に対する演算体系
代数構造 𝐴,+,⋅,−,0,1 , 𝐴∈𝑈 演算の強さ：　NOT > AND > OR 否定

18 ブール代数の公理（１） 𝐴,𝐵∈𝑈を前提とする 公理1: 公理２： 公理３：交換則 (a) 𝐴+𝐵∈𝑈 (b) 𝐴⋅𝐵∈𝑈

19 ブール代数の公理（２） 公理４：（分配則） 公理５：元0と元１が唯一であるとき， なる元 𝐴 が存在する
(a) 𝐴+ 𝐵⋅𝐶 = 𝐴+𝐵 ⋅(𝐴+𝐶) (b) 𝐴⋅ 𝐵+𝐶 = 𝐴⋅𝐵 +(𝐴⋅𝐶) 公理５：元0と元１が唯一であるとき， 　　なる元 𝐴 が存在する 公理６： 𝑈には𝐴≠𝐵となる𝐴と𝐵が存在する ∀𝐴∈𝑈, 𝐴⋅ 𝐴 =0, 𝐴+ 𝐴 =1

20 双対性 ある論理関係の０を１，１を０，＋を・，・を＋に置き換えて出来る関係を｢双対｣という 双対性が成り立つ公理 公理1aと1b

21 閑話休題 公理 証明不可能であるとともに、また証明を必要とせず直接に自明の真として承認され他の命題の前提となる根本命題。(ｲ)ある理論領域で仮定される基本前提。この場合、公理は自明な真理ではなく、公理系のとり方によって定まる。従ってある公理系で公理である命題も、他の公理系においては公理から証明される定理となることや、また偽となることがある。 定理 (theorem) すでに真なりと証明された一般的命題。公理または定義を基礎として真であると証明された理論的命題。

22 主なブール代数の定理（１） 公理2aを満たす元０および公理2bを満たす元１は，それぞれ唯一つ存在する
公理５を満たす元 𝐴 はただ1つだけ存在する 任意の元Aに対し，次のべき等則が成立する　 𝐴+𝐴=𝐴 𝐴⋅𝐴=𝐴

23 主なブール代数の定理（３） 𝐴 =𝐴 𝐴+𝐵 +𝐶=𝐴+ 𝐵+𝐶 𝐴𝐵 𝐶=𝐴(𝐵𝐶) 任意の元𝐴に対し，次の復帰則が成立する
任意の元𝐴,𝐵,𝐶に対し，次の結合則が成立する 𝐴 =𝐴 𝐴+𝐵 +𝐶=𝐴+ 𝐵+𝐶 𝐴𝐵 𝐶=𝐴(𝐵𝐶)

24 主なブール代数の定理（４） 𝐴+𝐴⋅𝐵=𝐴 𝐴 𝐴+𝐵 =𝐴 𝐴+𝐵 ⋅ 𝐴+ 𝐵 =𝐴 𝐴⋅𝐵 + 𝐴⋅ 𝐵 =𝐴
任意の元𝐴,𝐵に対し，次の吸収則が成立する 任意の元𝐴,𝐵に対し，次の第２吸収則が成立する 𝐴+𝐴⋅𝐵=𝐴 𝐴 𝐴+𝐵 =𝐴 𝐴+𝐵 ⋅ 𝐴+ 𝐵 =𝐴 𝐴⋅𝐵 + 𝐴⋅ 𝐵 =𝐴

25 主なブール代数の定理（５） 任意の元𝐴,𝐵に対し，次のド・モルガンの定理が成立する 𝐴+𝐵 = 𝐴 ⋅ 𝐵 𝐴⋅𝐵 = 𝐴 + 𝐵

26 練習問題 下の式をブール代数を用いて証明せよ 𝐴+ 𝐴 ⋅𝐵=𝐴+𝐵　 𝐴 𝐴 +𝐵 =𝐴⋅𝐵　　

27 本日のまとめと来週の予定 論理演算の基本 来週の予定 命題と論理変数 真理値と真理値表 基本的な論理演算（AND, OR, NOT）
ブール代数の公理と定理 来週の予定 ２変数論理関数とド・モルガンの法則 加法標準形と乗法標準形