形式論理学(5)

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

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

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

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

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

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

0：出発点.任意のｎ項述語の後ろにｎ個の名称を続けたものは文である。（ｎ＝２の場合の例：Ｔａｂ,Ｔｂｂは文です。しかし,Ｔｘｂは文ではありません。ｘは変項であって名称(名前)ではないからです。）

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

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

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

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

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

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

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

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

↑(再掲終わり)

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

これを用いる１例として,文："∀ｘ(Ｔｘｂ⇒Ｔａｂ)"を作る場合なら,まず,出発点の規則(0)によりＴｃｂとＴａｂを作り,次に規則(4)によって(Ｔｃｂ⇒Ｔａｂ)とします。

そして,規則(6)によって,∀ｘ(Ｔｘｂ⇒Ｔａｂ)を作るわけです。

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

これは,ホームズをａ,モリアーティをｂ,"捕まえることができる"をＴという記号で表現すると"1.∀ｘ(Ｔｘｂ⇒Ｔａｂ)(前提);2.￢Ｔａｂ(前提);⇒ 3.￢∃ｘＴｘｂ(結論)"という論理式になります。

そして,この命題の妥当性を示すことは３つの文の集合:"1.∀ｘ(Ｔｘｂ⇒Ｔａｂ);2.￢Ｔａｂ;3.￢￢∃ｘＴｘｂ"の矛盾を示すことと同等になります。

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

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

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

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

次に,"5.Ｔｂｂ⇒Ｔａｂ"は"￢Ｔｂｂ∨Ｔａｂ"と同値ですから,ここから"6a.￢Ｔｂｂ"と"6b.Ｔａｂ"の２つの文に分岐します。

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

一方,"4.∃ｘＴｘｂ"は,Ｔｘｂを成立させるあるｘが存在することを意味するので,この"ｂを捕まえることができる(Ｔｂ)少なくとも１人は存在する(∃ｘ)誰か＝ｘ"の名称をｃとして,"7.Ｔｃｂ"と書くことができます。

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

さらに,もう１度"1.∀ｘ(Ｔｘｂ⇒Ｔａｂ)"を用いて,"8.Ｔｃｂ⇒Ｔａｂ",すなわち"8.￢Ｔｃｂ∨Ｔａｂ"が成立します。

この8.は"9a.￢Ｔｃｂ","9b.Ｔａｂ"と展開できます。

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

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

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

(ＵＩはuniversal instantiationの略)

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

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

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

(ＥＩはexistential instantiationの略)

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

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

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

そこで,例えば上のＵＩの規則を∀ｘ(Ｍｘ⇒Ｈ)には適用できますが,∀ｘＭｘ⇒Ｈには適用できません。

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

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

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

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

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

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

これの真理の木は,"1.∀ｘＭｘ","2.✓￢∃ｘＭｘ"3.∀ｘ￢Ｍｘ","4.￢Ｍａ"(3より),"5.Ｍａ"(1より)です。

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

もう１つ例を出します。

それは命題:"(∃ｘＭｘ⇒Ｈ)⇒∀ｘ(Ｍｘ⇒Ｈ)"です。

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

これの妥当性の論証は"∃ｘＭｘ⇒Ｈ;￢∀ｘ(Ｍｘ⇒Ｈ)"の矛盾を示すことと同値です。

これの真理の木は,"1.✓∃ｘＭｘ⇒Ｈ","2.✓￢∀ｘ(Ｍｘ⇒Ｈ)","3.✓∃ｘ￢(Ｍｘ⇒Ｈ)"(2より),"4.✓￢(Ｍａ⇒Ｈ)"(3より),"5.✓Ｍａ∧￢Ｈ"(4より),"6.Ｍａ"(5より),"7.￢Ｈ"(5より),"8.✓ ￢(￢∃ｘＭｘ∧￢Ｈ)"(1より),"9.✓Ｈ∨∃ｘＭｘ"(8より),"10a.Ｈ"(9より) ←この枝は×です(7より)。

また,"10b.✓∃ｘＭｘ"(9より),"11.∀ｘ￢Ｍｘ"(10bより),"12.￢Ｍａ"(11より) ←この枝は×です(6より)。

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

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

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

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

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

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

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

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

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

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

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

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

← クリックして投票してください。(ブログ村科学ブログランキング投票です。１クリック＝１投票です。１人１日１投票しかできません。クリックするとブログ村の人気ランキング一覧のホ－ムページームに跳びます。）

　

形式論理学(4)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

こうした表記法ではＴａｂなどが原子文になります。この例では,∀ｘ(Ｔｘｂ⇒Ｔａｂ)；￢Ｔａｂ;故に￢∃ｘＴｘｂと表現されます。

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

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

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

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

1.∀ｘ(Ｔｘｂ⇒Ｔａｂ);2.￢Ｔａｂ;3.￢￢∃ｘＴｘｂと書きます。

まず,3.￢￢∃ｘＴｘｂをチェックして,4.∃ｘＴｘｂを得ます。

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

そこでｘ＝ｂとして,5.Ｔｂｂ⇒Ｔａｂが成立します。

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

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

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

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

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

一方,4.∃ｘＴｘｂはＴｘｂを成立させる,ある人物ｘが存在することを意味するので,この少なくとも１人の存在する誰かの名称をｃと置いて, 7.Ｔｃｂと書くことができます。

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

さらに,1.∀ｘ(Ｔｘｂ⇒Ｔａｂ)をもう１度用いて,ｘ＝ｃとおいて,8.Ｔｃｂ⇒Ｔａｂ,あるいは 8.￢Ｔｃｂ∨Ｔａｂと書くことができますから,9.￢Ｔｃｂ,Ｔａｂと展開できます。

これで9.の左側の分枝:￢Ｔｃｂは 7.Ｔｃｂ によって閉じます。

また,9.の右の分枝:Ｔａｂも再び 2.￢Ｔａｂ によって閉じます。

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

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

内部構造を有する原子文は一般にＭａ,Ｔａｂ,Ｒａｂｃ，..などの形をとります。

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

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

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

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

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

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

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

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

同様に２項述語:Ｔ,３項述語:Ｒはそれぞれ２つ,３つの個体の間の関係を表わします。すなわち,Ｔａｂ,Ｒａｂｃです。

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

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

0：出発点.任意のｎ項述語の後ろにｎ個の名称を続けたものは文である。（ｎ＝２の場合の例：Ｔａｂ,Ｔｂｂは文です。しかし,Ｔｘｂは文ではありません。ｘは変項であって名称(名前)ではないからです。）

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

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

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

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

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

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

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

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

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

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

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

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

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

← クリックして投票してください。(ブログ村科学ブログランキング）

    物理学

形式論理学(3)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

特に,￢Ａが１つの行として経路Ｐに現われているとすると,単独の文字Ａで表わされる文は場合Ｄでは偽になります。

なぜなら,Ｐは開いた経路なので￢ＡがＰに現われている以上,Ａが１つの行としてＰに現われることはないからです。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

← クリックして投票してください。(ブログ村科学ブログランキング）

    物理学

形式論理学(2)

　形式論理学の続きです。

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

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

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

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

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

　まず,出発点;startです。１.Ｂ⇒￢Ａ,２.￢Ｂ⇒Ｃ,３.￢(Ａ⇒Ｃ)ですね。

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

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

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

つまり,￢(Ａ∧Ｂ)＝￢Ａ∨￢Ｂ,￢(Ａ∨Ｂ)＝￢Ａ∧￢Ｂですね。

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

そして,１.Ｂ⇒￢Ａ(前提),２.￢Ｂ⇒Ｃ(前提)ですが,３.￢(Ａ⇒Ｃ)から,４.Ａ,５.￢Ｃを得ます。

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

４.Ａ,５. ￢Ｃは４'.Ａ∧￢Ｃとまとめて書いてもいいわけです。

次に第２段階です。１.Ｂ⇒￢Ａ(前提)を考えると,これと同値な言明(は￢(Ｂ∧Ａ)＝￢Ｂ∨￢Ａです。

これは￢Ｂ,または￢Ａであることを意味しますから,ここで木は２つの場合に分岐します。

４.Ａ,５.￢Ｃと６.￢Ａの分枝では,Ａと￢Ａの両方が現われているのでこの経路は閉じています。

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

次に,第３段階です。既に１.Ｂ⇒￢Ａ(前提),２.￢Ｂ⇒Ｃ(前提),３.￢(Ａ⇒Ｃ),４.Ａ,５. ￢Ｃ,６.￢Ｂの分枝しか残っていません。

２.￢Ｂ⇒Ｃ(前提)を考えると,これと同値な言明は￢(￢Ｂ∧￢Ｃ)＝Ｂ∨Ｃです。

これはＢまたはＣを意味しますから,再びＢとＣに分岐しますが,Ｂのほうは６.￢Ｂによって直ちに閉じるし,Ｃの方も５.￢Ｃ,６.￢ＢよりＣと￢Ｃが共存しますから閉じます。

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

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

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

対応する集合は{Ａ⇒Ｂ,￢Ａ,￢Ｂ}です。

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

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

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

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

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

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

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

← クリックして投票してください。(ブログ村科学ブログランキング）

    物理学

形式論理学(1)

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

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

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

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

[妥当性の定義]:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(1)Ａ:Ｔ,Ｂ:Ｔの場合は￢(Ａ∧Ｂ):Ｆ,Ａ:Ｔ,￢Ｂ:Ｆ (2)Ａ:Ｔ,Ｂ:Ｆの場合は￢(Ａ∧Ｂ):Ｔ,Ａ:Ｔ,￢Ｂ:Ｔ (3)Ａ:Ｆ,Ｂ:Ｔの場合は￢(Ａ∧Ｂ):Ｔ,Ａ:Ｆ,￢Ｂ:Ｆ (4)Ａ:Ｆ,Ｂ:Ｆの場合は￢(Ａ∧Ｂ):Ｔ,Ａ:Ｆ,￢Ｂ:Ｔとなります。

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

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

今度は"Ｍが家にいること"をＡ,"Ｍが船にいることをＢ"とする他に,"Ｈが家にいること"をＣで表わすことにします。

前提は,"Ａ∨Ｂ,Ａ∨Ｃ,￢Ａ"です。

これに対する真理表で,これら３つの前提が全てＴとなる場合を調べると,それは,Ａ:Ｆ,Ｂ:Ｔ,Ｃ:Ｔの場合で,それ以外にはありませんから,結論は"Ｂ∧Ｃである"ということになります。

前提が全て真の場合には,"Ｂ∧ＣがＴである"という例しかないので,結論は間違いなく,"Ｍは船にいて,Ｈは家にいる。"ということです。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

このときＡを前件,Ｂを後件と呼びます。

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

すなわち,￢(Ａ∧￢Ｂ)がＴになるのはＡ∧￢ＢがＦのとき,つまりＡがＴ,かつＢがＦなる文が否定されるときだけです。

これは,"ＡがＴならば必ずＢもＴであること",あるいは,"ＢがＦならばＡもＦであること"を意味するので,"Ａ⇒ＢがＴであること"と同じです。

￢(Ａ∧￢Ｂ)がＦになるのは,Ａ∧￢ＢがＴのときですから,

Ａ⇒ＢはＦです。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

例えば,"Ａ⇒Ｃ;Ａ⇒￢Ｃ;Ａ"の３つの文の集まりは,矛盾した集合になります。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

← クリックして投票してください。(ブログ村科学ブログランキング）

    物理学

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

　　　　　　　　Ｚの中で証明できる。

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

sub(ｍ,ｎ,ｋ) :

"ｍが表わす記号列αの中の,ｎが表わす記号列βを,ｋが表わす記号

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

ｇ(ｍ)　:

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

neg(ｍ) :

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

号列"のゲーデル数

とします。

以下,証明手順です。

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

そして２変数ｍ,ｎの関数 sub(ｍ,17,ｇ(ｎ))を考えます。

ｘの関数で与えられるある論理式Ｐ(ｘ)のゲーデル数がｍの場合,

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

これは,(ｍが表わす記号列)＝Ｐ(ｘ)の中の(17が表わす記号列)＝ｘを(ｇ(1)が表わす記号列)＝１に置き換えて得られる記号列はＰ(1)ですから,結局,"Ｐ(1)のゲーデル数"のことです。

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

故に,一般にsub(ｍ,17,ｇ(ｎ))はＰ(ｎ)のゲーデル数となります。

ここで,今の話では論理式:Ｐ(ｘ)のゲーデル数がｍのときにはsub(ｍ,17,ｇ(ｎ))はＰ(ｎ)のゲーデル数ですが,これはＰ(ｘ)でなくて,Ｑ(ｘ)のゲーデル数がｓでもsub(ｓ,17,ｇ(ｎ))がＱ(ｎ)のゲーデル数であることを意味します。

つまりＰ(ｘ)とｍ,Ｑ(ｘ)とｓのゲーデル数の対応がありさえすれば,論理式はＧ(ｘ)でも何でもいいということです。

ここでｐ_mn≡sub(ｍ,17,ｇ(ｎ))と置いた自然数の２重数列{ｐ_mn}の表において対角線を取り,自然数値をとる１変数ｘの関数 ｐ_xx＝sub(ｘ,17,ｇ(ｘ))を作ります。(対角線論法)

そしてＧ(ｘ)≡￢Probable(sub(ｘ,17,ｇ(ｘ)))と定義すると,このＧ(ｘ)も体系Ｚの中の１つの論理式なので,それに付随するゲーデル数があるはずです。

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

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

なぜなら,

Ｇ(1117) ⇔ ￢Probable(sub(1117,17,ｇ(1117)))

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

← クリックして投票してください。(ブログ村科学ブログランキング）

    物理学

ゲーデルの不完全性定理

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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