恒真式
- العربية
- مصرى
- Български
- Català
- Čeština
- Dansk
- Deutsch
- English
- Esperanto
- Español
- Eesti
- Euskara
- فارسی
- Français
- Galego
- עברית
- Magyar
- Bahasa Indonesia
- Íslenska
- Italiano
- 한국어
- Кыргызча
- Lietuvių
- Македонски
- Nederlands
- Norsk bokmål
- Polski
- Português
- Русский
- Simple English
- Slovenčina
- Српски / srpski
- Svenska
- Türkçe
- Українська
- اردو
- 中文
恒真式(こうしんしき、トートロジー、英: 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] 。
定義と例
[編集 ]ここでは古典命題論理における恒真式の定義を述べる。{\displaystyle \mathrm {Val} } を命題変数の全体とする。{\displaystyle f:\mathrm {Val} \to \{\top ,\bot \}} なる写像、すなわち命題変数への真理値割り当てを考える。{\displaystyle \top }は恒真、{\displaystyle \bot }は矛盾。次のようにして {\displaystyle f} の始域を論理式の全体 {\displaystyle \mathrm {Fml} } に拡張する(右辺の {\displaystyle \wedge \vee \neg \to } は論理記号ではなく {\displaystyle \{\top ,\bot \}} 上の 演算である):
- {\displaystyle f(\alpha \wedge \beta ):=f(\alpha )\wedge f(\beta )}
- {\displaystyle f(\alpha \vee \beta ):=f(\alpha )\vee f(\beta )}
- {\displaystyle f(\neg \alpha ):=\neg f(\alpha )}
- {\displaystyle f(\alpha \to \beta ):=f(\alpha )\to f(\beta )}
このようにして得られる写像 {\displaystyle f:\mathrm {Fml} \to \{\top ,\bot \}} を付値という。任意の付値 {\displaystyle f} に対して {\displaystyle f(\alpha )=\top } となるとき、{\displaystyle \alpha } を恒真式という。
古典論理の上で、次の論理式は恒真式である。
- {\displaystyle \neg (\alpha \wedge \neg \alpha )}
- {\displaystyle \alpha \vee \neg \alpha }
- {\displaystyle (\alpha \to \beta )\Leftrightarrow (\neg \beta \to \neg \alpha )}
- {\displaystyle \neg \neg \alpha \Leftrightarrow \alpha }
- {\displaystyle \neg (\alpha \wedge \beta )\Leftrightarrow (\neg \alpha \vee \neg \beta )}
- {\displaystyle ((\alpha \to \beta )\wedge (\beta \to \gamma ))\to (\alpha \to \gamma )}
主な恒真式として、同一律、排中律、矛盾律、二重否定の法則、巾等律、交換律、結合律、分配律、吸収律、ド・モルガンの法則、対偶律、選言的三段論法、前件肯定式、推移律、移入律、移出律 (英語版)、縮小律、拡大律、構成的両刀論法 (英語版)などがある[4] 。
恒真式である確認
[編集 ]命題論理
[編集 ]ある式が恒真式であるかどうかを確認することは命題論理の基本である。一般に、真理値表をつくって真理値分析を行う作業になる。命題変数がn個存在する場合2n通りのケースを調べればよい。 例えば {\displaystyle \alpha \to (\beta \to \alpha )} であれば次の4通りのケースを調べる。
{\displaystyle \alpha } | {\displaystyle \beta } | {\displaystyle \beta \to \alpha } | {\displaystyle \alpha \to (\beta \to \alpha )} |
---|---|---|---|
T | T | T | T |
T | F | T | T |
F | T | F | T |
F | F | T | T |
次のようにして、代数的な式変形によっても確認できる。
{\displaystyle \alpha \to (\beta \to \alpha )=\neg \alpha \vee (\neg \beta \vee \alpha )=(\alpha \vee \neg \alpha )\vee \neg \beta =\top \vee \neg \beta =\top }
脚注
[編集 ]参考文献
[編集 ]- 清水義夫『記号論理学』東京大学出版会、1984年。
関連項目
[編集 ]外部リンク
[編集 ]この項目は、数理論理学に関連した書きかけの項目 です。この項目を加筆・訂正などしてくださる協力者を求めています。