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

暇つぶしに見て
暇つぶしに見て

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

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

スポンサーリンク

全称除去(普遍例化)

定義

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

ある項 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)(→除去)

6)∀x∀y(P(x) ∧ (P(y) → Q(y)) ⊢ Q(d)

1. ∀x∀y(P(x) ∧ (P(y) → Q(y))
2.∀y(P(d)⋏(P(y)→Q(y))(∀除去)
3.P(d)⋏(P(d)→Q(y))(∀除去)
4.P(d),P(d)→Q(d)
5.Q(d)(→除去)

もう少し馴染みのある方法に応用してみようと自然の加法で全称除去の問題を考えてみました。

∀x((x+2)=S(S(x)))

意味としては単純に任意のxに2を加えるとxの次の次の数になるってだけ。
演繹してみます。
2は0の後者の後者S(S(0))と定義します。

1.∀x(x+2)(仮定)
2.a+2(全称除去)
3.S(a)+1(加法定義)
4.S(S(a))+0(加法定義)
5.S(S(a))(加法定義)
6.∀x(S(S(x)))(全称導入)

同値変形しただけなのでS(S(a))から∀x(x+2)も演繹できますので同値関係が成立します。

【加法定義】
すべての自然数 a に対して、a + 0 = a
すべての自然数 ab に対して、a + suc(b) = suc(a + b)

Wikipedia

∀x∀y((x+y)=)

∀x∀y((x+y)

関連記事

長濱陸Tシャツ

お求めはこちらから

お問い合わせはこちら

パーソナルトレーニングやグループトレーニング、セミナーや取材、YouTubeコラボなどのご依頼はこちらからよろしくお願いします。

トレーニングの依頼などはこちらから

スポンサーリンク
Die Hard – ダイ・ハード
この記事を書いた人

第41第東洋太平洋(OPBF)ウェルター級王者
元WBC世界同級34位
元WBO-AP同級3位
元角海老宝石ジム所属

股関節おじさんをフォローする
スポンサーリンク
スポンサーリンク
股関節おじさんをフォローする

コメント

タイトルとURLをコピーしました