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

第18回 真理値表から論理式をつくる[後編]

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

コラム 論理のクイズに挑戦

せっかく論理の数学を学んだのですから,論理的なクイズを解くのに利用しない手はありません。次のクイズを,論理の数学を利用して解いてみましょう。

  • クイズ 5人のコビト
    5人のコビトたちが誰が一番ののっぽかと言い争っています。この中で,一人だけがへそを曲げて嘘を言っています。自分が一番ののっぽではないと思って,悔しかったのでしょうか。しかし,正直者で絶対に嘘を言わないコビトもいたのです。正直者のコビトはA~Fの誰でしょう?

    •  コビトA「BはCよりもちっちゃいよね。」
    •  コビトB「そうかい,AだってDよりちっちゃいよ。」
    •  コビトC「うーん,EはAよりちっちゃいなぁ。」
    •  コビトD「CはEよりちっちゃいてば。」
    •  コビトE「あっはっは。BはDよりちっちゃいなー。」

整数変数AからEをコビトの身長を表すものとし,数値を代入しておきます。仮にAが一番身長が低く1,Eがもっとも身長が高く5であるとします。それぞれのコビトの条件を評価していくたびに,単純に序列を入れ替えましょう。

  • 初期状態
    1 2 3 4 5
    A B C D E
    コビトAによる B<C  より
    1 2 3 4 5
    A B C D E  変化なし
            次へ
    コビトBによる A<D
    1 2 3 4 5
    A B C D E  変化なし
            次へ
    コビトCによる E<A
    1 2 3 4 5
    E B C D A  E とA 交換
            コビトAの条件OK
            コビトBの条件NG
    E B C A D  D とA 交換
            コビトAの条件OK
            コビトBの条件OK
            コビトCの条件OK
            次へ
    コビトDによる C<E
    1 2 3 4 5
    C B E A D  E とC 交換
            コビトAの条件NG
    B C E A D  B とC 交換
            コビトAの条件OK
            コビトBの条件OK
            コビトCの条件OK
            コビトDの条件OK
            次へ
    コビトEによる B<D
    1 2 3 4 5
    B C E A D  変化なし
            次へ
            次はないので終了

この通り,すべての条件に対して無矛盾で序列できました。しかし,誰かが確実に嘘を言っているのです。

嘘をついているのは一人だけですから,BCEADの序列には一箇所真実ではない場所があります。二箇所以上真実でない場所があるということは,複数嘘をついている人がいることになります。

それでは確認を始めましょう

コビトAが嘘を言っているとします。!(B < C) ですから,C < B が真です。序列に反映し,C,B,E,A,Dとしてみます。

この序列について,5人のコビトの言葉を検証します。

  • コビトA B < C は嘘なのでFalse
  • コビトB A < D はTrue のまま
  • コビトC E < A はTure のまま
  • コビトD C < E はTrue のまま
  • コビトE B < D はTure のまま

コビトA以外は真実を語っているように読めますから,コビトAが嘘をついている可能性が消し去れません。

コビトBが嘘を言っているとします。真の序列はB,C,E,D,A となります。同様に検証してみます。

  • コビトA B < C はTrue のまま
  • コビトB A < D は嘘なのでFalse
  • コビトC E < A はTure のまま
  • コビトD C < E はTrue のまま
  • コビトE B < D はTure のまま

コビトB以外は真実を語っているように読めますから,コビトBが嘘をついている可能性が消し去れません。

コビトCが嘘を言っているとします。真の序列はB,C,A,E,D などとなります。同様に検証してみます。

  • コビトA B < C はTrue のまま
  • コビトB A < D はTrue のまま
  • コビトC E < A は嘘なのでFalse
  • コビトD C < E はTrue のまま
  • コビトE B < D はTure のまま

コビトC以外は真実を語っているように読めますから,コビトCが嘘をついている可能性が消し去れません。

コビトDが嘘を言っているとします。真の序列はB,E,C,A,D などとなります。同様に検証してみます。

  • コビトA B < C はTrue のまま
  • コビトB A < D はTrue のまま
  • コビトC E < A はTrue のまま
  • コビトD C < E は嘘なのでFalse
  • コビトE B < D はTure のまま

コビトD以外は真実を語っているように読めますから,コビトDが嘘をついている可能性が消し去れません。

コビトEが嘘を言っているとします。真の序列はC,E,A,D,B などとなります。同様に検証してみます。

  • コビトA B < C はFalse
  • コビトB A < D はTrue のまま
  • コビトC E < A はTrue のまま
  • コビトD C < E はTrue のまま
  • コビトE B < D は嘘なのでFalse

さて,ここで問題と矛盾が生じました。うそつきは一人のはずなのに,もう一人嘘をついているコビトがいることになります。つまり,コビトEだけは,⁠嘘をついていることにすると矛盾が発生する」唯一の存在だとわかりました。

確実に嘘を言っていないと保証できるコビトはEだけです。

このような問題は,論理のパズルとしてよく紹介されます⁠ 。クイズを解くときに,数学的な手段にこだわるところにつけ込む⁠とんち⁠パズルなら仕方ありませんが,純粋に論理的なパズルは,論理の言葉で明確に問題を書き表し,確実に列挙していくと手数はかかりますがスムーズに問題が解けます。

手順が機械的ですから,プログラム化してクイズを解くことが可能です。お時間が許せば,プログラム化に取り組んでみられてはいかがでしょうか。

※)
参考文献 ⁠グングン脳がめざめる算数パズル』現代数学セミナー編 角川文庫

著者プロフィール

平田敦(ひらたあつし)

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