矢沢 久雄 グレープシティ アドバイザリースタッフ

 今回は,論理演算に関する様々な法則がテーマです。まず,交換法則,分配法則,結合法則の三つを説明します。複数の論理演算を組み合せた複雑な演算式は,これらの法則を適用することで単純な演算式に整理できる場合があります。それによって,ハードウエアの回路もプログラムのコードも単純化できるのです。ベン図を使うことで,複雑な演算式を簡単に分析できることも説明しましょう。次に,情報処理技術者試験の定番問題としてよく出題され,理解するのが難しいと言われている「ド・モルガンの法則」を説明します。ド・モルガンの法則は,それが逆転の発想を表していることさえ分かれば,いとも簡単に理解できます。

●論理演算の交換法則,分配法則,結合法則

 皆さんは,中学の数学で習った交換法則,分配法則,結合法則を覚えていますか?もしも忘れてしまったと言う人は,演算式を変形するための法則だと考えてください。中学で習った法則は,四則演算に関するものでしたが,論理演算にも同様の法則があります。

 まず,「交換法則」です。交換法則とは,論理演算される2つのデータの順序を入れ替えても,演算結果は変らないということです。例えば,1 AND 0の演算結果と,0 AND 1の演算結果は,どちらも0で同じです。

【四則演算の交換法則】
a + b = b + a
a × b = b × a

【論理演算の交換法則】
a AND b = b AND a
a OR b = b OR a

 次に,「分配法則」です。分配法則とは,カッコの外にある演算をカッコ内のデータに分配して作用させることです。

【四則演算の分配法則】
a ×(b + c)=(a × b)+(a × c)

【論理演算の分配法則】
a AND(b OR c)=(a AND b)OR(a AND c)
a OR(b AND c)=(a OR b)AND(a OR c)

 最後は,「結合法則」です。結合法則とは,演算する順番を変えても結果は変わらないというものです。

【四則演算の結合法則】
a +(b + c)=(a + b)+ c
a ×(b × c)=(a × b)× c

【論理演算の結合法則】
a AND(b AND c)=(A AND b)AND c
a OR(b OR c)=(a OR b)OR c

図1●ベン図で表したa AND b
図2●ベン図で表したa OR b
図3●ベン図で表したNOT a
図4●a AND (b OR c)の領域
図5●ベン図で論理演算式を単純化する

●複雑な論理演算はベン図で考えよう

 四則演算の法則については,それぞれの法則の名前は忘れていても,普段の計算で無意識のうちに使っているものばかりだということがお分かりいただけたと思います。論理演算では,上記の法則を丸暗記する必要などありません。論理演算の演算式が,交換法則,分配法則,結合法則を使って変形できることを知っていただければ十分です。

 交換法則,分配法則,結合法則が成り立つかどうかを確認する場合や,ちょっと複雑な論理演算式の結果がどうなるかを判断する場合には,「ベン図」を使うと便利です。ベン図も中学で習ったはずです。論理演算でベン図を使う場合は,円の中が1で,円の外が0であるとします。複数の円の交わりがANDになります。複数の円の結び(領域を合わせたもの)がORになります。円の外がNOTです(図1[拡大表示],図2[拡大表示],図3[拡大表示])。

 ベン図を使って,a AND(b OR c)=(a AND b)OR(a AND c)という分配法則が成り立つことを確認してみましょう。左辺のa AND(b OR c)は,aと(bとcの結び)の交わりですから,図4[拡大表示]の領域になります。

 右辺の(a AND b)OR(a AND c)は,(aとbの交わり)と(aとcの交わり)の結びですから,やはり図4と同じになります。これで,a AND(b OR c)=(a AND b)OR(a AND c)という分配法則が成り立つことを確認できました。

 今度は,(a AND b)OR((NOT b)AND a)という複雑な演算式を単純化してみましょう。数学の得意な人なら,交換法則,分配法則,結合法則を駆使して,式を変形することもできるでしょう。もしも,数学が苦手ならベン図を使いましょう。(a AND b)OR((NOT b)AND a)=aであることが容易にわかります(図5[拡大表示])。

●ド・モルガンの法則

 「ド・モルガンの法則」とは,AND演算とOR演算を相互に変換するものです。以下のように,左辺のAND演算を右辺のOR演算に変換したり,左辺のOR演算を右辺のAND演算に変換します。ド・モルガンの法則に相当するものは,四則演算にはありません。論理演算ならではの法則なのです。

【ド・モルガンの法則】
NOT(a AND b)=(NOT a)OR(NOT b)
NOT(a OR b)=(NOT a)AND(NOT b)

 ド・モルガンの法則が言わんとしていることは,「AND演算も見方によってはOR演算に見え,OR演算も見方によってはAND演算に見える」ということです。この見方とは,これまで真理値表の1を真,0を偽と見てきましたが(これを「正論理」と呼びます),逆転の発想で0を真,1を偽と見る(これを「負論理」と呼びます)ことです。このように見方を変えると,AND演算の真理値表はOR演算の真理値表になり,OR演算の真理値表はAND演算の真理値表になるのです。何とも不思議なことかもしれませんが,表1表2,および表3表4を見比べれば,納得していただけるでしょう。

表1●正論値のAND演算の真理値表
aの値bの値a AND bの演算結果
1(真)1(真)1(真)
0(偽)1(真)0(偽)
1(真)0(偽)0(偽)
0(偽)0(偽)0(偽)
表2●負論値のOR演算の真理値表
aの値bの値a OR bの演算結果
1(真)1(真)1(真)
0(偽)1(真)0(偽)
1(真)0(偽)0(偽)
0(偽)0(偽)0(偽)
表3●正論値のOR演算の真理値表
aの値bの値a OR bの演算結果
1(真)1(真)1(真)
0(偽)1(真)1(真)
1(真)0(偽)1(真)
0(偽)0(偽)0(偽)
表4●負論値のAND演算の真理値表
aの値bの値a AND bの演算結果
1(真)1(真)1(真)
0(偽)1(真)1(真)
1(真)0(偽)1(真)
0(偽)0(偽)0(偽)

 NOT演算は,1と0を反転させるものです。NOT(a AND b)=(NOT a)OR(NOT b)は,aとbを反転させると,AND演算の演算結果の反転が,OR演算の演算結果になることを意味しています。NOT(a OR b)=(NOT a)AND(NOT b)は,aとbを反転させると,OR演算の演算結果の反転が,AND演算の演算結果になることを表しています。ド・モルガンの法則も,複雑な演算式を単純化する場合などに利用されます。

 今回のお話は,まるで数学の授業みたいだったでしょう。コンピュータは,本来なら数値でないデータも含めて,あらゆるデータを数値で表すのですから,数学みたいな話題が多く登場するのも当然なのです。皆さんは,数学がお好きですか?もしも,数学が苦手でも心配しないでください。コンピュータで登場する数学っぽい知識は,ここであげた程度のものが最高レベルです。難しい三角関数や微分積分などの知識はいりません。ド・モルガンの法則まで理解できたなら合格でしょう。どうぞ自信を持ってください。

 次回は,プログラミングの世界で論理演算がどのように活用されるかを説明します。お楽しみに!