トートロジー

from 命題論理

恒真式

命題変数にどのような真理値を入れてもTになるような論理式のこと

表記

$ \vDash\varphiとか

$ \topとか

具体例

命題定数のT

$ P\land(P\rightarrow Q)\rightarrow Q

table:真理値表

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\equiv Bがトートロジーであるとき、$ Aと$ Bは論理的に同値であると言い、$ A\sim Bとかく

トートロジー的に同値

表記

$ A\sim B

もしくはスクボではかけないが$ A\vDash \Dashv Bと書く

例

$ A:\lnot p \land q,$ B: \lnot(p\land \lnot q) のとき

table: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のタブローを作る

https://gyazo.com/33e9501b1a5a7a1c85a08675f1a627c4

経路は2つあり両方ともに$ p,\lnot pが出てきており閉じているのがわかる

よって、$ \phiはトートロジー