恒真式

この項目では、論理学用語について説明しています。修辞法については「トートロジー」をご覧ください。

恒真式（こうしんしき、トートロジー、英: tautology、ギリシャ語のταυτο「同じ」に由来）とは論理学の用語で、「aならば aである (a → a) 」「aである、または、aでない (a ∨ ￢a)」のように、そこに含まれる命題変数の真理値、あるいは解釈に関わらず常に真となる論理式である。

対義語としては変数の値にかかわらず常に偽となる矛盾である。

命題論理[編集]

命題論理において、命題を記号化したものが論理式であるが、論理式を構成している、最も単純な文に相当する要素式の真偽値の取り方に関係なく常に真（恒真）となる論理式が存在し、それらはトートロジーもしくは恒真式と呼ばれる^[1]。真にも偽にもなりうる論理式を整合式（英: consistent well-formed formula）、恒に偽になる論理式を恒偽式もしくは矛盾式（英: contradictory well-formed formula）という。

述語論理[編集]

述語論理においては、トートロジーを考える事はないが、同様な概念を考える事ができる。論理式が、全ての解釈にたいして真になるとき、この論理式は恒真 (validity) で、妥当式 (valid wff) になる。少なくとも一つの解釈で論理式が真になるとき、この論理式は充足可能 (en:Satisfiability) で、充足可能式 (satisfiable wff) になる。全ての解釈で論理式が偽になるとき、この論理式は充足不可能で、矛盾式 (contradictory wff) になる^[2]^[3]。

定義と例[編集]

ここでは古典命題論理における恒真式の定義を述べる。 $\mathrm {Val}$ を命題変数の全体とする。 $f:\mathrm {Val} \to \{\top ,\bot \}$ なる写像、すなわち命題変数への真理値割り当てを考える。 $\top$ は恒真、 $\bot$ は矛盾。次のようにして $f$ の始域を論理式の全体 $\mathrm {Fml}$ に拡張する（右辺の $\wedge \vee \neg \to$ は論理記号ではなく $\{\top ,\bot \}$ 上の演算である）：

$f(\alpha \wedge \beta ):=f(\alpha )\wedge f(\beta )$
$f(\alpha \vee \beta ):=f(\alpha )\vee f(\beta )$
$f(\neg \alpha ):=\neg f(\alpha )$
$f(\alpha \to \beta ):=f(\alpha )\to f(\beta )$

このようにして得られる写像 $f:\mathrm {Fml} \to \{\top ,\bot \}$ を付値という。任意の付値 $f$ に対して $f(\alpha )=\top$ となるとき、 $\alpha$ を恒真式という。

古典論理の上で、次の論理式は恒真式である。

$\neg (\alpha \wedge \neg \alpha )$
$\alpha \vee \neg \alpha$
$(\alpha \to \beta )\Leftrightarrow (\neg \beta \to \neg \alpha )$
$\neg \neg \alpha \Leftrightarrow \alpha$
$\neg (\alpha \wedge \beta )\Leftrightarrow (\neg \alpha \vee \neg \beta )$
$((\alpha \to \beta )\wedge (\beta \to \gamma ))\to (\alpha \to \gamma )$

主な恒真式として、同一律、排中律、矛盾律、二重否定の法則、巾等律、交換律、結合律、分配律、吸収律、ド・モルガンの法則、対偶律、選言的三段論法、前件肯定式、推移律、移入律、移出律（英語版）、縮小律、拡大律、構成的両刀論法（英語版）などがある^[4]。

述語論理において、妥当式になる主な論理式は以下の通りになる^[5]。

$\forall x_{i}Ax_{i}\supset At$ ( $t$ は項で、 $Ax_{i}$ の $x_{i}$ にたいして自由)
$At\supset \exists x_{i}Ax_{i}$ ( $t$ は項で、 $Ax_{i}$ の $x_{i}$ にたいして自由)
$\lnot \forall x_{i}Ax_{i}\equiv \exists x_{i}\lnot Ax_{i}$
$\lnot \exists x_{i}Ax_{i}\equiv \forall x_{i}\lnot Ax_{i}$
$\forall x_{i}\forall x_{j}Ax_{i}x_{j}\equiv \forall x_{j}\forall x_{i}Ax_{i}x_{j}$
$\exists x_{i}\exists x_{j}Ax_{i}x_{j}\equiv \exists x_{j}\exists x_{i}Ax_{i}x_{j}$
$\exists x_{i}\forall x_{j}Ax_{i}x_{j}\supset \forall x_{j}\exists x_{i}Ax_{i}x_{j}$
$\forall (Ax_{i}\land Bx_{i})\equiv (\forall x_{i}Ax_{i}\land \forall x_{i}Bx_{i})$
$\exists x_{i}(Ax_{i}\lor Bx_{i})\equiv (\exists x_{i}Ax_{i}\lor \exists x_{i}Bx_{i})$
$(\forall x_{i}Ax_{i}\lor \forall x_{i}Bx_{i})\supset \forall x_{i}(Ax_{i}\lor Bx_{i})$
$\exists x_{i}(Ax_{i}\land Bx_{i})\supset (\exists x_{i}Ax_{i}\land \exists x_{i}Bx_{i})$
$\forall x_{i}(C\land Ax_{i})\equiv (C\land \forall x_{i}Ax_{i})$ ( $C$ に自由変項として $x_{i}$ が含まれていない)
$\forall x_{i}(C\lor Ax_{i})\equiv (C\lor \forall x_{i}Ax_{i})$ ( $C$ に自由変項として $x_{i}$ が含まれていない)
$\exists x_{i}(C\land Ax_{i})\equiv (C\land \exists x_{i}Ax_{i})$ ( $C$ に自由変項として $x_{i}$ が含まれていない)
$\exists x_{i}(C\lor Ax_{i})\equiv (C\lor \exists x_{i}Ax_{i})$ ( $C$ に自由変項として $x_{i}$ が含まれていない)
$\forall x_{i}(C\supset Ax_{i})\equiv (C\supset \forall x_{i}Ax_{i})$ ( $C$ に自由変項として $x_{i}$ が含まれていない)
$\forall x_{i}(Ax_{i}\supset C)\equiv (\exists x_{i}Ax_{i}\supset C)$ ( $C$ に自由変項として $x_{i}$ が含まれていない)

恒真式である確認[編集]

命題論理[編集]

ある式が恒真式であるかどうかを確認することは命題論理の基本である。一般に、真理値表をつくって真理値分析を行う作業になる。命題変数がn個存在する場合2ⁿ通りのケースを調べればよい。例えば $\alpha \to (\beta \to \alpha )$ であれば次の4通りのケースを調べる。

$\alpha$	$\beta$	$\beta \to \alpha$	$\alpha \to (\beta \to \alpha )$
T	T	T	T
T	F	T	T
F	T	F	T
F	F	T	T

次のようにして、代数的な式変形によっても確認できる。

$\alpha \to (\beta \to \alpha )=\neg \alpha \vee (\neg \beta \vee \alpha )=(\alpha \vee \neg \alpha )\vee \neg \beta =\top \vee \neg \beta =\top$

述語論理[編集]

述語論理において論理式が妥当式かを求める方法を示す。ある推論が、次の5つの推論規則を用いて正しい事を示し、その推論を論理式に変換したものが妥当式になる事から求める方法がある^[6]。

UI（全称例化）: ∀ $x_{i}Ax_{i}$ から $At$ を導き出す事ができる。ただし、 $t$ は項であり、 $Ax_{i}$ の $x_{i}$ に対して自由であること。
UG（全称汎化）: $Ax_{i}$ から∀ $x_{i}Ax_{i}$ を導き出す事ができる。ただし、 $x_{i}$ が前提の諸式に自由変項として現れていないこと。また、 $x_{i}$ が不確定名の添字になっていないこと。
EI（存在例化）: ∃ $x_{i}Ax_{i}$ から $A{\alpha }_{j}$ を導き出す事ができる。ただし、 $A{\alpha }_{j}$ は不確定名であること。
EG（存在汎化）: $At$ から∃ $x_{i}Ax_{i}$ を導き出す事ができる。ただし、 $t$ は項であり、また $t$ は $Ax_{i}$ の $x_{i}$ に対して自由であること。
P（命題論理的推論）: 命題論理で正しい推論式は述語論理でも正しい。

論理式への変換: $A_{1}\cdots A_{n}$ → $C$ が正しい ⇔ ( $A_{1}$ ∧ $\cdots$ ∧ $A_{n}$ )⊃ $C$ が妥当式

「タブローの方法」も参照

脚注[編集]

[脚注の使い方]

^ 清水 1984, pp. 7-15.
^ “記号論理学”. 静岡理工科大学　菅沼研究室. 2020年9月9日閲覧。
^ 清水 1984, p. 51.
^ 清水 1984, pp. 14-15.
^ 清水 1984, pp. 51-53.
^ 清水 1984, p. 57.

参考文献[編集]

清水義夫『記号論理学』東京大学出版会、1984年。

外部リンク　[編集]

この項目は、数理論理学に関連した書きかけの項目です。この項目を加筆・訂正などしてくださる協力者を求めています。

[FOOTNOTE清水19847-15-1] 清水 1984, pp. 7-15.

[2] “記号論理学”. 静岡理工科大学　菅沼研究室. 2020年9月9日閲覧。

[FOOTNOTE清水198451-3] 清水 1984, p. 51.

[FOOTNOTE清水198414-15-4] 清水 1984, pp. 14-15.

[FOOTNOTE清水198451-53-5] 清水 1984, pp. 51-53.

[FOOTNOTE清水198457-6] 清水 1984, p. 57.

[1]

[2]

[3]

[4]

[5]

[6]

恒真式

目次

命題論理[編集]

述語論理[編集]

定義と例[編集]

恒真式である確認[編集]

命題論理[編集]

述語論理[編集]

脚注[編集]

参考文献[編集]

関連項目[編集]

外部リンク　[編集]

案内メニュー

検索

恒真式

命題論理[編集]

述語論理[編集]

定義と例[編集]

恒真式である確認[編集]

命題論理[編集]

述語論理[編集]

脚注[編集]

参考文献[編集]

関連項目[編集]

外部リンク [編集]

案内メニュー

検索

外部リンク　[編集]