第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