ある論理式がトートロジーかどうかを判定する決定的手続き

同じことは真理値表を書いても得られるが、それよりも工数も考えることも少なくできる

規則に従ってタブローという名のツリーを作っていく

タブロー法のタブロー規則

用語

根

ツリーの一番上の今考えている論理式

葉

ツリーの下側。リテラルになっている。

経路

根から葉までの一本筋。葉の数だけある。

手順

哲学演習「論理学入門」第8回に例が載っている

タブローを書く際のコツ p.99~

複数の展開対象がある際に、できるだけ枝分かれしない方を先に展開するといい

途中で\botになるものがあれば、それ以上展開する必要はない

どうせ\botなので

これだけ読んでも意味がわからないと思うので、↑の本を読むと良い

タブローを用いた論理式の妥当性 p.101

「A_1,\cdots,A_nから結論Cを導くという論証が妥当か」という問題をタブローを使って解く

A_1,\cdots,A_nと\lnot Cを縦に並べたタブローを解いて、全ての経路が\botになれば、妥当

\lnot Cを使うのと、\botにさせるのがミソやね

例

論理式(p\lor q)\land(q\land \lnot r)が真になるときのp,q,rの組み合わせを知りたい！

真理値表を使う場合

たいへん！！！！

↑2つの「これ」を見つけるために全パターンを洗い出さないといけない

タブロー法を使う場合

規則を上から a , b , a を使って以下のようなタブローを作る

左側の丸から(p,q,r)=(1,1,0)のときと、

右側の丸から(q,r)=(1,0)のとき、

つまり、pはどっちでもいい

上の論理式が真になることがわかる

これをよく考えると右側の丸は左側を包含していることがわかる(p,q,r)=(\ast,1,0)なら良い

具体的に書くと(p,q,r)=(1,1,0),(0,1,0)

これが求めたかったもの。規則を参照して機械的に操作するだけで真理値表を埋めるよりもずっと速く求まる

ラベル付きのタブロー法の規則

上と同じだがラベル付き版。

基本参照しなくていい

タブロー法に慣れていない人が導入に使うようなもの

参考

『論理学をつくる』 4章

コツとか書いてる