かじもとにっき

ゆるふわなおはなしをかきます

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

日記が少し遅くなりましたが、第1回 ものまね鳥をまねる会 - connpassに参加しました。
改めて問題を計算によって解いておきます。

1章の4問目

問題を形式化する為に命題変数を3つ導入します。
a:君くんはA賞を得る。
b:君くんはB賞を得る。
c:君くんはC賞を得る。
さらに、君くんが述べる命題にQというラベルを付与しておきます。

ここで、a,b,cが同時に1つだけ真になることをF0として形式化します。
F0:(a \equiv b \equiv c) \wedge \neg (a \wedge b \wedge c)

すると、仮定F0の下で、
(Q \Rightarrow a \vee b) \wedge (\neg Q \Rightarrow c) \Rightarrow a
が恒真式であれば、私さんが(Q \Rightarrow a \vee b) \wedge (\neg Q \Rightarrow c)を満たしてくれることによって、君くんはA賞を得ることが出来ます。
よって、そのようなQを見つければ良いことになります。

(Q \Rightarrow a \vee b) \wedge (\neg Q \Rightarrow c) \Rightarrow a
\equiv (Q \Rightarrow a \vee b) \wedge (\neg Q \Rightarrow (a \equiv b)) \Rightarrow a
\equiv (Q \Rightarrow b) \wedge (\neg Q \Rightarrow \neg b) \Rightarrow a
\equiv (Q \equiv b) \Rightarrow a
\Leftarrow Q {\not \equiv} b

なので、Qとして\neg bを用いれば良いことが分かります。

2014/6/3追記

…という解答だと、(Q \Rightarrow a \vee b) \wedge (\neg Q \Rightarrow c)が恒偽の解答(コメント欄で頂いたQ \equiv cの場合など)も出てくる可能性がありますので、最後に(Q \Rightarrow a \vee b) \wedge (\neg Q \Rightarrow c)が充足可能か調べる必要があります。

もっと良い解答は、条件に(Q \Rightarrow a \vee b) \wedge (\neg Q \Rightarrow c) \Leftarrow aを追加して、

(Q \Rightarrow a \vee b) \wedge (\neg Q \Rightarrow c) \equiv a
\equiv (Q \Rightarrow (a \not \equiv b)) \wedge (\neg Q \Rightarrow (a\equiv b)) \equiv a
\equiv Q \equiv a \not \equiv b \equiv a
\equiv Q \not \equiv b

とでもすることかと思います。

1章の5問目

問題を形式化する為に命題変数を4つ導入します。
a:君くんはA賞を得る。
b:君くんはB賞を得る。
c:君くんはC賞を得る。
d:君くんはD賞を得る。
さらに、君くんが述べる命題にQというラベルを付与しておきます。

ここで、a,b,c,dが同時に1つだけ真になることをF0として形式化します。
F0:(a \equiv b \equiv c \not \equiv d) \wedge \neg (a \wedge b) \wedge \neg (a \wedge c)  \wedge \neg (a \wedge d) \wedge \neg (b \wedge c) \wedge \neg (b \wedge d) \wedge \neg (c \wedge d)

すると、仮定F0の下で、
(Q \Rightarrow a \vee b) \wedge (\neg Q \Rightarrow c \vee d) \Rightarrow c
が恒真式となるようなQを見つければ良いことになります。

この式から変数の数を減らすために、
a \vee b \equiv \neg c \wedge \neg d
という事実が使えます。
実際このことは、

a \equiv b \equiv c \not \equiv d(これはF0の第1論理積成分)
\equiv \neg (a \wedge b \equiv a \vee b \equiv c \wedge d \equiv c \vee d)
\equiv \neg (a \vee b \equiv c \vee d)
\equiv a \vee b \equiv \neg c \wedge \neg d

のように、仮定F0から導くことができます。

従って、

(Q \Rightarrow a \vee b) \wedge (\neg Q \Rightarrow c \vee d) \Rightarrow c
\equiv (Q \Rightarrow \neg c \wedge \neg d) \wedge (\neg Q \Rightarrow c \vee d) \Rightarrow c
\equiv (Q \Rightarrow \neg d) \wedge (\neg Q \Rightarrow d) \Rightarrow c
\equiv (Q \not \equiv d) \Rightarrow c
\Leftarrow Q \equiv d

なので、Qとしてdを用いれば良いことが分かります。

2014/6/3追記

…という解答だと、(Q \Rightarrow a \vee b) \wedge (\neg Q \Rightarrow c \vee d)が恒偽の解答も出てくる可能性がありますので、最後に(Q \Rightarrow a \vee b) \wedge (\neg Q \Rightarrow c \vee d)が充足可能か調べる必要があります。

もっと良い解答は、条件に(Q \Rightarrow a \vee b) \wedge (\neg Q \Rightarrow c \vee d) \Leftarrow cを追加して、

(Q \Rightarrow a \vee b) \wedge (\neg Q \Rightarrow c \vee d) \equiv c
\equiv (Q \Rightarrow \neg c \wedge \neg d) \wedge (\neg (c \vee d) \Rightarrow Q) \equiv c
\equiv Q \not \equiv c \vee d \equiv c
\equiv Q \not \equiv c \not \equiv d \equiv c
\equiv Q \equiv d

とでもすることかと思います。

1章の6問目

命題変数やラベルは5問目のものを引き継ぎます。

題意を考えると、私さんが(Q \Rightarrow a \vee b) \wedge (\neg Q \Rightarrow c \vee d)を絶対に満たせないような、すなわちこの式が恒偽となるようなQを見つければ良いことが分かります。

(Q \Rightarrow a \vee b) \wedge (\neg Q \Rightarrow c \vee d) \equiv false
\equiv \neg ( (Q \Rightarrow \neg c \wedge \neg d) \wedge (\neg Q \Rightarrow c \vee d) )
\equiv \neg ( (c \vee d \Rightarrow \neg Q) \wedge (\neg Q \Rightarrow c \vee d) )
\equiv \neg (\neg Q \equiv c \vee d)
\equiv Q \equiv c \vee d

よって、Qとしてc \vee dを用いれば良いことが分かります。