がんばれ！！しんちゃん
子育てから、音楽・ビデオ鑑賞などの趣味、学問や能力開発等生活全般に関する話題を断片的に書き綴る。
コンピュータ科学基礎��
コンピュータ科学基礎��


論理演算・論理回路



(1)命題

●命題の真偽
　真　...　True　又は、1
　偽　...　False　又は、0

(2)論理演算

●論理和(OR)　...　いずれか一方が真であれば、結果が真となる








論理和の真理値表
ABA　OR　B
０００
０１１
１０１
１１１


●論理積(AND)　...　双方が真の場合のみ、結果が真となる








論理積の真理値表
ABA　OR　B
０００
０１０
１００
１１１


●排他的論理和(Exclusive OR：EOR又はXOR)　...　いずれか一方が真の場合は結果が真に、双方の値が一致した場合は結果が偽となる








排他的論理和の真理値表
ABA　OR　B
０００
０１１
１０１
１１０



●否定(NOT)　...　真偽を反転させる






排他的論理和の真理値表
ANOT A
０１
１０




(3)論理演算の公式

●分配則
　A・（B＋C）＝（A・B)＋（A・C）
　A＋（B・C）＝（A＋B）・（A＋C）

●吸収則
　A＋（A・B）＝A
　A・（A＋B）＝A
　A＋（¬A・B）＝A＋B

●ド・モルガンの法則
　¬（A・B）＝¬A＋¬B
　¬（A＋B）＝¬A・¬B

(例)　X・¬Yの真理値表は？






XYX　AND　¬Y
０００
０１０
１０１
１１０


(例)ビット数が等しい任意のビット列aとbに対して、等式a=bと a XOR同じことを表すものはどれか？

　(ア)a　AND　b　＝　００・・・０
　(イ)a　OR　ｂ　＝　１１・・１
　(ウ)a　XOR　ｂ　＝　００・・・０
　(エ)a　XOR　ｂ　＝　１１・・・１





AND　・・・双方のビットが１の場合のみ結果が１となる
OR　・・・一方のビットが１であれば結果が１となる
XOR　・・・同じビットパターンの場合、結果が０となる


a　XOR　ｂ　＝　００・・・０　は成り立つ

(4)論理回路

mil



●半加算回路　...　下位桁からの桁上がりを考慮しない1桁の2進数の加算を行う回路。

２つの入力AとBに対し、AとBの加算の結果をSに、桁上がりがあればCに出力する。








半加算回路の真理値表
入力A入力B出力C出力S
００００
０１０１
１００１
１１１０



mil_han



●全加算回路　...　下位桁からの桁上がりも考慮に入れた加算回路。

半加算回路を組み合わせることで、下位桁からの桁上がりを考慮した2進数1桁の加算を行うことができる。
最下位桁は半加算回路、それ以外を全加算回路として構築できる。
加算回路があれば、負の数を補数表示することにより減算も可能になり、加算を繰り返すことで乗算を、減算を繰り返して除算を行うことが可能にる。

mil_zen


(5)シフト演算

ビット列に対する演算も1ビットごとに独立した演算と考えればよく、この場合、算術演算と異なり、桁上がりを考慮する必要がない。
なお、ビット列を右や左に移動(シフト)することによって演算(2x倍のみ)を行うシフト演算がある。









A・Bのビット演算
Ａ０１０１０１０１
・・・・・・・・
・・・・・・・・
・）Ｂ００１１１１００
______________________________
０００１０１００












A＋Bのビット演算
Ａ０１０１０１０１
・・・・・・・・
・・・・・・・・
+）Ｂ００１１１１００
______________________________
０１１１１１０１


●論理シフト演算
論理シフトは、指定されたビット数だけ全体をシフトし、空いたビットには０を挿入する。
右にｎビットシフトすると数値を２−ｎ倍、左にシフトすると数値を２ｎ倍にすることができる。
ただし、値がオーバフロー、またはアンダフローを起こさない場合に限る。








A＋Bのビット演算
１００１００１０・・・146
右に１ビットシフト（×２−１）↓↑アンダフローされるビット
０１００１００１・・・73
↑挿入されたビット


●算術シフト演算
符号ビット(一番左のビット)を固定することで、負の数のシフト演算も可能にする。
右シフトした場合は、符号ビットと同じ値を空いたビットに挿入する。
左シフトの場合は、空いたビットに０を挿入する。






１１１１００００・・・-32
右に１ビットシフト（×２−１）↓↑アンダフローされるビット
１１１１００００・・・-16
↑挿入されたビット








１１１０００００・・・-32
左に１ビットシフト（×２１）　↓　↑オーバフローされるビット
１１００００００・・・-16
↑挿入されたビット


●シフト演算の組み合わせによる計算

シフト演算では、2n倍しかできないが、シフト演算を組み合わせることによって、様々な演算を行うことができる。
例えば、５倍したい場合は、２ビット左シフト(２2＝４倍)したものと元の値を加算すれば丁度５倍になる。

(例)32ビットレジスタに(ABCD)16が入っているとき、2ビットだけ右に論理シフトしたときの値は？

まず、2進数に変換する。
(ABCD)16　→　(1010　1011　1100　1101)2

次に、右に2ビット論理シフト演算をする。
(1010　1011　1100　1101)2　→　(001010　1011　1100　1101)2
2進数を１６進数に戻す。
(001010　1011　1100　11)2　→　(2AF3)16

構文と数式の表現



(1)BNF(Back-Naur Form)

つづく
2006/10/01(日) 19:14:25| 情報処理| トラックバック：0 コメント：0
| ホーム |
無料ホームページ アフィリエイト レンタルサーバー FC2ブログ
≪PortableなGimpやOpenOffice | ホーム | 良いサンタクロース・悪いサンタクロース≫
コメント
この記事へのコメント
コメントを投稿する
URL:
Comment:
Pass:
秘密: 管理者にだけ表示を許可する
 
トラックバック
この記事のトラックバックURL
http://pirolinten.blog58.fc2.com/tb.php/42-ea610162
この記事にトラックバックする(FC2ブログユーザー)
この記事へのトラックバック