286 第Ⅳ部論理学はここから先が面白い ! 進んだ話題のロードマップ 真ん中は決め手がない。おそらくウカシエヴィッツは P → P を 3 値トートロジーにしておき たかったのだろう。 さて , 検討しなければならないのは , このように定義された 3 値論理において 0.5 という値が 本当にウカシエヴィッツが意図したように「可能」という意味を持っていると考えてよいかとい う点だ。このことについて次のように異議を唱えることもできるだろう。私の使っているコン ピュータのハードディスクは最近変な音を立てている。そこで , A を「明日私のコンピュータ は壊れる」としよう。今日の段階では A は真とも偽とも決まっていず , そういうこともあるか もしれないし , ないかもしれないという可能な状態にとどまっている。だとするなら , ¯IA も ' こまではよい。しかし , 「明日私のコンピュータは 真とも偽とも決まっていないはずである。 壊れ , しかも壊れない」ということは今日の段階ですでに , そのようなことはありえない , 不可 能だと断言できるのではないだろうか。つまり A △¯IA は偽であるように思われる。つまり , 「可能」な命題同士が互いに相手を排除して両方が成り立っことはできなくなってしまう , とい うことがあるように思う。しかし , すでに見たようにウカシエヴィッツの 3 値論理では A △¯IA は A が 0.5 のときは 0 . 5 になってしまう。どうもちょっとズレがあるようだ。 11.2.2 フアジー論理 ・・といくらでもたくさんの真理値を考えることができ , 論理結合 多値論理体系は 3 値 , 4 値・・ 子の定義の仕方もいろいろありうる , というわけですごくバラエティに富んでいる。じっさい , 数えきれないほどの体系がつくれる。しかし , 逆にこのことのために , 多値論理はあまりに人工 的すぎて , 数学的興味で研究するにはおもしろいかもしれないが , 我々が現実にやっている推論 とどんな関係があるの ? という疑問もなきにしもあらずだ。実際 , 1920 年代から 30 年代にかけ ての成立期ののち , しばらくは多値論理の研究はあまりばっとしない分野になってしまった。と ころが最近になって多値論理は再び多くの人々の関心の的として復活してきた。それはフアジー 論理 (fuzzy logic) という分野が発展してきたことが原因だ。フアジー論理とはどのような論理 なのだろう。ちょっと回り道になるが次の有名なパラドクスを味わってみることからはじめよ 連鎖推論のパラドクス 次の 3 つの命題を見てみよう。 ( a ) 頭髪が 0 本の人はハゲである。 ( b ) 頭髪が 100 万本の人はハゲ ではない。 ( c ) すべての自然数 n について , 頭髪が n 本の人がハゲなら , 頭髪が n 十 1 本の人もハ ゲである , が成り立つ。 ( a ) ( b ) が真であるということに異議はない。 ( c ) はどうか。 ( c ) も真みたいだ。 1 本くらい毛が増 えたからといってハゲがハゲでなくなるわけではないでしょ ? しかし , 人によっては (c) を受け 入れるのに抵抗があるかもしれない。そういう人は次のように考えてみたらどうだろう。 ( c ) が偽 であるとするためには何を受け入れなければならないか。 B(n) を「頭髪が n 本の人はハゲであ る」を表す述語とすれば , ( ) が偽であると考える人は , ¯lVn(B(n) → B(n 十 1)) を真であるとし

1 28 第Ⅱ部論理学をひろげる 7 行目の式▽ x Qx には , すでに立てた規則を適用して , 量化子を はずして , x に a を代入してやる。そうすると , お見事 ! タブローは 閉じました。 ほとんど同じ代入規則だ。こんなことで大丈夫だろうか。いまの論証が に ] , [ Ⅵ , いヨ ] , [ Ⅵを並べてみると・・・・・・何か変。に ] とⅣ ] は というわけで 規則をたてることができた。それを列挙しておこう・・ というわけで , 2 つの量化子の肯定形 , 否定形についてそれぞれ展開 5.4.2 展開規則とその使い方 Vx()x → Qx) 3xPx ! ー 1 ヨ xQx Pa Pa → Qa ! •Pa x Qa ▽ x¯Qx ¯nQa うまく判定されたのはまぐれかもしれない。そこで , こんどは明らかに充足可能な式集合がこの やり方できちんと充足可能と判定されるかどうかみてみよう。 存在量化子についての展開規則には制約条件がある 集合 { ヨ xpx, ヨ x•Px) は明らかに充足可能だ。例えば , Px を「 x は北アイ ルランドの連合王国からの分離に賛成である」としてみたらよい。しかし , さっ きの展開規則に ] を第 1 行と第 2 行にあてはめると , 右のように閉鎖タブロー が生じ , まちがった判定が出てしまう。 まずかったのは , 2 行目に展開規則を適用して 4 行目を得たところだ。 1 行目 は「 P なものがある」と言っており , 2 行目は「 P でないものがある」と言って ヨ xPx ! ヨ x•Px ! Pa •Pa いる。 3 行目を得たときは , 「 P なものがある」のだからそいつを a と名づけたわけだ。しかし , さらに 4 行目を得るとき , 2 行目で存在すると言われている「 P でないもの」がこの a とは限ら ない , というよりこの場合は a ではありえないのに¯lPx に a を代入してしまった。 2 行目で存 在が主張されている「 P でないもの」は a とはべつのもの , 例えば b にしておかねばならな かったはずだ。ようするに , 分離に賛成の人がいるということだから , それを a さんとしま しよう , としておきながら , すぐに , 分離に反対の人もいるということだから , その人も a さ んとしちゃいましよう・・ ・・とやってしまったらナンセンスでしょ , ということ。 つまり , ヨについての展開規則では代入してよい個体定項に制約がある。 2 行目に規則を適 用するとき , 経路のなかにはすでに a が現れているから a は使えず , まだ現れていない個体定 項 b を使わねばならない。そうすると , 上のタブローで Pa, •Pa だったところが , Pa, •Pb となり , [ x ] を当てはめることができなるなるから開放タブローが得られる。だったら , ラー メン屋の事例がうまく判定されたのはいったいなぜだろう。それはいちばん始めに [ ヨ ] を使っ たからだ。その段階ではまだ経路にはひとつも個体定項が現れていなかったから , たまたま , ま だ経路に現れていない個体定項を代入することになり , 知らず知らずのうちに制約条件を満たし ていたというわけだ。 ここで , きちんと展開規則に ] を書きなおしておこう。この規則を存在例化 (El:existential instantiation) と呼ぶ。

付録 370 AV(BVC) と ( AVB ) vC は論理的に同値である。だから A - BYC と書いてもまぎれはないのだが ( 3 ) 「または」を景品の「または」として理解した A B C A V B V C A または B または C 場合の「 A または B または C 」は , A, B, C のどれ 1 1 1 1 0 1 0 0 0 1 か 1 つだけが 1 になり残りは 0 の場合 ( 4 , 6 , 7 行 0 1 0 0 1 目 ) だけで 1 になる。これに対し , A v B v C は第 1 1 0 0 1 1 行目でも 1 になっている。したがって両者は論理的 0 1 1 0 0 0 1 0 1 1 同値ではない。つまり , A v B は景品の「または」と 0 0 1 1 1 して理解した場合の「 A または B 」と同じことなの 0 0 0 0 0 だが , これを拡張した A v B v C は景品の「または」 として理解した場合の「 A または B または C 」とは異なる。 ( 4 ) では , AVBVC の真理表はどのような意味で AVB の真理表を拡張したものになっているの だろう。さらに , A v B \/ C v D の真理表を書いてみるとわかるのは , A V B ▽ C V D は A, B, C, D のうち奇数個の式に 1 が割り当てられている真理値割り当てのもとで 1 になっているということであ る。そう思って A v B v C の真理表を見直してみると , やはり同様に A, B, C のうち奇数個の式に 1 が割り当てられている行で 1 になっている。もともとの A v B も A, B のどちらか一方だけが 1 になるときに 1 になるのだが , これは要するに A, B のうち奇数個 ( つまり 1 個 ) の式に 1 が割り 当てられるような真理値割り当てのもとで 1 になるということに他ならない。 12 ( 1 ) (a) PQR が順に 011 , 001 , 000 となる行でこの 3 つの式は同時に 1 になる。したがって充足 可能。 (b) PQR が順に 010 , 000 となる行でこの 3 つの式は同時に 1 になる。したがって充足可能。 ( 2 ) (a) 矛盾している。この集合には P と¯IP とがともに含まれる。この 2 つを同時に真にする 真理値割り当ては存在しないから , この集合全体を同時に真にする真理値割り当てはなおさら存在し ない。 (b) 矛盾していない。 P と Q から△だけを用いてつくることのできるどの論理式も , P, Q にと もに 1 を割り当てるような真理値割り当てのもとでは真である。したがってこの集合に含まれるすべ ての論理式を同時に真にする真理値割り当てが存在する。 ( 3 ) 【証明】が矛盾しているのに I* U △が矛盾していないと仮定しよう。 U △が矛盾していな いということは , U △に属するすべての式を一斉に 1 にするような真理値の割り当て方 V があると いうことである。しかしこのとき , 当然のことながら V は IA に属するすべての式を一斉に 1 にする。 なぜなら I* に属する式はすべて IA U △にも属しているからである。ということは , IÄは充足可能で あり , IA が矛盾しているという仮定に反する。したがって , IÄが矛盾しているのに I* IJ △が矛盾して いないというようなことはありえない。■ 13 ( 1 ) 「我々の少なくとも 1 人は悪党だ」は•A ▽•13 と記号化できる。 これを a が言うことのでき るのはどのような場合だろうか。 •AV¯IB A+(¯lA\/¯nB) A B 1 0 0 0 1 1 1 1 0 0 1 0 1 亠 1 ・亠 -0- -0- というわけで , a が騎士 , b が悪党である。

第 7 章さらに論理言語を拡張する 201 に転用することができるということを証明しておく。こうすれば , 停止問題が求めるアルゴリズ ムは存在しないのだから , PPL の任意の式集合の矛盾 / 充足可能性を判定するようなアルゴリズ ムもまた存在しない , ということが言える。 こまでは本当に大ざっぱなお話しだ。チューリングマシンとは何か , それが計算できない問 題とはなにかを知りたくなった人は , 内井惣七 [ 1989a ] , 廣瀬健 [ 1975 ] , Boolos/Jeffrey [ 1989 ] などを読んでさらに勉強しよう。

133 第 6 章 おおっと述語論理のセマンティクスがまだだった 6.1 述語論理のセマンティクスをつくらなけれは M PL に対して使えるようにタブローも整備したし , あとはタブローの信頼性を示せばパー フェクトだ。タブローが信用できるということは , 「から開放タブローが生じるは充 足可能」ということだから , これを示せばよいわけだ。 ・・と考えて , はたと気がつくことがあ る。まだ肝心のことをやっていない ! つまり , そもそも , 述語論理で書かれた式の集合が矛盾 しているとか充足可能だということがどういうことかをはっきりさせていないじゃないか。例え ば , { ▽ x()x → (x), ヨ xQx, ヨ xPx} はどう考えても矛盾している。これが矛盾していると いうことは , 命題論理の場合と同じように 3 つの式がいっぺんに真になるような真理値の割り当 てがない , ということなのだろうが , そもそも述語論理式に対する真理値の割り当てって何だろ 命題論理のときは , PA ¯IQ は , 原子式 P に 1 , Q に 0 を割り当てる真理値割り当てのもとで 1 になる , などと言っていた。この場合 , 原子式の P や Q は分析の最小単位なので , さらに 「 P が 1 になるというのはどういうときか」を問うことはなかった。さて , 述語論理の場合も , ヨ xQx はヨ xQx が 0 のときに 1 になる , といったことは言える。しかしこんどはヨ xQx は 最小単位ではないから , それが 0 になるというのはどういうときかに答えなくてはならない。 れまでは , こうしたことを直観にまかせてやってきた。しかし , このへんでそろそろ厳密にやっ ておかないと先へ進めなくなってしまう。というわけで , 述語論理のセマンティクスをきちんと 展開するのがここでの課題だ。今回も直観的な場面から出発して徐々にセマンティクスを作り上 う述語の意味が分からないからだ。そこで , それをはっきりさせてやる。 いきなり , 「ヨ x()x △ (x) は真ですか偽ですか」と聞かれても答えられない。 P とか Q とい 6.1.1 論理式の真偽は解釈で決まる げていくというやり方をとって説明しよう。

付録 は非可算なのである。 364 4.3 基数の系列 アレフ 濃度というのは , 集合の要素の個数という概念を無限集合についても使えるように拡張したも のだ。 空集合の濃度は一と表される。空集合の要素の個数は 0 だから , ト 0 と書くことにし よう。次に , A= (a) の濃度いーは同様に 1 と書くことにしよう。 ・・そうすると , それぞれの 自然数は , しかるべき大きさの有限集合の濃度に対応するものだということがわかる。 だとしたら , 無限集合の濃度からもある種の数を引き出すことができるだろう。これはものの 個数としての自然数を無限集合へ拡張したものだ。このように , 濃度をある種の数のようにして 捉えると基数 (cardinalnumber) という言い方をされるようになる。 0 , 1 , 2 , ・・・など , 有限集合の 濃度を表すような基数を有限基数 , 有限基数でない基数を無限基数または超限基数とよぶ。 超限基数は大きさの順に並べることができる。それを順に ド 0 , ド 1 , ド 2 , と書くことにする。この文字はヘブライ語のアルファベットで「 A 」にあたる文字だ。「アレフ」 と読む。ド 0 が最小の無限基数だということになる。実は , ー N ー = ド 0 であることがわかってい る。つまり , 自然数の集合は無限集合のなかでいちばんサイズの小さいものだということだ。 連続体仮説 さて , 連続体濃度 2X0 ( なぜこのように表せるのかについて説明すると長くなるから省略。実は実数 の集合 R と区間 I , さらに N のベキ集合 p ( N ) の濃度はみんな一緒で , 基数 2X 。を用いて表される ) は 自然数全体の集合の濃度ド 0 よりは大きい。では , どのくらい大きいのだろう。カントールは , 2X 。 = ド 1 と予測した。これを連続体仮説 (continuum hypothesis) という。つまり , 連続体濃度 は自然数全体の濃度の次に大きな無限基数だという仮説である。 N と R の中間の大きさの無限 集合はないのだ , と考えたわけだ。 この仮説は正しかったのだろうか。いまでは次のようなことが分かっている。つまり , 集合に ついての基本的な事実を公理系の形でまとめあげた標準的な理論 ( 公理的集合論といわれる ) に おいては , 連続体仮説は provable でない。それどころか , その否定も provable でない。つま り連続体仮説は集合論の公理系から独立なのである。 4.4 すべての論理式は枚挙可能である コンパクト性定理の証明や , リンデンバウムの補助定理の証明の中では , すべての論理式を AO , AI , A2 , ・・・という具合に並べておいて , 最初のものから順番に 1 つずっ IÄに付け加えるかど うかをチェックする・・・というような手続きが含まれていた。こうした操作ができるためには , 無

152 第Ⅱ部論理学をひろげる 【定義】 A が妥当式である VM,6(A) = 1 すべてのモデル M とアサインメントびについて , これらの定義によって , Fx △ Gx からは Fx が論理的に出てくると言えるし , Px → Px は妥当 式だと言える。これは方針 T ではできないことだ。しかし , やはり , 閉論理式の範囲では 2 つ の方針に基づく定義は一致する。したがって , 6.2.8 以下では , 特に開いた論理式のことを考え なければならないときを除き , より簡便な方針 T による定義を使ってゆくことにしよう。 【定義】 次に , いくつかのよく使われる言い回しを定義しておく。 いくつかの言葉づかいの定義 練習問題 41 アサインメントびがある。 ( 3 ) 論理式の集合 IA が充足可能であるのすべての要素を同時に満たすモデル M と ( 2 ) 論理式 A が充足可能である VM,6(A) = 1 となるモデル M とアサインメントびが I' のモデルであると言う。 ( 1 ) 論理式の集合に含まれるすべての閉論理式がモデル M のもとで真になるとき , M は ( 1 ) ( 2 ) ( 3 ) FxAGx から Fx が論理的に帰結するということを定義に沿って示せ。 Px → Px が妥当式であることを定義に沿って示せ。 次のことを証明せよ。 AI , A2 , ・・・ , An ト C 論理式 ( AI △ A2 ^ ・・・△ An ) → C が妥当式である。 6.2.8 反証モテル 以下では方針 T のもとで述べてゆくことにする。 直しすれば方針 S でも同じような話はすぐにできる。さて , 前提 I* から論理式 A を導く論証が これは話を簡単にするためで , ちょっと手 という論証を考えてみよう。この論証は妥当ではなさそうだ。そこで反証モデルを構成すること ル (countermodel) と呼ぶことにしよう。例えば , 「ヨ x(PxAQx), したがって , Vx()x → (x) 」 そのようなモデルが論証の反例と呼んでいたものに相当する。こうしたモデルを論証の反証モデ が結論 A は偽にするようなモデルが 1 つでも見つかれば , その論証は妥当ではないことになる。 モデルはすべて A も真にする , ということだ。したがって , I* のあらゆるメンバーを真にする 妥当である ( つまり (A) ということはいまの定義によると , のあらゆるメンバーを真にする

第Ⅳ部のまとめ 347 記号そのものに求めた。これもまた , 第 II 部でヒンティッカ集合の充足可能性を証明した際に用 いたやり方と同じだった。 ・公理系 AFOL の完全性証明の副産物として , コンパクト性定理とレーヴェンハイム・スコー レムの定理が導かれる。 言語 FOL を用いることによって , ある分野の基本的知識を公理系のかたちで与えることが できる。それは , AFOL の公理 ( 論理公理 ) に , さらにその分野に特有の公理 ( 固有公理 ) を付 け加えることによってなされる。こうした公理系を理論と呼ぶ。 ・理論の例として , ロビンソン算術 Q を紹介した。 Q は自然数とその上の足し算 , かけ算に ついての基本的知識を公理化したものである。 Q はその作り方からして , 自然数の世界をモデル にもっことは当然だが , 自然数とは同型でない構造もモデルにもってしまう。こうしたモデルを 非標準的モデルと言う。ある理論が同型のモデルしかもたない場合 , その理論を範疇的と言う が , 0 は範疇的ではない , ということだ。 ・それどころか FOL で書くことのできる算術の理論はかならず , 自然数全体の集合に同型で ないようなモデルをもってしまうことが証明できる。これにはコンパクト性定理が使われる。 ・第 12 章の最後に , FOL をこれまでとは異なった方向に拡張することを試みた。ギーチ・カ プラン文や「無限にたくさんのものがある」のような文は , FOL の論理式として表すことがで きない。こうした文も翻訳しようとすると , 論理式で述語記号が占めている位置を量化しなけれ ばならない。こうした量化を許す論理を第 2 階の論理と言う。 ・述語への量化を許す第 2 階の言語を用いると , 数学的帰納法の公理が表現可能になる。この 公理を Q に付け加えると , 第 2 階のペアノ算術という公理系になる。第 2 階のペアノ算術 PA2 は範疇的である。つまり , PA2 のモデルはすべて自然数全体の集合に同型なものばかりであ レーヴェンハイム・スコーレムの定理などの性質を失ってしまう。 ・しかしながら , 第 2 階の論理は表現力の高さと引き替えに , 第 1 階の論理がもっていたコン パクト性 , 完全性 ,

第 4 章機械もすなる論理学 93 U, S → W, (WV-•V) → P} というような集合が矛盾しているかどうかを真理表を使っ て調べようとすると , えらいことになる。 7 種類の原子式を含んでいるから , 27 = 128 行の真理 表を書かなきゃならない。これは人力ではまず無理だ。 真理表よりもう少し実用に耐えるチェック法はないものか。その 1 つが , 真理の木 (truth tree) とか意味論的タブロー (semantic tableau) または分析タブロー (analytic tableau) と呼ば れる方法だ。これは , ヒンティッカ (Jaakko Hintikka) らのモデル集合という考え方を応用し て , スマリャン (RaymondSmuIIyan) によって広められたすぐれた方法である。 てみよう。 タブローの方法がどのような発想に基づいているかを理解してもらうために , 次の問題を考え 4.1.2 タブローのルーツ 割り当てを求める試みはすべて失敗した。したがって , これらの式は一斉に 1 になること ( 11 ) 以上のようにして ( P , へ、一一 - ー、 Q ) と ( PVQ ) △ Q をともに 1 にする首尾一貫した真理値 ては見つからない。 ばならないのだった。したがって , こちらの方向でも与式がすべて 1 になる真理値割り当 ⑩最後に残ったのは -•Q が 0 となる場合である。しかし , ( 3 ) により , .Q は 1 でなけれ ない。 だった。したがって , こちらの方向では与式がすべて 1 になる真理値割り当ては見つから ⑨そこで P が 0 であるとする。しかし , ( 7 ) により , いま p が 1 の場合を考えているの •(P ^ (Q) が 1 であるためには , p か—.Q のどちらかが 0 でなければならない。 ( 7 ) そこで , P が 1 の場合を追求してみよう。以下は p が 1 だと考えている。 とがわかった。 したがって , こちらの方向では与式が両方とも 1 になる真理値割り当ては見つからないこ ( 6 ) そこで , まず Q が 1 であるとしよう。しかし , ( 4 ) により , Q は 0 でなければならない。 ( 5 ) ところで , P ▽ Q が 1 になるためには , P か Q のどちらかが 1 でなければならない。 ( 4 ) —-Q が 1 であるためには Q が 0 でないといけない。 ( 3 ) (P v Q) △—•Q が 1 になるためには , P ▽ Q が 1 , —-Q が 1 でなければならない。 ( 2 ) そこで , -•(P △ (Q) と (P 、 v Q) △ -•Q がともに 1 であると仮定してみる。 矛盾しているということがわかるはずだ。 れるかどうかを追求してみよう。それに成功すればこの集合は充足可能だし , 失敗すれば ( 1 ) この集合に含まれるすべての論理式を 1 にする首尾一貫した真理値割り当てを見つけら 真理表を書けばこのことは簡単に分かるが , 次のように考えることもできる。 【問い】式の集合 { ーー 1 ( P △ Q ) , (PVQ)A•Q) は矛盾しているかそれとも充足可能か。

86 第 I 部論理学をはじめる 3.11.3 コンバクト性定理の証明・バートⅡ △をもとに原子式への真理値割り当てをつくる △をもとにして , 次のように原子式への真理値割り当て V をつくろう。 【 V の定義】原子式 Pi が V のもとで真である P に△ つまり , △に含まれているかどうかに応じてそれぞれの原子式に真または偽を割り当てるよう な真理値割り当てを V とする。この V は△がもつ「都合のよい性質」のおかげで次のような補 助定理を満たす。 【補助定理 20 ー 2 】任意の論理式 A について , A が V のもとで真である Ae △ ようするに , V は△に属するすべての式 , そしてそれらの式だけを充足する真理値割り当て になっているというわけだ。この補助定理が成り立てば , IÄ△だから , この真理値割り当て V これは A の結合子の数についての帰納法を使って行 はに属するすべての論理式を充足する。つまり , I* は充足可能である。というわけで , あと 【証明】 は補助定理 20 ー 2 の証明だけが残っている。 ( 2 ) このとき , k 十 1 個の結合子を含む A についても , A が V のもとで真である A △ 立っていると仮定する。 ( 1 ) k 個以下の結合子を含む論理式については , A が V のもとで真である Ae △が成り [lnduction step] A が V のもとで真である Ae △は V の定義により明らか。 [Basis] A が 0 個の結合子を含むとき , つまり A が原子式のとき , が成り立っていることを言う。 ・ Subcase 1. A が¯nB という形のとき , —nB が V のもとで真である B が V のもとで偽である B △ ( 帰納法の仮定により ) -nBe △ ( △の都合のよい性質 ( 2 ) により ) ・ Subcase 2. A が B △ C という形のとき , B △ C が V のもとで真である B が V のもとで真であり , る Be △かっ Ce △ ( 帰納法の仮定により ) BACe △ ( この理由は次に示す ) かっ C が V のもとで真であ 理由 : Be △かっ Ce △であるのに B △ CG △であるとする。すると△の都合のよい性 質 ( 2 ) により , ( B △ C ) e △である。しかし , そうすると集合 { B , C , ( B ^ C ) } は△の有限部 分集合となるが , この集合は矛盾している。これは△が有限充足可能であることに反する。