記号論理学� 2000 年度冬学期試験解答例

理科一類 24 組 師 芳卓

2002 年 2 月 1 日

問題は省略することにします。過去問リンクからダウンロードしてください。超厳密な証明を要する教科なので間違っている部分があるかもしれません。なので答を 100 ％信じるの

は危険です。ここは変じゃないですか？と思ったら遠慮なく質問してください。

問題 1

(1) Den(ρ, 「Sx_{3} ¯+SS¯0」)

= Den(ρ, 「Sx_{3}」) + Den(ρ, 「SS¯0」)) = (Den(ρ, x_{3}) + 1) + (Den(ρ, 「S¯0」) + 1)) = (Den(ρ, x_{3}) + 1) + ((Den(ρ, ¯0) + 1) + 1)) = (ρ(3) + 1) + ((0 + 1) + 1)) = 8

(2) ∀x_{0}(¬Sx_{0} ≡ ¯0) ∈ T rue ⇔ Πρ(Sat(ρ, 「∀x_{0}(¬Sx_{0} ≡ ¯0)」)) ⇔ ΠρΠσ(σ ∈ F amily(ρ/0) ⇒ Sat(σ, 「¬Sx_{0} ≡ ¯0」)) ⇔ ΠρΠσ(σ ∈ F amily(ρ/0) ⇒∼ Sat(σ, 「Sx_{0} ≡ ¯0」)) ⇔ ΠρΠσ(σ ∈ F amily(ρ/0) ⇒∼ (Den(σ, 「Sx_{0}」) = Den(σ, 「¯0」))) ⇔ ΠρΠσ(σ ∈ F amily(ρ/0) ⇒∼ (Den(σ, x_{0}) + 1 = 0)))

(3) まず、適当な ρ を固定する。次に前提として σ ∈ F amily(ρ/0) を仮定すると、 σ(0) ∈ N なので、

∀_{d∈N}(∼ (d + 1 = 0))

∼ (σ(0) + 1 = 0) ∼ (Den(σ, x_{0}) + 1 = 0)

となる。ここで先ほどの前提を消して ⇒ を導入すると、

\frac{σ ∈ F amily(ρ/0) ⇒∼ (Den(σ, x_{0}) + 1 = 0)}{ΠρΠσ(σ ∈ F amily(ρ/0) ⇒∼ (Den(σ, x_{0}) + 1 = 0)))}

(2) から N ⊧ 公理 1 が示された。

問題 2

(1) Sat を用いると次のように書き換えられる。ただし、 σ ∈ M, ρ ∈ M とする。 Π_{M}(Π_{σ}(Sat(σ, A)) ⇒ Π_{ρ}(Sat(ρ, B))) ⇒ Π_{M}Π_{σ}(Sat(σ, A) ⇒ Sat(σ, B))

(2) まずは、 Sat(σ′, A) と Π_{M}(Π_{σ}(Sat(σ, A)) ⇒ Π_{ρ}(Sat(ρ, B))) を仮定する。 A,B は閉じた式であるから、 F V (A) = 0, F V (B) = 0 であり、レジュメの [III](1) の補題より、 Π_{σ}Π_{ρ}(Sat(σ, A) ⇒ Sat(ρ, A)) が成り立つ。よって Sat(σ′, A) から Π_{σ}(Sat(σ, A)) が導かれる。あとは証明図にそっていくと、

[Π_{M}(Π_{σ}(Sat(σ, A)) ⇒ Π_{ρ}(Sat(ρ, B)))]_{2}
Π_{σ}(Sat(σ, A)) ⇒ Π_{ρ}(Sat(ρ, B)) Π_{σ}(Sat(σ, A))
Π_{ρ}(Sat(ρ, B))
Sat(σ′, B) _{1}
Sat(σ′, A) ⇒ Sat(σ′, B)
Π_{M}Π_{σ}(Sat(σ, A) ⇒ Sat(σ, B)) _{2}

Π_{M}(Π_{σ}(Sat(σ, A)) ⇒ Π_{ρ}(Sat(ρ, B))) ⇒ Π_{M}Π_{σ}(Sat(σ, A) ⇒ Sat(σ, B))

Sat(σ′, A) は [Sat(σ′, A)]_{1} として消されているのでこれで証明された。

問題 3

(1) すべて書き切れないのでところどころ文章が入る。 (途中の括弧は後にはずされることになるので最初は気にしなくて良い)

\frac{[∀x_{1}∃x_{0}(F x_{0} → Gx_{1})]_{4}}{∃x_{0}(F x_{0} → Gx_{i})}

ここで x_{0} を x_{k} で例化してサブプルーフに入る。まず、 F x_{k} → Gx_{i} の前提を導くため、次のように証明を進める。

\underline{\begin{matrix}[¬F x_{k}]_{2}[F x_{k}]_{1} \\ ⊥ \\ Gx_{m} _{1} \\ F x_{k} → Gx_{m} \\ ∀x_{1}(F x_{k} → Gx_{1}) \\ ∃x_{0}∀x_{1}(F x_{0} → Gx_{1}) \end{matrix} [¬∃x_{0}∀x_{1}(F x_{0} → Gx_{1})]_{3}}

\begin{matrix}⊥ _{2} \\ ¬¬F x_{k} \\ F x_{k} \end{matrix}

これで前提が導けたので

\frac{F x_{k} F x_{k} → Gx_{i}}{Gx_{i}}

となる。ここでサブプルーフを抜ける。

Gx_{i}

F x_{j} → Gx_{i}

∀x_{1}(F x_{j} → Gx_{1}) ∃x_{0}∀x_{1}(F x_{0} → Gx_{1}) となり、先ほども用いた過程とあわせて矛盾を導く。 ∃x_{0}∀x_{1}(F x_{0} → Gx_{1}) [¬∃x_{0}∀x_{1}(F x_{0} → Gx_{1})]_{3}

⊥ _{3}

¬¬∃x_{0}∀x_{1}(F x_{0} → Gx_{1})
∃x_{0}∀x_{1}(F x_{0} → Gx_{1}) _{4}

∀x_{1}∃x_{0}(F x_{0} → Gx_{1}) → ∃x_{0}∀x_{1}(F x_{0} → Gx_{1})

となり、証明された。

(2) 問題の手順に従って証明する。 (2-1) M_{0}, σ_{0} |< ∃x_{1}∀x_{0}(F x_{0} → Gx_{1}) ⇔ Sat(σ_{0}, 「∃x_{1}∀x_{0}(F x_{0} → Gx_{1})」) ⇔ Σρ_{1}(ρ_{1} ∈ F amily(σ_{0}/1)&Sat(ρ_{1}, 「∀x_{0}(F x_{0} → Gx_{1})」) ⇔ Σρ_{1}(ρ_{1} ∈ F amily(σ_{0}/1)&Πτ_{1}(τ_{1} ∈ F amily(ρ_{1}/0) ⇒ Sat(τ_{1}, 「F x_{0} → Gx_{1}」)))

(2-2) M_{0}, σ_{0} |< ∀x_{0}∃x_{1}(F x_{0} → Gx_{1}) ^{1} ⇔ Sat(σ_{0}, 「∀x_{0}∃x_{1}(F x_{0} → Gx_{1})」) ⇔ Πρ_{2}(ρ_{2} ∈ F amily(σ_{0}/0) ⇒ Sat(ρ_{2}, 「∃x_{1}(F x_{0} → Gx_{1})」) ⇔ Πρ_{2}(ρ_{2} ∈ F amily(σ_{0}/0) ⇒ Στ_{2}(τ_{2} ∈ F amily(ρ_{2}/1)&Sat(τ_{2}, 「F x_{0} → Gx_{1}」)))

(2-3) 問題文が理解不能です。が、一応問題文を「ρ_{2}(0) だけを ρ_{1}(0) へと取り替えた」の部分を「ρ_{2}(1) だけ

を ρ_{1}(1) へと取り替えた」とすればなんか上手くいきそうなのでそれでやってみます。でも (2-2) の訂正もそうだが、問題文ってそんな間違いがあるものではないとと思うんだけどな…

問題文の ρ_{3} は ρ_{3}(1) = ρ_{1}(1)、 ρ_{3}(1) は任意の値をとり、それ以外は σ_{0} と一致する列である。なので、 ρ_{3} ∈ F amily(ρ_{2}, 1) は当然のこと、 ρ_{3} ∈ F amily(ρ_{1}/0) も成立し、 τ_{1}, τ_{2} としての条件を満たす。因みに ρ_{3} を考えている時点で前提に ρ_{2} ∈ F amily(σ_{0}/0) があることもお忘れなく。

さて、 (2-1) を前提としているのでここから証明図を書いていくと、

Πτ_{1}(τ_{1} ∈ F amily(ρ_{1}/0) ⇒ Sat(τ_{1}, 「F x_{0} → Gx_{1}」))

ρ_{3} ∈ F amily(ρ_{1}/0) ⇒ Sat(ρ_{3}, 「F x_{0} → Gx_{1}」) ρ_{3} ∈ F amily(ρ_{1}/0)

Sat(ρ_{3}, 「F x_{0} → Gx_{1}」)

ここで ρ_{3} ∈ F amily(ρ_{2}, 1) と合わせ、

ρ_{3} ∈ F amily(ρ_{2}, 1) Sat(ρ_{3}, 「F x_{0} → Gx_{1}」) ρ_{3} ∈ F amily(ρ_{2}, 1)&Sat(ρ_{3}, 「F x_{0} → Gx_{1}」)

Στ_{2}(τ_{2} ∈ F amily(ρ_{2}/1)&Sat(τ_{2}, 「F x_{0} → Gx_{1}」))

ここで前提であった ρ_{2} ∈ F amily(σ_{0}/0) を⇒の導入則を用いて消すと、

\frac{ρ_{2} ∈ F amily(σ_{0}/0) ⇒ Στ_{2}(τ_{2} ∈ F amily(ρ_{2}/1)&Sat(τ_{2}, 「F x_{0} → Gx_{1}」))}{Πρ_{2}(ρ_{2} ∈ F amily(σ_{0}/0) ⇒ Στ_{2}(τ_{2} ∈ F amily(ρ_{2}/1)&Sat(τ_{2}, 「F x_{0} → Gx_{1}」)))}

これで (2-2) が導けたことになる。 M_{0}, σ_{0} |< ∃x_{1}∀x_{0}(F x_{0} → Gx_{1}) ⇒ M_{0}, σ_{0} |< ∀x_{0}∃x_{1}(F x_{0} → Gx_{1}) ⇔ M_{0}, σ_{0} |< ∃x_{1}∀x_{0}(F x_{0} → Gx_{1}) → ∀x_{0}∃x_{1}(F x_{0} → Gx_{1}) σ_{0} を全称量化し、 ⇔ M_{0} ⊧ ∃x_{1}∀x_{0}(F x_{0} → Gx_{1}) → ∀x_{0}∃x_{1}(F x_{0} → Gx_{1}) 閉じた式であるから ⇔ M_{0} ⊧ ∃x_{1}∀x_{0}(F x_{0} → Gx_{1}) ⇒ M_{0} ⊧ ∀x_{0}∃x_{1}(F x_{0} → Gx_{1}) M_{0} を全称量化すれば証明すべき式が得られる。

1 過去問では x_{0} と x_{1} が逆になっていたので注意してください。

問題 4

(1) ∀_{x}(< x, 0, x >∈ Add) ^{2}

(2) ∀_{x}∀_{y}∀_{z}(< x, y, z >∈ Add →< x, Sy, Sz >∈ Add)

(3) ’の有無に気をつけてください。 ∀_{x}∀_{y}∀_{z}(< x, y, z >∈ Add ↔ ∀_{W} (∀_{x′}(< x′, 0, x′ >∈ W)∧∀_{x′}∀_{y′}∀_{z′}(< x′, y′, z′ >∈ W →< x′, Sy′, Sz′ >∈

W) →< x, y, z >∈ W))

(4) わかりません。これがわからないと意味がないという説もありますが…。現在、何をすればよいのか調査中です。

2 過去問では ∀_{x}(x + 0 = 0) となっていましたがこれは明らかにおかしいので ∀_{x}(x + 0 = x) であるとして問題を解きました。