普遍的な一般化

Rule of inference in predicate logic

普遍的な一般化

タイプ	推論の規則
分野	述語論理
声明	が任意に選択された に対して真であるとすると、 はすべてに対して真となります。 ${\displaystyle P}$ ${\displaystyle p}$ ${\displaystyle P}$
象徴的な声明	${\displaystyle \vdash \!P(x)}$、 ${\displaystyle \vdash \!\forall x\,P(x)}$

述語論理において、一般化（普遍一般化、普遍導入、^{[1] [2] [3]} GEN、UGとも呼ばれる）は有効な 推論規則である。これは、が導出されていれば、が導出できるということを述べている。 ${\displaystyle \vdash \!P(x)}$ ${\displaystyle \vdash \!\forall x\,P(x)}$

仮説による一般化

完全な一般化規則は、ターンスタイルの左側に仮説を許容しますが、制約があります。が式の集合、式、および が導出されていると仮定します。一般化規則は、が で言及されておらず、に出現しない場合、 が導出できることを述べています。 ${\displaystyle \Gamma }$ ${\displaystyle \varphi }$ ${\displaystyle \Gamma \vdash \varphi (y)}$ ${\displaystyle \Gamma \vdash \forall x\,\varphi (x)}$ ${\displaystyle y}$ ${\displaystyle \Gamma }$ ${\displaystyle x}$ ${\displaystyle \varphi }$

これらの制約は健全性のために必要です。最初の制約がなければ、仮説から結論を導き出すことができます。2番目の制約がなければ、次のような推論を行うことができます。 ${\displaystyle \forall xP(x)}$ ${\displaystyle P(y)}$

1. ${\displaystyle \exists z\,\exists w\,(z\not =w)}$（仮説）
2. ${\displaystyle \exists w\,(y\not =w)}$（存在のインスタンス化）
3. ${\displaystyle y\not =x}$（存在のインスタンス化）
4. ${\displaystyle \forall x\,(x\not =x)}$（誤った普遍的一般化）

これは、不健全な推論であるを示すことを意図しています。が で言及されていない場合、 は許​​容されることに注意してください（ の意味構造は変数の置換によって変化しないため、2番目の制限は適用する必要はありません）。 ${\displaystyle \exists z\,\exists w\,(z\not =w)\vdash \forall x\,(x\not =x),}$ ${\displaystyle \Gamma \vdash \forall y\,\varphi (y)}$ ${\displaystyle y}$ ${\displaystyle \Gamma }$ ${\displaystyle \varphi (y)}$

証明の例

証明: はおよびから導出可能です。 ${\displaystyle \forall x\,(P(x)\rightarrow Q(x))\rightarrow (\forall x\,P(x)\rightarrow \forall x\,Q(x))}$ ${\displaystyle \forall x\,(P(x)\rightarrow Q(x))}$ ${\displaystyle \forall x\,P(x)}$

証拠：

ステップ	式	正当化
1	${\displaystyle \forall x\,(P(x)\rightarrow Q(x))}$	仮説
2	${\displaystyle \forall x\,P(x)}$	仮説
3	${\displaystyle (\forall x\,(P(x)\rightarrow Q(x)))\rightarrow (P(y)\rightarrow Q(y))}$	（１）ユニバーサルインスタンス化による
4	${\displaystyle P(y)\rightarrow Q(y)}$	(1)と(3)からModus ponens
5	${\displaystyle (\forall x\,P(x))\rightarrow P(y)}$	（２）ユニバーサルインスタンス化による
6	${\displaystyle P(y)\ }$	(2)と(5)からModus ponens
7	${\displaystyle Q(y)\ }$	(6)と(4)からModus ponens
8	${\displaystyle \forall x\,Q(x)}$	(7)から一般化
9	${\displaystyle \forall x\,(P(x)\rightarrow Q(x)),\forall x\,P(x)\vdash \forall x\,Q(x)}$	（1）から（8）までの要約
10	${\displaystyle \forall x\,(P(x)\rightarrow Q(x))\vdash \forall x\,P(x)\rightarrow \forall x\,Q(x)}$	(9)演繹定理より
11	${\displaystyle \vdash \forall x\,(P(x)\rightarrow Q(x))\rightarrow (\forall x\,P(x)\rightarrow \forall x\,Q(x))}$	(10)演繹定理より

この証明では、ステップ 8 で普遍一般化が使用されました。移動される式には自由変数がないため、ステップ 10 と 11 では演繹定理が適用できました。

参照

• 一階論理
• 性急な一般化
• 普遍的なインスタンス化
• 存在の一般化

参考文献

1. コピとコーエン
2. ハーレー
3. ムーアとパーカー

Retrieved from "https://en.wikipedia.org/w/index.php?title=Universal_generalization&oldid=1316812016"