論理学入門

古典命題論理のタブロー

§2.1 命題論理のタブローの規則

タブローとは、分析したい命題を「根」として、様々な「枝」や「葉」を付け加えることによって得られる図のことで、「木」構造をしている。例えば、A,B,C,…,Hを命題としたとき、Aを分析するタブローは次のようになるかもしれない。

このとき、一番上にあるAが根であり、命題から伸びる線分および線分間を接続する命題B, C, Eが枝、枝の末端にある命題D, F, G, Hが葉となる。

タブローは、次の7種類の規則に従って描かれる。ただし、点線部分は、その部分に任意の長さの枝が現れてもよいということを表している。

全てのタブローの規則は、

  1. 枝分かれしない場合には、規則を適用した命題が真ならその規則を適用して得られる全ての命題も真
  2. 枝分かれする場合には、規則を適用した命題が真ならその規則を適用して得られる二つの命題のどちらか少なくとも一方も真
となるように定められている。タブローのある規則がこれらの条件を満たしているとき、その規則は上から下への真理保存性を満たしているといい、全ての規則が上から下への真理保存性を満たしているとき、タブローは上から下への真理保存性を満たしているという。

例えば、A_1∧A_2が真なら、それに∧規則を適用して得られるA_1とA_2も共に真となり、A_1∨A_2が真なら、それに∨規則を適用して得られるA_1とのA_2のどちらか少なくとも一方も真となる。

また、全てのタブローの規則は、

  1. 枝分かれしない場合には、その規則を適用して得られる全ての命題が真なら規則を適用した命題も真
  2. 枝分かれする場合には、その規則を適用して得られる二つの命題のどちらか少なくとも一方が真なら規則を適用した命題も真
となるように定められている。タブローのある規則がこれらの条件を満たしているとき、その規則は下から上への真理保存性を満たしているといい、全ての規則が下から上への真理保存性を満たしているとき、タブローは下から上への真理保存性を満たしているという。

例えば、A_1とA_2が共に真なら、それらを得るために∧規則を適用したA_1∧A_2も真となり、A_1とA_2のどちらか少なくとも一方が真なら、それらを得るために∨規則を適用したA_1∨A_2も真となる。

∧規則と∨規則以外の規則もこの二つの真理保存性を満たしているということは、次のようにして確かめられる。(§1.5を参照せよ)
  1. まず、ド・モルガンの法則から¬(A_1∧A_2)は¬A_1∨¬A_2と同じ意味をもつので、¬∧規則は∨規則に還元される。また、再びド・モルガンの法則から¬(A_1∨A_2)は¬A_1∧¬A_2と同じ意味をもつので、¬∨規則は∧規則に還元される。よって、両者はそれぞれ二つの真理保存性を満たす。
  2. 次に、実質含意の別表現からA_1→A_2は¬A_1∨A_2と同じ意味をもつので、→規則は∨規則に還元される。また、実質含意の別表現とド・モルガンの法則から¬(A_1→A_2)は¬¬A_1∧¬A_2と同じ意味をもつので、¬→規則は∧規則に還元される。よって、両者はそれぞれ二つの真理保存性を満たす。
  3. 最後に、二重否定則ら¬¬A_1はA_1と同じ意味をもつので、二重否定除去則は、二つの真理保存性を満たす。

§2.2タブローの描き方

命題論理のタブローの枝が完成するとは、その枝に現われるどの命題にもタブローの規則が可能な限り適用されていることを言い、命題論理のタブローが完成するとは、そのタブローの全ての枝が完成することをいう。

では、実際に§2.1で述べた規則を用いてタブローを完成させてみよう。例えば、¬(A∧B)∧¬Cのタブローは、次のような手順で描くことができる。まず、¬(A∧B)∧¬Cに∧規則を適用することで、¬(A∧B)と¬Cを縦に並べる。次に、¬(A∧B)に¬∧規則を適用することで、¬Aと¬Bを横に並べる。

これ以上タブローの規則を適用することはできないので、これでタブローは完成した。この場合、¬Cが¬∧規則の点線部分に相当する。つまり、¬∧規則は¬Cを挟んで遠隔的に適用されている。このように、タブローの規則が遠隔的に適用される場合には、どれが適用された命題で、どれがその結果として得られた命題なのかが分かりにくいので、次の図のように、その二つの命題を曲線で結ぶことにする。

他の例もみてみよう。例えば、¬(A∨B)∧Cのタブローは、次のような手順で描くことができる。まず、¬(A∨B)∧Cに∧規則を適用することで、¬(A∨B)とCを縦に並べる。次に、¬(A∨B)に¬∨規則を適用することで、¬Aと¬Bを縦に並べる。

これ以上タブローの規則を適用することはできないので、これでタブローは完成した。

タブローを描くにあたって、気をつけなければならないことが二つある。

第一に、枝分かれする前の命題に規則を適用するなら、分かれたそれぞれの枝をその規則によって伸ばさなければならない。例えば、¬((A∧B)∨¬C)のタブローは次のようになる。

このように、¬¬Cに対して二重否定除去則を適用することで、¬Aと¬BのそれぞれからCを葉とする枝が伸びる。

第二に、タブローの規則は、どの順番で適用してもよい。例えば、¬((A∧B)∨¬C)のタブローは次のように描くこともできる。

つまり、先に¬(A∧B)に¬∧規則を適用し、その後で¬¬Cに二重否定除去則を適用するか、その順序を逆にするか、ということは自由に決めてよい。ただし、枝分かれしない規則(この場合は、二重否定除去則)を先に適用したほうが楽にタブローを描けるので、そうすることを推奨する。

§2.3 タブローによる反例の発見

§1.6では、真理値表を用いて論証の妥当かどうかを判定する方法を学んだ。しかし、タブローを用いれば、より楽に判定できる。

まずは、論証が妥当ではないということをタブローによって示してみよう。例えば、(A→B) ⊭ Aとなるということを示すためには、(A→B)→Aが恒真ではないということを示せばよい。そのために、(A→B)→Aは偽となる場合があるということを示す。なぜなら、もしも偽となることがないのであれば、それは恒真になるということであり、論証は妥当になってしまうからである。このような、命題が偽となる場合のことをその命題の反例という。(A→B)→Aの反例を見つけるために、それを否定した¬((A→B)→A)のタブローを描いてみよう。

§2.1で確認したように、全てのタブローの規則は下から上への真理保存性を満たすように定められていたので、このタブローから、¬AとBのどちらか少なくとも一方が真ならA→Bは真となるので、¬((A→B)→A)も真、つまり(A→B)→Aは偽となることが分かる。

よって、次の二通りの場合が反例になる。

  1. Aが偽となる。(Bは真でも偽でもよい)
  2. Aが偽かつBが真となる。

反例(i)は、¬Aを葉とする枝、反例(ii)は、Bを葉とする枝に注目することで得られる。しかし、iとiiには重複があるので、重複がないように分けると次のようになる。

  1. AとBは共に偽となる。
  2. Aが偽かつBが真となる。

このことは、真理値表によって確かめることもできる。(A→B)→Aの真理値表は下の表2.1のようになる。この表によれば、(A→B)→Aが偽になるのは、確かにAとBが共に偽となる場合とAが偽かつBが真となる場合の二通りとなっている。

このように、タブローの方法では4個の命題を含む表を描くだけでよかったが、真理値表の方法では4×4=16個の真理値を含む表を書かなければならないので、タブローを用いた方が楽に反例を見つけることができる。しかも、原子命題の種類がさらに増えれば、その労力の差は圧倒的なものとなる。タブローの方法と真理値表の方法でこれほどまでの労力の差が生まれるのは、前者は目的の命題を偽にする場合のみを効率的に調べるのに対して、後者は全ての可能性をしらみ潰しに調べるからである。

他の例もみてみよう。例えば、¬(A∧B) ⊭ ¬Bとなるということを示すためには、¬(A∧B)→¬Bが偽となる場合があるということを示せばよい。そこで、それを否定した¬(¬(A∧B)→¬B)のタブローを描いてみると次のようになる。

先ほどの例と同じように考えてみると、次の二通りの場合が反例になる。

  1. Aが偽かつBが真となる。
  2. Bが真かつ偽となる。(Aは真でも偽でもよい)
しかし、Bはそれが命題である限り真か偽のどちらか一方に定まるので、Bが真かつ偽となるということはない。よって、反例はAが偽かつBが真となる場合のみである。

このように、原子命題Aとその否定¬A(この二つの形をした命題のことをそれぞれリテラルと呼ぶ)が、ある枝に同時に現われるとき、その枝は閉じるといい、×を付けることにする。例えば、¬(¬(A∧B)→¬B)のタブローは次のようになる。

特に、命題論理のタブローの全ての枝が閉じるとき、そのタブローは閉じるという。また、命題論理のタブローの枝が開くとは、その枝が完成している上に閉じていないことをいう。特に、命題論理のタブローのある枝が開くとき、そのタブローは開くという。

§2.4 タブローによる妥当性の証明

次に、論証の妥当性をタブローによって示してみよう。例えば、§1.7によれば、選言的三段論法はA∨B,¬A ⊨ Bという形をしていた。そこで、(A∨B)∧¬A→Bが恒真になるということを示そう。まずは、タブローによって反例を探したときと同じように、(A∨B)∧¬A→Bを否定した¬((A∨B)∧¬A→B)のタブローを描いてみると次のようになる。

すると、このようにタブローは閉じる。全てのタブローの規則は上から下への真理保存性を満たすように定められていたので、このタブローから、¬((A∨B)∧¬A→B)が真ならAを葉とする枝に現われている全ての命題が真となるか、Bを葉とする枝に現われている全ての命題が真になる。よって、前者の場合にはAと¬Aが、後者の場合にはBと¬Bが同時に真になる。しかし、Aが真なら¬Aは偽、¬Aが真ならAは偽、Bが真なら¬Bは偽、¬Bが真ならBは偽となるので、いずれの場合も起こりえない。よって、¬((A∨B)∧¬A→B)が真になることはないので、(A∨B)∧¬A→Bが偽になることはない。ということは、(A∨B)∧¬A→Bは恒真になるので、選言的三段論法は確かに妥当になっている。

このことは、真理値表によって確かめることもできる。(A∨B)∧¬A→Bの真理値表は下の表2.2のようになるので、確かに恒真になっている。

以上の内容を§2.3の内容と組み合わせれば、論証が妥当かどうかをタブローによって判定する方法が得られる。

例えば、「君が勉強するなら、君は試験に合格する。君が酒を飲むなら、君は試験に合格しない。従って、君が酒を飲むなら、君は勉強しない」という論証を分析してみよう。Aを「君は勉強する」、Bを「君は試験に合格する」、Cを「君は酒を飲む」とすると、A→B,C→¬BからC→¬Aへの論証となるので、¬((A→B)∧(C→¬B)→(C→¬A))のタブローを描くと次のようになる。

すると、このようにタブローは閉じるので、A→B,C→¬B ⊨ C→¬Aとなる。

§2.5 命題論理のタブローの健全性と完全性

タブローを用いる方法と真理値表を用いる方法は、論理式の妥当性について、同じ判定結果を出すということをいくつかの具体例についてみてきた。しかし、一般にそれらの結果が一致するということは、まだ示されていない。そのことを示すためには、任意の命題A_0に対して、次の二つを示せばよい。

  1. ¬A_0のタブローが閉じるならA_0は恒真になる。
  2. A_0が恒真なら¬A_0のタブローは閉じる。
(a)をタブローの健全性、(b)をタブローの完全性という。

つまり、健全性と完全性は、タブローという図によって命題が恒真かどうかを正しく判定できるということの保証を与えている。

まずは、タブローの健全性から示そう。健全性を示すために、対偶「A_0が恒真ではないなら¬A_0のタブローは開く」を示す。A_0が恒真ではないならA_0の反例が存在する。つまり、¬A_0は真になり得る。よって、タブローの上から下への真理保存性から、¬A_0が真なら¬A_0のタブローのある完成した枝に現われる全ての命題も真になる。このとき、もしもその枝に原子命題Aとその否定¬Aが同時に現れれば、両者は共に真となるはずだが、Aが真なら¬Aは偽で、¬Aが真ならAは偽になるはずなので、そのようなことは起こりえない。よって、その枝にAと¬Aが同時に現われることはない。つまり、その枝は開く。

次に、タブローの完全性を示す。完全性を示すために、対偶「¬A_0のタブローが開くならA_0は恒真ではない」を示す。¬A_0のタブローが開くなら、ある開いた枝が存在するので、その枝に現われる全てのリテラルを確認し、Aという形のリテラルが現れるならAを真、¬Aという形のリテラルが現れるならAを偽とする。このとき、タブローの下から上への真理保存性から、その開いた枝に現われる全ての命題は真になる。よって、その枝の根にある¬A_0も真になる。つまり、A_0には反例がある。従って、A_0は恒真ではない。

このように、健全性を示す過程では上から下への真理保存性が、完全性を示す過程では下から上への真理保存性が本質的な役割を果たしている。全てのタブローの規則は、この二つの真理保存性を満たすように定められていたので、言い換えれば、実はタブローが健全性と完全性を満たすようにタブローの規則を定めていたということになる。

健全性と完全性は論理に関する性質である。このように、論理の性質を示すために用いた「論理」のことをメタ論理といい、これまで対象にしてきた論理(対象論理)とは区別する。メタ論理は、いわば元々の論理よりも一つ上の段階の論理になっている。

次の章に進む
inserted by FC2 system