はじめMath! Javaでコンピュータ数学

第25回 図による論理式の整理 その1[後編]

この記事を読むのに必要な時間:およそ 2 分

前回は2変数の論理式を,カルノー図で簡略化する方法を紹介しました。今回は演習問題に取り組み,この便利な道具を自分のものにしましょう。

問題:以下に示す論理式をカルノー図を利用して式変形しましょう。

解説

1.

図25.1に式変形の手順を示しました。

図25.1 カルノー図で式変形1.

図25.1 カルノー図で式変形1.

図に示す手順は,カルノー図を初めて自分で作成する,という読者を想定していますから,少々冗長で回りくどいと感じられるかもしれません。慣れたら,途中の手順を頭の中で行い,いきなり図の(c)を作成できるようになるでしょう。それでは,ステップ・バイ・ステップで解説します。

図25.1の(a)が真の場合を表す二つの枠にチェックを入れたところです。

図25.1の(b)が真のところにチェックを入れたところです。一つしかありません。

そして,図25.1の(c)を表すカルノー図です。(a)(b)でチェックの入ったところをあわせたものです。

こうしてチェックの終わったカルノー図をぐっとにらみ,図25.1の(d)のようにグループ化します。

囲み方は長方形か正方形です。L字形はありませんから,今回はこのような赤と青,二つの囲みになります。なるべく囲みは大きく,そして囲みの数は少なくと考えれば,自然とこの形になります。

赤いグループに注目すると,の真偽に関わらず,=1のときにチェックが入っています。ですから,赤いグループはを表しています。

青いグループに注目すると,の真偽に関わらず,=1のときにチェックが入っています。ですから,青いグループはを表しています。

このカルノー図全体が表す論理式は,赤と青のグループの論理和です。よって,と表せることがわかりました。

この結果は,連載第18回問題の(3)で導いた結論と一致します。カルノー図が確かに有効であることがわかりますね。


2.

図25.2に式変形の手順を示します。

図25.2 カルノー図で式変形2.

図25.2 カルノー図で式変形2.

図25.2の(a)が真である枠にチェックを入れたものです。

図25.2の(b)が真である枠にチェックを入れたものです。

図25.2の(c)ですから,(a)(b)で両方チェックの入っている枠を選び出したものです。

こうしてチェックの終わったカルノー図をぐっとにらみ,チェックの入った枠をできるだけ大きく,少ない数の囲みでグループ化します。すると,図25.2の(d)に示すように,赤い囲みが一つ出来上がります。この囲みは,の真偽に関わらず,が真の時にチェックが入っています。ですから囲みが表している論理式はであるとわかります。従って,問題の論理式は次のように整理されます。

この式は連載20回『論理代数の公式[中編]』で学んだ吸収則そのものですね。


3.

図25.3に式変形の手順を示します。式の形から,ド・モルガンの定理を取り扱おうとしていることがわかると思います。カルノー図で見事定理どおりの式が導かれるでしょうか。

図25.3 カルノー図で式変形3.

図25.3 カルノー図で式変形3.

図25.3の(a)が真である枠にチェックが入っています。(a)でチェックの入っていないところを表しますから,図25.3の(b)のようになります。

チェックの入っているところがひとつしかありませんから,図25.3の(c)のように,この枠のみが囲みの中に入ります。そしてこの囲みがあらわす論理式はかつすなわちであることがわかります。

以上のことから,次のとおり,ド・モルガンの定理の式が導かれました。


4.

図25.4に式変形の手順を示します。排他的論理和を,カルノー図を用いて(オープラス)を用いずに表そうという試みです。

図25.4 カルノー図で式変形4.

図25.4 カルノー図で式変形4.

図25.4の(a)が真である枠にチェックが入っています。あるいはどちらかのみが真のとき,その枠が真です。

こうして出来上がったカルノー図のチェックをグループ分けしようとするのですが,それぞれチェックの入った枠の辺が接していません。図25.4の(b)のように,それぞれひとつずつの枠が個別のグループをなしています。ですから,赤い囲みと青い囲みそれぞれについて論理式を立て,それらの論理和を取ったものが全体の論理式をあらわすのです。赤の囲みは青の囲みがですから,全体としてはがこのカルノー図の表す論理式です。

以上のことから,次の式が導かれます。

これは連載第18回『真理値表から論理式をつくる[後編]』の問題で取り組んだ,真理値表から導いた結果とも一致しています。

今回はここまで

『図による論理式の整理 その1』前編・後編では,カルノー図がいかに便利な方法か,肌で感じていただくことができたことでしょう。最もシンプルな場合として二変数のカルノー図を取り扱いましたが,実際のプログラミングでは,論理変数,すなわち命題が三つ,四つと登場します。次回はそのような論理変数が多い場合でカルノー図を利用してみます。次回紹介する内容が身につけば,多くの場合で効果を実感できるようになります。お楽しみに。

今回のまとめ

  • カルノー図は,どんな複雑な論理式でも,決まった手順に従って操作を繰り返すことで,式の変形を行うことができる方法です。

著者プロフィール

平田敦(ひらたあつし)

地方都市の公立工業高等学校教諭。趣味はプログラミングと日本の端っこ踏破旅行。2010年のLotYはRuby。結城浩氏のような仕事をしたいと妄想する30代後半♂。

コメント

コメントの記入