数理論理学なのですが

質問

次の４つの論理式のうち１つを選び，ＮＫで証明せよ．
(a) ∀x R(f(x),x) ⊃ ∃x R(f(f(x)),x)
(b)∃x R(f(x),x) ⊃ ∃x R(x,f(x))
(c)∀x R(f(x),x) ⊃ ∃x R(f(f(x)),f(x))
(d) ∃x R(f(x),x) ⊃ ∀x ￢R(x,x)
ＮＫで証明できない論理式もあることに注意せよ．

これを中学生でも分かる程度に解説してくれませんか？一応ほんのちょっとの基本なら分かります(ＮＫは分かりません)

回答No.1

akatsuki_0 · ベストアンサー

NKは自然演繹という証明体系の一種につけられた名前ですね。この体系には幾つかの推論規則があって、それを使って論理式の証明をします。
(c)で試してみましょう。記号の意味は分かりますか? 「∀」はドイツ語で全てを意味する`aller'の頭文字をひっくり返したものです。「∀x」は「どのxについても」と読めばいいです。「∃x」は「あるxがあって」と読みます。
Rは関係記号とよばれます。x,yはいわば空所です。R(x,y)は「xがyとRの関係にある」と読めばいいです。また、fは関数記号とよばれます。f(x)は、入力xに対してf(x)という値を返します。「⊃」は馬蹄記号とよばれ、`if then'の意味です。
そうすると、「∀x R(f(x),x) ⊃ ∃x R(f(f(x)),f(x)))」は、「どのxについてもf(x)とxがRの関係にあるならば、あるxがあってf(f(x))はf(x)とRの関係にある」です。これを示すのに使う推論規則は、全称例化と存在汎化の規則です。正確に述べようとすると結構面倒な規則ですが、直観的な意味は明らかです。前者は

∀xφx
------
φt

という感じの推論で、後者は

φt
------
∃xφx

という感じです。上が言えれば下も言えるのは、まぁ大体分かりますよね。証明の流れは、「∀x R(f(x),x)」を仮定して、例化して、存在汎化する感じです。最後に「⊃」の導入という規則を使います。大雑把にいうと、仮定φから結論ψを導いたら「φ⊃ψ」を推論してよいという規則です。

お礼

なるほど ありがとうございます！

補足

しかし、
∀xφx
------
φt

φt
------
∃xφx

がよく分からないです…

回答No.2

akatsuki_0

たしかに、tが何なのかを全く言ってなかったですね…。正確に述べるのは結構大変なので、大雑把な補足だけします。
1つ目の推論（全称例化）の例になるのは、「すべてのxは奇数か偶数である」から「0は奇数か偶数である」を導く推論です。2つ目の推論の例になるのは、「0は偶数である」から「あるxがあって、それは偶数である」を導く推論です。
これだけ見ればどちらも自明ですよね。要するに、全称例化の推論
∀xφx
------
φt
が言っているのは、すべてのものについてφであると言えるなら、特定の何か（t）についてもφであると言える、というそれだけのことです。(当たり前ですが、これの逆は言えません。「0は偶数である」から「すべてのxは偶数である」などが反例になるでしょう)
存在汎化の場合は、特定の何か（t）についてφであると言えるなら、どれかは特定しなくとも、何らかのxについてφであると言える（あるいは、φであるものが存在する）、ということになります。
回りくどい言い方になって済みません。

お礼

なるほど ありがとうございます！