第 12 章古典論理にもまだ学ぶことがたくさん残ってる レーヴェン / 、イム・スコーレムの定理 329 完全性定理の証明で構成したモデル M について振り返ってみよう。 M の論議領域は , そもそ ものに含まれていた項とそれに付け加えた可算無限個の個体定項からっくれるだけっくった 項の全体からなっている。付録 A の 4.4 で確認したように , FOL に含まれる項の数は可算無限 個だから , M の論議領域は可算無限の濃度をもっている。そして , M をある意味で縮めて最終 的につくったモデル M' の論議領域の濃度は明らかに M の濃度と同じかそれよりも小さい。 を可算モデル countable model と言う ) が存在する。 のとき , △を充足するモデルで高々可算個の個体からなる論議領域をもつようなものにれ 【定理 53 : レーヴェンハイム・スコーレムの定理】論理式の集合△は充足可能だとする。 のことから , 次の定理が導かれる。 Q の文法 おこう。ロビンソン算術 (Robinson arithmetic) と呼ばれる理論だ。この理論を Q で表す。 と論理 (logic) をごっちゃにしないように。実例が手つ取り早いので , 理論の例を次に挙げて の形でまとめることができる。これを第 1 階の理論 (first order theory) と言う。理論 (theory) FOL で許される語彙と FOL で定義できる論理式とを使って , ある分野の基本的知識を公理系 公理的理論とは 12.3 第 1 階の理論 充足可能である。したがって , △も可算モデルによって充足可能である。■ る極大無矛盾集合が存在する。完全性定理の証明から明らかなように , I** は可算モデルによって 【証明】△が充足可能なら , △は構文論的に無矛盾である ( 健全性による ) 。そうすると△ IÄ* な ( 1 ) ( 1 ) ( 2 ) ( 3 ) ( 4 ) 語彙 原子項 個体定項 0 個体変項 x, y, z, 述語記号はつかわない 関数記号 1 変数関数記号 2 変数関数記号 論理定項 ーロ「コ → , ▽ 十 , △ ,

索 A. 事 「多くて」 207 引 項 あ行 曖昧性のパラドクス 曖昧な述語 287 アサインメント 145 アサインメントの変種 「当てはまる」 145 アルゴリズム 92 , 199 生きている仮定 2 7 移出律 44 287 置き換え規則 249 置き換えの定理 52 , 7 1 か行 外延的 18 。 , 352 回帰的定義 25 解釈 134 下位導出 217 開放経路 98 開論理式 125 , 137 会話の含意 157 ( 三段論法の ) 格 161 可算モデル 329 可算濃度 3 朝 可算集合 36 。 重なり合った量化 168 隠れた前提 155 確定記述句 13, 2 。 8 拡張としての非古典論理 拡大律 44 ( 三段論法の ) 格式 162 完全 252 完全性証明 248 , 265 完全性定理 266 冠頭形 199 関連性にかかわる違和感 146 2 1 7 記号論理学 16 記述理論 210 基数 364 ギーチ・カプラン文 帰納的定義 25 帰納法の仮定 29 逆 5 。 338 ( 導出が ) 依存している 一意的存在 2 。 6 1 次下位導出 217 427 8 1 2 1 5 , 2 19 1 対 1 写像 357 一致の原理 148 意図されたモデル 移入律 44 意味言侖 36 , 261 意味論的帰結 261 意味論的タブロー 意味論的に閉じた ( 仮定を ) キャンセルする 吸収律 44 , 5 1 共外延的表現 180 極大無矛盾 268 , 323 共通集合 353 337 吾 88 93 305 極大無矛盾集合の充足可能性補助定 意味論的パラドクス 89 意味論的矛盾 262 入れ替え律 45 , 51 , 102 上への写像 358 ウォーターゲートのパラドクス 33 , 9 。 カッコ省略のための取り決め 合併集合 353 可能 284 可能性演算子 3 。 5 可能世界意味論 310 124 理 269 空虚な現れ 125 , 185 空集合 352 偶然的真理 47 , 282 「偶然 P である」 3 。 5 繰り返し規則幻 8 クリスプな述語 288 クリプキ・セマンティクス 経験的真理 46 形式的真理 6 , 46 形成の木 26 , 123 経路 95 結合律 44 , 51 決定可能性 103, 189 決定手続き 92 299 うそっきのパラドクス 89 n 項関係 166 n 項述語 166 n 変数命題関数 166 演繹 215 , 222 , 254 演繹定理 256 演繹の枠組みをまずつくれ 220 可能な知識状態 299 還元法則 3 。 6 関数 356 関数的完全性の定理 間接証明 2 76

第 7 章さらに論理言語を拡張する ・ Subcase 5. A が -- ー 1 ▽穹 B の形のとき , Subcase 4 と同様。 197 ( 3 ) 以上より , すべての論理式について「 A e △ A はモデル M のもとで真」が成り立つ。 タブローの開放経路はヒンティッカ集合であることの証明 【証明】いかなる原子式 A についても A と¯nA の両方が開放経路 @ に属することはない。した がってヒンティッカ集合の条件 ( ー 1 ) を満たしている。また , タブローをつくるための展開規則によ り @ が残りの条件を満たすことも明らかだ。少しとまどうところがあるとしたら条件 ( ーコヨ ) , ( ーーーⅣ ) だろうが , ー 1 ヨ A が経路に含まれていれば , 展開規則により , ▽穹 A も経路に含まれて おり , したがって経路に現れるすべての個体定項について A / 刳が含まれているはずだか ら , 開放経路は ( ーー 1 ヨ ) を満たしている。 ( ーーコ V ) も同様。したがって開放経路⑧はヒンティッカ集 合である。 定理 34 により , いかなるヒンティッカ集合も充足可能であるから @ も充足可能である。また r は @ の部分集合であるから , @ が充足可能である以上も充足可能である。 7.4 論理学者を責めないで 7.4.1 PPL の決定不可能性 タブローだけが悪いのではない 決定問題と計算の理論 「タブローの方法で判定しようとしても止まらなくなっちゃっうケースがあるんだってさ。タ プローってのはダサイなあ。だったら , タブローの欠陥を直して , タブローメソッド・ターボと か , もっとよい判定方法をつくれば , どんな式の集合に対してもきちんと有限ステップで判定が 下せるようになるんじゃない ? そういう方法はもうできてるんでしよ。え , ない ? 論理学 者ってあんがい無能なんだなあ」。 論理学者はそんなにポンクラではない。実は , PPL の式のどんな有限集合を与えられても , 有限ステップのうちにそれが矛盾しているか充足可能かを判定してくれるような機械的方法はあ りえない , ということが証明されている ( 定理 35 ) 。つまり , タブローを改善したものであろう が , 全く異なる発想に基づく方法であろうが , 機械的方法である限りは , 有限ステップでの判定 がつかなくなってしまうケースが必ずある。そのために , どんなに論理学者ががんばっても , あ りとあらゆるケースを判定してくれるような機械的方法はつくれない。だから , 以上で見てきた タブローの方法の限界は , タブローがたまたま欠陥商品だったことを示すのではなくて , PPL について成り立つごく一般的な事実の現れと見なすべきなのだ。 したがって , 「決定不可能性」というのも , そもそもはタブローの方法などの一つ一つの方法 について言われるべきことがらではなくて , PPL そのものについて言われるべきことがらだ。

200 第Ⅱ部論理学をひろげる せておかなくてはならない。こうして , アルゴリズムの一般的・厳密な定義が必要になる。アル ゴリズムすべてに共通の特質は何か , アルゴリズムとアルゴリズムでないものの線はどのように して引いたらよいかという問題が , 決定問題の否定的解決に先立つ問題として生じてくる。 アルゴリズムの概念の明確化とチャーチの提案 アルゴリズムとは何かを 92 ページで説明したが , これは論理式を「記号を意味をなすように 並べたもの」と説明するようなもので , 厳密な定義ではなかった。しかし決定問題の否定的解決 を追求するにはそのようなばんやりした概念を使い続けているわけにはいかない。こうして 1930 年代から 40 年代にかけて , 多くの数学者・論理学者が「厳密な仕方でアルゴリズムを定義 するにはどのようにしたらよいか」という問題に頭を悩ませることになり , アルゴリズムという ばんやりとした概念に置き換えることのできるような , 厳密に定義された概念がいくつか提案さ れた。 ( 1 ) チャーチの「え定義可能性」 , ( 2 ) チューリングの「チューリングマシン計算可能性」 , ( 3 ) ゲーデル , クリーニの「帰納的関数」などがそれだ。 このほかにも , 何人かの人たちが独自にアルゴリズム概念に置き換えるべき厳密な概念を定義 した。驚いてしまうのは , それぞれ独立に提案されたこれらの概念がすべて互いに同等だったと いうことだ。これは偶然の一致というには出来すぎているので , これらの概念はみなアルゴリズ ムというばんやりした概念の正体をうまく捉えているらしい , と考えられるようになった。そこ で , 次のような提案がなさることになる。 【チャーチのテーゼ】アルゴリズムがある , とだと考えよう。 というのはチューリングマシンで計算できるこ チューリングマシンというのは , 数学的に厳密に定義された抽象的な架空の計算機のことだ。 決定問題を否定的に解く典型的な方法 定のもとで , そのアルゴリズムをちょっと変えれば , 停止問題が求めているようなアルゴリズム し PPL の任意の式集合の矛盾 / 充足可能性を判定するようなアルゴリズムがあったならという仮 題が否定的に解かれているとする。このとき , さらに PPL の決定不可能性を証明するのに , も また , すでに否定的に解かれた別の決定問題を利用することもできる。例えば , すでに停止問 から矛盾を導くという方針だ。 決定問題が要求するような計算をするチューリングマシンがプログラムできたと仮定して , そこ いことを証明するということだ。これは , 背理法を使って証明されることが多い。つまり , その 解決するとは , 要求された計算を行うようにチューリングマシンをプログラムすることができな よって , 決定問題の否定的解決ということがどういうことかが明確になる。決定問題を否定的に う提案であって , このこと自体は数学的に証明されるようなことではない。しかし , この提案に チューリングマシン計算可能性という数学的にきちんと定義できる概念で置き換えましようとい チャーチのテーゼはあくまでも , アルゴリズムといういままで使ってきたばんやりした概念を

第 11 章めくるめく非古典論理の世界にようこそ ! うちのひとつを現実世界とみなす。論理式はそれぞれの可能世界で真理値をもつ。それは 世界によって異なっていてもかまわない。 ( 2 ) 可能世界のあいだには到達可能性 (accessibility) という関係が定義される。世界 w か ら見て世界 w' が到達可能であるとは , 直観的には , 世界 w をちょっと変えることによっ て世界 w' に移ることができることと考えてもよいし , w からが「見える」というこ とだと考えてもよい。 ( 3 ) この上で , 各可能世界における「ロ A 」 , 「◇ A 」の真偽を次のように定義する。 31 1 可能世界 w において口 A が真 真。 可能世界 w において◇ A が真 て A が真。 w から到達可能なすべての可能世界において A が w から到達可能な可能世界のうちのどれかにおい そして , 可能世界間の到達可能性という関係にさまざまな条件を課すことによってさまざまな 公理系に対するセマンティクスを得ようというわけだ。もうすこし詳しく見てみよう。 【定義 : クリプキ・フレーム (Kripke Frame) 】空でない集合 W と W 上の 2 項関係 R のペア F = くⅥ気 R> をフレームという。 W の要素を「可能世界」と呼ぶ。 R を到達可能性関係と呼ぶ。 フレームによって決まるのは , どのような可能世界があるかということと , どのような到達可能性があるかということだ。 それらのあいだに 【定義 : フレーム F に基づくクリプキ・モデル】フレーム F= <W, R> に対して , 3 つ組 M = <W, R, V> をフレーム F に基づくクリプキ・モデル M と言う。ここで , V は付値関数 と言い , 各可能世界に応じて原子式のそれぞれに真理値を割り当てる関数である。 V がモ デル M の可能世界 w において原子式 A に与える真理値を VM ( w , A ) で表す。またモデルの 名前をいちいち区別して言及する必要がないときは単に V(), A) と書く。 というわけで , クリプキ・モデル M は次の 3 つの要素からなる。 ( 1 ) 可能世界の集合 W, ( 2 ) その 可能世界どうしの到達可能性関係 R, ( 3 ) 原子式のそれぞれに , それが各可能世界でとる真理値を 割り当てる付値関数 VO フレームが同じでも V が異なれば , それぞれの可能世界でどのような 原子式が真なのかが異なるわけだからモデルとしては違うモデルになる。 モデルにおける真理の定義 さて , 次に複合的なものも含む一般の論理式 A がモデル M の可能世界 w でとる真理値 VM (), A) を定義しなくては。もうわかっていると思うけど , 帰納的定義を使う。

[ 1995 ] を見てほしい。 のある読者はジェフリー てもう少し掘り下げておく。 7.4.2 決定問題 決定問題とは ぶ。 【決定問題 (decision problem) 】任意の { 198 第Ⅱ部論理学をひろげる 決定不可能性 【定理 35 : PPL の決定不可能性 (undecidability) 】 PPL の任意の論理式の有限集合が与えら れたときにそれが矛盾しているか充足可能であるか , また PPL の任意の論証が与えられた ときに , その論証が妥当であるかどうかを機械的手続きの有限の適用によって判定するため 以上の話をもう少し広い視点から見てみよう。まず , 次の形式をもった問いを決定間題と呼 この定理の証明には , 相当な準備が必要だ。したがって , 本書では証明できない。残念。興味 の一般的方法 ( アルゴリズム・決定手続き ) は存在しない。 ' こでは , その代わりにこの定理の意味につい } を入力したときに , つねに有限 ステップ内で { } を出力してくれるようなアルゴリズムが存在するか ? いま問題になっていたのは , 任意の { PPL の論理式の有限集合 } を入力したときに , つねに 有限ステップ内で { それが矛盾しているかどうかの判定結果 } を出力してくれるようなアルゴリ ズムが存在するか ? という決定問題なのだった。そして , 定理 35 によれば , そのようなアルゴ リズムは存在しない。このとき , この決定問題は否定的に解かれたと言う。逆にそのようなアル ゴリズムをひとつでもよいから具体的につくることができたなら , その決定問題は肯定的に解か れたと言われる。 肯定的に解かれた決定問題 肯定的に解かれた決定問題としては次のようなものがある。 ( 1 ) 任意の { L の論理式の有限集合 } を入力したときに , つねに有限ステップ内で { それが矛 盾しているかどうかの判定結果 } を出力してくれるようなアルゴリズムは存在するか ? この決 定問題は肯定的に解かれた。具体的には真理表やタブローが要求されたアルゴリズムに他ならな ( 2 ) 任意の { MPL の論理式の有限集合 } を入力したときに , つねに有限ステップ内で { それ が矛盾しているかどうかの判定結果 } を出力してくれるようなアルゴリズムは存在するか ? とい う決定問題も肯定的に解かれた。タブローがそのアルゴリズムだ。つまり , 多重量化を含まない 述語論理を考えれば , それは決定可能。

第 3 章人工言語に意味を与える 【補助定理 20 ー 1 】どの△も有限充足可能である。 85 【証明】仮定により出発点の ( つまり△ 0 ) は有限充足可能である。だから , △が有限充足可能な ら次の△ n + 1 も有限充足可能である , ということを示せばよい。そのためには , △が有限充足可能 なのに , 次の△。 + 1 になるはずの△。 U { ーーー IA 。 + 1 } も△ nU{An + けもいずれも有限充足可能ではない , と いうことがありえないということを言えばよい。 そこで背理法を使う。つまり , ( 1 ) △が有限充足可能であり , ( 2 ) △。 U { An + 1 } は有限充足可能で はなく , (3) △ nU{An + I) も有限充足可能ではないと仮定する。 そうすると , ( 2 ) より , △。 U { ーーー lAn + 1 } の有限部分集合で充足可能でないものがあることになる。そ れは△ n の何らかの有限部分集合△言に¯nAn+I を合わせたものになっているはずである ( △ U{¯1An + 1} の有限部分集合には一・一 - lAn + 1 を含まないものもあるが , それは△の有限部分集合になっ てしまうから , それが充足可能でないとすると ( 1 ) に反してしまう ) 。したがって , △言 CJ { A 。 + 1 } が 矛盾する ( つまり△言 , -- ー lAn + 譱である ) ような△の有限部分集合△言が存在する。 同様に ( 3 ) より , ぷ , An + 譱であるような△の有限部分集合ぶが存在する。 さて , △言 , ーー - ー lAn + 譱と△ : ; , An + 譱より , △ー - ー 1 -- -- -1 An + 1, △ -- ー lAn + 1 である ( 定理 15 ( 5 ) からすぐに 出てくる ) から , △ : ICJ △ー一一。 1 一一一 1 A ・¯nAn + I となり , 集合△ : ICJ △ : ; は矛盾していることになる。と ころで , △言 U ぷは△ n の有限部分集合だから , このことは△ n が有限充足可能であるという仮定に 反する。ー △の定義 ・ , △ n, ・・・にでてくる集合はどれも有限充足可能であること 以上により , 集合の列△ 0 , △ 1 , △ 2 , がわかった。次にこの列に現れるすべての集合の合併集合 U △ n を△とおく。この△は作り方 からして次の性質を持っていることは明らかだ。 n 十 1 , n=0 【△の都合のよい性質】 ( 1 ) 1 △ ( 2 ) すべての論理式 A について , ( 3 ) △は有限充足可能である。 A か A のいずれかが△に属している。 このうち ( 3 ) だけは証明しておいたほうがよさそうだ。 【 ( 3 ) の証明】△のどの有限部分集合△ ' も , 有限集合であるからにはそれが含んでいる An ( あるいは ¯nAn) には最も番号の大きなものがあるはずだ。その番号をかりに n とすると , ぷは△ n の部分集 合だということになる。補助定理 20 ー 1 によりどの△ n も有限充足可能だから , △ n の有限部分集合 である△ ' も充足可能。したがって△のどの有限部分集合も充足可能である。・ のよい性質とはここで挙げた 3 つの性質に他ならない。 この△が前ページで「都合のよい性質を持つ集合△」と呼んでいたものだ。そしてその都合

3 1 2 第Ⅳ部論理学はここから先が面白い ! 【定義】 = 0 進んだ話題のロードマップ ( 4 ) A がロ B という形の論理式のとき , ( 3 ) A が B → C という形の論理式のとき , VM(), A) = 1 VM(), B) = 0 または ( 2 ) A が一旧という形の論理式のとき , VM (), A) = 1 ( 1 ) A が原子式のとき , VM(W,A)=1 VM(W,A)=I からが到達可能だが , からは到達可能ではなく , から到達可能な世界はない・・ る。このとき , このフレームを次のように図示することができる。つまり世界から W2, フレーム F = く W , R > が , W={Wl,W2,W3}, R = { く , > , く , > } で与えられているとす モデルの例 VM(W',B)=I VM (), A) = 1 wRw' であるような少なくとも 1 つの可能世界 w ' において , ( 5 ) A が◇ B という形の論理式のとき , VM(W,A)=1 wRw ' であるようなすべての可能世界 w ' において , VM(w',B)=1 といったフレームだ。 ' こでは , 原子式は P だけとしてそれを次のよ 当てれば , モデル M = <W, R, V> が確定する。 さらに , このフレーム F の各可能世界に , それぞれの原子式がその世界でとる真理値を割り うに与えてみよう。 V(WI, P)=I v(W2, P)=I v(W3, P) このモデルをフレームの図に書き込む。いろいろなやり方があるが , の下にそれぞれの式がとる真理値を書いていくという方法が便利だ。 次のように , 各可能世界 P 1 1 0 ( 1 ) さて , 例えば論理式 P →ロ P は可能世界で真だろうか。 WI から到達可能な世界は W2 だけだ。で P は真だから , ロ P は可能世界で真。したがってロ P は可能世界 WI で な具合に定義にしたがって , 各世界での論理式の真偽を決めていくことができる。 偽。前件の P は可能世界で真だから , 全体として P →ロ P は可能世界で偽。

第 11 章めくるめく非古典論理の世界にようこそ ! このフレームで , ロ P → P が妥当であることを示せ。 315 ( 4 ) ( 5 ) 11.4.4 論理式と到達可能性関係との対応 どん詰まり世界を含むフレームではロ P →◇ P が妥当式ではないことを示せ。 問題 ( 3 ) のフレームでロ P →ロロ P は妥当にならないことを示せ。 練習問題 93 の ( 3 ) をやってみると , 次のことがわかるのではないだろうか。到達可能性関係が したがって , R が反射性を満たすようなモデルではつね その世界から到達可能な世界の中には自分じしんも含ま 反射性 Vw ( wRw ) を満たしていると , 各可能世界は自分自身に到達可能になるから , どの可能 練習問題 94 にロ A → A が妥当になる。 れるので , A はその世界で真になる。 世界でも , もしそこでロ A が真なら , つまり , ある世界から到達可能であるような世界同士も到達可能である。 ( 5 ) R がユークリッド的である VwVw'Vw"[(wRw'Aw'Rw") → w'Rw"] ( 4 ) R が推移的 (transitive) である VwVw'Vw"[(wRw'Aw'Rw") → wRw"] ( 3 ) R が対称的 (symmetric) である VwVw'(wRw' → w'Rw) ( 2 ) R が反射的 (reflexive) である Vw(wRw) ない ) から到達可能な世界が少なくともひとつある , つまりそのフレームにはどん詰まり世界が存在し ( 1 ) 到達可能性関係 R が serial である Vw ヨ w'(wRw') ( つまりどの可能世界にもそこ 【定義】 ' こで考える到達可能性関係の性質を列挙しておく。 的な結果をまとめておこう。まず , しく調べる分野は対応理論 (correspondence theory) とよばれる。そこで次に , 対応理論の代表 をはっきりさせたのがクリプキ・セマンティクスのすごいところなんだなあ。この対応関係を詳 このように , 論理式の妥当性と , 到達可能性関係の性質との間には対応関係がある。このこと 【定理 46 】ロ A → A がフレーム F = < W , R > で妥当である R が反射的である。 以上のことより , 次の定理が成り立っことがわかる。 いフレームにおいてはつねにロ A → A が真にならない世界を含むモデルがつくれることを示せ。 そこで逆に , ロ A → A が妥当になるフレームはみな反射的であることを示せ。つまり反射的でな

第 3 章人工言語に意味を与える 43 ・・そんな馬鹿なことはないだろう。実は , どうも我々は双条件法を表すときにも「なら ば」で済ませているようなのである。例えば , 誘拐犯人が「明日までに 1 億円用意できなかった ならば息子の命はないものと思え」と言ったとしよう。このとき , 前件が偽で後件が真の場合 , つまり 1 億円用意したのに息子が殺された場合 , 犯人のことを「嘘っきめ ! 」と罵るだろう。っ まり , 前件が偽で後件が真の場合には犯人の発言は偽になると我々は考えているわけだ。これは 犯人が使った「ならば」を我々は条件法ではなく双条件法として解釈している証拠ではないだろ うか。 これからは , 「←」と , すでに出てきた「 v 」も論理結合子の仲間に入れて使ってゆくことに 3.3 3.3.1 トートロジー トートロジーとは何か 真理値分析の練習問題をやってみるとわかることだが , かによって次の 3 種類に分類できる。 論理式は , どのような場合に真になる ( 1 ) ( 2 ) ( 3 ) トートロジー それに含まれる原子式の真理値の取り方に関係なく常に 1 となる式。 事実式 それに含まれる原子式の真理値の取り方によって 1 にも 0 にもなる式。 矛盾式 それに含まれる原子式の真理値の取り方に関係なく常に 0 となる式。 トートロジーはその別名を , 「恒真式」 , 「真理関数的に妥当な式 (truth-functionally valid wff) 」 トートロジーと事実式をあ などとも言われる。矛盾式の別名としては「恒偽式」がある。また , る式を含んでいる。 わせたカテゴリーは , つねに 1 になるかどうかはともかくとして , とにかく 1 になることができ このカテゴリーを充足可能式と言う。 誦理 充足可能式 satisfiable wff. 式 トートロジー tautology 事実式 contingency 充足不可能式 矛盾式 inconsistent wff.