Wakamatz's diary

第2回ものまね鳥をまねる会の続き

最後、時間がなくて解けなかった問題について解いてみました。

３－７　セビリアの理髪師

まず、5人の集合 $M=\{Al,Br,Bn,Ro,Ra\}$ を引数に持つ述語を次のように定義する。

$P(x)：x$ がかつらをかぶる。

また、理髪師を $Bb \in M$ とする。

どの2人も同時にかつらをかぶらない日が存在するというのは

$\forall x, \forall y,P(x) \equiv P(y) \Rightarrow x= y \tag{*}$

次に事実１~５を論理式で記述する。

Fact1 : $P(Br) \equiv \neg P(Bn)$

Fact2 : $P(Ro) \equiv \neg P(Ra)$

Fact3 : $P(Ra) \equiv P(Al) \wedge P(Bn)$

Fact4 : $P(Al) \wedge P(Bb) \Rightarrow P(Br)$

Fact5 : $\forall x \in M,(P(x) \wedge P(Al) \Rightarrow P(Br)) \Rightarrow (P(x) \Rightarrow P(Bb))$

このFact1~5を用いて理髪師が誰かを決定するわけです。

STEP1　 $P(Bb) \Rightarrow P(Ro)$ を示す。

Fact4より

$P(Al) \wedge P(Bb) \Rightarrow P(Br)$

$\equiv P(Bb) \Rightarrow \neg P(Al) \vee P(Br)$

$\equiv P(Bb) \Rightarrow \neg P(Al) \vee \neg P(Bn) \hspace{30pt} \text{（Fact1より）}$

$\equiv P(Bb) \Rightarrow \neg (P(Al) \wedge P(Bn))$

$\equiv P(Bb) \Rightarrow \neg P(Ra) \hspace{30pt} \text{（Fact3より）}$

$\equiv P(Bb) \Rightarrow P(Ro) \hspace{30pt} \text{（Fact2より）}$

STEP2　 $P(Al) \wedge P(Ro) \Rightarrow P(Br)$ を示す。

Fact2より

$P(Al) \wedge P(Ro) \equiv P(Al) \wedge \neg P(Ra)$

$\equiv P(Al) \wedge (\neg P(Al) \vee \neg P(Bn)) \hspace{30pt} \text{（Fact3より）}$

$\equiv (P(Al) \wedge \neg P(Al)) \vee (P(Al) \wedge \neg P(Bn))$

$\equiv P(Al) \wedge P(Br)) \hspace{30pt} \text{（Fact1より）}$

$\Rightarrow P(Br)$

STEP3　 $P(Ro) \Rightarrow P(Bb)$ を示す。

STEP2とFact5より $P(Ro) \Rightarrow P(Bb)$

STEP4　 $Bb=Ro$ を示す。

STEP1とSTEP3の結果より $P(Bb) \equiv P(Ro)$

これと(*)より $Bb=Ro \ \Box$

第2回ものまね鳥をまねる会

第2回ものまね鳥をまねる会で手こずった問題を改めて解きました。

３－３　一日理髪師

$f:DAY \rightarrow MAN$ を $E \in DAY$ に対し、公認理髪師 $X \in MAN$ を紐づける写像とする。

また、 $g:MAN \rightarrow MAN$ を $X \in MAN$ に対し、 $X$ が公認理髪師のときに最初にひげをそる人 $X^* \in MAN$ を紐づける写像とする。

さらに $P(D,X,Y)$ を「 $E \in DAY$ 日に $X \in MAN$ が $Y \in MAN$ のひげをそる。」という述語として定義する。

このとき、最初の条件は

$\forall E \in DAY, P(E,f(E),g(f(E))) \tag{1}$

2つ目の条件は

$\forall D, \exists E \in DAY, \forall X, \forall Y \in MAN,P(E,X,Y) \Rightarrow P(D, g(X), Y) \tag{2}$

となる。

(1)、(2)を合わせて

$\forall D, \exists E \in DAY, P(E,f(E),g(f(E))) \wedge (\forall X, \forall Y \in MAN,P(E,X,Y) \Rightarrow P(D, g(X), Y) )$

$\Rightarrow \forall D, \exists E \in DAY, P(D,g(f(E)),g(f(E))) \tag{3}$

一方求めるべき式は $\forall D \in DAY, \exists X \in MAN, P(E,X,X) )$ だが、これは $X=g(f(E))$ とすると(3)に他ならない。 $\Box$

３－６　排他的クラブ

この問題は翻訳に翻訳に誤りがありました。

「AであるのはBの場合に限る。」とあるのですが、解答から逆算すると、「AであるのはBの場合であり、かつその場合に限る。」としないと解けません。

記号で説明すると、 $A \Leftrightarrow B$ を前提として解くべき問題を、 $A \Rightarrow B$ としたため誤った問題となったわけです。

「~ if and only if ~」をわかりやすく翻訳しようとして失敗したんでしょうか？

誤解なくわかりやすく記述しようとするなら、まず数式か論理式でシンプルな形に記述してみるのがお勧めです。

次回からは原著も準備しよう。