出典: フリー百科事典『ウィキペディア(Wikipedia)』
恒真式(こうしんしき、tautology)とは論理学の用語で、「aならば aである(a → a)」「aである、または、aでない(a ∨ ¬a)」のように、そこに含まれる命題変数の真理値にかかわらず常に真となる論理式である。
トートロジーとも呼ばれる。
定義と例
式に含まれる命題変数に関係なく、常に真となる命題論理式は全て恒真式である。すなわち恒真式は無限個存在する。
有名な例として以下のようなものがある。
排中律:
対偶:
背理法:
ド・モルガンの法則:
三段論法:
恒真式である確認
ある式が恒真式であるかどうかを確認することは命題論理の基本である。命題変数がn個存在する場合2n通りのケースを調べればよい。
例えば背理法であれば、
であり、命題変数は2個である。よって4通りのケースを調べれば良い。
A
|
B
|
|
|
|
|
T
|
T
|
T
|
T
|
T
|
T
|
T
|
F
|
T
|
T
|
T
|
T
|
F
|
T
|
T
|
F
|
F
|
T
|
F
|
F
|
F
|
T
|
F
|
T
|
ブール代数では、上式が恒真式であることを公理及び定理から導くことが可能である。
⇒の定義より、
と変形でき、対合律を適用すると、
となる。左分配律より、
補元律より、
となり、は和の単位元であるから、
とおける。再度補元律を適用すれば、
となる。これは上式が恒真式であることを示す。
関連項目