302. 論理学・数学基礎論

2008年9月22日 (月)

形式論理学(5)

 ブログ記事の中には私自身の気紛れのために途中で他に関心が移り,数回の連載を意図して書き始めたにも関わらず,結局最後まで完遂することなくほったらかしになった記事もいくつかあります。

 

 ときどきブログ全体を回顧して見ることがあるのですが,そうした途中やめになっている記事についても,日頃からいつかはそれらの続きを書きたいと思っています。

というわけで今回は2007年10月4日から10月18日にわたり4回だけ連載して中途になっている記事「形式論理学(1)」,形式論理学(2) 」,「形式論理学(3) 」,「形式論理学(4)の続きを書こうと思います。

シリーズ最後の記事「形式論理学(4)は新しい"一般性を持った論理の規則=形成規則"を定める次の文章で終わっています。

(過去記事の再掲部分)↓

  

かくして,論理形式に適した文の新しい形成規則としては,出発点となる文の範囲(0)をやや拡張し,与えられている文から新しい文を作るための方法を定める規則:1~5 に,量化子∀,∃を扱う規則;6を追加したもので与えられることになります。

 

0:出発点.任意のn項述語の後ろにn個の名称を続けたものは文である。(n=2の場合の例:Tab,Tbbは文です。しかし,Txbは文ではありません。xは変項であって名称(名前)ではないからです。)

 

※新しい文を生み出す6つの操作 

 

 1:否定.任意の文の先頭に ¬ をつける。

 2:連言:2つ以上の任意の文の列において隣り合う文の間に∧を書き,そうしてできたものを括弧でくくる。

 3:選言:2つ以上の任意の文の列おいて隣り合う文の間に∨を書き,そうしてできたものを括弧でくくる。

 4:条件. 任意の2つの文の間に⇒を書き,そうしてできたものを括弧でくくる。

 5:双条件. 任意の2つの文の間に ⇔ を書き,そうしてできたものを括弧でくくる。

 6:量化.何らかの名称rが現われているが変項が現われない全ての文,..r..において,rが現われる全ての箇所をxで置き換え,先頭に ∀x,または ∃xを付ける。

 後にさらに改定した規則を与えるまでの間は,規則:0~6 から得られるもの以外に文であるようなものは存在しないとします。

 

(再掲終わり)

 

 上述の形成規則を形成の木と呼びます。

  

これを用いる1例として,文:"∀x(Txb⇒Tab)"を作る場合なら,まず,出発点の規則(0)によりTcbとTabを作り,次に規則(4)によって(Tcb⇒Tab)とします。

 

そして,規則(6)によって,∀x(Txb⇒Tab)を作るわけです。

例えば "あらゆるxについて(xはモリアーティを捕まえることができる⇒ホームズはモリアーティを捕まえることができる);¬(ホームズはモリアーティを捕まえることができる):それ故,¬(モリアーティを捕まえることができるようなxが存在する)"という命題を考えます。

 

これは,ホームズをa,モリアーティをb,"捕まえることができる"をTという記号で表現すると"1.∀x(Txb⇒Tab)(前提);2.¬Tab(前提);⇒ 3.¬∃xTxb(結論)"という論理式になります。

 

そして,この命題の妥当性を示すことは3つの文の集合:"1.∀x(Txb⇒Tab);2.¬Tab;3.¬¬∃xTxb"の矛盾を示すことと同等になります。

そして既に前の記事で述べたことですが,これを示すには次のようにします。

まず,"1.∀x(Txb⇒Tab);2.¬Tab;3. ¬¬∃xTxb"なる3つの文の集合の中から,"3.¬¬∃xTxb"にチェック(✓)を付け,その代わりに"4.∃xTxb"なる行を追加します。

さらに,"1.∀x(Txb⇒Tab)"なる文の前提は∀xなので,これはxが何であろうと括弧の中の命題は成り立つことを意味しますから," 5.Tbb⇒Tab"が成立します。

 

しかし,命題1.からは,なおも5.とは別の独立な情報が獲得できる可能性があるので,まだ1.にはチェック印✓をつけません。

次に,"5.Tbb⇒Tab"は"¬Tbb∨Tab"と同値ですから,ここから"6a.¬Tbb"と"6b.Tab"の2つの文に分岐します。

 

この段階で,"6b.Tab"の方の分枝は,前に"2.¬Tab"があり,これと矛盾するので閉じますが,"6a.¬Tbb"につながる分枝はなお開いています。

一方,"4.∃xTxb"は,Txbを成立させるあるxが存在することを意味するので,この"bを捕まえることができる(Tb)少なくとも1人は存在する(∃x)誰か=x"の名称をcとして,"7.Tcb"と書くことができます。

 

そして,この 4.は1度しか使えないので,"7.Tcb"を作るのに使用したため,4.には使用済みのチェック印✓をつけます。

さらに,もう1度"1.∀x(Txb⇒Tab)"を用いて,"8.Tcb⇒Tab",すなわち"8.¬Tcb∨Tab"が成立します。

 

この8.は"9a.¬Tcb","9b.Tab"と展開できます。

 

そして,左の分岐"9a.¬Tcb"は前の文"7.Tcb"と矛盾するので閉じます。

 

一方,右側の分岐"9b.Tab"は,再び"2.¬Tab"との矛盾によって閉じます。

上のように,文を∀xで表現する規則を普遍例化(UI)といいます。

 

(UIはuniversal instantiationの略)

 

"∀x..x.."というような形の行を持つ開いた経路がある場合,その行にはチェック済みの印✓を付けず,その経路に現われる名前nの全てについて,上のxにnを代入した,"..n.."をその経路の下端に書き足します。

 

しかし,もしもその経路にどんな名前も現われていないなら,適当な名前nを取って"..n.."を書き足します。

また,文を∃xで表現する規則を存在例化(EI)といいます。

 

(EIはexistential instantiationの略)

 

"∃x..x.."というような形の行のうち,まだチェックされていないものがあれば,まずそれにチェック済みの印✓を付けます。

 

そして,その行を含む全ての開いた経路を見て,それが上のxにnを代入した,"..n.."という形の行を含んでいればそのままにしておき,一方,そうした行がないなら,まだその経路に現われていない適当な名前nを選んで経路の下端にxにnを代入した"..n.."を書き足します。

ただし,この2つの規則は括弧を省略せず,形成規則通りに書いたときに,文字通り先頭に量化子が来ている行だけに適用できます。

 

そこで,例えば上のUIの規則を∀x(Mx⇒H)には適用できますが,∀xMx⇒Hには適用できません。

 

後者は(∀xMx⇒H)の省略形でこれの先頭は括弧であって量化子∀ではないからです。

また,こうした量化子を含む文の否定は単に¬∀xを∃x¬に,¬∃xを∀x¬に,と書き換えればよくて,これによって行を簡単に処理できることもわかります。

 

実際,ド・モルガンの規則などの説明と同じく,論理的に考えると"¬∀x○"は空でない論理領域の中での全てのものが○という属性を持つことの否定ですが,これはその論理領域の中に属性○を持たないものがあるということ:"∃x¬○"と同値です。

 

そして,"¬∃x○"は論理領域の中に属性○を持つものがあることの否定ですが,これはその論理領域の中の全てのものが属性○を持たないということ:"∀x¬○"と同値ですね。

そこで,¬∀xを∃x¬に,∀xを¬∃x¬に,¬∃xを∀x¬に,∃xを¬∀x¬に書き換えてよい,という簡単な規則が得られます。

例として,"∀xMx⇒∃xMx"なる文の妥当性の論証を考える場合なら,これは"∀xMx,¬∃xMx"の矛盾を示すことと同値です。

 

これの真理の木は,"1.∀xMx","2.✓¬∃xMx"3.∀x¬Mx","4.¬Ma"(3より),"5.Ma"(1より)です。

 

したがって,4,5から木は閉じているので,この枝に×印をつけて最初の命題は妥当であることがわかります。

もう1つ例を出します。

 

それは命題:"(∃xMx⇒H)⇒∀x(Mx⇒H)"です。

 

この命題の意味は,例えばMが母親であること,Hが大人であることを意味する場合であれば,"ある人の母親であるなら彼女は大人である。"ということが正しいなら"xの母親なら彼女は大人である,ということがどんなxについても成り立つ。"ということを表わします。

 

これの妥当性の論証は"∃xMx⇒H;¬∀x(Mx⇒H)"の矛盾を示すことと同値です。

これの真理の木は,"1.✓∃xMx⇒H","2.✓¬∀x(Mx⇒H)","3.✓∃x¬(Mx⇒H)"(2より),"4.✓¬(Ma⇒H)"(3より),"5.✓Ma∧¬H"(4より),"6.Ma"(5より),"7.¬H"(5より),"8.✓ ¬(¬∃xMx∧¬H)"(1より),"9.✓H∨∃xMx"(8より),"10a.H"(9より) ←この枝は×です(7より)。

 

また,"10b.✓∃xMx"(9より),"11.∀x¬Mx"(10bより),"12.¬Ma"(11より) ←この枝は×です(6より)。

 

以上からこの木は閉じていることが示されました。

この論題について述べるのは久しぶりなので,思い出すという意味で,今日のところはこれで終わります。

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

 

緊急告知!! Attention!! [広告宣伝]です。

http://www.rakuten.co.jp/trs-kenko-land/  健康商品の店「TRS健康ランド」- SCS(食品洗浄剤),黒ウコン,酒の帝王,鵜鶏王などの専売店  ←この店は私TOSHIが店長をしています。(楽天ショップです。TRSのTはTOSHIのTです。)

 「TRS健康ランド」では2008年1月10日よりお徳用SCS500mlを新発売!!当店の専売です。

 そこのお酒のみの方,いろいろと飲食の機会の増えたあなた,悪酔いを防止すると言われているウコンがいいですよ!! そして特に今回提供する沖縄原産の純粋な黒ウコンは当店が専売の新製品ですが古くから沖縄地方ではいわゆる男性の力に効果があると言われています。

 おやおや,そこの静電気バチバチの人、いいものありますよ。。。

 それから農薬を落とした後の皮がピカピカに光っているリンゴなど商品として販売する際の見栄えをよくするなどのために化学処理をした食品を安全に洗浄する新商品の洗浄液SCSはいかがですか。。。

http://www.mediator.co.jp/category/pages.php?id=115「中古パソコン!メディエーター巣鴨店」

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

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

にほんブログ村 科学ブログへ にほんブログ村 科学ブログ 物理学へクリックして投票してください。(ブログ村科学ブログランキング投票です。1クリック=1投票です。1人1日1投票しかできません。クリックするとブログ村の人気ランキング一覧のホ-ムページームに跳びます。)icon

ブックオフオンライン オンライン書店 boople.com(ブープル)

| | コメント (0) | トラックバック (0)

2007年10月18日 (木)

形式論理学(4)

 これまでは文の分析は,文そのものを最小単位とするところで終わっていました。

 

 今日は,より複雑な論証の分析に耐えられるように,論証を構成する文とその規則を一般化します。

 "ワトソン(Dr.Watson)がモリアーテイ(Pf.Moriarty)を捕まえることができるならホームズ(S.Holmes)にもできる"は,W⇒H;"ホームズはモリアーテイを捕らえることができない"は,¬H;そこで,"ワトソンはモリアーテイを捕まえることができない"は,¬W;

 

 のような論証の前提や結論は,単に分析の最小単位となる原子文:W,Hを,⇒ や ¬ といった真理関数的結合子で結合した,いわば"分子"になっています。

上の論証の前提と結論の論理構造は,分析の最小単位となる原子文を示す文字と,原子から分子を作るための括弧,否定記号,条件法を表わす矢印を使って表現されています。

こうした論証の妥当性は,前提と結論が持つ分子構造による妥当性であって,原子文の内部構造はとりあえず無視されていました。

ところが,一般に我々が行う論証の多くは,こうした単純なやり方での分析では手に負えない有機的で複雑な構造を持っています。

"誰であれ,モリアーティを捕まえることができるとしたら,それはホームズだ。";"ホームズはモリアーティをを捕まえることができない。"それ故,"誰もモリアーテイを捕まえることができない。"

 

という論証を与えたとき,これは今までのような単純な構造になっていないことがわかります。

この論証が妥当であるということを示すためには,分析を原子よりもさらに下のレヴェルまで行なう必要があります。

 

つまり,原子文を,それ自体が文でも真理関数的結合子でもない構成要素にまで分解して分析しなければなりません。

そこで我々は単純な真理関数的論理に別れを告げることになります。

 

手始めに前提と結論を既に自由に扱えるようになった論理的表記法と日本語を混ぜた形に直して論理的構造を見やすくしてみます。

"あらゆるxについて(xはモリアーティを捕まえることができる⇒ホームズはモリアーティを捕まえることができる)";"¬(ホームズはモリアーティを捕まえることができる)":それ故,"¬(モリアーティを捕まえることができるようなxが存在する) "

こうすると,第1の前提と結論に出てくる,"あらゆるxについて~"とか,"~のようなxが存在する"に対応する論理的表記法が必要になります。そこで,これらを次のように表わすことにします。

すなわち,"あらゆるxについて~"を,∀x(普遍量化子,または全称量化子)で,そして,"~のようなxが存在する"を,∃x(存在量化子)で表現します。

そこで小文字a,bで,それぞれ,ホームズとモリアティという人称を表わし,大文字のTを"~は~を捕まえることができる"という関係を表わす句の代わりに用いれば,上に例示した論証は全て論理的表記法で表現することができます。

 

こうした表記法ではTabなどが原子文になります。この例では,∀x(Txb⇒Tab);¬Tab;故に¬∃xTxbと表現されます。

こうした∀xや∃xのような論理的表記におけるxを,変項と呼ぶことにします。そして,それぞれの論証で変項が表わすことのできるものを集めた集合を,その変項の論議領域といいます。

そして,この論証が妥当であることを示すためには,変項xがどのような範囲のものを表わしていようと,つまりxの論議領域が何から成っていようと,そしてその何かがa,bという名称で指定されていようと,さらにTなる関係を如何なるものと解釈しようと,論証の前提の全てと結論の否定が同時に真になることは決して有り得ないことを示せばいいわけです。

こうした論証の妥当性もテストできるように真理の木の方法を拡張することを試みます。

 

まず,論証の前提と結論の否定とをリストアップします。

1.∀x(Txb⇒Tab);2.¬Tab;3.¬¬∃xTxbと書きます。

 

まず,3.¬¬∃xTxbをチェックして,4.∃xTxbを得ます。

ところで,1.∀x(Txb⇒Tab)において,(Txb⇒Tab)の前提は∀xなので,xが何であっても括弧の中の命題は成り立つはずです。

 

そこでx=bとして,5.Tbb⇒Tabが成立します。

 

しかし,命題 1.からは,なお,5.とは独立な別の情報をも引き出せる余地があるので,この時点で 1.にチェックをつけることはしません。

 

この新しい規則を普遍例化(UI)と呼びます。

そして,5.Tbb⇒Tabは,¬Tbb∨Tabと論理的に同値ですから,このステップで2つに分岐して,6.¬Tbb,Tabの左右両方の2つの経路になります。

 

この段階で,6.の右側のTabの分枝は,2.¬Tab があるので閉じています。

 

しかし, 6.の左側の¬Tbbにつながる分枝は,なお開いています。

一方,4.∃xTxbはTxbを成立させる,ある人物xが存在することを意味するので,この少なくとも1人の存在する誰かの名称をcと置いて, 7.Tcbと書くことができます。

 

この4.は1度しか使えないので,4.にはチェック印をつけます。この新しい規則は存在例化(EI)と呼びます。

さらに,1.∀x(Txb⇒Tab)をもう1度用いて,x=cとおいて,8.Tcb⇒Tab,あるいは 8.¬Tcb∨Tabと書くことができますから,9.¬Tcb,Tabと展開できます。

 

これで9.の左側の分枝:¬Tcbは 7.Tcb によって閉じます。

 

また,9.の右の分枝:Tabも再び 2.¬Tab によって閉じます。

以上で木のあらゆる経路=分枝は全て閉じて,全体として閉じた木になるため,例として出された論証の妥当性は真理の木によって証明されました。

 

したがって,真理の木による妥当性検証の方法は量化子と変項を含んだ一般的な論証に対しても拡張適用が可能なことがわかりました。

内部構造を有する原子文は一般にMa,Tab,Rabc,..などの形をとります。

 

そこで我々は在庫として,まず個体の名称,原子文を表わす文字(文記号),そして個体の持つ属性を表わす記号:2つの個体,3つの個体,あるいはそれ以上の数の個体の間に成り立つ関係を表わす記号を持つ必要があります。

 

特定の論証を分析するには,こうした記号は有限個あれば足ります。

しかし,我々が出会うあらゆる論証を分析するには一体どれだけの記号が必要であるかわかりません。

 

とにかく今のところは,アルファベットの小文字を名称に使い,これを大文字の後に続けて書くことで文を作ることにします。

 

この大文字の方は述語と呼びます。

0-項述語とは原子文を表わす文字・文記号の別の言い方です。

 

1項述語とは,変項xの値に成れるもの,つまり個体の属性を表わしています。

 

こうして例えばMなる属性を文にするためには,1つの個体を示す名称=小文字が必要でMaと書けば文になります。

同様に2項述語:T,3項述語:Rはそれぞれ2つ,3つの個体の間の関係を表わします。すなわち,Tab,Rabcです。

 

同様に,一般に任意の非負整数nについてn項述語が定義できます。

かくして,論理形式に適した文の新しい形成規則としては,出発点となる文の範囲(0)をやや拡張し,与えられている文から新しい文を作るための方法を定める規則:1~5 に,量化子∀,∃を扱う規則;6を追加したもので与えられることになります。

 

0:出発点.任意のn項述語の後ろにn個の名称を続けたものは文である。(n=2の場合の例:Tab,Tbbは文です。しかし,Txbは文ではありません。xは変項であって名称(名前)ではないからです。)

 

※新しい文を生み出す6つの操作 

 

 1:否定.任意の文の先頭に ¬ をつける。

 2:連言:2つ以上の任意の文の列において隣り合う文の間に∧を書き,そうしてできたものを括弧でくくる。

 3:選言:2つ以上の任意の文の列おいて隣り合う文の間に∨を書き,そうしてできたものを括弧でくくる。

 4:条件. 任意の2つの文の間に⇒を書き,そうしてできたものを括弧でくくる。

 5:双条件. 任意の2つの文の間に ⇔ を書き,そうしてできたものを括弧でくくる。

 6:量化.何らかの名称rが現われているが変項が現われない全ての文,..r..において,rが現われる全ての箇所をxで置き換え,先頭に ∀x,または ∃xを付ける。

 後にさらに改定した規則を与えるまでの間は,規則:0~6 から得られるもの以外に文であるようなものは存在しないとします。

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

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

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

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

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

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

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

| | コメント (2) | トラックバック (1)

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健康ランド」

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

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

| | コメント (0) | トラックバック (1)

2007年10月 6日 (土)

形式論理学(2)

 形式論理学の続きです。

 以下では,論証の妥当性を論じるのに,全ての場合について真理値を与えて,そのテーブル(表)を調べるという有る意味で真っ正直な真理表を用いる非効率的と思える方法よりも,はるかに効率的でしかも機械的に行なえる真理の木の方法を紹介して説明します。

 例えば"前提がB⇒¬A,¬B⇒C;結論がA⇒C"という論証が妥当であることは集合{B⇒¬A,¬B⇒C,¬(A⇒C)}が矛盾することと同等です。

 

 実際,この論証は妥当で集合は矛盾していますが,これは真理の木という手法では閉じた木になっているという事実によって示されます。

 これはどういう意味かというと,木のてっぺんから末端まで続く経路のなかの,継続したいくつかの分枝のどれにも,それぞれ何らかの文(肯定)とその否定の両方が現われているような木のことです。

真理の木の導入的な説明のために,上に例示した論証の妥当性を対応する集合の元の全てが同時に真となるような場合があるかどうかで確かめる真理の木を作ってみます。

 まず,出発点;startです。1.B⇒¬A,2.¬B⇒C,3.¬(A⇒C)ですね。

次に第1段階です。startの1と2については,それぞれ真になる場合は1つしかないので,3から始めます。

 

実はどこから始めても全体として経路が短いか長いかだけの違いですから,始まりはどこでもかまいません。

当然,推論規則として集合論ではド・モルガンの法則(deMorgan's law)とよばれる論理命題は大いに活用します。

 

つまり,¬(A∧B)=¬A∨¬B,¬(A∨B)=¬A∧¬Bですね。

 

その他,否定の否定は肯定である:¬(¬A)=Aとか,紛らわしくないときには,¬¬A=Aと書きますが,こうした規則を使用します。

そして,1.B⇒¬A(前提),2.¬B⇒C(前提)ですが,3.¬(A⇒C)から,4.A,5.¬Cを得ます。

 

4,5がどうして得られるのかも考えるのが嫌なら,A⇒Bと¬(A∧¬B)が論理的に同値であることを既に真理表によって示しているので,¬(A⇒C)はA∧¬Cと論理的に同値ですから,これも推論規則に含めておいてよいので,これの理由を考える必要がなくなります。

 

4.A,5. ¬Cは4'.A∧¬Cとまとめて書いてもいいわけです。

次に第2段階です。1.B⇒¬A(前提)を考えると,これと同値な言明(は¬(B∧A)=¬B∨¬Aです。

 

これは¬B,または¬Aであることを意味しますから,ここで木は2つの場合に分岐します。

 

4.A,5.¬Cと6.¬Aの分枝では,Aと¬Aの両方が現われているのでこの経路は閉じています。

 

つまり,この流れでは共に真になることは有り得ないAとAの否定の両方が現われているので,こちらの道では真に到ることに失敗したということで,下にバツ:×を書いてこの道はここで終わりにします。

次に,第3段階です。既に1.B⇒¬A(前提),2.¬B⇒C(前提),3.¬(A⇒C),4.A,5. ¬C,6.¬Bの分枝しか残っていません。

 

2.¬B⇒C(前提)を考えると,これと同値な言明は¬(¬B∧¬C)=B∨Cです。

 

これはBまたはCを意味しますから,再びBとCに分岐しますが,Bのほうは6.¬Bによって直ちに閉じるし,Cの方も5.¬C,6.¬BよりCと¬Cが共存しますから閉じます。

こうして木は完成し,集合{B⇒¬A,¬B⇒C,¬(A⇒C)}が矛盾することが示されたので,論証:"前提がB⇒¬A,¬B⇒C;結論がA⇒C"が妥当であることを明示することに成功したわけです。

 

もちろん,この例のような単純な論証では,むしろ複雑になったと感じるかもしれませんが,これの威力がわかるのはより複雑な論証に適用する場合です。

一方,妥当でない論証:"前提がA⇒B,¬A;結論がB"を真理の木でテストをするとどのようになるかを見てみます。

 

対応する集合は{A⇒B,¬A,¬B}です。

 

A⇒Bは¬A∨Bと同値です。これを¬A,¬Bの後に書くとそこで¬A,¬B,¬Aの経路と¬A,¬B,Bの経路に分かれますが,後者は¬BとBがあるので閉じていて,一方は開いたままです。

 

開いた経路:¬A,¬B,¬Aはこれらが同時に真になる場合,つまり反例の存在を意味します。

短かいけれど,今日はここまでにします。

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

 

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

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

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

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

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

| | コメント (0) | トラックバック (0)

2007年10月 4日 (木)

形式論理学(1)

 数回に分けて,真理の木による方法での形式論理学のエッセンスについて述べていきたいと思います。

形式論理学は演繹の科学です。

 

それは,それぞれの論証について,結論として主張されているものが,本当にその前提から帰結するかどうか,つまりその論証が"妥当"なのかどうかを判定するための系統的な手段を与えることを目指すものです。

まず,論証が妥当であるとは,どういう意味なのかについて,その定義を与えます。

 

[妥当性の定義]:

妥当な論証とは,その前提が全て真であるようなあらゆる場合に,その結論も真になるような論証のことである。

つまり,妥当な論証というのは前提が全て真なのに結論が偽になるような場合がない論証のことです。

 

以下では,前提が全て真なのに結論が偽になるような場合を反例と呼ぶことにします。

 

こうすれば,"妥当な論証とは反例がない論証のことである。"と言うこともできます。

我流で考えると,形式論理学というのは次のことを目指す学問です。

 

すなわち,「前提がこうだから結論はこうだ。」というような混乱しそうな具体的な論証について,頭の中であれこれ論理をめぐらして思案して迷うことなく,

  

与えられた前提や結論の命題,そして論理展開の各々を記号化して,その記号が従うべき規則の通りに文章を機械的に展開していくことです。

  

頭を悩ませることなく,自然にそうした論証が妥当かどうか?という情報を得る方法を与えてくれるものだ,と考えられます。

まず,例として"Mは家と船の両方にいることはない。Mは家にいる。だからMは船にはいない。"という簡単な論証を表わす文を考えます。

 

これは,いわゆる真理関数的論理の立場から見ると,妥当であることがわかります。

 

前の2つの文が前提で"だから"という言葉が結論を示すしるしになっています。

この程度の三段論法なら別に悩む必要もないのですが,記号論理化の出発点としては,この程度の単純なものから始める必要があります。

 

そして,これら単純なものから,複雑なものを構築するわけです。

そして今,"Mが家にいること"をA,"Mが船にいること"をB,として記号で表すと,上の論証は"¬(A∧B),かつA→¬B"と書けます。

 

この論証が"妥当である,あるいは反例がないこと"を示すための素朴な方法としては真理表を用いる方法があります。

すなわち,ある命題が真なるときは,T(=true),偽なるときはF(=false)なる文字,つまり真理値を与える,という約束の下で,あらゆる場合について,前提と結論の全てに関する真理値の表を作り,反例の有無を調べる方法です。

(1)A:T,B:Tの場合は¬(A∧B):F,A:T,¬B:F (2)A:T,B:Fの場合は¬(A∧B):T,A:T,¬B:T (3)A:F,B:Tの場合は¬(A∧B):T,A:F,¬B:F (4)A:F,B:Fの場合は¬(A∧B):T,A:F,¬B:Tとなります。

 

これを見ると2つの前提が共にTなのは(2)だけで,そのときは結論もTで,それ以外の場合で2つの前提が共にTなのに結論がFの場合という反例が全くないので,妥当性の定義によって,これは妥当な論証である,と結論されるわけです。

次の例として,"Mは家にいるか船にいる。MまたはHは家にいる。Mは家にはいない。"という前提から,どのような結論が得られるか? について考察してみます。

 

今度は"Mが家にいること"をA,"Mが船にいることをB"とする他に,"Hが家にいること"をCで表わすことにします。

前提は,"A∨B,A∨C,¬A"です。

 

これに対する真理表で,これら3つの前提が全てTとなる場合を調べると,それは,A:F,B:T,C:Tの場合で,それ以外にはありませんから,結論は"B∧Cである"ということになります。

 

前提が全て真の場合には,"B∧CがTである"という例しかないので,結論は間違いなく,"Mは船にいて,Hは家にいる。"ということです。

偽の前提から出発した論証は,たとえそれが妥当なものであっても,そして仮に結論が真であったとしても,欠陥があると思われます。

 

例えば,"月は惑星である。したがって地球または月は惑星である。"というようなものがそうです。

 

この論証は妥当であり,結論も真ですが偽の前提から出発しています。そこでこうした論証は"健全ではない。"と言います。

そして,「健全な論証」とは,"妥当でありしかも偽の前提を持っていない論証である。"と定義されます。

 

こう定義すれば,健全な論証なら結論が真なることが保証されます。

次の論証の妥当性は認めることにします。

 

すなわち,"もしAならばBである。Aである。だからBである。"という文です。

 

これの妥当性を認めるということは,"AがT,BがFなるときには,A⇒BはFでなければならない。"という言明が成立するのを認めることを意味します。

ここで,今までは定義しないで使ってきた記号たち:結合子を整理しておきます。結合子というのは文に働いて新しい文を生み出す文法上の道具を言います。

まず,"否定(but):でない"は ¬,"連言(and):そして(かつ)"は∧,"選言(or):または"は∨で表現します。

 

A∧Bを"連言肢",A∨Bを"選言肢"と呼びます。これらが否定と組み合わされた文は,¬A∧Bとか,¬(A∨B)と書かれます。

 

括弧(bracket)は,それでくくられた文全体を示しますから,¬A∧Bが,"Aでなく,かつBである"という意味なのに対し,¬(A∧B)は"AかつBである"の否定を示すものです。

次に,条件法ですが,これは,"もし~ならば"を含む言明のことです。

 

論理的表記法ではこれを2つの言明の間に⇒を書いて作ります。

  

つまり,A⇒Bという表記によって,"もしAならばBである"という文を表わすわけです。

 

このときAを前件,Bを後件と呼びます。

ここで,A⇒Bと¬(A∧¬B)は,全く同じ言明を示していること,つまり,両者がいかなる場合も同じ真理値を持つことを示しておきます。

すなわち,¬(A∧¬B)がTになるのはA∧¬BがFのとき,つまりAがT,かつBがFなる文が否定されるときだけです。

  

これは,"AがTならば必ずBもTであること",あるいは,"BがFならばAもFであること"を意味するので,"A⇒BがTであること"と同じです。

 

¬(A∧¬B)がFになるのは,A∧¬BがTのときですから,

A⇒BはFです。

次に,"AならばBである。"と"Aであるときに限ってBである。"という2つの条件が同時に言明されている文章を考えます。

 

前者はA⇒Bということですが,後者は¬A⇒¬Bを意味していますから,B⇒Aなることと同じです。

 

そこで,全体として"(A⇒B)∧(B⇒A)"と表記することもできますが,これを論理的表記法では,A⇔Bと書き,双条件法と呼びます。

双条件法:A⇔Bが真(=T)になるのは,AとBが論理的に同値なとき,つまりAとBが全く同じ真理値を持つときです。

 

一応後付けながら「論理的同値の定義」を述べておくと,

 

"「2つの文が論理的に同値である」と言われるのは,あらゆる場合にそれらが同じ真理値を持つときである。"ということです。

 

ただし,これは「論理上の同値性」の意味でのことであり,現実の「事実としての同値性」を意味するものではありません。

ここで,論理形式に適した文の形成規則を与えます。

 

0:出発点.アルファベット,ただし添字がついていてもよい。

 

1:否定.文の先頭に¬をつける。

 

2:連言.2つ以上の文の列において隣り合う文の間に∧を書きそうしてできたものを括弧でくくる。

 

3:選言.2つ以上の文の列おいて隣り合う文の間に∨を書き,そうしてできた文を括弧でくくる。

 

4:条件.2つの文の間に⇒を書き,できた文を括弧でくくる。

 

5:双条件.2つの文の間に⇔を書き,できた文を括弧でくくる。

実際上は,より長い文の一部としてではなく,単独で現われているものについては両端の括弧は省きます。しかし,それでは文の判断がつかない場合は判断のため,規則通りに補助的に括弧を付けることにします。

 

こうした文法規則に従って作られる文を論理式と呼びます。

 

また,この形成規則の出発点となるアルファベットの大文字で表わされる文,結合子を一切含んでいない文は原子文,または原子式と呼ばれます。

次に,幾つかの文の集まりを考えます。

 

この"集まりが整合的である(無矛盾である)"というのは,そこに含まれる全ての文が真になる場合があることを意味します。

 

逆に,この集まりが矛盾しているというのは,そのような場合が全くないことを意味します。

例えば,"A⇒C;A⇒¬C;A"の3つの文の集まりは,矛盾した集合になります。

 

単独の文についても,それが真になる場合があるかないかに応じて整合的である,矛盾している,と言われます。

 

矛盾した単独の文のことは自己矛盾的な文,単に矛盾と言われます。

上述の整合性と矛盾の定義によれば"A∧B,¬A,故にB"のような前提と結論を有する論証の妥当性は,前提と結論を含む集合{A∧B,¬A,¬B}の矛盾を示すことに相当します。

 

つまり,前提A∧B,¬Aが共に真で結論Bが偽になるような場合は論証の反例ですが,集合{A∧B,¬A,¬B}が矛盾することはこうした反例がないことを意味します。

われわれが普通に真理と読んでいるものは,一方では理性的真理,あるいは論理的真理,もう一方は事実的真理と呼ばれるものであると思われます。

形式論理学の対象となるのは前者のほうで,論理的真理は現実の事象とは無関係にどんな場合でも真です。

 

"論理的真理の中で最も単純な種類のもの"="真理関数的論理"の範囲での論理的真理,つまり,"その文の最小構成単位となっている文たちの真理値がどんな組み合わせになっても,全体としては常に真になる文"をトートロジー(tautology:恒真,同義語反復)と言います。

 

正しくは,"トートロジーとはその真理表にFになる場合が全く出てこないような文を言う。"と定義されます。

トートロジーの実例としては,"A∨¬A","A⇒A","A∨B∨¬(A∧B)"があります。

 

次のような形式の論証が妥当になるのは,これに対応する1つの条件文:2がトートロジーであるときです。

 

すなわち,1."前提1,前提2,..,前提n,それ故,結論"に対応する1つの文 2."(前提1)∧(前提2)∧..∧(前提n)⇒(結論)"です。

なぜなら,2が偽になるのは1の前提が全て真であるにも関わらず結論が偽になるという場合ですが,これは論証1の反例ですから2がトートロジーであるということは,こうした反例が全くない,つまり論証1が妥当であることを意味します。

 

それ故,文2がトートロジーであるということ,恒真であること,と論証1が真理関数的に妥当であること,は同じことを意味するわけです。

この意味で,"形式論理学=真理関数的論理学"は演繹の科学であり,反証の科学であると同時にトートロジーの科学であるとも言えます。

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

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

 

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

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

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

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

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

| | コメント (7) | トラックバック (1)

2007年9月22日 (土)

ゲーデルの完全性,不完全性

 ゲーデル(Kurt Gödel)と彼の証明した定理については,以前の2006年8月10日の記事「ゲーデルの不完全性定理」でも紹介しました。

 今日は,ゲーデル数を用いた不完全定理の,概略的ですが一応,具体的な少しは内容のある証明手順について記述してみたいと思います。

去年の暮れまで住んでいた巣鴨の昔の住居のすぐ近くのトランクルームの中に,かつて部屋の中で本の山古墳を形成していた千冊足らずの専門書,啓蒙書や辞書,資料,小説などが,いくらか整理された形で眠っていて,ときどき金に困ると数冊ごとに,現金に化けたりしています。

先日,ある物理の本を探しに入った際に,記号論理学,数学基礎論,あるいはゲーデルに関する本にちょっと目が止まりました。

 

そうした関係の本は啓蒙書,専門書を合わせて10冊以上もありますが,私的には理解しやすい王道的なものは今まで見た中には全くなかったと思います。

 

もっとも,この種の本は軽い啓蒙書以外は一冊通して精読したこともありませんが。。

 

一番最近では,一昨年に「形式論理学」という本を途中まで読んだくらいですかね。

この論題には定期的に興味が湧いて,そのときどきに本屋で思いつきで買ったりするのですが,大抵は途中で挫折することの繰り返しでした。

 

でも門前の小僧というのか,これを10回以上も繰り返していると,少しずつですが理解は深まってきているような気がします。

 

今回もトランクルームから1冊だけ持って帰って読んでみました。

 

それは野崎昭弘著「不完全性定理」(日本評論社)です。

 

ただし啓蒙書の類であって専門書ではありません。

さて,こうした数学の体系の論理的な無矛盾性の論議をする際に特に問題となるのは「排中律」です。 

 すなわち,「"~である。"という命題と,"~ではない。"という命題というのは,両方が同時に成立する」とすれば,これは明らかに論理的に矛盾するわけです。

 

 しかし,ちょっと微妙な表現ですが,そういう明らかな矛盾ではなくて,「"これらのどちらかであって,どちらでもないその中間である。"ということは有り得ない」というのが「排中律」です。

 例えば"ある性質を満たす実数が存在する。"という命題を証明しようとするときに,実際に具体的にこの性質を満たす実数を構成して,この命題の成立を証明する方法が困難なことがあります。

 

 そのとき,こうした正攻法ではなく「"そういう実数が存在しない。"ことを仮定して,その結果として矛盾に導く」といういわゆる背理法で命題が証明できると考えるのは「命題の否定が矛盾に至るならば逆にその命題は成立する。」という論理が正当であることを既に認めています。

 

 つまり"存在と非存在以外にはあり得ない。"という「排中律」の成立を暗黙裡に認めているというわけです。

 しかし,問題としている実数が存在することを証明するのに,それが存在しないことを仮定して矛盾を導くという"背理法=非構成的存在証明の手法"によってこれを行うことは可能でも,具体的にその実数を構成して存在を陽に示すという手法がどうしても不可能な場合があります。

 

 普通の感覚では,非存在の定義そのものが,存在の否定=存在しないことを意味し,逆もまたそうですから,わざわざ「排中律」のようなルールを言明しなくても自明なことで蛇足のように思えます。

 

 しかし,必ずしも存在しないことの否定が存在することを意味するとは言えないのではないか?との疑問が生じることがあります。

 

 特に,非可算集合に属する要素の存在証明などの命題に関しては,そうした疑問が顕在化します。

 すなわち,記号論理学においての証明手順は論理式を与える長さが有限の記号列を順に並べていく,という手続きを連続する行為ですから,普通の三段論法や帰納法など,あらゆる証明の集合の要素全体で,それらの記号の数を全部数えても高々可算無限個しかないと考えられます。

 したがって,証明の対象が非可算集合における存在,非存在に関するものなら,実際問題として「排中律」の成立は疑わしいことになります。

 

 例えば,体系を集合論で自然数全体の集合から始めるとしても,それの"全ての部分集合の集合=ベキ集合"を作ると,それは既に非可算集合です。

 そこで,そうしたものに関連した存在証明であれば,背理法は使えず,存在するという証拠としては具体的にそれを構成してみせる方法しかない,と考えられるわけです。

そして,次のように表わされる命題=ゲーデルの不完全性定理もそうしたデリケートな問題を含んでいると考えられます。 

(不完全性定理):自然数論を含む述語論理の体系Zは,それがもし無矛盾ならば形式的に不完全である。

 

(ここで完全というのは任意の論理式Aについて,Aあるいは¬Aのいずれかが必ず証明できることを言います。)

 

(証明)上述の命題の証明のために,ゲーデル文と呼ばれる次の論理式Gが存在することを具体的に示す,という手法を用います。

ここでゲーデル文とは,"この論理式Gは証明できない。"ことを表現している論理式Gのことを言います。 

もしもこのような論理式Gが存在することが示せたならば,Gが証明されれば,"Gが証明できない。"という命題Gと矛盾します。

 

一方,証明が不可能であるということが判明すれば,"Gが証明できない。"という命題が成立するので,論理式Gの内容である"Gは証明できない。"という命題が証明される,ことになるのでこれも矛盾です。

 

後者は,"Gと¬Gが共に証明できる。"ということを示しているのですから,記号論理学的にも明らかに矛盾です。

 

つまり,G∧¬Gは恒偽であるのは明らかですから,これが真であるという証明は矛盾そのものです。

 

それ故,体系が無矛盾であるなら,"Gと¬Gのどちらも証明できない。=体系は不完全である"ということが正当化されるわけです。

したがって,最初に述べたように,こうしたゲーデル文を示す論理式Gの存在が,具体的にそれを構成することによって示されたなら,体系Zが無矛盾ならGと¬Gのどちらも証明できない,ことが証明されたことになりますから体系Zが不完全であることが判明するわけです。

この定理は言い方を変えると,"Zが無矛盾なら,正しいとしても証明できない論理式がある。"ということもできます。

具体的にGの存在を示すため,既に述べたように,あらゆる論理記号とその記号列,あるいは論理式は高々可算個しかないので,それらを暗号化してその各々に自然数の固有の番号を附与し,それをゲーデル数と呼ぶことにします。

そしてゲーデルによれば,次のような性質を持つ論理式:W(n)が具体的に構成できます。

 これは,"W(n)⇔nはある論理式のゲーデル数である。"なる文です。

 

 ここで記号 ⇔ はこれの左辺の記号が右辺と論理的に同値である,ことを示しています。

 この論理式[W(n)の構成が可能であることに関連して,ゲーデルはGの存在証明に必要な以下のような論理式の存在をも具体的に構成可能なことを示すことに成功しました。 

Probable(m) ⇔ mはある論理式のゲーデル数であり,その論理式は

        Zの中で証明できる。

また,証明に必要となる次のような関数を定義しておきます。 

sub(m,n,k) :

 

"mが表わす記号列αの中の,nが表わす記号列βを,kが表わす記号

γで置き換えて得られる記号列"のゲーデル数

(m) :

 

"自然数mを表わす記号列"のゲーデル数

neg(m) :

 

"自然数mを表わす記号列の前に,否定記号¬を付加して得られる記

列"のゲーデル数

とします。

 

以下,証明手順です。

変数xのゲーデル数が仮に17であるとします。

 

そして2変数m,nの関数 sub(m,17,g(n))を考えます。

 

xの関数で与えられるある論理式P(x)のゲーデル数がmの場合,

  

まず,sub(m,17,g(1))は,"mが表わす記号列の中の17が表わす記号列をg(1)が表わす記号列に置き換えて得られる記号列"のゲーデル数を意味します。

 

これは,(mが表わす記号列)=P(x)の中の(17が表わす記号列)=xを(g(1)が表わす記号列)=1に置き換えて得られる記号列はP(1)ですから,結局,"P(1)のゲーデル数"のことです。

同様にして,sub(m,17,g(2))はP(2)のゲーデル数,sub(m,17,g(3))はP(3)のゲーデル数,sub(m,17,g(4))はP(4)のゲーデル数,..となることを示すことができます。

 

故に,一般にsub(m,17,g(n))はP(n)のゲーデル数となります。

  

ここで,今の話では論理式:P(x)のゲーデル数がmのときにはsub(m,17,g(n))はP(n)のゲーデル数ですが,これはP(x)でなくて,Q(x)のゲーデル数がsでもsub(s,17,g(n))がQ(n)のゲーデル数であることを意味します。

 

つまりP(x)とm,Q(x)とsのゲーデル数の対応がありさえすれば,論理式はG(x)でも何でもいいということです。

ここでpmnsub(m,17,g(n))と置いた自然数の2重数列{pmn}の表において対角線を取り,自然数値をとる1変数xの関数 xxsub(x,17,g(x))を作ります。(対角線論法)

そしてG(x)≡¬Probable(sub(x,17,g(x)))と定義すると,このG(x)も体系Zの中の1つの論理式なので,それに付随するゲーデル数があるはずです。

 

そこで仮に論理式G(x)を具体的に表わしたときのゲーデル数が,1117であったとします。(ゲーデル自身は,当然,このゲーデル数も具体的に求めています。)

このとき,論理式:G(1117)が求めるゲーデル文です。

なぜなら,

 

(1117) ⇔ ¬Probable(sub(1117,17,g(1117)))

sub(1117,17,g(1117))が表わす論理式はZの中で証明できない。

⇔ 論理式G(x)のxに1117を代入して得られる論理式は証明できない。

⇔ 論理式G(1117)は証明できない。

となり,G(1117)が先に述べた"存在を証明すべき具体的なゲーデル文G"になっていることがわかります。(証明終わり)

"何だ,簡単じゃないか。"と思われるかもしれませんが,実はゲーデル自身が行なったと仮定して省略した部分の労力は,人間業ではないと思われるほどの凄いものであったらしいです。 

背理法的感覚であれば,上の証明の中で使用したように変数xのゲーデル数が17であるとかG(x)のゲーデル数が1117であるとか,あるいは17,1117でなくても存在しさえすればこれら2つのゲーデル数がどんな勝手な数の組であってもよいわけです。

 

実際,別のどんな2つの数であっても証明に全く支障はなく同じ結論が得られます。

元々,論理記号や論理式であれば,それに付随したゲーデル数は必ず存在するという前提で考察しているわけですから,x,G(x)のゲーデル数も必ず存在すると考えるのは自然な考え方です。

しかし,最初に述べたように存在するから,といってそれを仮想して設定できるとするのは,"背理法=非構成的存在証明の手法"にも似た考え方であり,今は自然数論を含む述語論理の体系Zを考えているのでその部分集合の族が既に非可算集合であることからも許されません。

 

そもそも,今の場合は"存在すること"を証明するのに,"存在すること"を前提にするのは,いかにも馬鹿げています。

 

そうした論法が可能であるなら,ゲーデルの労力は全く不要であったということになります。 

クレタ人のウソつきのパラドックスなど,幾つかの論理パラドックスの存在なら大昔から知られていたわけですから,既に通常の体系は矛盾があるか不完全かのどちらかであることはずっと昔からわかっていた,とする立場を取るなら,ゲーデルの仕事は徒労だったということになってしまいます。 

まあ,他にもゼノンのアキレスと亀などの幾つかの背理(パラドックス)なども,高校の数列や級数の収束程度の論理,あるいは大学で習うコーシー(Cauchy)のε-δ論法などの論理で解決済みとする立場もありますが,

 

人によっては,より突き詰めた考察をしたり,"そうした論旨は解決にはなっていない。"とする立場もあるようですから,これも似たようなものかもしれませんが。。。

参考文献:野崎昭弘 著「不完全性定理」(日本評論社)

 

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

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

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

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

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

| | コメント (34) | トラックバック (2)

2006年8月10日 (木)

ゲーデルの不完全性定理

 今日もまた軽い話題を少し。。。。

 ゲーデル(Kurt Gödel)の「不完全性定理」は"通常の数学の公理から出発して証明することが不可能な命題が存在する。"というような定理だったと思いますが集合の「ラッセルの背理」などと同じような範疇に入りますね。

 "一つの数学の体系があるとき,その閉じた体系の枠内から自分自身の体系が無矛盾かどうか?を判定することはできない。”という類の定理なのでしょうね。

 有名なところでは,"クレタ人はみんなウソツキである。とクレタ人が言った。"という文があります。

 この場合,,"クレタ人はみんなウソツキである。"という命題が「正しい」のであればこのクレタ人はウソツキではないので,"クレタ人はみんなウソツキである。"という命題が「間違い」だということになります。

 一方,この命題が「間違い=ウソ」であれば,"クレタ人はウソツキである。"ということが間違いなので,"クレタ人はウソツキではない。"ことになるにも関わらず,"これを言ったクレタ人はウソツキである。"というジレンマに陥ります。

 そこで,この,,"クレタ人はみんなウソツキである。"という命題を含む全体の文,"クレタ人はみんなウソツキである。とクレタ人が言った。"というのは"パラドックス=矛盾"であるというわけですね。

(PS:このクレタ人の話については上では"みんな"という人称を入れて「クレタ人はみんなウソツキである。」という命題を含む文にしました。

 しかし,厳密にはこの命題が「間違い=ウソ」の場合の否定命題は「ウソツキでない人もいる。」ということなので,全体としての文は別に"パラドックス=矛盾"ではなかったですね。

 この文をパラドックスの例として挙げたのは,適当ではなかったことに後で気付くきました。"「私=Aはウソツキである。(Aはウソしか言わない。)」とAが言った。"と1人称の文にすべきでした。

 失礼しました。(多重人格を除きます。))

 まあ,簡単に述べるなら,ゲーデルが証明したことは,"「この文は誤りである。」という文は正しいのか誤りなのかを証明できない。"という類のことです。

 "この文が誤り"であることが"正しい"と証明されれば"この文は正しい"ことになるので,"この文は誤り"であり,逆に"誤り"であると証明されれば"この文は正しい"ことになるので"この文が誤り"というのが正しいことになります。

 彼(ゲーデル)はこうした”証明することができない命題が数学の論理体系の中には必然的に存在する。"ことをカントールの対角線論法を使って証明したというわけです。

 (まあ,数学の公理系の無矛盾性の証明ができないことを証明した。という意味では「この文は正しい」という文が正しいことをこの文だけから証明することはできない。と言ったほうが適切なのですが,それではパラドキシカルな説明ができなくて面白味がないと思ったので逆にしました。)

 説明しようする私自身が完全には理解していないので,既にかなり混乱していますが,結局,"文を次々と枚挙してゆき,それが正しいなら誤りという文をつくって連ねていくと,正しくてかつ誤りであるというような"矛盾した文"が必ずできるということになり,ゲーデルは,そうした文が常に存在する。"ということを厳密に証明したということでしょうか。

 まあ,厳密には形式論理学の"論理式をトートロジー変形していく操作",例えば"「真理の木」のようなダイアグラムを作る操作"を続けていって最終的に矛盾を導くことなをしなければならないのでしょうね。

 参考文献:リチャード・ジェフリー著「形式論理学」(産業図書)

PS:後記事ですがこれの続編として,2007年9/22の記事「ゲーデルの完全性,不完全性」があります。

また,さらに続いて2007年10/4の「形式論理学(1)」に始まり,(1)から(6)までで途中で中断している論理学シリーズ記事もあります。

http://fphys.nifty.com/(ニフティ「物理フォーラム」サブマネージャー)                                       TOSHI 

http://blog.with2.net/link.php?269343(ブログ・ランキングの投票)↑ここをクリックすると投票したことになります。

| | コメント (10) | トラックバック (0)

その他のカテゴリー

001. 目次 002. 募金・ボランティア 003. 日記・回想 004 訃報 005. 心身・思想・哲学 006. 社会・経済・政治 007. 病気(診察・薬) 008. 恋愛・異性 009 宗教・神話 010 歴史(日本,世界) 011. 将棋 012. TV(ニュース・ドラマ) 013 スポーツ(ニュース・イベント) 014 ノン・フィクション 015 小説・詩・評論 016 漫画・劇画・アニメ 017 演劇・映画・舞踊 018 音楽(日本・西洋・他) 019 タレント(俳優・お笑い) 020 ミュージシャン 021 アイドル・ヒーロー 022 創作 023 シャレ・ギャグ等 024 競馬・toto・賭け事 025 ファッション・風俗 100. 物理学一般 101 教育・学校(物理) 102. 力学・解析力学 103. 電磁気学・光学 104. 熱力学・統計力学 105. 相対性理論 106. 星・ブラックホール・一般相対性 107. 重力・宇宙・一般相対性 108. 連続体・流体力学 109. 物性物理 110. 複雑系・確率過程・非線型・非平衡 111. 量子論 112. 原子・分子物理 113. 原子核物理 114 . 場理論・QED 115. 素粒子論 116. 弦理論 118. 観測問題・量子もつれ 119. 電気回路 200. 問題・解答 201. 自然科学一般 202. 気象・地学・環境 203. 生物学・生理学・生化学 204. 経済学(ミクロ・マクロ・マルクス) 300 数学一般・算数 301. 集合・位相 302. 論理学・数学基礎論 303. 代数学・数論 304. 解析学 305. 複素数・複素関数論 306. 線型代数学 307. 幾何学(トポロジー・他) 308. 微分方程式 309. 確率・統計 310. 関数解析・超関数 311 .数値計算・調和解析・離散数学 312. 公式・特殊関数 501. 商用宣伝・アフィリエイト