|
|
1行目: |
1行目: |
− | '''恒真式'''(こうしんしき、'''トートロジー'''、{{lang-en-short|tautology}}、ギリシャ語の{{lang|el|ταυτο}}「同じ」に由来)とは[[論理学]]の用語で、「a[[論理包含|ならば]] aである(a → a)」「aである、[[論理和|または]]、aで[[論理否定|ない]](a ∨ ¬a)」のように、そこに含まれる[[命題変数]]の[[真理値]]、あるいは[[一階述語論理#論理式の真偽|解釈]]に関わらず常に[[真]]となる論理式である。 | + | '''恒真式'''(こうしんしき、'''トートロジー'''、{{lang-en-short|tautology}}、ギリシャ語の{{lang|el|ταυτο}}「同じ」に由来) |
| | | |
− | ==定義と例==
| + | 空でない (少くとも1つの個体が存在する) 領域で妥当な論理式のこと。言い換えると,所与の領域に属する個体が,可能なあらゆる組合せを行なっても真である論理式のこと。 |
− | ここでは古典命題論理における恒真式の定義を述べる。<math> \mathrm{Val}</math> を命題変数の全体とする。<math> f:\mathrm{Val}\to\{\top,\bot\} </math> なる写像、すなわち命題変数への真理値割り当てを考える。<math>\top</math>は恒真、<math>\bot</math>は矛盾。次のようにして <math>f</math> の始域を論理式の全体 <math>\mathrm{Fml}</math> に拡張する(右辺の <math>\wedge\vee\neg\to</math> は論理記号ではなく <math>\{\top,\bot\}</math> 上の [[真理関数|演算]]である):
| |
− | * <math> f(\alpha \wedge \beta) := f(\alpha) \wedge f(\beta) </math>
| |
− | * <math> f(\alpha \vee \beta) := f(\alpha) \vee f(\beta) </math>
| |
− | * <math> f(\neg \alpha) := \neg f(\alpha) </math>
| |
− | * <math> f(\alpha \to \beta) := f(\alpha) \to f(\beta) </math>
| |
− | このようにして得られる写像 <math>f:\mathrm{Fml}\to \{\top,\bot\}</math> を付値という。任意の付値 <math>f</math> に対して <math>f(\alpha)=\top</math> となるとき、<math>\alpha</math> を恒真式という。
| |
| | | |
− | 古典論理の上で、次の論理式は恒真式である。
| + | {{テンプレート:20180815sk}} |
− | | |
− | * <math> \neg(\alpha\wedge\neg\alpha) </math>
| |
− | * <math> \alpha\vee\neg\alpha</math>
| |
− | * <math> (\alpha\to \beta)\Leftrightarrow(\neg \beta\to \neg \alpha)</math>
| |
− | * <math> \neg\neg\alpha\Leftrightarrow\alpha </math>
| |
− | * <math> \neg(\alpha\wedge \beta)\Leftrightarrow(\neg \alpha\vee\neg \beta)</math>
| |
− | * <math> ((\alpha\to \beta)\wedge(\beta\to \gamma))\to(\alpha\to \gamma)</math>
| |
− | | |
− | ==恒真式である確認==
| |
− | ある式が恒真式であるかどうかを確認することは命題論理の基本である。命題変数がn個存在する場合2<sup>n</sup>通りのケースを調べればよい。
| |
− | 例えば <math>\alpha \to (\beta \to \alpha)</math> であれば4通りのケースを調べれば良い。
| |
− | {| class="wikitable" style="text-align: center;" | |
− | |-
| |
− | |<math>\alpha</math>
| |
− | |<math>\beta</math>
| |
− | |<math>\beta\to\alpha</math>
| |
− | |<math>\alpha \to (\beta \to \alpha)</math>
| |
− | |-
| |
− | |T
| |
− | |T
| |
− | |T
| |
− | |T
| |
− | |-
| |
− | |T
| |
− | |F
| |
− | |T
| |
− | |T
| |
− | |-
| |
− | |F
| |
− | |T
| |
− | |F
| |
− | |T
| |
− | |-
| |
− | |F
| |
− | |F
| |
− | |T
| |
− | |T
| |
− | |}
| |
− | | |
− | 次のようにして、代数的な式変形によっても確認できる。
| |
− | | |
− | <math> \alpha\to(\beta\to\alpha)
| |
− | = \neg\alpha\vee(\neg\beta\vee\alpha)
| |
− | = (\alpha\vee\neg\alpha)\vee\neg\beta
| |
− | = \top \vee \neg\beta
| |
− | = \top </math>
| |
− | | |
− | ==関連項目==
| |
− | *[[トートロジー]]([[修辞法]])
| |
− | | |
− | {{論理演算}}
| |
− | {{math-stub}}
| |
| | | |
| {{DEFAULTSORT:こうしんしき}} | | {{DEFAULTSORT:こうしんしき}} |