論理学をつくる 第1部論理学をはじめる 読書メモ

論理学をつくる 第1部論理学をはじめる 読書メモ

論理学は、人間が考える方法や議論の方法について研究する学問分野であり、特に、命題や推論に関する基本的な概念を扱うものとなる。

論理学の基本的な概念として、命題や命題論理、論理学の記号体系などがある。命題とは、真偽が決まる文句であり、真か偽かが確定するものとなる。命題論理は、命題を扱う論理学の分野であり、論理的な関係を表すための論理演算子が用いられる。論理学の記号体系は、論理的な演算を表すための記号を定めた体系であり、命題論理においては「否定」「論理積」「論理和」などの論理演算子が用いられる。

論理学には、命題論理以外にも、一階述語論理や高階論理などの分野もある。一階述語論理は、命題論理に述語や変数を導入することで、より複雑な論理的な関係を表現することができるものとなる。高階論理は、集合や関数などの数学的概念を含む論理を扱うものとなる。

論理学には、命題の真偽を決定する方法や、正しい推論を行うための方法についても研究されている。例えば、命題の真偽を決定する方法として、真理値表や証明という方法がある。真理値表は、命題に対して全ての可能な真偽の組み合わせを試して、命題の真偽を決定する方法となる。証明は、命題が正しいことを示すための論理的な手順であり、公理や推論規則を用いて、命題の真偽を導き出す。

また、論理学を学ぶための基礎的な理論としては”集合論の概要と参考図書“に記載している集合論がある。

論理学は、哲学や数学、人工知能などの分野にも深く関わっている。哲学においては、論理学の概念を用いて論理的な議論を行い、数学においては、論理学を用いて数学的な命題を導出するための基礎的な体系を構築する。人工知能においては推論技術や知識情報処理技術のベースとなっている。

今回は数理論理学の著名な教科書である「論理学をつくる」より、読書メモを示す。

まずは第1部第一部論理学をはじめるについて述べる。

はじめに

第Ⅰ部　論理学をはじめる

第1章　What is THIS Thing called Logic?
1.1　論理とは何か？　そして論理学は何をするのか

1.1.1　どのようにスタートを切るかが実は難しい
1.1.2　論理学の３つの顔
論証の正しさについての学としての論理学
出てくる(flow)とか出てこないという概念が論理学の第一の主題
論証(argument)、推論(inference)
しかじかの前提から、かくかくの結論が出てくるのはどういうことか?
論理的帰結(logical consequence)という概念の研究が論理学
正しい論証とは何か、正しい論証とそうでない論証とをどのように区別するのか　につついての系統的な研究
命題・文・考えの集まりとしての論理学
論理的に見てどうこうということが問題になる場面以外
論理学の第二の主題
「矛盾している(inconsist)」とかしていないとかの概念
矛盾は、いくつかの文(主張)の集まりについて言われる
いくつかの文の集まりがいっぺんに成り立つとき、その集まりは無矛盾だとか整合的だ(consistent)と言われる
2つの顔は一つである
論理学の持つ2つの課題は実は同じ事柄の裏表
形式的真理としての論理学
「〜は…であるかないかのいずれかである」という形をしているだけの理由で正しい
形式的真理とは何か、ある文が形式的真理であるかないかを判定するにはどのような方法があるか」を体系的に研究するのが、論理学の第三の目標
論理学の目標と本書の戦略
3つの重要な概念について説明
1.1.3　論理学っておもしろいんだろうか？
論理学は何をもたらしてくれるのか
連濁
規則によって二つの言葉が繋がって、濁音になったりならなかったりする
自分が使っていても規則がわからない
これまで出会ったことのない全く新しい組み合わせが所依寺たときにも、ごく自然に濁るか濁らないかの区別かできる
論理学の不思議な身分
ウェイソンとジョン・レアードの研究
(1)フォックスが信用できる男ならUFOは存在する。フォックスは信用できる男である。よってUFOは存在する
(2)フォックスが信用できる男ならUFOは存在する。UFOは存在しない。よってフォックスは信用できる男でない
(1)も(2)も論証としては正しい
人は(2)の論証の正しさの判定をするのに(1)よりも格段に下手になる
どのようなメカニズムにより推論を行っているのか
論理の正しさを認識する心の仕組みがどのようになっているのか

1.2　論理の正しさをどこに求めたらよいか

1.2.1　論証の正しさを命題の真偽と区別しよう
論証の正しさと命題の真
例
1+1=2 ボスニア・ヘルツ後ビアの首都はサラエボである イソギンチャクは咽調動物である
3つの命題はどれも真
しかし、論理的には出てこない
論証の正しさと、命題の真偽は区別した方が良い
偽の命題が含まれていても、論証としては正しいことがある
真の命題だけからなっていても、論証としては間違いということもある
命題には「真(true)/偽(false)」
論証の正しさには「妥当である(valid)/非妥当である(invalid)」
1.2.2　成功した論証と言えるためには
論証の結論を信頼して良いのは以下の時
論証が妥当であり
なおかつその前提が全て真である
なぜ論証の妥当性だけを取り出して研究するのか
論証や推理を行う目的が、 すでに真だとわかっている事柄から、 別の真なる命題を導くことだけではない
1.2.3　論証の正しさはその形式で決まる
とりあえず確認しておくこと
命題の真偽と区別された論証の妥当性の正体は一体何?
前提が全て真なのに結論が偽になるケースはあり得ない
言い換えれば、前提が実際に真であるかどうかはともかく
仮に前提が全て真であるようなときには、全体に結論も真である
論証の妥当性は論証の内容ではなく形式に関わる
妥当な論証と非妥当な論証を厳密に区別するには論証のどこに注目すれば良いか
〇〇はすべて■■である ■■はすべてXXである ————————- 〇〇はすべてXXである
1.2.4　論証の形式に関わる語とそうでない語
論証の妥当性は、 そこに現れる「すべて」「でない」「または」「ならば」「Every」などの 語の意味だけによって決まるのであって、それ以外の語の意味には無関係である
論理定項(logical constant)
論証の正しさに直接関わってくる「すべて」「でない」「または」「ならば」「Every」などの語のこと
3つのグループに分類することができる
否定項
「でない」
接続詞
「または」、「ならば」
量化詞
「すべて」「Every」「a」

第2章　論理学の人工言語をつくる
2.1　自然言語から人工言語へ

2.1.1　論理学が人工言語を使うわけ
現代の論理学は、記号論理学(symbolic logic)と呼ばれる
人工言語(artificial language)を利用
自然言語では命題の論理形式が文法形式に覆い隠されてしまうことがある
2.1.2　どのように記号化を進めようか
例
トムは今の蚤取りか昼寝をしている トムが今昼寝をしているのならばジェリーも今昼寝をしている ジェリーは昼寝をしていない —————————————————————— トムは蚤取りをしている
「ジェリーは今昼寝をしている」をPに置き換える
トムは今の蚤取りか昼寝をしている トムが今昼寝をしているのならばP Pでない —————————————————————— トムは蚤取りをしている
「トムは今昼寝をしている」をQに置き換える
トムは今の蚤取りをしているまたはQ QならばP Pでない —————————————————————— トムは蚤取りをしている
「トムは今蚤取りをしている」をRに置き換える
RまたはQ QならばP Pでない —————— R
単純命題と複合命題
肯定形の短文で表される命題が形式かの最小単位とされる
P,Q,R
最も単純な命題
3つの前提はぞれぞれ、2つの命題が「または」「ならば」 のような接続詞でくっついたもの、 または一つの単純命題に「でない」がくっついたものになっている
単純命題を構成要素として作られたより複合的な命題
何を単純命題とするかは、 どのような論証を相手にして、 どのような形式を取り出そうとしているのか、 に応じて異なってくる
2.1.3　論理式と論理結合子
「か」、「あるいは」「差もなければ」、「or」は役割は同じ
同様に
「ならば」
「でない」
例の最終的表現は
RⅤQ Q→P ¬P ——– R
論理的構造
それぞれの命題を記号化したものを論理式 (well-formed formula, 略してwff)
単純命題P,Q,Rを「原子式(atomic formula)」と呼ぶ
論理結合子
接続詞や否定詞を記号化したもの
andとbutの違い?
「xxであり、しかもxxである」と「xxであるにもかかわらずxx」は同じ「Λ」
ただし文中に込めた感情的な意味は異なる
記号論理ではそれらを排除する
真理関数的結合子
自然言語には2つ以上の命題をつないで複合的な命題を作る方法が他にもたくさんある
because(ので)は全体の真偽が構成要素である単純命題の真偽よって一通りには決まらない
なのにどうして「かつ」「または」「ならば」「でない」の4つの限るのか
「かつ」とか「でない」といった結合子は「真理関数的(truth-functional)」という

2.2　人工言語L

2.2.1　なぜ人工言語をきちんと定義すべきなのか
もっともな疑問
目的は、論証の妥当性を明確にするという目的に適した人工言語を作ること
L(logic)の語彙と文法とは?
論理学は普遍的な研究であるべきだ
2.2.2　人工言語Ｌの定義
人工言語を定義するとき
その言語で使われる語彙の範囲を確定し
Lの語彙
Lで用いられる語彙は、3つのグループに分かれる
(1)原子式
P,Q,R,…
(2)結合子
→,Ⅴ,Λ,¬,…
(3)補助記号
(,)
次にその語彙をどのように組み合わせると その言語で許される複合的な表現が得られるかについての規則、 つまり文法を定める必要がある
Lの文法、すなわち論理式の定義
(1)原子式、すなわちP,Q,R,…は論理式である
(2)A,Bを論理式とすると(AΛB),(AⅤB),(A→B),(¬A)は各々の論理式である
(3) (1),(2)によって論理式とされるもののみが論理式である
帰納的定義
回帰的定義
上記がどうして論理式の定義なのか
形成の木
1
2
AやBはなんだろう
メタ論理的変項 (meta-logical variable)
もう一つの帰納的定義の例
数列の漸化式
2.2.3　論理式を帰納的に定義することの意味
数学的帰納法による証明
帰納的に定義された対象に関しては、独特な証明方法を用いることができる
帰納的定義の最大のメリット
式の長さについての機能法による証明
2.2.4 Unique Readabilitiy Theorem
2.2.5　論理式の形に関するいくつかの用語
2.2.6　シンタクスとセマンティクスを区別しよう

第3章　人工言語に意味を与える —— 命題論理のセマンティクス
3.1　結合子の意味と真理表

はじめに
論証の正しさは結合子(論理定項)の意味に関係がある
3.1.1　「かつ」の意味を示す真理表
「ヴァネッサは芝居がうまい、かつ、ヴァネッサは歌がうまい」と言う命題について
上記の複合命題の真偽が、2つの原子命題の真偽とどのように関係しているのか?
真理表(truth table)で考える
2価原理
本書では、真理値を真と偽の2つに限定して
論理式は全て、 常に真・偽いずれかの真理値を待つ」 と言う2値原理(principle of bivalence)を採用する
多値原理(many-valued logic)
真・偽の他に、「どちらでもない」とか「わからない」と言った真理値を考えて2つ以上の真理値を持つ論理学
3.1.2　他の結合子の意味も真理表で与えることができる
真理表1
真理表2
2種類の選言
「Ⅴ」についての疑問
日本語の「または」どちらか一方だけを意味することが多い
排他的選言(exclusive disjunction)
AⅤBは、AとBが両方とも真になる場合も含む
非排他的選言(non-exclusive disjunction)
「選言」では非排他的選言を意味するものとする
→について変だなぁと思うあんたは偉い
条件「→」を定義する真理表を見る
「AならばB」は
AとBが共に真の時は真
Aが真でBが偽のときは偽
前件Aが偽のときは、後件Bが真偽に関わりなく真
直感的に変
AならばBという使い方は、AとBに何らかの内容上のつながりを期待する
Aじゃないと言う前提で考えることはあまりない
真偽表での「→」に意味を与えようとする限り
内容のつながりは無視して、真理値の組み合わせだけでことを勧めるしかない
真理値の組み合わせだけで「ならば」を 近似しようとすることにそもそも無理がある
以下の2つを考慮するのがベストな選択
論理学の規定された目標に役立つ限りで「ならば」を近似すれば良い
真理値の組み合わせだけで、しかも2値原理を満たす仕方で「ならば」を近似せねばならないと言う制約条件
インチキ臭い説明
父親が子供に「今度の算数のテストで100点を取ったら、ファミコンを買ってあげる」と約束した場合
100点をとり、ファミコンを買ってもらう
父親が約束を守った
100点を取ったが、ファミコンを買ってもらえない
父親が約束をやぶった
100点を取らなかったが、ファミコンをかってもらった
約束を破っていない
約束を守った
100点を取らなかったが、ファミコンを買ってもらえない
約束を破っていない
約束を守った

3.2　論理式の真理値分析

3.2.1　真理値分析のやり方
真理表を使って結合子の意味を定義すると、 どんな論理的についても、それがどんなときに真になるのか (その論理式の真理条件(truth condition)と言う)を分析できる
3.2.2　新しい結合子を追加する
双条件(biconditional)
A, if and only if B
(A→B)Λ(B→A)と真理表はおなじ
日常生活では「ならば」で済ませている
「明日までに1億円用意できなかったら息子の命はないと思え」
一億円用意したのに(偽)、息子が殺されたら(真)、嘘つきめ(偽)と罵る

3.3　トートロジー

3.3.1　トートロジーとは何か
論理式は、 どのような場合に真になるかによって3種類に分類できる
トートロジー
それに含まれる原子式の真理値の取り方に関係なく常に1になる
事実式
それに含まれる原子式の真理値の撮り方によって1にも0にもなる式
矛盾式
それに含まれる原子式の真理値の撮り方に関係なく常に0となる式
充足不可能式
トートロジーと事実式は、常に1になるかどうかはともかく、とにかく1にらなることができる式を含んでいる
3.3.2　代表的なトートロジー
トートロジーは無数にあるが、 その中の代表的な幾つかのパターンには名前がついている
同一律(law of identity)
排中律(law of excluded middle)
2重否定律(law 0f contradiction)
巾等律(idempotent law)
変換律(commutative law)
結合律(associative law)
分配律(distributive law)
吸収律(absorptive law)
ド・モルガンの法則(Do Mrgan’s law)
対偶律(law of contraposition)
選言的三段論法(disjunctive syllogism)
推移律(transitive law)
肯定式(modus pones)
否定式(modes tollens)
拡大律(付可律)(law of addition)
縮小律(law of simplification)
移入律(law of importation)
移出律(law of exportation)
構成的両刀論法(constructive dilemma)
添加律
パースの法則(Perce’s law)
入れ替え律(law of permutation)
合成律(law of composition)
図式についての注意
上記のものは
それ自体がトートロジーであると言うよりは
トートロジーであるような論理式に共通した型
3.3.3　トートロジーってのは結局何なんだ
形式的真理としてのトートロジー
トートロジーとは
構成要素となる命題の内容によらず、その形式だけで真になるような命題
形式的に真になる命題(より正確には論理定理の意味だけによって真になる命題)
分析的真理と経験的真理
「真理」とは一口に言ってもいくつかの種類がある
例
(1)スパイク・リーが映画監督であるならば、スパイク・リーは映画監督である
(2)スパイク・リーが映画監督であるならば、スパイク・リーは映画を作る人である
(3)スパイク・リーは映画監督であり、自作のDo the lright thingではピザ屋の店員役で出演もした
(1),(2)は言葉の上だけで正しいことがわかる
必然的真理
(2)は言葉の意味を知って初めてできる
(1)つまりトートロジーは言葉の意味が必要ない
(3)は実際に調べないとわからない
実験や観察といった調査を通じて初めて知られる真実
世界の有様により真となる
世界のたまたまの事情により真になっている真理
トートロジーと情報量
トートロジーは現実がどうなっているかについて何も語らない

3.4 「何だ、けっきょく同じことじゃない」を捉える —— 論理的同値性

3.4.1 論理的同値性の定義
真理値が常に一致する場合
その論理式同士は論理的同値 (logically equivalent)であると言う
二つの論理式A,Bが論理的同値である
⇔
A,Bは、それを構成する原子式の真理値のいかなる組み合わせに対しても常に同じ値となる
〜⇔….
〜と言うのはつまり、次のことの手短な言い方(書き方)である。すなわち….
⟷と混合しないことに注意
A⫦⫣B
論理式A,Bが論理的同値であること
対偶(contraposition)
「A→B」と「¬B→¬A」
3.4.2　同値変形
論理式Aをそれと論理的に同値な別の論理式Bに変換すること
3.4.3　置き換えの定理
論理式全体の変形と、論理式の一部の変形とは、論理的に異なる
置き換えの定理 (replacement theorem)
論理式Aを何回か含む論理式を、C[A]と書く
C[A]の中のAを論理式Bで置き換えた結果をC[B]とする
このとき、 AとBが論理的同値なら、C[A]とC[B]も論理的同値である
ある式の一部をそれと論理的に同値な式に置き換えた結果は元の式と論理的に同値である
強い置き換えの定理
(A→B)→(C[A]→C[B})はトートロジーである
長い連言(選言)もゆるす!
Λが結合するのは一回につき2つの式に限られる
「AΛ(BΛC)」か「(AΛB)ΛC」のような形の式は論理式として形成されるが
「AΛBΛC」の形の論理式は形成されない
しかしながら、式の意味(真偽)注目している場面では「AΛ(BΛC)」と「(AΛB)ΛC」は区別されない
よって「AΛBΛC」の書き方を許す
同様に「AⅤBⅤC」も許す
ダメな例
「(A→B)→C」と「A→(B→C)」は異なる
A→B→Cのような書き方はしない

3.5　真理表を理論的に反省する

3.5.1　真理値分析とは何をやることだったのか
真理値分析とは
原子式への真理値割り当て(例えばPに0、Qに1、と言うような)をもとにして
それを拡張して複合的論理式への真値割り当て(例えばP→Qに1、PΛ(P→Q)に0、(PΛ(PΛQ)→Qに1と言うような)作り出す作業
なぜそのような拡張ができるかと言うと
結合子の意味の定義を、どのような論理式にも何度でも適用できるような形(図式)で与えておいたからである
3.5.2　真理値割り当て
以上の話を任意の論理式に当てはまるように述べてみる
定義
Lの原子式からなる集合をFとする
Fに対する真理値割り当て(truth assignment)Vを上記のような関数とする
Vを「付値関数(valuation function)」と呼ぶ
一般化した表現
原子式の集合Fへの真理値割り当てVが一つ与えられたとき
Fに含まれる原子式から、機能的に定義される論理式全体の集合に対する真理値割り当てをVから派生させる
Fに含まれる原子式からスタートして帰納的に定義される論理式の全てからなる集合をḞとする。 我々の目標は、Fへの真理値割り当てVを拡張して、このḞに含まれる各論理式に1か0を割り当てる 拡張版の真理割り当てṼ:Ḟ→[1,0]を得ることである
Vを拡張してṼを作るときに「辻褄のあった」仕方で作る必要がある
「辻褄のあった仕方」は結合子の定義が教えてくれる
論理式の真理割り当ての拡大が
論理式の帰納的定義と並行していることが重要
真理割り当ての一貫性
条件を満たすようにVを拡張してṼを作ったら
Ṽはありとあらゆる論理式に必ず0か1いずれかの真理値を割り当てるものになっている
定義
原子式への真理割り当てVが論理式Aを充足する(あるいはAはVのもとで真である、とも言う)
⟺
V(A)=1

3.6　矛盾とは何か

3.6.1　論理式の集合の矛盾を定義する
いくつかの論理式の集まりがあったときに、 そこに含まれる論理式にはそんなに好き勝手に真理値を割り当てることはできない
例
¬Pも真、¬¬Pも真にするような真理値の割り当てはない
P、P→Q、¬QⅤR、R→Pの4つの式を同時に真とするような(原子式への)真理値割り当てはあるのか
全てが同時に1になる組み合わせはない
互いに矛盾している(inconsistent)と言う
「矛盾」は複数の論理式の集まり(論理式の集合)について言われる
今後、論理式の集合をギリシア文字𝜦,Θ,𝚺を使って表現
論理式の矛盾の定義
論理式の集合Γが矛盾している
⇔
Γに含まれる全ての論理式を同時に真にするような真理値割り当てが存在しない
Γが矛盾していないとき
Γに含まれる全ての論理式をどうじに真にするような真理値割り当てVが一つでもあるとき
論理式の無限集合
論理式は無限にある
論理式の集合には無限集合になっているものもある
例
Pを宮数回否定して作ることのできる全ての論理式の集合
こうした無限集合に対しても矛盾や充足可能性の定義は当てはまる
3.6.2　Knight and Knave
「騎士と悪党」と言う論理パズル
騎士は常に正直に語り
悪党は常に嘘をつく
道を歩いていると何人かの人に出会った、彼らは騎士か悪党か?
例
君はaとbに出会った。君の質問に対し、aは「私は悪党だがbは騎士だ」と答えた。さてaとbはそれぞれ悪党か騎士か
aが騎士であると言う命題をA、bが騎士であると言う命題をB
aが「私は悪党だがbは騎士だ」と言った
¬AΛBで歯足りない
「aが「P」といった」と言う命題の真理値
Pの真偽と、aが騎士か悪党かで決まる
「A⟷P」と同値

3.7　論証の正しさとは何か

3.7.1　論証の妥当性を理解する鍵は反例にある
論証の正しさをとらえる作業
論証が正しいとはどう言うことか?
例
先生:a2=1の時aはいくつか?
トモヤ:a=1ならばa2=1
先生:a=-1もあるだろう
なぜa=-1とすると論証の非妥当性を示したことになるのか?
論証の前提は両方とも真になるが、結論は偽になる
定義
論証の前提がすべて真になるが、結論は偽になるような場合をその論証の反例(counterexample)と呼ぶ
妥当な論証とは反例の存在しないような論証である
3.7.2　論証の妥当性を定義する
上記の例の真理表1
(灰色部)前提がともに1であるのに、結論が0になっている
反例があるからこの論証は妥当ではない
定義
前提A1,…,Anから結論Cを導く論証が妥当である
⇔
A1,…,An,Cを構成している原子式への真理値割り当てのうち、A1,…,Anを同時に1にし、Cを0とするようなもの(すなわち反例)が存在しない
3.7.3　構成的両刀論法と場合分けによる証明
ああ打つと負ける(A→C) こう打つと負ける(B→C) しかし、ああ打つかこう打つしかない(AⅤB) ————————————————- どっちみち負けだ(C)
どっちに転んでも同じ結果になる
<問題>
abの形をした数でaもbも無理数なのに有理数になるようなものがあることを証明せよ
√2√2が有理数である→abでaもbも無理数なのに有理数になるものがある √2√2が無理数である→abでaもbも無理数なのに有理数になるものがある √2√2が有理数であるⅤ√2√2が有理数である ————————————————————————————————– abでaもbも無理数なのに有理数になるものがある
ありうる場合を、A1ⅤA2Ⅴ…ⅤAnのようにn通りに分けて
そのどの場合においても同じCが成り立つことが言えれば
場合わけなしにCと言って良い
3.7.4　「矛盾からは何でも出てくる」の怪
霊魂が存在するならば現代科学は間違いだ 現代科学は間違っていない 霊魂も存在する ——————————————— 日本で最もハイセンスな都市は名古屋でぎゃ
論証の妥当性の定義によると妥当になる
反例を探そうとしても見つからない
そもそも全ての前提が1になる時がない
前提が全て1で0になる場合(つまり反例)は存在しない
前提が矛盾している論証は結論に何が来ようが妥当になる
矛盾している前提からはいかなる結論も論理的に出てくる
3.7.5　論理学の３つの顔は１つである
論理的帰結、矛盾、形式的真理と言う概念がお互いにどのような関係を持っているのか
論証の妥当性とトートロジー
定理9
前提A1,…,Anから結論Cを導く論証が妥当である
⇔
論理式(A1Λ…ΛAn)→Cがトートロジーである
妥当性と論理的同値性
定理10
AとBが論理的に同値
⇔
論証A/Bと論証B/Aが共に妥当
2つの論理式の論理的妥当性を、それらがお互いに相手から論理的に帰結することとしてとらえることもできる
<論証の妥当性><論理式の集合の矛盾><トートロジー>の3つの基本概念は互いに結びつく

3.8　論理的帰結という関係

3.8.1　論理的帰結を定義する
前提A1,…,Anと結論Cを持つ論証が妥当であると言うことは
A1,…,AnからCが論理的に出てくる (C logically follows from A1,…,An)
CはA1,…,Anの論理的帰結である (C is a logical consequence of A1,…,An)
論証の妥当性という概念が定義されると
「論理的に出てくる」という概念や論理的帰結という概念も定義される
CがA1,…,Anの論理的帰結である
「⊨」2重ターンスタイル(double turnstile)
ターンスタイル:遊園地や駅にあった回転式改札口
定義1
A1,…,An ⊨ C
⇔
A1,…,An,Cを構成している原子式への真理値割り当てのうち、 A1,…,Anを同時に1にし、 なおかつCを0とするような真理値割り当ては存在しない
全体として、左辺において論理式の集合と右辺の論理式の間にある関係が成り立っていることを主張している
論理式の任意の集合をΓで表し、次のように定義し直す
定義2
Γ ⊨ C
⇔
Γに含まれている式とCを構成している全ての原子式 (これを簡単に「ΓとCに含まれる原子式」ということにする) への真理値割り当てのうち、 Γに含まれる全ての式を同時に1とし、 なおかつCを0とするような真理値割り当ては存在しない
抽象的に考えられた論理式同士の間に、論証するかどうかとは無関係に成り立つ関係
簡略な表記の約束
2重ターンスタイルを拡大解釈する
Γが空集合の場合
定義
⊨ C ⇔　Cはトートロジーである
右辺に何もない場合
定義
Γ ⊨ ⇔ Γは矛盾している
3.8.2　論理的帰結関係について成り立つ定理
構造に関わる原理
論理的帰結関係について次の定理が成り立つ
定理14
A ⊨ A (つまり、いかなる論理式を自分自身を論理的に帰結する)
もし Γ ⊨ Aならば、Γ, B ⊨ A
thining、単調性(monotonicity)
ΓからAが論理的に出てくるのであれば、その前提にさらにどんなことBを付け加えても、依然としてAは出てくる
もしΓ ⊨ A, A, ∆ ⊨ Bならば、Γ,∆ ⊨ B
cuttingと呼ばれる
論理的結末の関係が推移的であること
AからBが論理的に出てきて(A⊨B)、 BからCが論理的に出てくるなら(B⊨C)、 AからCが論理的に出てくる(A⊨C)
単調性を持たない論理
それぞれの結合子に特有の原理
定理15
A, ¬A⊨B
矛盾からはなんでも出てくる
Γ, ¬A⊨ ⇔ Γ⊨A Γ, A⊨ ⇔ Γ⊨¬A
Γと¬Aを合わせると矛盾するなら、ΓからはAが論理的に出てくる
Γ⊨AΛB ⇔ Γ⊨A かつ Γ⊨B
Γ, AⅤB⊨ ⇔ Γ, A⊨ かつ Γ, B⊨
Γ, A⊨B ⇔ Γ⊨A→B

3.9　真理関数という考え方

3.9.1　真理関数とは何か
問題の発端
一体結合子は幾つ必要なのか
結合子を減らすと「何をするのに」困るのか
結合子を増やすと「何をするのに」いい事があるのか
「〇〇するために、この結合子で足りているのか」〇〇は何か?
真理関数
関数
N変数関数
集合の直積
真理表
P→Q自体が<1,1>に0、<1,0>に0、<0,1>に1、<0,0>に0を対応させる関数を表す
同様に¬PΛQは別の関数を表す
論理式は真理値の集合{1,0}の直積{1,0}2={<1,1>,<1,0>,<0,1>,<0,0>}から{1,0}への関数を表すものとみなせる
3.9.2　真理関数は何通りあるか
1変数真理関数
総数は22=4
f1-1はPからなるトートロジーならなんでも良い
PⅤ¬P
P→P
f1-2を表す論理式で一番シンプルなのはP
あとは¬¬P
同じ真理関数がたくさんのことなった論理式によって表現される
2変数真理関数
総数は24=16通り
2変数真理関数は全ての手持ちの結合子で表現できる
N変数の真理関数
例えば3変数
自然言語には3変数の真理関数を繋げる(3つの文をいっぺんに繋いでしまえる)ような接続詞はない
28=256通りある
3変数多数派関数 (3-place majority function)
入力される3つの真理値のうち常に多数派の方を出力せよ
対応する論理式
全ての真理関数を表現するために、これまで導入した結合子でたりるか?
真理関数の一般的定義
定義
{1,0}nから{1,0}への関数をn変数の真理関数という
数学的にはブール関数(Boolean function)と呼ばれる
N変数の真理関数の数
22n
3.9.3　真理関数の表現定理
定理17
¬、Λ、Ⅴのみを結合子として含む論理式によって、 n変数の真理関数は全て表せる
¬、Λ、Ⅴは「十全(adequate)」であるとか、 関数的に完全(functionally complete)である
例
出力が1になっているところに注目、3,7,8,12,16行目
3行目は、Pが1、Qが1、Rが0、Sが1
論理式としてPΛQΛ¬RΛSを作ると、3行目だけが1でその他は0の論理式ができる
7行目は、Pが1、Qが0、Rが0、Sが1となる
論理式としてPΛ¬QΛ¬RΛSを作ると、7行目だけが1でその他は0の論理的ができる
1となる全ての式をⅤで繋ぐ
(PΛQΛ¬RΛS)Ⅴ(PΛ¬QΛ¬RΛS)Ⅴ….
真理表の出力が出る論理式になる
3.9.4　どのような結合子の組み合わせが十全なのか
十全な結合子の組み合わせはさらに減らすことができるのか?
{¬,Λ}、{¬,Ⅴ}、{¬,→}は十全である
十全でない組み合わせ(1)
<定理18>
2項結合子Λ、Ⅴ、→、⟷だけを含む論理式は矛盾式になれない
十全でない組み合わせ(2)
「¬が含まれていれば十全である」は誤り
3.9.5　シェーファーの魔法の棒
上記の真理値を持つ2変数の真理関数
を表すような結合子を「|」と書き、「nand」と呼ぶ
A | B は¬(AΛB)と同じ
notとandの組み合わせなのでnand
この時
¬P ⊨⫤ P|P
PΛQ ⊨⫤ ¬(P|Q) ⊨⫤ (P|Q)|(P|Q)
Λと¬が|によって定義できる
{¬, Λ}が十全なので{ | }も十全となる
いかなる真理関数も{ | }で表せる
シェーファー関数
一つで十全であるような真理関数 (その関数だけを繰り返し使って 他の全ての真理関数を生み出す ことのできるような真理関数)
<定義19>2変数のシェーファー関数は|と、↓だけである
3変数、4変数、…のシェーファー関数はいくらでもある
3変数シェーファー関数の例
3変数のシェーファー関数
論理式では(PⅤQ)→¬Rでも表される
#を使って | を表すことができる

3.10　日本語の「ならば」と論理学の 「→」

3.10.1　「→」に感じる違和感
ならばに相当する結合子「→」を上から1011となる真理表で定義
A→Bを¬AⅤBとか¬(AΛ¬b)と同じこととして定めた
これらは「ならば」の大雑把な近似に過ぎない
「→」を日本語の「ならば」に謎なえて理解しようとすると、直感に合わない現象が起きる
(1)以下の形はどれもトートロジーになる
¬A→(A→B)、B→(A→B)、A→(¬A→B)
例えば「ならば」で読むと
Aでないならば、AならばBである
理解ができない
(2)前件が偽の時には後件の真理値に関わりなくA→Bは真、と定めたことによるだけではない
前件と後件が共に真の場合でも十分におかしい
例
P「ベンゼンは水に不溶である」
Q「2000年度アカデミー主演女優はジュリアロバーツである
PもQも真だかP→Qは真になる
「→」と「ならば」の決定的な違い
日本語の「ならば」
前件と後件の間に内容上の関連性があることを求める
「→」
そこに出てくる原子式の内容は問題にせず、ただ真理値の組み合わせだけを問題にする
どんなA とBに対しても(A→B)Ⅴ(B→A)はトートロジーになる
関連性(relevance)に関わる違和感がある
3.10.2　「→」の定義の正当化
例
ベビーシッターの子供にエバンゲリオンを作ってと言われて
(1)可塑性に富んだ材料(粘土)に切り替えて作るか
(2)積木で模型を作って、最も似ているのだということを説得するか
(2)の路線をとって「→」は真理関数の中では一番「ならば」に似ていると説得する
「ならば」について成り立つ重要な特徴
日本語の「ならば」が持っているあらゆる特徴を真理関数的結合の「→」に反映させることはできない
日本語の「ならば」が示す特徴の中からいくつかをピックアップする
(1)逆は必ずしも真ならず
「AならばB」が成り立つと言って「BならばA」が成り立つとは限らない
(2)推移性
「AならばBでありBならばCであるならば、AならばCである」はA,B,C にどんな命題がきても成り立つ
日本語の「ならば」についても推移律は形式的真理である
正当化の議論
この2つを「→」に反映させるには、以下の制約を課せば良い
(1)A→BとB→Aは論理的同値ではない
(2)(A→B)Λ(B→C))→(A→C)はトートロジーである
前件が0の時が問題だったので上記のようにα、βを導入
要件(1)を満たすにはαが1にならないといけない
要件(2)を満たすにはβが1にならないといけない
よって1011となる

3.11　コンパクト性定理

3.11.1　コンパクト性定理とは
定理20
論理式の集合Γが充足可能である
⇔
Γの全ての有限部分集合が充足可能である
Γが有限の時は当たり前(意義のないものになる)「トリビア流に設立する」という言い方をする
Γが無限集合でも⇒の方向はトリビア流に成立する
この定義に意味があるのはΓが無限集合の⇐の方向だけ
Γが無限にたくさんの式を含んでいる時
Γのどの有限部分集合をとってもそれぞれを充足する真理割り当てその都度見つかるならば
「Γは有限充足可能である(finitely satisfiable)」と言う
どのようなものかはわからないが、Γ全体を充足するような真理値割り当てがある
3.11.2　コンパクト性定理の証明・パートⅠ
3.11.3　コンパクト性定理の証明・パートⅡ

3.12　メタ言語と対象言語をめぐって

3.12.1　メタ言語と対象言語を区別しよう
言語L(例えばΛ、¬、↔︎)と、言語Lについて様々なことを述べるために使う表現(例えば⊨⫤、⇔)を混合していけない
Lは研究の対象になっているので「対象言語(object language)」
「P,Q,..,Ⅴ,Λ,¬,→,…」
何かを研究するには言語を使わなくてはならない
言語Lの性質についての話をするための言語を「メタ言語(meta-language)」
「真」、「トートロジー」、「論理的同値」、「論理子」、「結合子」
3.12.2　意味論的に閉じた言語とパラドクス
一つの言語が同時に対象言語としてもメタ言語としても使われる場合、その言語を「意味論的に閉じた言語」と言う
「意味論的に閉じた言語」では、言語がそれ地震について語る自己言及(self-reference)が可能になる
こうした自己言及は、様々な悪戯をする
典型例
意味論的パラドクス(semantic paradox)
嘘つきのパラドクス(Liar paradox)
「この文は偽である」
3.12.3　タルスキによる言語の階層化とうそつきのパラドクスについての最近の考え方
ポーランドの論理学者タルスキ(Alfred Tarski)は、 嘘つきのパラドクスを回避するため、 意味論的に閉じた言語を考察の対象から外すことにした
Lにおける真偽の定義は、Lとは別のメタ言語によって行われるべき
言語を階層化する
上記のやり方は行き過ぎだったとの批判
全ての自己言及を禁じる必要があったのか
明らかに無害なパラドクスを生まない自己言及はいくらでもある
例
この文は疑問文ですか?
この文は日本語の文である
嘘つきのパラドクスの責任は分にあるのか?
嘘つきのパラドクスを生じさせるためには自己言及は必要ない
例
郵便葉書のパラドクス(Postcard paradox)
表に「反対側には間違ったことが書いてある」、裏に「反対側には正しいことが書いてある」
書かれてある文だけ取り出してもパラドクスにはならない
自己言及は含まれていない
クリプキ(Saul Kripke)による提案
ウォーターゲートのパラドクス (Watergate paradox)
(1)ウォーターゲート事件に対してニクソンが言ったことはの半分は偽である
(2)ウォーターゲート事件に関してジョーンズが行ったあらゆることは真である
(1)をぃったのはジョーンズであった。それがジョーンズがウォーターゲート事件に関してなした唯一の発言だった
(2)を行ったのはニクソンであった。そして、この発言意外にウォーターゲート事件に関してニクソンが行ったのはちょうど真偽が半々だった
パラドクスを生むかどうかは、文がどのような状況で使われているかに依存するのであって
文だけを取り出して、パラドクスを生む生まないの区別をつけることはできない
嘘つきのパラドクスを生じさせる責任は文それ自体ではなく、文とそれが使われる状況にある
自己言及を含んでいるような文でも、パラドクスを生まないような使い方をすることは十分に可能
タルスキの言語階層という考え方はこうした文を全て排除してしまう
現在の論理学では
タルスキ的な言語階層を緩めて
意味論的に閉じた言語の中でどのように嘘つきパラドクスが生じないようにするかの研究に熱中している

第4章　機械もすなる論理学
4.1　意味論的タブローの方法

4.1.1　機械的な判定法を作ろう
妥当性、矛盾、トートロジーと言った論理学の重要概念を判定する決定手続き (decision procedure)があるなら、それを作る
その手続きは機械的手続きでなくてはならない
次の要件を満たす必要がある
手続きは明確でなくてはならない
次にすべき操作が一つに決まっている
その操作をした結果も一つに決まる
手続きには汎用性がなくてはならない
ダメなもの
前提が3つの論証の妥当性だけで判定できる手続き
「→」だけからなる論理式のトートロジー性だけを判定する手続き
どのような論証や論理式に対しても使えるものでなければならない
手続きは有限的でなくてはならない
いくら時間がかかっても良いから、用言数のステップをふむといつかは手続きの実行が終了する
以下の2つは別問題
妥当性、矛盾などの概念がどういうことであるかをはっきり定義すること
それを判定するアルゴリズムがあるか
真理表がそれに当たる
真理表はあまり使いやすいアルゴリズムではない
真理表を書く手続きは、創意工夫や感の働く余地がない
真理表の代わりの実用に耐えるチェック法
真理の木(truth tree)
意味的タブロー(semantic tableau)
4.1.2　タブローのルーツ
タブローの方法はどのような発想に基づいているのか?
例
式の集合{¬(PΛQ), (PⅤQ)Λ¬Q}は矛盾しているか、それとも充足可能か
(1)この式に含まれる全ての論理式を1にする 首尾一貫した真理値割り当てを見つけせられるかを追求する
成功すれば充足可能
失敗すれば矛盾している
(2)¬(PΛQ)と(PⅤQ)Λ¬Qが共に1であると仮定してみる
(3)(PⅤQ)Λ¬Qが1になるには、PⅤQが1、¬Qが1でなければならない
(4)¬Qが1であるためにはQが0でなければならない
(5)PⅤQが1であるためには、PかQのどちらかが1出なければならない
(6)Qが1は(4)と合わない
(7)Pが1であるとする
(8)(PⅤQ)Λ¬Qが1になるには、PかQのどちらかが0でなければならない
(9)Pが0は(7)と合わない
(10)¬Qが0とすると(3)と矛盾する
(11)¬(PΛQ)と(PⅤQ)Λ¬Qを共に1にする首尾一貫した真理地割り当ての試みは失敗した
4.1.3　機械的方法にしてゆくためのヒント
(A)上記の例を図式化
(B)簡略化して図式化すると
(C)更に感緑化すると
=1の部分を省略
=0は¬をつける
4.1.4　タブローを汎用的な方法にする
(C)のようなダイアグラムを「タブロー」と呼ぶ
タブロー(C)では、はじめ1本だった経路は枝分かれし、最終的に3本の経路が生じる
タブローを作る手続きをまとめる
定義
タプローのてっぺんから一つの末端までをずっとたどり、 そこに含まれる論理式を集めて作った式集合を経路(path)と呼ぶ
左の経路
{¬(PΛ¬Q), (PⅤQ)Λ¬Q, PⅤQ, ¬Q, P, ¬P}
真ん中の経路
{¬(PΛ¬Q), (PⅤQ)Λ¬Q, PⅤQ, ¬Q, P, ¬¬Q}
右の経路
{¬(PΛ¬Q), (PⅤQ)Λ¬Q, PⅤQ, ¬Q, Q}
タブローを作るとはどういうことだったのか
(C)を完成させるためには
(1)最初にチェックする式集合に含まれる論理式を列挙する
(2)2行目から3,4行目を作る
AΛBという形の経路が出てきたら、その経路に続けてAとBを縦に並べて書き加える
規則「Λ」
(3)3行目から5行目を作る。
「AⅤBという形の式が経路に出てきたら、経路を2つに分岐させ、一方の経路にA、一方の経路にBを書き加える
規則「Ⅴ」
(4)5行目まで伸ばしたところで、右の経路にQと¬Qが共に現れる
ある論理式とそれを否定したものが同時に現れるのであれば
失敗に終わった経路
(5)左側の経路は{¬(PΛ¬Q), (PⅤQ)Λ¬Q, PⅤQ, ¬Q, P, ¬P}
この経路を充足する真理値割り当てがあるかどうかはまだ未知数
この経路に含まれる¬(PΛ¬Q)が1になるにはどうしたらようか考える
6行目に枝分かれさせる
規則「¬Λ」
(6)規則「¬Λ」を当てはめた段階で経路は3本になっている
展開規則と判定基準
上記で述べた[Λ], [Ⅴ], [X], [¬Λ]などを「展開規則」と呼ぶ
展開規則
展開規則を割り当てる際の注意
タブローを構成するそれぞれの段階でこれらの規則を当てはめるには
必ず、式全体に適用し、部分論理式に当て嵌めなければならない
PΛ(QⅤR)に当てはめる場合は、[Λ]であって[Ⅴ]でない
4.1.5　閉鎖経路と閉鎖タブロー
{P→Q, Q→P}は矛盾していない
この式集合をタブローにかける
P→QとQ→Pを縦に並べて、 P→Qに「→」を当てはめる 当てはめ済みには「!」をつける
次に、Q→Pにもう一度「→」を当てはめる
Xのついていないものが残っているので矛盾しない
閉鎖経路
定義
末端にXのついた経路を「閉鎖経路(closed pqth)」、 そうでない経路を「解放経路(open path)」と言う
閉鎖タブロー
タブローの経路が全て閉じているかどうかが矛盾の判定基準になる
定義
全ての経路が閉鎖経路であるようなタブローを 閉鎖タブロー(closed tableau)と言い またはそのタブローは閉じて終わる、と言う 逆に展開規則を全て適用し終わった時点で まだ一つでも開放経路が残っているタブローを 開放タブロー(open tableau)と言い そのタブローは開いて終わる、と言う
論理式集合が矛盾しているかどうかの判定基準
論理式の集合{A1,A2…,An}が矛盾している
⇔
A1,A2,…,Anを縦に並べて始めたタブローが閉鎖タブローになる
4.1.6　人間らしくタブローを描こう――タブロー構成の攻略法
規則を当てはめる順序にはコツがある
非効率なタブロー
効率的なタブロー(1)
効率的なタブロー(2)
攻略法
枝分かれしない展開規則を先に適用する
枝分かれする場合には少なくとも一方の経路が閉じるような行に展開規則を適用する
4.1.7　妥当性、トートロジー性、論理的同値性の判定とタブロー
前提A1,A2,…,Anから結論Cを導く論証が妥当である
⇔
式集合{A1,A2,…,An,¬C}が矛盾している
論理式Aがトートロジーである
⇔
{¬A}が矛盾している
と言う関係性から
タブローは論証の妥当性や、論理式のトートロジー性の判定方法としても用いることができる
判定基準
前提A1,..,Anから結論Cを導く論証が妥当である
⇔
A1,…,An,および¬Cを縦に並べたものからはじめたタブローが閉鎖タブローになる
論理式Aがトートロジーである
⇔
¬Aから始めたタブロー閉鎖タブローになる

4.2　タブローの信頼性

4.2.1　なぜ信頼性を確認しなければならないか
機械的手続きとしてみたタブローの方法は、徹底して意味を無視したシンタックス的な手続き
そのような結果が、矛盾という記号の意味に係るセマンティクス的事実についての判定として信頼がおけるものになっているのか?
そのために
まず有限ステップのうちに終わるのか(決定可能性(decidability))を確認する
次に判定結果が常に正しいことが保証されているのか?を確認する
4.2.2　タブローの決定可能性
定理22
タブローの方法は決定可能である
4.2.3　閉鎖タブローが生じたならば矛盾している
定理23
式の有限集合Γからは閉鎖タブローが生じる
⇔
Γは矛盾している
4.2.4　矛盾した集合はいつでも閉鎖タブローを生む
定理24
式の有限集合Γは矛盾している
⇔
Γからは閉鎖タブローが生じる
対偶
Γから開放タブローが生じる
⇔
式集合Γは充足可能である
「どんな開放経路にも、そこに含まれる式を全て充足する真理割り当てVが必ず存在する」と言えれば、 このVは開放経路を充足する以上、出発点となったΓも充足する
開放経路からはそれに含まれる式を全て充足する真理割り当てを作れると言うことを
どんな開放経路にも当て嵌まるように厳密に証明
「モデル集合(model set)」あるいは 「ヒンティッカ集合(Hintikka set)」での証明アプローチ
ヒンティッカ集合
定義
次の条件を満たす論理式の集合∆をヒンティッカ集合という
(¬): 如何なる原始式PについてもPと¬Pの両方が∆に属することはない
(¬¬): ¬¬A∈∆ ⇒ A∈∆
(Λ): AΛB∈∆ ⇒ A∈∆かつB∈∆
(¬Ⅴ): ¬(AⅤB)∈∆ ⇒ ¬A∈∆かつ¬B∈∆
(¬→): ¬(A→B)∈∆ ⇒ A∈∆かつ¬B∈∆
(¬Λ): ¬(AΛB)∈∆ ⇒ ¬A∈∆または¬B∈∆
(Ⅴ): AⅤB∈∆ ⇒ A∈∆またはB∈∆
(→): A→B∈∆ ⇒ ¬A∈∆またはB∈∆
(↔︎): A↔︎B∈∆ ⇒ (A∈∆ かつ B∈∆) または (¬A∈∆ かつ ¬B∈∆)
(¬↔︎): ¬(A↔︎B)∈∆ ⇒ (A∈∆ かつ ¬B∈∆) または (¬A∈∆ かつ B∈∆)
ヒンティッカ集合の充足可能性
定理25
如何なるヒンティッカ集合も充足可能である
タブローの開放経路は充足可能性であることの証明
タブローの開放経路がヒンティッカ集合であれば証明できる

第Ⅰ部のまとめ

論理学の目標
論証の正しさ、矛盾、論理的真理という概念を明確にする
その形式を浮かび上がらせるのに都合の良い人工言語Lを作り
その言語の性質を研究することで上記の目的を達成しようとする
Lを定義するために、シンタックスを定める
語彙を確定
Lの論理式を機能的に定義
Lの論理式を機能的に定義したことの意義
可能な論理式全てを対象に入れられる
より単純な形の部分的論理式から機能的に作られることで
全ての論理式に対する事実を証明する技法
結合子と真理関数の一般化により日常行う論証や推論に、大きな飛躍を与えられる
N変数の真理関数に対する概念は自然言語にはない
帰納的に定義された論理式の無限集合の構造を
シンタックスとセマンティック酢の両面から調べていくこと
自然言語から離れて

次回は、第2部での読書メモを述べる。