« ローレンツ変換の導出 | トップページ | mixi(ミクシィ)に入会しました。 »

2007年10月15日 (月)

形式論理学(3)

 真理の木による論証のテストに関する考察の続きです。今日は,真理の木による方法が形式論理学の方法として信頼できるものであることを示します。

まあ,推論規則が信頼に足りるものであることは既にわかっているので,それに従って,トートロジー変形,つまり論理的に同値な変形を行った結果も,当然信頼できるはずですから,結局は問題としている木において開いた経路(分枝)があれば論証は非妥当であり,全ての経路が閉じていれば論証は妥当である,ということさえ証明されればいいわけです。

 出発点となるところの,妥当性を検証(テスト)すべき論証に対応する文のリストが無限に長いものでなければ,そのテストはいつかは終了します。これを決定可能性と言います。

テストが決定可能であれば,それはリストの整合性,つまりの妥当性について黒白の判定をつけることができる方法として信頼できるための1つの要件を満たしています。

 

しかし,このようにして決着がついたその結果が正しいのかどうかという問題が残ります。

 テストの結果,文の集合が矛盾であるという判定が出たならその判定が信頼できるとき,このテストは健全であると言われます。

 

 つまり,文の集合が矛盾ならば常に論証は妥当であると判定されること,そして現に整合的な文集合を矛盾と判定することは決してないということをテストの健全性と呼びます。

 これは同じ言葉を使ってはいますが以前に定義した論証の健全性とは別物です。

 テストの結果,文の集合が整合的という判定が出たならこれを信頼できること,これを矛盾と妥当性に対するテストの完全性と言います。

 

 すなわち,現に矛盾した文集合を整合的と判定をすることは決してないことを,テストは完全であるというわけです。

 真理の木を用いたテストは,上に定義した意味で健全かつ完全です。そして,また決定可能性をも満たしています。

 

 真理の木によるテストの決定可能性とは,最初に与えられたリストが有限であれば,テストが有限個のステップの後に終了することを意味します。

 まず,真理の木が決定可能性を満たすことを証明します。

(証明)それぞれの木は,完成したものも成長中のものも含めてある決まった認識番号を持つとします。ここではそれを無限数列として定義します。つまり,認識番号とは言うものの単なる1つの数字ではなくて,無限個の数字の羅列なわけです。

 まず,初項を,その木に現われている長さ1のチェック済みでない文の個数とし,第2項を長さ2のチェック済みでない文の個数,...,以下同様に際限なく続くものとします。

 

 しかし,もし木が有限個の行しか持っていないなら,この数列はある項から先には 0 がずっと続くだけになるはずです。

 木のどれかの行をチェックして新しい行を書き足すごとに,それで得られた新しい木の認識番号は,ある意味で"小さく"なっていきます。

 

 つまり,ある行をチェックしたとき,そのチェックした行は不要になってチェック済みの印を付けられ,代わりに推論規則に従って得られた有限の行が追加されます。

 

 しかし,推論規則に従えば,それぞれの追加される行は必ず今チェックした行よりも短かいので,結局,新しい木で行の数は増えても,認識番号を構成する数列で以前の木と数が異なる箇所のうち最も右にある数は必ず小さくなっています。これを"小さく"なると称するわけです。

 そこで,次々と木の行をチェックするにつれて認識番号を構成する数列の 0 でない項における値は単調に減少していくわけですが,チェック前の元の木では,認識番号を構成する数列の項の値は全て有限であったわけですから,こうしたステップは必ず有限回で終わらなければならないことになります。(証明終わり)

 次に,先に述べた健全性ですが,これは最初に与えられた文のリストが整合的ならば,そのリストに推論規則を適用して得ることのできるどんな木にも必ず開いた経路がある,ということを意味します。

 

 これらの開いた経路の存在する木は完成したものに限る必要はなく,例えば最初に与えられた文のリストそのものを木とみなしたものに対しても適用されます。

 では,真理の木の健全性を証明します。

(証明)まず,ある場合Cには最初に与えられたリストに含まれる全ての文が真になるものとします。すなわち,与えられたリストは整合的であるとします。

 そうすると,このリスト自体は開いています。つまり,このリスト自体がある文○の肯定と否定:すなわち,○と¬○を同時に含んではいないはずです。

 

 なぜなら,○と¬○を同時に含んでいるなら,一方は他方の真理値を逆転させるものなので,場合Cにおいて偽になってしまい,場合Cが全ての文が真になる場合でなくなってしまうからです。

 次に,場合Cにおいて,ある経路に含まれる行が全て真になるとします。そしてその経路の中のどれかの行に推論規則を当てはめて,経路の先に新しい行を書き足して経路を延長していくとします。

 

 我々の与えた推論規則そのものについては,通常の論理学として既に健全性は保証されているので,こうして延長して作られた経路のうちには,新しく書き足された全ての行が場合Cで真になるような経路が少なくとも1つ存在します。

 したがって,木が最終的に成長を終えたときには,場合Cにそこに現われる全ての行が真になるような経路が少なくとも1つは存在することになります。

 

 この経路は最初に与えられたリストと同様に,同じ理由で開いた経路です。つまり,どこまで行っても閉じて終わるということがありません。(証明終わり)

 最後に,完全性ですが,これは完成した木の中に1つでも開いた経路があれば,最初に与えられた文のリストは整合的である,ということを意味します。

 以下,真理の木の完全性の証明です。

(証明)完成した木が開いた経路Pを含んでいるとします。

 

 このとき最初に与えられた文のリストが全て真になるような場合が1つでも存在することを示せばいいことになります。

経路Pに文を示す単独の文字,例えばAとか,Bなどが1つの行として現われているときには,その文は全て場合Dで真になり,1つの行としては現われず複合的な文の一部としてだけ経路Pに現われる文字があれば,それが表わす文は全て場合Dで偽になる,ようなものとして,ある場合Dを想定することにします。

特に,¬Aが1つの行として経路Pに現われているとすると,単独の文字Aで表わされる文は場合Dでは偽になります。

 

なぜなら,Pは開いた経路なので¬AがPに現われている以上,Aが1つの行としてPに現われることはないからです。

最初に与えられた文のリストが整合的であることを示すために,経路Pに含まれる全ての行が,場合Dにおいては真になることを示すことにします。

 

このことを示せば最初に与えられた文のリストが真になる場合があることになります。

,木が完成しているものであると考えています。

 

完成した木なので,経路Pに含まれるある行に何らかの推論規則が適用可能なときに規則を適用した結果のリストは既にPの中に含まれているはずです。

 

こうした推論規則によって,ある長い行から幾つかの短かい行が得られたとします。

 

推論規則そのものは既に完全であることが保証されているので,そうした短かい行が全て場合Dにおいて真であるとわかっているなら,元の長い行もDにおいて真です。

かくして場合Dにおける真理に関しては,既にDにおいて真であるとわかっている行から,規則に従ってより長い行へとさかのぼっていくことができます。

 

こうしたプロセスは有限回のステップで終了します。

 

そして長い行ではなくて,元々経路Pに現われる単独の文字だけの行はDの定義によって既にDにおいて真であるとわかっています。

このようにして経路Pに現われる行は全て場合Dにおいて真になります。言うまでもないことですが任意の経路は出発点から連続していますから,経路Pも当然最初に与えられた文のリストを含んでいます。

 

それ故,場合Dは最初に与えられた文のリストが全て真である場合の1つになりますから,結局,Pが開いているならばリストが整合的なることが示されました。(証明終わり)

今日はここまでにします。

 参考文献:Richard Jeffrey著(戸田山和久 訳)「形式論理学」(その展望と限界)(産業図書)

 

http://folomy.jp/heart/「folomy 物理フォーラム」サブマネージャーです。

人気blogランキングへ ← クリックして投票してください。(1クリック=1投票です。1人1日1投票しかできません。)

http://homepage2.nifty.com/toshis-kaiga-auction/健康商品の店 「TRS健康ランド」

にほんブログ村 科学ブログへクリックして投票してください。(ブログ村科学ブログランキング)

にほんブログ村 トラコミュ 物理学へ
    物理学

|

« ローレンツ変換の導出 | トップページ | mixi(ミクシィ)に入会しました。 »

302. 論理学・数学基礎論」カテゴリの記事

コメント

コメントを書く



(ウェブ上には掲載しません)




トラックバック


この記事へのトラックバック一覧です: 形式論理学(3):

» ミラーマン植草一秀被告に重い懲役4月の実刑。 [ミラーマンの目は充血「懲役4月に処す。」]
「主文、被告人を懲役4月に処す」−。東京都迷惑防止条例違反の罪に問われた元早稲... [続きを読む]

受信: 2007年10月16日 (火) 17時31分

« ローレンツ変換の導出 | トップページ | mixi(ミクシィ)に入会しました。 »