情報科学概論

08情報科学概論(4)：2値論理計算
2008年5月8日
田中美栄子
今回の目標
2値情報を扱う基本となる理論（ブール代数）
から
アーキテクチャ（ハードウェアの実現）へ
２進
１６進
01000000 40
01000010 42
01000100 44
01000110 46
01001000 48
01001010 4A
01001100 4C
01001110 4E
01010000 50
１０進
64
66
68
70
72
74
76
78
80
２進１６進
01000001 41
01000011 43
01000101 45
01000111 46
01001001 49
01001011 4B
01001101 4D
01001111 4F
１０進
65
67
69
71
73
75
77
79
符号化の話
２進表示
８進表示
１６進表示
１０進表示
文字
ビット組合せ
1000001
101
41
65
Ａ
4/1
• ASCII符号 American Standard Code for
Information Interchange
ASCII コード表
00 NUL| 01 SOH| 02 STX| 03 ETX| 04 EOT| 05 ENQ| 06 ACK| 07 BEL|| 08 BS | 09 HT | 0A NL | 0B VT | 0C NP | 0D CR | 0E SO
| 0F SI ||
10 DLE| 11 DC1| 12 DC2| 13 DC3| 14 DC4| 15 NAK| 16 SYN| 17 ETB||18 CAN| 19 EM | 1A SUB| 1B ESC| 1C FS | 1D GS | 1E
RS | 1F US ||
20 SP | 21 ! | 22 " | 23 # | 24 $ | 25 % | 26 & | 27 ' 28 (| 29 ) | 2A * | 2B + | 2C , | 2D - | 2E . | 2F / ||
30 0 | 31 1 | 32 2 | 33 3 | 34 4 | 35 5 | 36 6 | 37 7 || 38 8 |
39 9 | 3A : | 3B ; | 3C < | 3D = | 3E > | 3F ? ||
40 @ | 41 A | 42 B | 43 C | 44 D | 45 E | 46 F | 47 G | 48 H |
49 I | 4A J | 4B K | 4C L | 4D M | 4E N | 4F O ||
50 P | 51 Q | 52 R | 53 S | 54 T | 55 U | 56 V | 57 W || 58 X
| 59 Y | 5A Z | 5B [ | 5C \ | 5D ] | 5E ^ | 5F _ ||
60 ` | 61 a | 62 b | 63 c | 64 d | 65 e | 66 f | 67 g || 68 h | 69
i | 6A j | 6B k | 6C l | 6D m | 6E n | 6F o ||
70 p | 71 q | 72 r | 73 s | 74 t | 75 u | 76 v | 77 w || 78 x | 79
y | 7A z | 7B { | 7C | | 7D } | 7E ~ | 7F DEL|
「ABC」３文字はコンピュータ内部では41 42 43
(16)
「123」３文字は、31 32 33 (16)
と表現される。
• ASCII コード表で、16進で 00 から 1F と 7F は、
普通の文字ではなく、制御文字(control
character,制御コード)。
• 0D (CR, Carriage Return)復帰(リターン)
漢字コード
• JIS
31 32 33 1B 24 42 34 41 3B 7A 1B 40 66 34 35 36：
1 2 3 ESC $ B 漢字 ESC ( J D E F
• EUC
31 32 33 B4 C1 BB FA 34 35 36
A B C 漢字 D E F
• SJIS
31 32 33 8A BF 8E 9A 34 35 36
A B C 漢字 D E F
• つまり、ノイマン式コンピュータはいろいろな
情報を2進数で記憶し、それらの演算をやっ
ているだけなのである
• 演算は単純化される
• 入力→演算→出力を自動的に行う素子で
回路を組み立てる（論理回路）
• すると、コンピュータができる
ブール代数：Boolean Algebra
• Booleさんの作った論理数学
• 論理変数（真/偽の2値：１と0で代用する）を扱う
• 基本演算はAND，OR，NOT
• 論理演算の機能を持つ論理素子を使って，論理関
数を回路で表現したものが論理回路
• ノイマン・コンピュータは基本的に論理回路で構成
基本論理演算
• 論理積（乗法 AND） x･y
– 2変数がともに1の時，論理積は1
– 2変数のいずれかが0の時，論理積は0
• 論理和（加法 OR） x+y
– 2変数のいずれかが1の時，論理和は1
– 2変数がともに0の時，論理和は0
• 論理否定（否定 NOT） x
– 変数が0の時，論理否定は1
– 変数が1の時，論理否定は0
演算の優先順位は，否定，乗法，加法の順
真理値表
論理変数の値とそれに対する論理関数の値の関係の表
x
y
x･y
x+y
x
0
0
0
0
1
0
1
0
1
1
1
0
0
1
0
1
1
1
1
0
ブール代数の定理
名称
単位元則
零元則
べき等則
補元則
交換則
結合則
分配則
吸収則
ド･モルガン則
AND形式
x･1=x
x･0=0
x･x=x
x･x=0
x･y=y･x
(x･y)･z=x･(y･z)
x+y･z=(x+y)･(x+z)
x･(x+y)=x
x･y=x+y
OR形式
x+0=x
x+1=1
x+x=x
x+x=1
x+y=y+x
(x+y)+z=x+(y+z)
x･(y+z)=x･y+x･z
x+x･y=x
x+y=x･y
例題1
分配則x+y･z=(x+y)･(x+z)を真理値表で確かめよ
x
0
0
0
0
1
1
1
1
y
0
0
1
1
0
0
1
1
z
0
1
0
1
0
1
0
1
y･z
0
0
0
1
0
0
0
1
x+y x+z
0
0
0
1
1
0
1
1
1
1
1
1
1
1
1
1
(x+y)･(x+z)
0
0
0
1
1
1
1
1
x+y･z
0
0
0
1
1
1
1
1
論理式の作り方
すべての論理関数は，真理値表，論理式で表現できる．
論理式を回路で構成したものが論理回路（論理式と1対1
対応）
• 入力のすべての組み合わせのうち，出力が1の
ものだけについて，入力が1のものはそのまま，
0なら否定したものの積の式を書く．この式を最
小項という．
• 最小項の論理和が求める論理式である．
主加法標準形 or 積和標準形
例題2
3入力のうち，多数が1の時出力1となり，多数が0
の時出力0となる多数決論理の論理式を書け
x
y
z
f
0
0
0
0
1
1
1
1
0
0
1
1
0
0
1
1
0
1
0
1
0
1
0
1
0
0
0
1
0
1
1
1
x･y･z
x･y･z
x･y･z
x･y･z
f = x･y･z + x･y･z +
x･y･z + x･y･z
演習問題
• 吸収則x･(x+y)=x, x+x･y=xを真理値表で確
かめよ
• 2入力の比較器(2入力が同じなら1，異なるな
ら0を出力)の真理値表と論理式を書け
演習問題1
吸収則x･(x+y)=x, x+x･y=xを真理値表で確かめよ
x y
0
0
1
1
0
1
0
1
x+y
x･(x+y)
x･y
x+x･y
0
1
1
1
0
0
1
1
0
0
0
1
0
0
1
1
演習問題2
2入力の比較器(2入力が同じなら1，異なるなら0
を出力)の真理値表と論理式を書け
x
y
f
0
0
1
1
0
1
0
1
1
0
0
1
x･y
f = x･y+ x･y
x･y
x y
0
0
1
1
0
1
0
1
x･y x･y x･y+ x･y
1
0
0
0
0
0
0
1
1
0
0
1
f
1
0
0
1

Download Report