トートロジー
from 命題論理
恒真式
命題変数にどのような真理値を入れてもTになるような論理式のこと
表記
\vDash\varphiとか
\topとか
具体例
命題定数のT
P\land(P\rightarrow Q)\rightarrow Q
真理値表
| P | Q | P→Q | P∧(P→Q) | P∧(P→Q)→Q |
| 1 | 1 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 | 1 |
| 0 | 1 | 1 | 0 | 1 |
| 0 | 0 | 1 | 0 | 1 |
contradiction
矛盾式ともいう
トートロジーの逆
常に偽になる
\botで表す
事実式
contingency
整合式ともいう
0にも1にもなる
トートロジー的に同値
表記
A\sim B
もしくはスクボではかけないがA\vDash \Dashv Bと書く
例
A:\lnot p \land q,B: \lnot(p\land \lnot q) のとき
e
| p | q | A | B |
| T | T | F | F |
| T | F | F | F |
| F | T | T | T |
| F | F | F | F |
AとBが一致する！
トートロジー的に含意
例
A:p\land q, B:p
トートロジーかどうかをタブロー法を用いて調べる
\phiが恒真\Rightarrow\lnot \phiが恒真でない\Rightarrow\lnot\phiのタブローの経路が閉じている
手順
考える論理式の否定を考え、その経路が全て閉じた経路になっていれば、この論理式はトートロジーである
例
\phi=((p\rightarrow q)\rightarrow p \rightarrow p)を調べる
なので\lnot\phiのタブローを作る
経路は2つあり両方ともにp,\lnot pが出てきており閉じているのがわかる
よって、\phiはトートロジー