2値論理方程式で天使と悪魔問題を解く
正直者と嘘つき者が出てくる問題を方程式を使って解く話です。
ただし、変数に入るのは0,1の真理値、
演算子も論理演算子$ \land \lor \lnotをなど用います。
前提
ここでは、前提として以下の法則を使います。
その他の法則は都度説明します。
また、$ A,B,Cのうち真である要素の個数を$ |(A,B,C)|と表記します
問題１
ご紹介するのは2016年度青山学院大学(全学部日程)の問題です。
A，B，Cの3名がいて、正直者が2人、残りの1人が嘘つきである。そして3名とも誰が正直者で、誰が嘘つきかは知っているとする。ここで、正直者とは常に真実をいう人、嘘つきとは常に真実と反対のことをいう人である。このとき、つぎのようなA，B，Cの証言が得られた。
Aの証言：Cは嘘つきである。
Bの証言：Aは正直者である。
Cの証言：Bは嘘つきである。
これらの証言に基づいて、以下の手順にしたがって誰が嘘つきかを決定しよう。
解法
A, B, Cを真理値とすると、
$ |(A,B,C)| = 2
それぞれの証言より、
$ A = \lnot C
$ B = A
$ C = \lnot B
が言えます
これを解いて
$ A = B = \lnot C
$ |(A,B,C)| = 2より
$ (A,B,C) = (1,1,0)
類題
Q.202 ☆1 2017 関西医大
次の5つの命題がある。
命題1:「命題1は真」
命題2:「命題1は偽」
命題3:「命題2は真」
命題4:「命題3は偽」
命題5:「命題4は偽」
この5つの命題の中で,2つの命題が真で3つの命題が偽であるとき,真の命題はどれか答えよ。
命題1〜5を$ p_1,p_2,p_3,p_4,p_5とすると
$ |(p_1,p_2,p_3,p_4,p_5)| = 2
$ p_1 = p_1
$ p_2 = \lnot p_1
$ p_3 = p_2
$ p_4 = \lnot p_3
$ p_5 = \lnot p_4
これを解いて
$ p_1 = \lnot p_2 = \lnot p_3 = p_4 = \lnot p_5
$ (p_1,p_2,p_3,p_4,p_5) = (1,0,0,1,0),(0,1,1,0,1)
$ |(p_1,p_2,p_3,p_4,p_5)| = 2 より
$ (p_1,p_2,p_3,p_4,p_5) = (1,0,0,1,0)
式をみてみると、問題1, 類題ともに必要のない条件が1つあることもわかります。
問題2
2004年 慶應義塾総合政策（類題）
天使はつねに真実を述べ、悪魔はつねに嘘をつく。A, Bは悪魔か天使であることはわかっているが、どちらかはっきりしない。
(中略)
Aがこういった。
「Bが天使ならば、私は悪魔ですよ！」
さて、AとBはそれぞれ天使、悪魔のいずれか。
解法
「Bが天使ならば、私は悪魔ですよ！」を論理式にすると
$ B \to \lnot A
論理包含 $ \to について
$ (P \to Q) \Leftrightarrow (\lnot P \lor Q)
が成り立つので、
$ B \to \lnot A \Leftrightarrow \lnot B \lor \lnot A
Aが「Bが天使ならば、私は悪魔ですよ！」という関係は
$ A = (B \to \lnot A)
$ A = \lnot B \lor \lnot A
$ A = \lnot (A \land B)
と表せます。
table: xor
A B ¬ (A ∧ B) A = ¬(A ∧ B)
0 0 1 0
0 1 1 0
1 0 1 1
1 1 0 0
よって $ (A,B) = (1,0) と特定できました。
排他的論理和(XOR) を用いた式変形
次の問題を解くために、この問題に、排他的論理和を導入してみます。
詳しい説明はWikipediaに任せるとして、
以下の関係が成立します。
table: xor
A B A XOR B
0 0 0
0 1 1
1 0 1
1 1 0
https://upload.wikimedia.org/wikipedia/commons/thumb/4/46/Venn0110.svg/320px-Venn0110.svg.png
また、XOR演算についても以下の法則が成立します。
交換律 $ x \oplus y = y \oplus x
結合律 $ x \oplus (y \oplus z) = (x \oplus y) \oplus z
分配律 $ a \land (x \oplus y) = (a \land x) \oplus (a \land y)
また、排他的論理和には
$ x \oplus x = 0
両辺を否定して、
$ \lnot x \oplus x = 1
といった関係があります。
----
$ A = \lnot (A \land B)
の両辺に$ \oplus Aを加算し
$ A \oplus A = \lnot (A \land B) \oplus A
$ 0 = \lnot (A \land B) \oplus A
$ (A \land B) \oplus A = 1
これは、
table: xor
A B (A ∧ B) A XOR (A ∧ B)
0 0 0 0
0 1 0 0
1 0 0 1
1 1 1 0
図で表現すると
$ A \land B
https://upload.wikimedia.org/wikipedia/commons/thumb/9/99/Venn0001.svg/320px-Venn0001.svg.png
および$ A
https://upload.wikimedia.org/wikipedia/commons/thumb/1/10/Venn0101.svg/320px-Venn0101.svg.png
であるから、
これらの排他的論理和 $ A \land \lnot B
https://upload.wikimedia.org/wikipedia/commons/thumb/e/e6/Venn0100.svg/320px-Venn0100.svg.png
が求める値となります。
問題3
いよいよ本題です。
扉が2つあり、片方は天国に、もう片方は地獄に繋がっているが、見た目では区別ができない。
扉の前に2人の門番がおり、片方は天使で、片方は悪魔だが、どちらがどちらだかは判断できない。
天使は常に真実を述べ、悪魔は常に嘘をつく。
この門番のどちらかに、yesかnoで答えられる質問を1回だけして、天国に行ける扉を100%特定したい。
どのような質問を行えば良いか
解法
ドア,門番,質問の真理値を$ d,g,qとする。
この時、質問の回答は
$ g = qを$ \lnot g \oplus q = 1と変換できることから
$ \lnot (g \oplus q) と表せる。
例えば、「このドアは天国に続いていますか」などといった $ dの真理値を問う質問は
$ q = d
であり、
この時の門番の回答は、$ \lnot (g \oplus d) である。
$ dを特定するためには、質問の回答が$ dの真理値となる$ qを求めればよい
$ d = \lnot (g \oplus q)
両辺に$ \lnotを適用して
$ \lnot d = g \oplus q
両辺に$ \oplus gを加算して
$ \lnot d \oplus g = g \oplus q \oplus g
交換法則より
$ \lnot (g \oplus d) = q \oplus (g \oplus g) = q
$ q = \lnot (g \oplus d)
ここで、$ \lnot (g \oplus d)は$ dの真理値を問う質問をした時の門番の回答なので、
「dの真理値を問う質問をした時の門番の回答」を問う質問への回答、がdの真理値となる。
すなわち、「『このドアは天国に続いていますか』という質問の回答はyesですか」などといった質問をすれば良いことがわかります。
また、
$ g \oplus g = 0をうまく使って門番の真理値の変数を打ち消す、というのが、この論理パズルの構造だったこともわかります。
終わりに
論理パズルを論理式を用いて解くことで見通しを良くしたり、
質問を閃きではなく式変形によって求められることを示しました。
問題1の類題は謎解きでもたまに出題されるので、
論理式への変形をイメージできると暗算で素早く解くことができるかもしれません。
面白い発見があれば教えてください！