恒真式

テンプレート:Otheruses 恒真式（こうしんしき、トートロジー、テンプレート:Lang-en-short、ギリシャ語のテンプレート:El「同じ」に由来）は、論理学の用語で「aであるならばaである（a → a）」「aである、または、aでない（a∨￢a）」のように、そこに含まれる命題変数の真理値、あるいは解釈に関わらず常に真となる論理式のことである。

恒真式の否定は、変数の値にかかわらず常に偽となる式、すなわち矛盾である。

命題論理

命題論理において、命題を記号化したものが論理式であるが、論理式を構成している、最も単純な文に相当する要素式の真偽値の取り方に関係なく常に真（恒真）となる論理式が存在し、それらはトートロジーもしくは恒真式と呼ばれるテンプレート:Sfn。真にも偽にもなりうる論理式を整合式（テンプレート:Lang-en-short）、恒に偽になる論理式を恒偽式もしくは矛盾式（テンプレート:Lang-en-short）という。

述語論理

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

定義と例

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

• $f(\alpha \wedge \beta ):=f(\alpha )\wedge f(\beta )$
• $f(\alpha \vee \beta ):=f(\alpha )\vee f(\beta )$
• $f(\mathrm{\neg }\alpha ):=\mathrm{\neg }f(\alpha )$
• $f(\alpha \to \beta ):=f(\alpha )\to f(\beta )$

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

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

• $\mathrm{\neg }(\alpha \wedge \mathrm{\neg }\alpha )$
• $\alpha \vee \mathrm{\neg }\alpha$
• $(\alpha \to \beta )\iff (\mathrm{\neg }\beta \to \mathrm{\neg }\alpha )$
• $\mathrm{\neg }\mathrm{\neg }\alpha \iff \alpha$
• $\mathrm{\neg }(\alpha \wedge \beta )\iff (\mathrm{\neg }\alpha \vee \mathrm{\neg }\beta )$
• $((\alpha \to \beta )\wedge (\beta \to \gamma ))\to (\alpha \to \gamma )$

主な恒真式として、同一律、排中律、矛盾律、二重否定の法則、巾等律、交換律、結合律、分配律、吸収律、ド・モルガンの法則、対偶律、選言的三段論法、前件肯定式、推移律、移入律、テンプレート:仮リンク、縮小律、拡大律、テンプレート:仮リンクなどがあるテンプレート:Sfn。

恒真式である確認

命題論理

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

$\alpha$	$\beta$	$\beta \to \alpha$	$\alpha \to (\beta \to \alpha )$
テンプレート:Yes2	テンプレート:Yes2	テンプレート:Yes2	テンプレート:Yes2
テンプレート:Yes2	テンプレート:No2	テンプレート:Yes2	テンプレート:Yes2
テンプレート:No2	テンプレート:Yes2	テンプレート:No2	テンプレート:Yes2
テンプレート:No2	テンプレート:No2	テンプレート:Yes2	テンプレート:Yes2

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

$\alpha \to (\beta \to \alpha )=\mathrm{\neg }\alpha \vee (\mathrm{\neg }\beta \vee \alpha )=(\alpha \vee \mathrm{\neg }\alpha )\vee \mathrm{\neg }\beta =\mathrm{\top }\vee \mathrm{\neg }\beta =\mathrm{\top }$

テンプレート:See also

参考文献

• テンプレート:Citation

関連項目

• 論理的真理
• 推論
• 完全性
• 論理回路
• 論理記号の一覧
• 循環定義

外部リンク　

• 7.恒真命題・恒偽命題　(山陽学園大学　論理学)
• 11.述語論理　(山陽学園大学　論理学)