数理論理学について

質問

導出原理を使い，次の論理式が恒真であることを示せ．
∀xR(x,f(x)) ∧ ∀x∀y(R(x,y)⊃R(y,x)) ⊃ ∀x∃yR(f(x),y)
なお，この論理式をスコーレム標準形にすると，次の論理式が得られる．
∃w∃x∃y∃z ( ￢R(w,f(w)) ∨ (R(x,y)∧￢R(y,x)) ∨ R(f(c),z) )

この答え分かりますか？

回答No.1

AxiomOfChoice · ベストアンサー

質問者さんが示す論理式
　∀xR(x,f(x)) ∧ ∀x∀y(R(x,y)⊃R(y,x)) ⊃ ∀x∃yR(f(x),y)
を
　( ∀xR(x,f(x))∧∀x∀y(R(x,y)⊃R(y,x)) ) ⊃ ∀x∃yR(f(x),y) 　-　☆
と解釈して、数理論理学を少しかじっただけの私が、"証明可能性”について、こう考えました：
　∀xR(x,f(x))　を仮定 - (1)
∀x∀y(R(x,y)⇒R(y,x))　を仮定 - (2)
　xを任意に取る。　- (3)
(1)から∀除去規則　→　R(x,f(x)) - (4)
　(2)から∀除去規則　→　R(x,f(x))⇒R(f(x),x) - (5)
(4)、(5)とmodus ponens(三段論法) →　R(f(x),x)　－　(6)
　(6)から∃導入規則　→　∃yR(f(x),y) - (7)
　(3)、(7)と∀導入規則 →　∀x∃yR(f(x),y) - (8)
　(1),(2),(8)　→　( ∀xR(x,f(x))∧∀x∀y(R(x,y)⊃R(y,x)) ) ⊃ ∀x∃yR(f(x),y) ー　(9)

　述語論理の健全性と(9)　→　(9)は恒真
　’証明’完了。

これでどうでしょうか？参考になりましたか？
他にも、恒真性を証明するのに、タブローを使う方法があると思います。

次に、星を論理的同値について式変形をします：
　☆　は、　￢( ∀xR(x,f(x))∧∀x∀y(R(x,y)⊃R(y,x)) ) ∨ ∀x∃yR(f(x),y)
　つまり、　￢∀xR(x,f(x)) ∨ ￢(∀x∀y(R(x,y)⊃R(y,x))） ∨ ∀x∃yR(f(x),y)
つまり、 ∃x￢R(x,f(x)) ∨ ( ∃x∃y(R(x,y)　∧　￢R(y,x)) ) ∨ ∀x∃yR(f(x),y)
つまり、 後はよろしく。(∃や∀の移動に関する定理など)
という具合でしょうか？

ちなみに参考図書として、「論理学をつくる」が無茶苦茶わかりやすいです。←高校生でも頑張れば理解出来る。URLは、http://www.amazon.co.jp/%E8%AB%96%E7%90%86%E5%AD%A6%E3%82%92%E3%81%A4%E3%81%8F%E3%82%8B-%E6%88%B8%E7%94%B0%E5%B1%B1-%E5%92%8C%E4%B9%85/dp/4815803900/ref=sr_1_1?ie=UTF8&qid=1309191999&sr=8-1

お礼

ありがとうございます！