読者です 読者をやめる 読者になる 読者になる

数学塾variée@吉祥寺

数学塾の中の人の日記

論理パズルを命題論理で(1)

数学/その他

『論理パズルとパズルの論理』という本を読みました。論理パズルを命題論理で解こうという本です。易しい論理パズルをシラミツブシや背理法で解くのに飽きてきたので,一網打尽にする方法を探してこの本に行き着きました。

論理パズルとパズルの論理 (アウト・オブ・コース)

論理パズルとパズルの論理 (アウト・オブ・コース)

本の内容紹介

内容は3つに分かれています。

  1. 基本的な論理式
  2. 論理式の分解(例.「A→B∧C」=「A→B かつ A→C」)
  3. 真理値表から論理式を作る(例. 天使と悪魔の問題)

とりあえず1.がわかれば十分かな〜と思うので,これについて書きます。

論理式の作り方

論理記号

まずは論理記号(∧/∨/¬)を使って命題をあらわします。「→」は使いません。


と書き換えます。これについては一旦否定して真理集合の包含関係を考えると分かりやすいと思います。「A→B」=「A⊆B」の否定は「x∈A かつ x∉B をみたす x が存在する」です。この条件 A∧¬B をもう一度否定して,ド・モルガンの法則を使います。

真理値表を考えてもいいでしょう。A→B は A が偽のとき,B の真偽によらず真になります。A→B が真になる条件は「Aが偽」または「A, B とも真」で,まとめると ¬A∨B です。

式の整理

次に分配則やド・モルガンの法則などを使って,論理式を「∨」を「∧」で結んだ形(∨∧標準形)に直します。「∧」を「∨」で結んだ形ではないことに注意してください。「∧」の方があとあと便利なのでこうします。

ちなみに分配則の式は2つあります。


∨/∧を和/積と対応づけて覚えていると,第1式が出てこないかもしれません。ベン図を描いて納得してください。

この他,便利な公式もありますが省略します。

簡単な例

「AかBならば,Cではない」は「A∨B → ¬C」

まず (P→Q) = ¬P∨Q を使って「→」を解消します。


これをド・モルガンの法則と分配則を使って変形します。


これが∨∧標準形です。このあと,∧で結ばれた各パーツを証明に利用するわけです。

実際に使ってみよう(1)

普通の論理パズルの解き方は本に載っているので,ここでは入試問題を例にとります。2000年の麻布大学の問題です。今日は問題紹介だけにして,実際にどう解くかは次回書きます。

ある地方で,騒音・悪臭・水質汚濁・大気汚染の少なくとも一つの公害を発生させている事業所(工場など)に立ち入り検査をしたら,次のことがわかった。

  • 騒音か悪臭を発生させていれば,水質汚濁は発生させていない。
  • 騒音を発生させていなければ,悪臭か大気汚染を発生させている。
  • 騒音も水質汚濁も発生させていなければ,大気汚染を発生させている。

次のように判断することは正しいか? ○×で答えよ。答えのみでよい。

(1) 水質汚濁を発生させていれば,悪臭は発生させていない。

(2) 4つの公害すべてを発生させている事業所がある。

(3) 水質汚濁を発生させていれば,大気汚染は発生させていない。

(4) 水質汚濁を発生させていなければ,騒音か悪臭を発生させている。

(5) 悪臭も大気汚染も発生させていなければ,騒音を発生させている。

(6) 騒音を発生させていれば,悪臭も大気汚染も発生させていない。

(7) 大気汚染を発生させていなければ,騒音も水質汚濁も発生させている。

(8) 騒音も水質汚濁も発生させていれば,大気汚染は発生させていない。