第３回情報科学概論：2値論理計算 2014年4月21日田中美栄子今回の目標 2値情報を扱う基本となる理論（ブール代数）からアーキテクチャ（ハードウェアの実現）へ 10進数・16進数・2進数復習 64 65 66 67 68 69 40 41 42 43 44 45 1010 1011 1100 1101 1110 1111 70 71 72 73 74 75 46 47 48 49 50 51 10000 10001 10010 10011 10100 10101 符号化の話２進表示８進表示１６進表示１０進表示文字ビット組合せ 1000001 101 41 65 Ａ 4/1 • ASCII符号 American Standard Code for Information Interchange ASCII コード ASCII( American standard code for information interchange) コンピュータその他の通信機器において最もよく使われている文字コード ASCII コード 10進 16進文字 10進 16進文字 0 0x00 NUL（null文字) 65 0x41 A 1 0x01 SOH（ヘッダ開始） 66 0x42 B 2 0x02 STX（テキスト開始） 67 0x43 C 3 0x03 ETX（テキスト終了） 68 0x44 D 4 0x04 EOT（転送終了） 69 0x45 E 70 0x46 F 71 0x47 G 32 0x20 （スペース） 33 0x21 ! 34 0x22 " 35 0x23 # 36 0x24 $ 37 0x25 % 「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 • 英語圏の文字コードは１Byte言語 – 1bitはパリティービットに使用する(誤り検出用) – 7bitで128種を扱う • 日本語・中国語・ハングルは２Byte言語 – 65536種類の表記が可能 – JIS X 0208では記号も入れて6879文字を規定 • つまり、ノイマン式コンピュータはいろいろな情報を2進数で記憶し、それらの演算をやっているだけなのである • 演算は単純化される • 入力→演算→出力を自動的に行う素子で回路を組み立てる（論理回路） • すると、コンピュータができるブール代数：Boolean Algebra • Booleさんの作った論理数学 • 論理変数を扱う ① A B A B A B – （真/偽の2値：１と0で代用する） • 基本演算は ①AND ②OR ③NOT • 論理演算の機能を持つ論理素子を使って，論理関数を回路で表現したものが論理回路 • ノイマン・コンピュータは基本的に論理回路で構成 ② ③ 基本論理演算 • 論理積（乗法 AND） x･y – 2変数がともに1の時，論理積は1 – 2変数のいずれかが0の時，論理積は0 • 論理和（加法 OR） x+y – 2変数のいずれかが1の時，論理和は1 – 2変数がともに0の時，論理和は0 xx x 00 0 00 １ 11 11 yy 00 11 x １０ x+y x･y 00 0１ 00 0１ 11 11 • 論理否定（否定 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 (x+y)･(x+y)・x 答組複えみ雑を合な求わ論めせ理らて演れいけ算るばもブール代数の定理名称単位元則零元則べき等則補元則交換則結合則分配則吸収則ド･モルガン則 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