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

第28回論理のプログラミング演習

これまで十数回にわたって論理の数学を学習しました。今回はその総まとめとして、ひとつの命題を論理式にまとめ、プログラムに組み込んで実行させる演習をしましょう。ただ実行させるだけではつまらないので、論理式を整理する前後で、実行速度がどのくらい異なるのかテストしてみましょう。実行速度の改善・高速化は、プログラマにとって自分の腕を試す・磨くためのよいテーマです。およそ職人と呼ばれる職業では、その腕を競うコンテストがあるものです。入門者として学習中の読者の皆さんは、現在の自分を試合相手と思い、プログラムの改善に取り組みましょう。今までよりも効率よく・速く正確に動くプログラムを作り出せたら、それはこれまでの自分に勝利したのです。勝利の行進を始めましょう。

図28.1 毎日が自分相手のコンテスト
図28.1 毎日が自分相手のコンテスト

問題:3者の多数決をとるプログラムを作りましょう。

この課題は、具体的には「三つのスイッチのうち、二つ以上オンになったらランプを点灯する仕組みをつくりなさい。」という場合が考えられます。完成した論理式を電気回路で組み立て設置すると面白いのですが、今はプログラミングの学習。Java言語で書き表してみましょう。

図28.2 ランプ点灯多数決処理
図28.2 ランプ点灯多数決処理

問題解決の手順を示しますのです(1⁠⁠~⁠5)に従って取り組んでみて下さい。

(1)「3つの論理値A、B、Cのうち、2つ以上が真なら全体の値Zが真になる」という命題の真理値表を作りましょう。

(2)真理値表を元に論理式を作りましょう。

(3)(2)で作った論理式をもとに、ひとつめのプログラムを作りましょう。入力となる論理値は、ソースコード中で設定してください。

(4)(2)の論理式を、カルノー図を利用して簡略化しましょう。簡略化した論理式をコードにしましょう。

(5)論理式が簡略化前と後でどれだけ実行時間に差がでるか、計測するコードを書き加えましょう。

実行時間の計測には、次の命令を用いるとよいでしょう。システムから現在の時刻をミリ秒単位で得ることができます。処理の実行直前に時刻を取得しておき、終了直後の値と差をとればよいのです。

long time = System.currentTimeMillis();

一度だけの論理式実行では大きな実行時間の差となって表れませんから、今回は100万回繰り返し実行するのに要する時間を計測してみましょう。

解説

(1)「3つの論理値A、B、Cのうち、2つ以上が真なら全体の値Zが真になる」という命題の真理値表を作りましょう。

題意の真理値表を以下に示します。Zが真をとる場合が全体の半分であることがわかります。

ABCZ
FFFF
FFTF
FTFF
FTTT
TFFF
TFTT
TTFT
TTTT

(2)真理値表を元に論理式を作りましょう。

真理値表を元にたてた論理式を以下に示します。

(3)⁠2)で作った論理式をもとに、プログラムを作りましょう。入力となる論理値は、ソースコード中で設定してください。

取り組み(2)でたてた論理式を試すプログラムの例を以下に示します。

1: //filename : Tasuuketu.java
2: class Tasuuketu {
3: 
4:   public static void main(String[] args) {
5:     boolean a,b,c,z;
6:     a = true; b = false; c = false;
7:     System.out.println("z("+a+","+b+","+c+") = " + z(a,b,c));
8:     a = true; b = true; c = false;
9:     System.out.println("z("+a+","+b+","+c+") = " + z(a,b,c));
10:   }// end of main
11: 
12:   static boolean z(boolean a, boolean b, boolean c) {
13:     return (!a&&b&&c)||(a&&!b&&c)||(a&&b&&!c)||(a&&b&&c);
14:   }//end of function
15: 
16: }// end of class

(4)(2)の論理式を、カルノー図を利用して簡略化しましょう。

カルノー図を用いて次のように簡略化てみる。

図28.3 多数決の論理式をカルノー図で式変形
図28.3 多数決の論理式をカルノー図で式変形

図中の各グループを論理式の各項に書き表すと次のようになります。

以上の作業により、カルノー図から次の式が得られました。

ついでなので、真理値表からたてた式28.1を論理代数の公式を用いて式を整理してみましょう。

このように、真理値表から得た式28.1から、カルノー図を用いて導いた式28.2と等価な式を得ることができました。論理代数の公式を用いて、結果が正しいことも確認されました。

(5)論理式が簡略化前と後でどれだけ実行時間に差がでるか、計測するプログラムを作成してみましょう。

式を整理した後の論理式は、次のようなJavaコードに書き出せます。

static boolean z(boolean a, boolean b, boolean c) {
  return (a&&b)||(a&&c)||(b&&c);
}//end of function

時間を計測するコードを加えてたものを次に示します。

1: //filename : TasuuketuBench.java
2: class TasuuketuBench {
3:   public static void main(String[] args) {
4:     boolean a,b,c,z;
5:     long time = System.currentTimeMillis();
6:     System.out.println("測定開始 その1");
7:     for(int i=0;i
8:       a = true; b = false; c = false; z = z1(a,b,c);
9:       a = true; b = true; c = false; z = z1(a,b,c);
10:     }// of for i
11:     time = System.currentTimeMillis() - time;
12:        System.out.println("経過時刻:  " + time + "[msec]");
13: 
14:     time = System.currentTimeMillis();
15:     System.out.println("測定開始 その2");
16:     for(int i=0;i
17:       a = true; b = false; c = false; z = z2(a,b,c);
18:       a = true; b = true; c = false; z = z2(a,b,c);
19:     }// of for i
20:     time = System.currentTimeMillis() - time;
21:     System.out.println("経過時刻: " + time + "[msec]");
22:   }// end of main
23: 
24:   static boolean z1(boolean a, boolean b, boolean c) {
25:     return (!a&&b&&c)||(a&&!b&&c)||(a&&b&&!c)||(a&&b&&c);
26:   }//end of function
27: 
28:   static boolean z2(boolean a, boolean b, boolean c) {
29:     return (a&&b)||(a&&c)||(b&&c);
30:   }//end of function
31: }// end of class

お手元の環境で実行してみましょう。実行時間は使用している環境によって異なります。私の実行環境では次のような結果になりました。

計算処理を数万回繰り返すような場合というと、滅多にないように感じるかもしれませんが、現在のコンピュータは一秒かからずにその程度の回数のループを実行できます。少しくらい効率の悪いコードを書いても、コンピュータが年々高速になっているから問題にならないよ、という意見を持つ方もあるでしょう。しかし、ちょっとした違いは、コンピュータの処理速度が上がった現在こそよくわかるようになりました。ちょっとした違いが数万回・数百万回になると大きな違いとなるからです。もし、効率のよいコードを書けるなら、それに越したことはありません。ちょっとしたコツを活かしてコーディングすれば、意外と大きな利潤を生むこともあるのです。これこそ、ハッピー・ハッキングです。

今回取り上げた多数決の仕組みは、論理式を用いずとも「真の場合の数がすべての場合の数の半数を超えた」という数の判断でも実装できます。今回は論理の演習ですから論理を用いました。皆さんがこれから実際に直面するプログラミングの課題については、論理を用いるのか、数値を用いるのかといった判断は問題に応じて適切に行ってください。判断基準は、実行速度・ソースコードの読みやすさ・わかりやすさなど様々です。適材適所、場合に応じた解決を選択するようにしましょう。

※)
Pentium4 2.66GHz

論理の数学のおわりに

論理の数学の学習は、いかがだったでしょうか。記事に関して「日頃何となく使っている論理の数学も、式や文章にしてしまうと意外と難しく感じた」⁠アプリケーション内の条件には、複雑な論理式はなるべく使わない方がよい」という貴重なご意見をいただきました。みなさんの業務や研究の内容によって、それぞれ必要となる論理の数学の道具立ては異なります。不必要に重たい道具だと感じられれば、その道具を使わない勇気もまた必要なものです。ただ、道具はいざ必要が生じたとき、使い方がわからなければもったいありません。これまでに紹介した論理の数学の各種ツールがいつか役に立つこと、必要になったときこの記事が助けになることを祈りつつ、論理の数学の部を終了したいと思います。

おすすめ記事

記事・ニュース一覧