２章　論理演算　＜基本情報処理試験＞

２０１８/　１/　１９　五十川 晶一

１　論理演算の種類

 

１－１ ３種類の演算

前項のシフト演算に続いて、今項では論理演算について取り扱います。
論理演算とは真（True）か偽（false）を判断できる文のことです。
この真偽を真理値、または真偽値、論理値などと呼びます。

基本的な論理演算には、AND演算、NOT演算、OR演算の３種類が存在します。
演算の意味は次のようになります。

 A AND B ……　Aが真　かつBが真　なら　真

 A OR B   ……　Ａが真　もしくはＢが真　なら　真

 NOT A　 ……　Ａが真　じゃない　なら　真

 

 

１－２　真理値表

論理演算の結果を表にまとめたものを真理値表と呼びます。
以下はＡ、Ｂをなんらかの条件とした真理値表です。

真理値表そのものを丸暗記する必要はありませんが、
それぞれの演算結果がどうなるかをしっかり覚えておきましょう。

 

１－３　NOTとXの演算

NOT演算が反対の値を返す演算であることは理解しましたか？
このNOT演算と、AND・OR演算を組み合わせる事が出来ます。
それぞれ、NAND演算、NOR演算と呼びます。（NはNOTの頭文字）
演算結果をNOT演算（反対に）するものだと覚えてください。

また、OR演算にはXOR演算という派生があります。（XはExclusiveの略）
この演算はどちらか一方が真である場合のみ真を返します。
イメージしにくいですが、極端になったOR演算だと考えましょう。

まとめると、以下のようになります。

A NAND B　……　Aが真　かつ　Bが真　なら偽

A NOR B　……　Aが真　もしくは　Bが真　なら偽

A XOR B　……　Aが真　もしくは　Bが真、両方とも真でないとき　なら真

真理値表で表すと以下の通りです。

 

さて、論理演算はビット演算に使用されます。
下は、ABそれぞれに1か0を入力した場合の、論理演算の真理値表です。

何の演算をすれば何が出力されるのか、原理は先ほど説明した通りです。
後のマスク処理等でよく使うので、覚えておいてください。

 

１－４　論理式

さて、論理演算を複数使った式を論理式と呼びます。
例えば、こんな式です。

　　A OR B AND C

どこから演算しますか？A OR Bですか？それともB AND C？
仮に上の式が下のようだったら、順番では悩まないと思います。

　　A ＋ B × C

乗算が加算より優先されるので、B × Cを行った後にAを足す事になります。
さて……こんな風に、四則演算には優先順位が存在しますよね。
そして、実は論理演算にも優先順位があるんです。
左側から優先順位が高い順に並んでいます。

　　NOT > AND > OR

先ほどの例に戻りましょう。
優先順位の高いB AND Cから計算を行います。
論理演算後、AとAND演算結果をOR演算するのが正解です。
この論理式は、後ほども例に使いますので、もう少し覚えていてください。

ここまでは各論理演算について説明してきました。
これからの項目全ての基礎となってくるので、
まずはここまでの内容を復習してみてください。

 

 

 

２　○○で見る論理演算

 

２－１　表記で見る論理演算

まずは、各演算が文章上に出てきたときの表記方法を学習します。
表記上とは、すなわち文中に出てくる文章のことです。

また、数学的な記号として、AND演算には∩（キャップ）、
OR演算には∪（カップ）が用いられることがあります。
NOT演算は演算記号と同じく―（バー）を上につけてAと書きます。
特に∩と∪は間違えやすいので、注意してください。

例：　A AND B 、 AとBの論理積 、 A ・ B 、 A ∩ B

上の論理演算は、まったく同じ意味を表しています。
1つ覚えればいい、ではなく、どれも（文中に）出る可能性があるので、
流し見せずになんとか覚えてください。

 

２－２　ベン図で見る論理演算

数学には集合を視覚的に表したベン図というものがあります。

このベン図によって、論理演算を表すことができます。
論理演算をそれぞれベン図で表すとどうなるか、見てみましょう。
以降、対象が示す範囲をピンクで塗りつぶしています。

・NOT関数比較

左がA、右がNOT A

・AND関数比較

左がA AND B、右がA NAND B
 

・OR関数比較

左がA OR B、右がA NOR B

下がA XOR B

真偽値表の中身が、図になるとこうなると考えてください。

今度は、論理式をベン図に表します。
問題は前に例として使った、A OR B AND Cを図式しましょう。

問題　A OR B AND C

デフォルト

①まずは、優先順位の高いB AND Cを行います。

Ｂ AND C

②次に、その結果とAをOR演算します。

A OR B AND C

③上のピンクの範囲がA OR B AND Cの演算結果です。

先にA OR Bを行うと全く違う結果になってしまうので、
最初に学んだ優先順位をよく思い出しましょう。

ベン図自体は論理演算の理解に使えますが、
それよりも試験問題としてよく出題されます。

 

２－３　フローチャートで見る論理演算

今度は、フローチャートで論理演算を見てみましょう。
フローチャートとは、プログラム全般で使われる処理の流れ図です。
使われる記号は主に以下の通りです。


基本的に上から下に流れていきます。

処理が順番に進むことを順次と呼びます。
その順次と分岐、繰り返しの３つが大まかな流れの分類です。

では具体的に、分岐や繰り返しの条件分に論理式を入れてみましょう。
図記号に入れる文字にルールはないので、英語（ANDなど）から
日本語（かつ、など）まで色々と入ります。
下図は、その一例です。

・分岐の例

この場合、「A>0 AND B>0」が真ならYESに、
NOなら右のNOに飛びます。

・繰り返しの例

この場合、「A>0 OR B>0」が真である限り、
ループを繰り返します。

今は「そんな風に図にするのか」と覚えておいてください。
後のアルゴリズムの章で、流れを図式化する際に使います。
「なんだっけこの記号……」となった時は、ここで学んだ事を
見返してみてください。

 

２－４　ド・モルガンと見る論理演算

最後の○○はド・モルガンという数学者の名前が入ります。
数学者にはよくある事で、自分の名前を法則名につけました。
という事で、ド・モルガンの法則について見ていきましょう。

A AND B

ある論理式があります。意味は「AかつB、でない」ですが、
この法則を当てはめると、同じ意味を持ちながら別の式に変更できます。

A AND B = A OR B

「AかつB、でない」を「Aではない、または、Bでない」に変えました。
意味は変わらずに、記述の方法だけが変わったのです。
また、同様の法則で以下の変更もできます。

A OR B = A AND B

「AまたはB、ではない」を「Aでなく、かつ、Bでない」に変えました。

例えばフローチャートの条件分岐は、なるべくシンプルな方が良いですよね。
この法則を知っていると、条件次第で簡略化が出来るかもしれません。
計算過程の省略（変更）方法として、ぜひ頭に入れてください。

 

 

 

３　論理演算のマスク処理

 

３－１　論理演算によるマスク

論理演算の使い方には、データを部分的に変化、取り出す手法があります。
これをマスク処理と呼びます。
1ビット毎に元のデータとマスクのデータを論理演算する手法です。
ここでは、8ビットのデータ01010110とマスク用のデータ00001111を例に、
それぞれの演算でどうなるかを見ていきます。

・AND演算のマスク

マスクのビットが0の場合、その部分は0に変化します。
マスクのビットが1の場合、その部分は変化しません。
特定の値を0にするとき、または特定の値を取り出す時に使います。

・OR演算のマスク

マスクのビットが0の場合、その部分は変化しません。
マスクのビットが1の場合、その部分は1に変化します。
一定の範囲を1にしたい場合に用いられるマスクです。

・XOR演算のマスク

マスクのビットが0の場合、その部分は変化しません。
マスクのビットが1の場合、その部分の値が反転します。
特定範囲を反転したい場合に用いることができるほか、
11111111をマスクする事で全範囲を反転することができます。
全範囲の反転はNOT演算でも可能ですが、
部分的な反転はXOR演算のマスク処理でしか行えません。

今までの目的、マスクパターンを纏めると、以下の表になります。

ORとXORのマスクの違いに注意してください。

 

３－２　マスクの使用例

使い方がわかったところで、使用例を見てみましょう。
以下は過去に試験に出た問題です。　（H27　春　問1より引用）

複雑な問題ですが、まずは手順通りやってみましょう。
問題文にある通り、ここは00101000をベースに解いていきます。

手順１では、ビット列A=00101000から1引いたビット列Bを作成しています。
というわけで、ビット列B＝00100111とします。

手順２では、先ほどのビット列AとBをXOR演算しています。
XOR演算のマスクは覚えていますか？
マスクが0の場合そのままの値を、1の場合は逆の値になります。

よって、ビット列C＝00001111になります。

さて、手順３でようやく今回の本題に入ります。
ビット列Aとビット列Cで何等かの論理演算をして、00001000を出します。

マスク＝ビット列Cが0の場合に0、1の場合は値が変化していませんね。
以前の図を覚えていますか？答えは……そう、AND演算になります。
このように、複数の論理演算とビットを関連付けた問題が出てきます。

 

３－３　目的のビットを得る

先ほどの説明にもありましたが、AND演算で目的のビットを取り出す
ことができます。例えば、先ほどの例だと……

00101000 AND 00001111 = 00001000

下位4ビットを1にマスクする事で、そのまま下位ビットを得る事ができます。
ちなみに、上位ビットを得たい場合は逆のことを行います。

00101000 AND 11110000 = 00100000

上位4ビットを1にマスクして、上位4ビットを得る事ができました。

また、シフト演算と組み合わせる事ができます。
（そして、そういう問題も試験に出ます）
同じマスクを使いまわす場合は、以下の手順を行います。
以下はその一例です。

例）　ビット列01101100を4ビットずつ分ける。

ここでは、２つの変数①と②に入れることにします。

手順1　ビット列と00001111をAND演算
　　　　01101100 AND 00001111 = 00001100

手順2　演算結果を変数①に入れる

手順3　ビット列を4ビット右に論理シフト
　　　　01101100 >> 4 …… 00000110

手順4　シフト結果を変数②に入れる

8ビットの場合だと恩恵を薄く感じてしまうかもですが、
対象が16ビット等になってくると、シフト演算を使った手順は
繰り返しに向いており、処理が非常に楽になります。

マスク処理は、論理演算の有用な使用方法の一つです。
次のネットワークでは、早速ビットをマスクする実例が出てきます。
他にはどこにどう使われているのか、是非関心を持ってみてください。

 

 

 

４　コンピュータの中の論理演算

 

４－１　論理回路とMIL記号

今までは論理演算という法則と、その応用について学んできました。
この章では打って変わって、コンピュータの中身について説明していきます。
まず、コンピュータ内部には論理演算用の論理回路という回路があります。
それを人が見るために図式したものがMIL記号と呼ばれるものです。

フローチャートと違うの？と思われるかもしれませんが、あちらは
あくまでプログラムの処理の流れ図であり、こちらは回路図です。
まずは、下の図をご覧ください。

まずはイメージです。左から入力データが入ってきて、
中心にMIL記号で図式された論理回路、
最終的に演算したものが右側に出力される、というイメージです。

では、論理回路の中身を見ていきましょう。
以下がMIL記号の各記号が対応する論理回路の表です。

例えば、AND演算をMIL回路で行うと次のようになります。
１本の電線ごとに0か1が入っています。

AND演算は二つのデータを使う演算なので、
左側の２本の電線から入力して、右側の１本から出力しています。
イメージできましたか？

今度は複数の論理回路の例です。
先ほどと同じく、１本の電線ごとに0か1が入っています。

●の交差で電線がつながっており、何もない交差は繋がっていません。
繋がった電線には、同じデータが通っている事が分かるでしょうか。
2つのNOT回路と3つのNAND回路を経て、最終的に0が出力されました。

なお、当然ですが、入力データが変われば出力結果も変わります。
ためしに、両方に1を入力してみましょう。

このように、MIL回路に数字を入力して確かめるケースは多いです。
論理演算の記号で惑わされがちですが、ANDとORの記号の違い、
NOT（○）の有無に気を付けながらMIL回路を読んでください。

以下は何も入力されていないMIL回路です。
練習問題だと思って、データにそれぞれ０と１を入れてみましょう。

できましたか？
では、実際に数値を入力してみましょう。

まずは、論理演算を行ってない状態です。
ここまではただ数字を通すだけなので、簡単だと思います。
それでは、一気に論理演算を行ってみましょう。

２回のNOT回路と２回のOR回路、最後のAND回路を経て、
最終的な出力結果は1になりました。

ちなみに、入力データが1,1の場合、0,0の場合だと最終出力が1になります。
せっかくなので、実際に数を入れて確かめてみてください。

 

４－２　半加算機と全加算機

さて、コンピュータ内部の論理回路に触れてきましたが、
今度はコンピュータの中で行われる加算についてお話しします。
なぜ論理演算の途中に加算が？と思われるかもしれませんが、
おいおい説明しますので、まずはこちらをご覧ください。

例として、ビット列0101とビット列0011の加算を見ていきましょう。


算数の筆算的な図を作成してみました。
一桁目の二つの数値の加算を半加算と呼び、
二桁目以降の三つの数値の加算を全加算と呼びます。

感覚的に理解できましたか？
では、内部ではどう動いているのか、これから説明していきます。

 

４－３　半加算器のしくみ

実は、半加算も全加算も論理回路で出来てるんです。
コンピュータ的に半加算を実現する演算装置を、半加算器と言います。
実際に、どんな論理回路か見てみましょう。
X、Yが入力データ、Cが桁上がり（Carry）、Sが合計値（Sum）です。

ここで注目してほしいのは、半加算器自体に次の桁に値を渡す回路が
備わっている事です。つまり半加算の機能は、

①値のビットの合計値を出力

②次の桁への桁上がりを出力

の二つだと言えます。

早速、前回の例（４－２を参照）を使って、
1 + 1を半加算器で見てみましょう。

C=1、S=0になりました。

４－４　全加算器のしくみ

半加算器があるので、全加算器もあります。
早速、MIL記号で覗いてみましょう。
X,Yが入力、C’が前桁からの桁上がり、Cが出力後の桁上がり、Sが合計です。

見覚えのある回路が2か所ありますね。
実は、半加算器2つとOR回路1つで出来ているんです。
イメージしにくいと思うので、行われてる事を順番に見ていきましょう。

①XとYで半加算器①で半加算を行う。
　合計値を半加算器②に。

②①の合計値とC’で半加算器②で半加算を行う。

③①と②の桁上がり同士でOR演算。

④②の結果が合計値、③の結果が桁上がりになる。

以上です。
半加算器のときと同様に、1+0+1を入れて確かめてみましょう。

結果はC=1、S=0になりました。

 

５　終わりに

論理演算という新しい演算方法、その応用方法、
そして論理演算で説明できるコンピュータの中身について触れてきました。

ここまでの中にも試験問題は幾つも含んでいますが、
フローチャートのように、後の章に接続する項目も含んでいます。
流し見した方は、折り返して一から確認してみてください。
論理演算の仕組みを正しく理解された方は、是非次の項に進んでみましょう。