タブロー法
同じことは真理値表を書いても得られるが、それよりも工数も考えることも少なくできる 規則に従ってタブローという名のツリーを作っていく
タブロー法のタブロー規則
https://gyazo.com/08e63af3574a9c3f70467a7ccc716fc7
用語
根
ツリーの一番上の今考えている論理式
葉
ツリーの下側。リテラルになっている。
経路
根から葉までの一本筋。葉の数だけある。
手順
タブローを書く際のコツ 『論理学をつくる』.icon p.99~
複数の展開対象がある際に、できるだけ枝分かれしない方を先に展開するといい
途中で$ \botになるものがあれば、それ以上展開する必要はない
どうせ$ \botなので
これだけ読んでも意味がわからないと思うので、↑の本を読むと良いmrsekut.icon
タブローを用いた論理式の妥当性 『論理学をつくる』.icon p.101
「$ A_1,\cdots,A_nから結論$ Cを導くという論証が妥当か」という問題をタブローを使って解く
$ A_1,\cdots,A_nと$ \lnot Cを縦に並べたタブローを解いて、全ての経路が$ \botになれば、妥当
$ \lnot Cを使うのと、$ \botにさせるのがミソやねmrsekut.icon
例
論理式$ (p\lor q)\land(q\land \lnot r)が真になるときの$ p,q,rの組み合わせを知りたい!
真理値表を使う場合
たいへん!!!!
table:真理値表
p q r p∨q q∧¬r (p∨q)∧(q∧¬r)
1 1 1 1 0 0
1 1 0 1 1 1 ←これ
1 0 1 1 0 0
1 0 0 1 0 0
0 1 1 1 0 0
0 1 0 1 1 1 ←これ
0 0 1 0 0 0
0 0 0 0 0 0
↑2つの「これ」を見つけるために全パターンを洗い出さないといけない
タブロー法を使う場合
規則を上からa,b,aを使って以下のようなタブローを作る
https://gyazo.com/355809a357678c79c3334abecbc58d95
左側の丸から$ (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)
これが求めたかったもの。規則を参照して機械的に操作するだけで真理値表を埋めるよりもずっと速く求まる
ラベル付きのタブロー法の規則
https://gyazo.com/71b2480ca98d9f91342ceec32050abbd
上と同じだがラベル付き版。
基本参照しなくていい
タブロー法に慣れていない人が導入に使うようなもの
参考
コツとか書いてる