A. A little bit of mathematics 現れない実数である。このことは , I と自然数全体の集合の間に全単射が存在するとした仮定が誤 りだったということを示している。■ この証明法は対角線論法 (diagonalargument) と呼ばれている。また , 川 = 訳ーであること も簡単に証明できる。これにより■ < 川司であることがわかった。つまり実数全体は 自然数全体よりもずっとたくさんあるということだ。 R の濃度沢一を連続体濃度と言う。 いくらでも大きな濃度がある 以上によって , 無限集合に少なくとも 2 つのサイズがあることがわかった。これは或る意味で はびつくりするような発見だった。というのも , 「無限とはそれ以上大きなものがないことだ」 と思っている人には , 無限にも大小のサイズがあるというのはほとんど理解しがたいことに思え るからだ。しかし , 実のところ , 無限には 2 つのサイズどころか無限にたくさんのサイズがある ことが言える。 363 【定理 64 】 A を任意の集合とすると , A のベキ集合の濃度田 ( A 刃は A の濃度よりも大き い。つまり , 田 ( A 刃 【証明】 ( 1 ) x e A とする。 x に (x) を対応させる 1 対 1 対応を考えると , これは A から P(A) の部分集合 への 1 対 1 対応を与える。したがって , 田 ( A 月剳である。 ( 2 ) 次に , P(A)—A でないことを言えばよい。そこで , P(A)—A が成り立っと仮定する。すると , A から P(A) への上への 1 対 1 対応中 : A P(A) があるはずだ。そこで , この中を使って , 次のような集合 B をつくる。 集合 B は A の部分集合であるから , B e P(A)O したがって , (b(b) = B なる b e A が存在す この b は B の要素なのだろうかそうではないのだろうか。 ( i ) そこで , be B としてみよう。このとき , b は B の定義式をみたすゆえ , b Q(b) である。 ところが , (b(b) = B なのだったから , このことは b& B ということである。矛盾。 (ii) そこで b& B としてみよう。このとき , B =<)(b) ゆえ bG (l)(b) である。したがって b は B の定義式である xæq)(x) を満たすゆえ , beB である。これも矛盾。 したがって , そもそもの仮定が間違っていた。つまり , P ( A ) ~ A が成り立っとしたのが間違っ ていたことがわかった。 ( 3 ) 以上 ( 1 ) と ( 2 ) より , 田 ( A 月である。ー この定理が示しているのは , ベキ集合をつくるという操作を使えばいくらでも濃度の大きな集 合をつくることができるということだ。 例えばく P ( N 月く P ( P ( N 川 < 田 ( P ( P ( N ) 川 < ・・・という具合にいくらでも大きな濃度を 考えることができる。自然数全体の集合は可算集合だが , N のすべての部分集合を集めた集合

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 論理式の真偽は解釈で決まる げていくというやり方をとって説明しよう。

96 第 I 部論理学をはじめる いう規則に従ったものと考えることができる。 A V B A B この規則を [ ⅵとする。 ( 4 ) 5 行目までのばしたところで , 右の経路には , Q と¯IQ とがともに現れる。ある論理式 とそれを否定したものとが両方とも 1 つの経路に現れるということは , この経路に含まれる論理 式を一斉に 1 にする真理値割り当てが存在しないということだ。タブローは , 上に書いた式が 1 になるためにはどのような式が 1 にならなければならないかを順々に分解して下に書き足して いったものだから , 与えられた式集合を充足する真理値割り当ての探求は , 少なくとも右の経路 では失敗に終わったということが示されている。そこで , x を書いたのだった。これも , 次のよ うな規則にしたがって x を書き込んだのだと考えればよい。 1 つの経路に , ある式とその否定が ともに現れたなら , その経路の末端に「 x 」を書き込めという内容の規則だ。 ↓ ( 5 ) この段階で左側の経路は , { ー 1 ( P △ Q ) , (PVQ)A•Q, PvQ, -•Q, P) という具合に のびてきている。この経路を充足する真理値割り当てがあるかどうかはまだ未知数だ。そこで , この経路に含まれる¯•(P △ (Q) が 1 になるにはどうでなければならないかを考えて , 6 行目で さらに枝分かれさせた。これは 1 行目に次のような規則を適用したと考えればよい。 ヨ A △ B) な展開規則を用意しておく必要があるだろうか。もともとが , A * B という形の式が 1 のときと 以上で取り出した [ △ ] , [ ⅵ , [ x ] , [ △ ] などの規則を展開規則と呼ばう。他にどのよう 展開規則と判定基準 判定する。 わった。そこで , 与えられた式集合を充足する真理値割り当ては存在せず , 矛盾していたのだと こうしてすべての経路で , 与えられた式集合を充足する真理値割り当ての探求が失敗に終 ので , ( 4 ) と同様に x をつける。 Q } である。いずれもある論理式とそれを否定したものとがともに現れている (Q)A¯•Q, P\/Q, ¯IQ, P, P } であり , 真ん中の経路は { ( P △ Q ) , (PVQ)A•Q, P\/ ( 6 ) 規則 [ △ ] をあてはめた段階で経路は 3 本になっている。左の経路は { ( P △ Q ) , (P を示したものと考えてよい。この規則を [ △ ] と名づける。 であるから , この規則も上段に書いた式が 1 になるにはどのような式が 1 にならねばならないか ¯I(A △ B) が 1 A △ B が 0 A, B のいずれかが 0 ¯IA が 1 または¯IB が 1 ,

第 12 章古典論理にもまだ学ぶことがたくさん残ってる タブローもそのまま使える 321 関数記号を含む論理式にタブローの方法を当てはめるときには規則を変更しなければならない ところはほとんどない ( ただし , 展開規則を当てはめる順序については特別の約束事が必要になる ) 。 また , 関数記号を含む言語に対してもタブローの方法で得られた判定結果はやはり信用がおける [ 1995 ] がわかりやすく ものであることが証明できる。こうしたことがらについてはジェフリー 解説してくれている。 12.1.2 FOL のセマンティクス に意味づけを行う部分を追加することだけである。 V は関数記号に D 上の n 変数関数を割り当てる。すなわち , D ( ただし , 関数 / は IY のすべての要素に V ( グ ) = 次のような関数 / , すなわち / : D 。 対して定義されているものとする ) これにともなって , アサインメントの定義もちょっとした変化が生じる。 FOL には項として は関数記号を含む複合的な項もある。そこで , 個体変項へのアサインメントびを拡張してびを 定義し , 個体変項だけでなく , これらの複合的項への割り当てもやらせることにしよう。 【定義】 FOL のあらゆる個体変項について論議領域 D の個体を割り当てるアサインメント びが与えられているとしよう。このとき , びの拡張び : T—>D ( ただし T は FOL でつくる ことのできるすべての項の集合 ) を次のように帰納的に定義する。 ( 1 ) 個体変項穹については , び ( の = び ( の , つまりもともとのアサインメントに一致す 次に FOL のセマンティクスを与えておこう。ここでやるべきことは関数記号とそれを含む項 ( 2 ) 個体定項については , の = V ( の ・ , 了 h が項 , ゲが n 変数関数記号であるとする。 ( 3 ) 了 1 , 了 2 , び ( 了 1 了 2 ・・・了。 ) = v ( 〆 ) ( び ( 了 1 ) , び ( 了 2 ) , このとき , こうして , アサインメントびとその拡張が定義できた。セマンティクスの次の仕事は , 個々の論理式 A に対して , 「モデル M はアサインメントびによって A を満たす」ということが どういうことかを定義することだ。この充足関係が定義できると , 閉論理式 A に対して「 A は モデル M のもとで真である」が定義され , また , 妥当式 , 論理的帰結 , 論理的同値などといっ た概念が次々に定義されていく。 旨を FOL に拡張しても , ' この部分は全く変更なしにそのまま使える。 うれしいことに 「コロロ ただし , 定義の中に出てくる「項了」の中に , 複合的な項も含めて考えることになったというだ けの違いだ。

298 第Ⅳ部論理学はここから先が面白い ! 進んだ話題のロードマップ さて , 古典論理を思い出せば分かるように 1 つの論理体系はセマンティクスとシンタクスと いう 2 つの視点から捉えることができる。そしてこ 2 つの視点を結びつけるのが完全性定理だっ た。したがって , 直観主義論理をもつばら自然演繹というシンタクス的な側面からだけ紹介する のは , 本当は片手落ちなのだ。直観主義論理にも立派なセマンティクスがある。それをちょっと だけ覗いてみることにしよう。 証明解釈とその限界 直観主義論理はどのような理由で排中律を拒否していたのかを思い出そう。それはヤン君が唱 えていたように , 我々には証明も反証もできないが「数の世界」では真か偽に決まっている , と 考えるのはおかしいのではないかという問題意識だった。つまり , 我々の認識能力とは無関係に 成り立っている真偽を考えるのは無意味であり , その事実を確認する方法 ( 数学で言えば証明 ) を持っているかどうかの方がずっと重要だと考えたわけだ。 このように直観主義論理は , 古典論理のセマンティクスが , 我々が知ろうが知るまいがおかま いなしに成り立っている「 A は真である」を基本概念に据えたのに対し , それを「 A を証明す る方法を持っている」に取り替えたセマンティクスをもっているはずだ。 直観主義論理のセマンティクスは 1931 年にハイティンクによってはじめて与えられた。それ は証明解釈 (proof-interpretation) と言われる。ハイティンクは次のように結合子の意味を与え 0 ( 1 ) ( 2 ) ( 3 ) A ▽ B : A を証明する方法をもっているか , または B を証明する方法をもっている。 A △ B : A を証明する方法をもっており , かっ B を証明する方法をもっている。 A → B : A の証明がかりに与えられたとしたら , それをもとに B の証明をつくりだす 方法をもっている。 ( 4 ) -•A : A の証明が与えられたと仮定し , それをもとに矛盾を導き出す方法をもってい 証明解釈を使うと , 直観主義論理での禁じ手がなぜ禁じられるべきだったのかがわかる。 ( 1 ) 排中律 : A \/ —•A を証明解釈で考えると , 「 A を証明する方法をもっているか , または A から矛盾を導き出す方法をもっている」になる。したがって , 排中律は , どんな命題も証明か反 証する方法をもっているということを意味することになる。これは我々には不可能だ。 ( 2 ) 背理法 : ¯IA から矛盾をみちびくことができたとしても , 直接に A を証明する方法が手 に入ったわけではない。これはヤン君も強調していたことである。例えば A が「しかじかの条 件を満たす数がある」という命題だとする。「そういう数がないと仮定するとおかしなことにな るから , どの数がそれなのかはわからないけどそういう数はあるはずだ」という議論を彼は認め ない。ャン君が A を認めるのはそうした条件を満たす数を実際に構成してみせることができた とき , あるいは少なくとも , こうすれば条件を満たす数がいつでも見つかるというアルゴリズム をもっているとき ( そのアルゴリズムの実行にヤン君の一生では時間が足りない場合でもよしとする ,

B. 練習間題解答 387 さて , ここでび ' / x ( x ) = 1 となる変種び・ / x を考えれば , び '/x ( x ) = le { 1 } = VM ( P ) だから , ( iv ) の右辺 は成り立つ。したがって VM,6 ・ ( ヨ xPx) = 1 , つまり M はび・によってヨ xPx を満たす。・ = 1 ( c ) の説明 : 明らかに 2e { 2 } も le { 1 } も成り立つから VM , び ( Qy △ Pa ) = 1 である。 VM(P) 2e { 2 } かっ le { 1 } ・・ VM,6(QyAPa)=1 VM,6(Qy)=l かっ VM,6(Pa)=1 6(y)eVM(Q) かっ 5(a)=V(a)e ( a ) の説明 : 39 ( 1 ) (a) 満たす ( 充足する ) (b) 満たす ( 充足する ) (c) 満たさない ( 充足しない ) ここでび / x ( x ) = 2 となる x 変種び / x をとれば , ( i ) は成り立たない。したがって VM , び ( ▽ xPx ) びのあらゆる x 変種び / x について , 5/x(x)eVM(P)={1) ・ VM,6(VXPX)=1 びのあらゆる x 変種の x について , VM,Øx(PX)=I ではない。 ( 2 ) (a) 満たさない ( a ) の説明 : (b) 満たす (c) 満たさない VM,6(QyAPa)=1 VM,5(Qy)=1 かっ VM,6(Pa)=1 6'(y)eVM(Q) かっ c'(a)=V(a)eVM(P) le { 2 } かっ le { 1 } こんどは明らかに le { 2 } は成り立たないから , VM , び ( Qy △ Pa ) = 1 ではない。 VM,6(PX)=I でないか VM , び ( Px ) = 1 であるか・・ VM,6()X → (x)= 1 ( 2 ) 任意のモデルとそれに基づく任意のアサインメントびとを考える。このとき , ンメントは , Fx も満たす。したがって , 前者は後者を論理的に帰結する。■ VM,6(FX)=I かっ VM,6(Gx)=1 VM,6(Fx)=l ゆえ , FxAGx を満たす任意のモデルとアサイ 41 ( 1 ) 任意のモデル M と任意のアサインメントびとを考える。このとき , VM,6()X △ (x) = 1 ば , 5/X(X)eVM(Q) とできるから , ( i ) は成り立つ。したがってこの式はこのモデルで真である。・ こで , いかなるアサインメントびが与えられたときでも , c/x(x) = ◆となるような変種をとれ どんなアサインメントびにも , VM, の x(Qx) = 1 となる x 変種がある・ ( 2 ) VM( ヨ xQx) = 1 すべてのアサインメントびについて , VM,6( ヨ xQx) = 1 V ( a ) = ・なのだから , び ( a ) eVM ( P ) はつねに成り立つ。したがって Pa は真である。■ こで , どのようなアサインメントについても 6(a) = メントびについて , 6(a)eVM(P)={ 40 ( 1 ) VM(Pa) = 1 すべてのアサインメント 5 について , VM,6(Pa) = 1 すべてのアサイン いかが決まってしまうようだ。 どうやら , 閉じた式は , モデルが決まりさえすればアサインメントによらず満たされるか満たされな ある。だから , このモデルでは V xPx はいかなるアサインメントによっても満たされることがない。 考えることになる。このうち x に 2 を割り当てる x 変種 c/x については , つねに 5/x(x) VM(P) で ても , このモデルではびの x 変種 c/x としては , x に 1 を割り当てるものと 2 を割り当てるものを は Pa はいかなるアサインメントによっても満たされる。また , どんなアサインメントびから出発し c'(a) = V(a) であって , 個体変項 a にはつねに同じ個体 1 が割り当てられる。だから , このモデルで れに関わりなく決まるのではないかと予想がっく。実際 , どんなアサインメントダを考えても , るが , 閉じた式 ( b ) や ( c ) が満たされるかどうかは , アサインメントがびであろうがダであろうが , そ 以上の ( 1 ) と ( 2 ) の結果から , 開いた式 (a) はアサインメントが異なると充足されたりされなかったりす

第 3 章人工言語に意味を与える 55 あった。我々は結合子の意味を真理表で与えたが , そこでは図式文字 A, B を使って , どんな 論理式にも適用できるように , しかも繰り返し使えるような形で与えてあった。だから , 第 3 列 で P と Q の真理値から P → Q の真理値を求めるときにも , 第 5 列で , PA(P → Q) と Q の真理値 から , ( P △ ( P → Q ) ) → Q の真理値を求めるときにも , 同じ→の真理表を参照してそれを行うこと ができたわけだ。 以上から分かったことをまとめると次のようになる。 ( 1 ) 真理値分析とは , 原子式への真理値割り当て ( 例えば P に 0 , Q に 1 , というような ) を 元にして , それを拡張して複合的論理式への真理値割り当て ( 例えば P → Q に 1 , p △ (p → Q) に 0 , (P △ (P → Q)) → Q に 1 というような ) を作り出す作業だと考えることができ る。 ( 2 ) なぜそのような拡張ができるかというと , 結合子の意味の定義を , どのような論理式に も何度でも適用できるような形 ( 図式 ) で与えておいたからである。 3.5.2 真理値割り当て さて , 以上の話を任意の論理式の真理値分析に当てはまるように述べてみよう。まず , P と Q 以外の原子式を含む論理式への真理値割り当ても扱えるように , 原子式をあらかじめ P と Q に 限定してしまうような語り方は避けよう。そこで次のように話を進めることにする。 【定義】 L の原子式からなる或る集合を F とする。 F に対する真理値割り当て (truth assign- ment) V を次のような関数とする。 v : F → { 1 , 0 } 数学的な表記法が出てきたからといって恐れる必要はない ( 関数については付録 A の 3 を見 よ ) 。ようするに , V は F に含まれる原子式のすべてに対し , それぞれ 1 か 0 を割り当てるその 割り当て方のことである。例えば , F= {P, Q, R) とするとき , P には 1 , Q には 0 , R には 1 と 割り当てることにすると , 1 つの V が決まる。このときは V(P) = 1 , V(Q) = 0 , V(R) = 1 と書 こう。このような V は何種類もある。 P には 0 , Q には 1 , R には 1 と割り当てるのだとする と , 別の V が決まる。そうすると , 真理表の 1 行 1 行がそれぞれ異なる V に対応していること がわかる。こうした関数 V を付値関数 (valuation function) と呼ぶこともある。 さて , まとめの ( 1 ) により , 真理値分析でやっていたことは , うんと一般化して言えば , 原子式 の集合 F への真理値割り当て V が 1 っ与えられたときに , F に含まれる原子式から帰納的に定 義される論理式全体の集合に対する真理値割り当てを V から派生させる , ということなのであ る。もう少しちゃんと述べておくと・・

第 1 章 What is THIS Thing called Logic ? I I ・論証 1 は真の命題のみを前提する妥当な論証だから成功している。だから , この論証はユ アンがジョージ・ルーカスのことを知っていると考える根拠を与えてくれる。 ・論証 2 は妥当な論証だが前提に偽の命題が含まれている。 ' こには事実の間違い ( 事実誤 認 ) が含まれている。したがってこの論証は成功していない。結論は信用しない方がよ ・論証 3 は前提はすべて真の命題からなるが , 論証じたいは妥当でない。ここには諞理上の 間違い ( 誤謬推論 ) が含まれており , したがって論証としては失敗している。だから , 確 かにこの論証の結論は正しいんだけれども , それはいわばまぐれ当たりであって , 結論を 信じたり主張したりする根拠にこの論証は使えない。 そして , 論理学が扱うのは , 論証が ( 1 ) の意味で正しいかどうか , つまり論証が妥当かどうかと いうことに限られる。論証が ( 1 ) 十 ( 2 ) の意味で正しいかどうか , つまり成功しているかどうかを判 定するには , 事実についての知識 , 例えば映画界についての知識が必要になり , これは論理学者 の守備範囲を超えている。だから , 論証が ( 1 ) 十 ( 2 ) の意味で成功しているかどうかを判定すること は論理学にはできない相談だ。もしそれが論理学の役割だったならば , 論理学者は , すべての学 問分野とすべての情報に通じていなければならないことになる。だとしたらだれも論理学者にな れないだろう。 しかしまだ次のような疑問が残ってしまう。 「前提がすべて真で , しかも妥当であるような論証が成功した論証なのだとすると , 成功した 論証であるための条件の半分に過ぎない妥当性だけをとりだして研究するのは何のためなんだろ う。ばくたちが実生活で関心を持つのは論証が全体として成功しているかどうかなんだから , そ の中の妥当性のところだけを取り出して研究して何になるんだ ? 」 この疑問は , 論証や推論を行う目的が , すでに真だと分かっていることがらから , 別の真なる 命題を導くことだけにあるとするなら , たしかに正しい。しかし , 我々が論証・推論を行う目的 はそれだけではない。次の例を考えてみよう。 ェニシダというマメ科の観葉植物がある。その名前からェニシダはシダ植物だと思いこん でいるマサヨシと , 思い違いを正そうとしているテルヲの会話。 テルヲ : じゃ , 君の言ふとおり , ェニシダはシダ植物だとしよう。シダ植物は胞子で増え るから花を咲かすことはあるまい。といふことは , ェニシダも花を咲かさないはず ではないのかね。 マサヨシ : 嗚呼。これはしたり。拙宅のェニシダはいま花盛りである。ということは , あ れはシダではなかったのか ! ここでテルヲはマサヨシに対して次のような論証をやってみせている。

第 3 章人工言語に意味を与える 49 れかが現実だ。今の場合は ( 2 ) が現実。さて , 各たれ込み屋の発言は 4 つの可能性のうちどれが現 実であるかについて語っているものと理解できる。たとえば , スティルスは , ( 1 ) と ( 2 ) のいずれか が現実だと言っている。ナッシュは , ( 2 ) の可能性だけが現実なのだと言っている。これは , ス ティルスの発言に比べて , 4 つの可能性のうち現実に生じているのはどれかをよりよく特定して いる。つまり , ナッシュのたれ込みは , 現実がどのようであるかについて , スティルスより多く の情報を伝えている。一方 , クロスビーは , 現実が ( 1 ) か ( 2 ) か ( 3 ) のどれかだと言っているわけで , 犯人の特定にあたって , より不確定だ。というわけで , 可能性を 1 つに絞っているナッシュの発 言が最も情報量が多く , 価値のある情報なのだと言える。 そうすると , ャングのたれ込みが無価値なのはなぜかがよくわかる。ャングは現実は ( 1 ) か ( 2 ) か ( 3 ) か ( 4 ) のいずれかだと言っているわけだ。ところが「 ( 1 ) か ( 2 ) か ( 3 ) か ( 4 ) 」というのは , 考えられる すべての可能性じゃないか。つまり , これは現実がどのようであるかについて何も語っていない ということだ。ャングのたれ込みは現実についていかなる情報ももたらしていない。 トートロジーは現実のあり方によって覆されることがない。それはトートロジーが確実なピカ ピカの真理だからと言うよりは , そもそも反証されるようなことがらを何も語っていないからで ある。つまり , トートロジーは無内容なのだ。これに対し , スティルスの発言は , もし現実が ( 3 ) だったら , その現実によって覆されて偽になってしまう。それは , スティルスの発言が「現実は ( 1 ) か ( 2 ) だ」という内容を持っていて , 現実はこうだ ! と語っているからだ。現実がこうだと語っ ているからこそ現実がその通りでなかった場合には偽になってしまうのである。 なーんだ。トートロジーなんて無内容で情報量 0 でつまらないものじゃないか。なんでまた , ・・うーん。確かに , 世界のありさまにつ 論理学はこんなつまらないものに関わるんだろう ? いて何か実のあることを言いましよう , とか , 世界について何か新しいことを知りましようとい うようなことがらにたずさわっている限り , トートロジーは何の価値もない。トートロジーが注 目に値するのは , それが論理学で果たす役割のおかげだ。これから見るように トートロジーは 論理学のあちらこちらに顔を出す。すでに強調してきたように論理学は , 内容は忘れて形式に注 目するという性格を持っている。このため , 「内容によらず形式により真である」というト 3.4.1 論理的同値性の定義 3.4 「何だ , けっきよく同じことじゃない」を捉える一一論理的同値性 ロジーの性格はまさに論理学の核心に触れているわけだ。 えるのと , ( 2 ) 「火曜じゃなかったら水曜日だ」と答えるのでは結局同じことだと思うだろう。そ げーっ。来週のいつですか ? 」この質問に意地悪な教師が , ( 1 ) 「さあね。火曜か水曜だよ」と答 式だけに成り立っことではない。次の例を考えてみよう。「来週論理学の試験をします。」「げ Ae → B は (A → B) △ (B → A) の略記と考えてもよいと述べた。こうした関係はこの 2 種類の論理 双条件法を導人した際に , A ( → B の真理表と ( A → B ) △ ( B → A ) の真理表は同じになるから ,

第 3 章人工言語に意味を与える 59 な真理値割り当て V が 1 つでもあるとき , V は r を充足する , とかは充足可能 (satisfiable) あるいは整合的 (consistent) であると言う。 日常的には , P と言ったそのロでと言ったりすると矛盾していると言われることが多い ようだ。たしかに , 矛盾した集合のうち最も簡単なものは {p, p } だけれど , このように矛盾 している集まりがいつもある式とその否定とのペアを含んでいるとはかぎらない。上で例として 扱った 4 つの式からなる集合が良い例だ。 論理式の無限集合 論理式は無限にたくさんある。だから論理式の集合には無限集合になっているものもある。例 えば , P を偶数回否定してつくることのできるすべての論理式の集合△ = { p , P, P, ・・・ } などというものを考えることができる。そして , ' こでの矛盾や充足可能 性の定義は , が有限集合でなくてはならないなどという条件は要求していなかったから , っ した無限集合にもそのまま当てはまるものと考えてよい。例えば , この△は充足可能であるが , △にさらに P を加えたもの , つまり△ IJ { P } は矛盾している ( この記号が分からない人は付録 A の 2 を見よ ) 。今後は , 「論理式の集合」という表現があった場合 , 特にが有限集合である という断り書きのない場合は , r が無限集合の場合も考えに入れているものと理解しよう。 練習問題 12 ( 1 ) 次の論理式の集合は矛盾しているか , それとも充足可能か。真理表を書いて確かめてみよう。 (a) {P → Q, ーー・ nQv R, R →•P) (b) {P → (Q → R), P → Q, •R) ( 2 ) 次の論理式の集合が矛盾しているか充足可能かを判定し , それを証明せよ。 (a) 原子式 P と Q からっくることのできるあらゆる論理式の集合 (b) 原子式 P と Q から結合子△だけを使ってつくることのできるすべての論理式の集合 ( 3 ) 次のことを証明せよ。 r が矛盾しているなら r()J △も矛盾している。つまり式をつけ加えても矛盾は解消できない。 3.6.2 Knight and Knave 有名な論理パズルに「騎士と悪党」というものがある。騎士はつねに正直に語り , 悪党はつね に嘘をつくものとする。さて , 道を歩いていると何人かの人に出会った。彼らはそれぞれ騎士か 悪党かのいずれかなのだが , それは君には分からない。そこで君は彼らに質問し , 答えをヒント に出会った相手がそれぞれ騎士なのか悪党なのかを当てる , というパズルだ。 【例題】君は a と b に出会った。君の質問に対し , a は「私は悪党だが b は騎士だ」と答え た。さて a と b はそれぞれ悪党か騎士か ? 【解答】せつかく真理表を使えるようになったのだから , このパズルも真理表を使って解い