全称除去の定義と練習問題

股関節おじさんの勉強部屋

2023.09.18

述語論理における全称記号∀を取り除く推論規則を見ていきます。

別名を普遍例化と呼ぶようです。

全称除去(普遍例化)

全称除去(普遍例化)

定義

例:「全ての犬は動物である。ポチは犬である。従って、ポチは動物である」

ある項 a について公理スキーマとして記号的に表すと以下のようになる。

$\displaystyle \forall x\,A(x)\Rightarrow A(a/x)$
ここで
$\displaystyle A(a/x)$ は A における x の自由な出現を a で置換した結果を表す。

推論規則としては次のように記述される。

from ⊢ ∀x A infer ⊢ A(a/x)
Wikipedia

難しくはありません。
ある集合の要素の全てに当てはまることは、aにも当てはまる。これを記号化した処理にあてはると全称記号が取り除かれて、要素が一つ定められます。
代数的な発想の根の部分でしょうかね。

練習問題

とりあえず練習問題でやりながら覚えます。ネットで適当に探してきた問題で演繹は定かではありません。

1)∀x(P(x)→Q(x)∧R(x),P(a)⊢Q(a))

1.∀x(P(x)→Q(x)∧R(x),P(x))(仮定)
2.P(a)→Q(a)∧R(a)()(∀除去)
3.[P(a)](仮定)
4.Q(a)∧R(a)(→除去)
5.Q(a)(∧除去)
6.P(a)→Q(a)(→導入)
7.(∀x(P(x)→Q(x)∧R(x)))→(P(a)→Q(a)) (→導入)
8.(∀P(x)→Q(x)∧R(x))∧(Pa)→Q(a)) (→言い換え)

2)P(d) , ∀x(P(x) → (P(x) → Q(x))) ⊢ Q(d)

1.P(d),∀x(P(x)→(P(x)→Q(x)))(仮定)
2.P(d)→(P(d)→Q(d))(∀除去)
3.P(d)→Q(d)(→除去)
4.Q(d)(→除去)

3). ∀x(P(x) → Q(x)) , ∀x(P(x) → R(x)) , P(d) ⊢ Q(d) ∧ R(d)

1.∀x(P(x) → Q(x)) , ∀x(P(x) → R(x)) , P(d) (仮定)
2.(P(d)→Q(d)),P(d)→R(d)(∀除去)
3.Q(d),R(d)(→除去)
4.Q(d)⋏R(d)(⋏導入)

4)∀x(P(x) ∧ (Q(x) → R(x))) , ∀x(P(x) → Q(x)) ⊢ R(d)

1.∀x(P(x) ∧ (Q(x) → R(x))) , ∀x(P(x) → Q(x)) (仮定)
2.P(d)⋏(Q(d)→R(x))(∀除去)
3.P(d),Q(d)→R(d)
4.P(d)→Q(d)(∀除去)
5.Q(d)(→除去)
6.R(d)(→除去)

5)∀x(P(x) → Q(x)) , ¬Q(c) ⊢ ¬P(c)

1.∀x(P(x) → Q(x)) , ¬Q(c)(仮定)
2.P(c)→Q(c)(∀除去)
3.￢Q(c)→￢P(c)(対偶)
4.￢P(c)(→除去)