うつし世はゆめ / 夜のゆめもゆめで“論理学”タグの付いているブログ記事

http://www.at-akada.org/blog/2007/03/post_118.html

この部分が間違っているような。 「A と A ⇒ B とから B を導き出す推論規則」は MP(modus ponens)、日本語で除去規則と呼ばれるもので、三段論法とは関係ない気がする。


これは嘘だったかもしれない。

今日↓の本を読んでいたら、この本にも「MP は三段論法とも呼ばれる」と書いてあった。

情報科学における論理

しかし、MP と三段論法のつながりはよくわからない。どういうことだろう。

三段論法については以下を参照。

http://ja.wikipedia.org/wiki/%E4%B8%89%E6%AE%B5%E8%AB%96%E6%B3%95

http://ja.wikipedia.org/wiki/%E4%B8%89%E6%AE%B5%E8%AB%96%E6%B3%95


伝統的論理学と三段論法について。

現代論理学は、経験的な学問ではない。現代論理学は、人工言語をつくり、その性質を調べる。その成果はたとえば、「かくかくのように言語を設定したら、しかじかの性質を持った」という形をとる。ここで、「しかじか」というのは、「かくかく」という言語に対する発見であって、自然言語に対する発見ではもちろんない。ただし論理学のユーザーが、日常言語に対する数学的モデルとして人工言語を使用することはある。言語学、言語哲学にとっての論理学の役割は、物理学にとっての数学の役割と同じ。しかし、物理数学が物理的事実を述べるものではないように、論理学自体は、経験的な事実を述べるものではない。すなわち、それは、われわれが日常用いる「論理」を対象とする学問ではない。

しかし一方、伝統的論理学はそうではないように思われる。「三段論法がいかなる形のときに妥当となるか」という伝統的論理学のテーゼは、「われわれが論証を行う方法」に関する経験的な事実と見なされうる。従って、現代論理学の成果と伝統的論理学の成果は、まったく性質を異にする。現代論理学が、あくまでも方法の精緻化にたずさわるものであった一方、三段論法の整備のような、伝統的論理学の仕事は、経験的事実の「発見」と見なされるべきものだ。それは論理学的・数学的というより、社会学的ないし言語学的(あるいは修辞学的)研究の成果だろう。

このように考えるとき、アリストテレスによる三段論法の分類は、その規模の大きさと明確な法則性からして、実に希有な仕事だ。現代の人文系学者の仕事で、これに匹敵しうるものがどれほどあっただろうか...。

...などということを考えていたのだが、伝統的論理学についてもう少し調べてみないと、あまり明確なことは言えないなあ。

とりあえず、伝統的論理学の問題は、アリストテレス以後、ほとんど誰も、それに匹敵する同じような性質の仕事を残せなかった点にある、ということは確かだろう。

http://ja.wikipedia.org/wiki/%E6%95%B0%E7%90%86%E8%AB%96%E7%90%86%E5%AD%A6

論理式から論理式を導き出す推論規則には、たとえば論理式 A と A ⇒ B とから B を導き出す推論規則がある。これはいわゆる三段論法である。

この部分が間違っているような。 「A と A ⇒ B とから B を導き出す推論規則」は MP(modus ponens)、日本語で除去規則と呼ばれるもので、三段論法とは関係ない気がする。

もちろん Wikipedia の記述に文句をつけるくらいなら、自分で直せばいいわけだが、アカウント持ってないし、とりあえずメモしておく。


ついでだから、論理学トリビア。どんな教科書でも最初に載ってるような基礎的な内容だけど。

「トートロジー」というのは、論理学的な概念だと思われてそうだが、論理学でいう「トートロジー」と日常語(むしろ修辞学の概念?)のトートロジーはだいぶ意味がちがう。

論理学以外でトートロジーというと、あまりよい意味ではない。「きみの議論はトートロジーだ」って言われたら、たいてい馬鹿にされてるのだ。一方論理学的トートロジーには悪い意味はまったくない。むしろトートロジーこそ論理学固有の対象であり、妥当な推論はすべてトートロジーであるとされる。

この「妥当な推論はすべてトートロジー」というのは、最初ちょっと戸惑うが、原因は「ならば」の働きにある。

推論は「(前提1)、(前提2)、(前提3)、ならば(結論)」という形をとる。このとき、推論が妥当なら、前提が真のとき結論も真であり、推論全体は真になる。前提が間違ってるなら、ありえない前提のもとでの推論なので、推論全体はやはり真になる。というわけで、妥当な推論はつねに真になる(=トートロジー)。一方妥当でない推論は、前提がすべて正しくても結論が偽になることがある(反例をふくむ)ので、トートロジーではない。


追記:

別のところにも変なのを発見した。

http://ja.wikipedia.org/wiki/%E7%9B%B4%E8%A6%B3%E4%B8%BB%E7%BE%A9%E8%AB%96%E7%90%86

直観論理(ちょっかんろんり)あるいは直観主義論理(ちょっかんしゅぎろんり)とは、従来の論理学(古典論理)は全てのものの真偽が明確になる「神の論理」であるとして、もっと慎ましやかに人間の立場の論理学を考えようということで提唱されたものである。

慎ましやかは関係がないのではないか。もしかしたら私が知らないだけでブラウワーがこう言ってるのかもしれないが、ふつう教科書的には直観主義論理は以下のように説明される。

直観主義論理学は排中律を認めない。排中律、すなわち「すべての命題は真か偽かいずれかである」ということを認めるには、対象はすでに決定ずみだと考えなければならない。しかし、未来のことや無限について、これが認められるかどうかは怪しい。たとえば「明日は雨だ」が真か偽かいずれかだというのは、未来がすでに決定ずみだという前提に立たないかぎり認められない。同様に、無限につづく数、たとえば円周率について「円周率には7の7連続が含まれる」などの命題が真か偽かのどちらかだと考えるのは、「神の立場」に立たないかぎり不可能だ。少なくとも人間の認識を基礎におくかぎり、これらの命題は真とも偽ともいえない。そこで、真でも偽でもない命題の存在を認め、排中律を持たない新しい論理としてつくられたのが直観主義論理。

(特に直観的にわかりやすい内容でもないため、直観主義論理という名前がふさわしいかどうかは知らない)。

もの・言葉・思考―形而上学と論理

三上真司(著)

東信堂、2007


2007/06/09訂正:

以下に書いたことは間違いであるか、少なくとも誤解を招くものでした。すいません。http://www.at-akada.org/blog/2007/06/post_218.html

↑訂正記事



同一性記号と変項の扱いについて、明らかに間違ったことが書いてある箇所があったので書き記しておく。というか間違いを書いた後でほめようと思っていたのだが、間違いについて長々書いているうちに眠くなってしまったので、ほめるのは明日以降に延期する。

同一性は「もの」と「もの」との関係なのだろうか。もしそうならば、それはいかなる関係なのか。「もの」とそれ自身の関係なのか、それとも「もの」と別の「もの」の関係なのか。もし前者ならば、同一性を言い表す言明は必然的に真であり、しかもこのうえなくつまらない同語反復でしかない (a=a)。もし後者ならば、それは必然的に偽である。それ自身とは別のものと同じであるようなものはないからである (a≠b)。p123-124

論理学には同一性を「『もの』と『もの』の関係」として把握する傾向が内在している。もし通例通り同一性の記号が「もの」と「もの」の関係として把握されるならば、それは上述のパラドックスに帰着する。p124

これは、かなり怪しい表現。

同一性記号を「ものとものの関係」だと把握すれば、確かにパラドックスでも何でも起きるかもしれないが、それは単に同一性記号に関する理解が間違っているからだ。同一性記号は「ものとものの関係」については特に何も言ってない。

同一性記号が意味するのは、「二つの名前が同じものを指示する」ということだ。

戸田山本から同一性記号の定義を引いてみよう。ただし、メタ言語のイコールとごちゃごちゃになってややこしいので、ここでは同一性記号には半角の「=」を使う。メタ言語のイコールには全角の「=」を使う。またギリシャ文字は使いたくないので、漢字に置き換えておく。

任意の個体定項甲、乙について、VM(甲=乙)=1 ⇔ V(甲)=V(乙)

p203

これが意味するのは、『モデルMのもとで、論理式「甲=乙」が真となるのは、定項「甲」に割り当てられる個体と定項「乙」に割り当てられる個体が同じとき、かつそのときのみですよー』ということだ。

以上のように同一性はあくまでも「2つの記号と1つのもの」の話なので、1つのものについてつねに1つの名前だけを割り当てるようにすれば、「a=b」などの文は必要がなくなる。このあたりは著者の言うとおり。

ただし、同一性記号が無意味になるのは定項の場合にかぎる。名前がつねに一個だけだとしても、自由な変項に関する同一性記号は無意味ではない。

たとえば、以下のようなモデルを考えよう。

議論領域: {1, 2, 3}
個体定項
a: 1
b: 2
c: 3
述語
2x: x が偶数である。

このとき、論理式「2b∧∀x(2x→x=b))」は無意味ではない。

これは「偶数なのはbだけですよー」という意味だ。無意味どころか、同一性記号を使わないとこの文は表現できない。

もう少し細かく言ってみよう。x は変項だ。変「数」であるということは、「そこに入る数が様々に変わる」ということを意味している。これと同様に、変「項」であるということは、「そこに入る『項』(記号)が様々に変わる」ということを意味している。つまり、「∀x(2x→x=b)」は、「どんな記号を x に入れてみても、(2x→x=b) が成り立ちますよ」という風に読める。今記号は、a と b と c しかないから、「∀x(2x→x=b)」が意味するのは、「a, b, c を順番に x に入れてみなさい。2x が成り立つなら、その記号は b と同一ですよ」ということだ。

だから文全体は「bは偶数であり、かつすべての記号について、その記号の指示先が偶数ならば、その記号の指示先は b と同じですよ」という風に読める。これを短く言うと、「偶数なのはbだけですよー」となる。これはトートロジーでも矛盾でもない。モデルによって真偽がかわる文であり、この場合はたまたま真になっている。

著者はおそらく変項というものについてよくわかっていないのだと思う。それがはっきりとわかる箇所は以下。

ただし、「二人の人が『ウェイヴァリー』を書いたことはなかった」も「二人の人が『マーミオン』を書いたことはなかった」も他とは独立した内容なので、すでに使われている変項を重複して述べることはできない。それを回避するならば、「『ウェイヴァリー』の著者は、『マーミオン』の著者と同一人物である」は次のように表すことができる。

(4) ∃x(Px∧Qx)∧¬∃y∃z{(Py∧Pz)∧¬(y=z)}∧¬∃v∃w{(Qv∧Qw)∧¬(v=w)}

p141-142

著者はできないと言っているが、(4)は以下のように書いてもかまわないし、ふつうはこう書くと思う。

∃x(Px∧Qx)∧¬∃x∃y{(Px∧Py)∧¬(x=y)}∧¬∃x∃y{(Qx∧Qy)∧¬(x=y)}

なぜこう書いてかまわないかというと、誤解の可能性がないからだ。この文を日本語で読むと次のようになる。「(Px∧Qx) に入れると成り立つような記号があります。かつ {(Px∧Py)∧¬(x=y)} に入れると成り立つような二つの記号 x, y はありません。かつ {(Qx∧Qy)∧¬(x=y)} に入れると成り立つような二つの記号 x, y はありません」。

ややこしいから、三つに分けよう。

ア: ∃x(Px∧Qx)

イ: ¬∃x∃y{(Px∧Py)∧¬(x=y)}

ウ: ¬∃x∃y{(Qx∧Qy)∧¬(x=y)}

ここでア、イ、ウはそれぞれ別の量化子のスコープ内にある。

アの部分は一個の記号 x について述べているが、括弧が閉じることによって x の話はいったん終わっている。だからイとウでもう一回 x を使っても誤解の可能性はない。

一方、これと違いイのなかの x と y は区別されなければならない。ここでは、∃x∃y という二つの量化子のスコープが重なっている。これは x と y という二つの記号について述べているのだと考えなければならない。x と y は同じかもしれないし、べつかもしれないし、どっちかわかんないから二つの記号を使うのだ。

∃x∃y(Px∧Py) が真であるのは、二つの違うものが 'P(...)' を充たすときである。「二つの違うもの」の差異は、'x' と 'y' という違った記号を使用することですでに尽きているのだから、¬(x=y) をその後に付加するのは余計なだけである。p143-144

ここは明らかに間違っている。x, y は違うものかもしれないが、同じものであってもかまわないのだ。

さっき私があげたモデルで、2x が成り立つ記号はひとつしかないが、「∃x∃y(2x∧2y)」は真になる。なぜなら「2b∧2b」は真だからだ。ここでは x と y が同一であるか別であるかについて何も言われていないため、x=y の可能性を排除できない。

権威付けのために教科書を参照しておくと、x, y が同じものであってもいいということは例えば、戸田山本の p179 などにかなりはっきりと書いてある。

というかだね。「同一性記号が役に立つのは、量化子のスコープのなかでだ(自由な変項についてだ)」というのはむしろ「視線の重ね合わせ」という著者の主張に適合しやすいことだと思われるのだ。そのため、こういう基礎的なレベルで間違いをおかされるのは、本書の読者としては残念でならない。このあたりの話をからめさえすれば、同一性に関する議論はもっとずっと深められたはずであったと思う。

論理学をつくる

戸田山和久『論理学をつくる』

名古屋大学出版会


私が『論理学をつくる』で論理学の勉強をする。発表が終わったのですかさず残っていた部分を終わらせた。めでたく全部おわった。

12章前半は少し前にやったが、記録してなかった。前半をやってしばらくたっていたので、内容を忘れていた。話がむずかしいうえに半分くらい忘れているので、あんまり理解できていない。


第12章 古典論理にもまだ学ぶことがたくさん残っている

12.1 完全武装した述語論理の言語 FOL

  • 12.1.1 言語 FOL
  • 12.1.2 FOL のセマンティクス
  • 12.1.3 述語論理の公理系

12.2 AFOL の完全性とそこから得られるいくつかの結果

  • 12.2.1 述語論理の完全性証明
  • 12.2.2 コンパクト性定理とレーヴェンハイム・スコーレムの定理

12.3 第1階の理論


12.4 モデル同士の同型性

  • 12.4.1 互いによく似たモデルとそうでないモデル
  • 12.4.2 同型なモデル
  • 12.4.3 理論の範疇性とノン・スタンダードなモデル

12.5 第2階の論理

  • 12.5.1 FOL では表現できない命題がある?
  • 12.5.2 第2階の論理のセマンティクス
  • 12.5.3 第2階のペアノ算術
  • 12.5.4 第2階の論理の特質

論理学小まとめ。


まとめと言ってもまだ終わってないわけだが、勉強していてわかったことで、今後も見解が変わらなさそうなことだけ書いておく。


論理学の構成。

古典論理は命題論理と述語論理からなる。そこにプラスアルファで、様相論理や直観論理や多値論理などの非古典論理学がつけくわわる。また、それぞれの論理について構文論と意味論がある。つまり、ふつうの古典論理は「命題論理/述語論理」×「構文論/意味論」で4つのジャンルからなる。

意味論は論理式の「意味」を扱う。ただしここで意味と言ってるのは、真理条件のこと。たとえば「P∧Q は P、Q がともに真のときのみ真」とかそういうことを扱うのが意味論。つまり、「左と右が両方真のときだけ真だよ」というのが、「∧」の意味であるわけだな。

一方、構文論は公理系をあつかう。公理系とは自動お絵かきプログラムのこと。公理系がするのは、あらかじめ決められた変形規則を使って、記号を並べることだけ。構文論では並べられた記号の意味はまったく考えないので、これは本当に絵を描くだけだ。しかもたいていの場合、架空のお絵かきプログラムだから、「このプログラムでこの絵は描けるのか」などと架空のソフトについて議論するわけわからん人たちみたいになる。


論理学の仕事。

論理学は人工言語をつくり、それについて調べる学問だ。

人工言語は日常の論理的推論や論証を「モデル」にしたものではあるが、日常言語からは完全に独立に定義されている。目的はちがうが、人工的に語彙と文法を与えられた言語という意味では、C言語とか PHP とか Ruby などのプログラミング言語みたいなもんだと思う。要するに、論理学者はその人工言語についてあれこれ調べることで、「C言語でうんぬんしてたら、ソートが少し速くなった」みたいなことをやってる。

言い換えれば論理学は論理そのものを扱っているわけではない。やってるのは論理に少し似た人工言語をつくったり調べたりすることだけ。人工言語を「モデル」として用いることで、日常の論理について考えることは、もちろんできる。でも、それはもう哲学やら言語学者やら何やらの仕事であって論理学者の仕事ではない。論理学の範囲は人工言語をつくってその性質を調べるところでおしまい。だから論理学は「論理」の学ではない。正確に言うと、論理をモデル化した人工言語の学だ。

したがって例えば、論理学の言語が日常言語に似ていないからまちがっているというのはおかしい。「似ていない」ことが問題になるのは、人工言語を日常論理に対するモデルとして使う文脈でのみありえることだ。人工言語自体は基本的に日常言語からは独立したものなので、他のことに使ってもまったくかまわない。ふつうの推論から恐ろしくかけ離れた言語をつくってもかまわないし、そのことによって論理学における定理の価値が下がるわけではない。「似ていないから使えない」というのはあくまでも論理学ユーザーの視点。論理学者がユーザーの視点に立ってものを言うことももちろんあるけど、例えば、証明の妥当性は、日常の論理に似ているかどうかとはまったく無関係に判断される。

だからして、論理学の定理が、日常の認識や判断について何か重要な意味を持っているかのように言うのもおかしい。重要な意味を持ちうるのは、「人工言語をモデルとして使うことで引き出された仮説」であって、論理学の定理それ自体ではない。C言語がどんな性質を持とうと、それによってC言語に無関係な人が影響を受けることはまずない、と思う。それと同じように、論理学の定理について、それが論理に関する新たな発見であるかのように言うのも基本的にはおかしい、と思う。

論理学をつくる

戸田山和久『論理学をつくる』

名古屋大学出版会


私が『論理学をつくる』で論理学の勉強をする。

今日は9章(自然演繹法)の後半と10章前半(APL)をやった。今日中に10章を終わらせて明日で11章まで終えるつもりだったが、このペースだとちょっとむずかしそうだ。

タブローもパズルだと思ったが、自然演繹法はもはや完全にパズルなので楽しい。ゲーム化したら人気が出るのではないだろうか。一方 APL はいまいちやり方がよくわからないので楽しめない。書き方もめんどくさいし、あまり好きではない。


おまけ

Tarski's World

http://www.bu.edu/linguistics/UG/course/lx502/local/tarski.html

戸田山『論理学をつくる』のブックガイドでも紹介されている論理学学習ソフト "Tarski's World" の Java Applet 版。要するに上のグリッド部分がモデルになっていて、式を書くとモデルから真偽を判定してくれるというものらしい。「∧」が「/\」、「∨」が「\/」「→」が「=>」、「∀」は「A」など。述語は Square(x) とか。Applet をダウンロードして、ローカルで使うと、モデルや式を保存することもできる。

しかし、これだけだとあまり遊び方が思いつかないなあ。どういう風に使えばいいのだろう。


8章 自然演繹法を使いこなそう

9.1 自然演繹法をつくる

  • 9.1.1 evaluation から construction へ
  • 9.1.2 形式化への第一歩
  • 9.1.3 演繹規則をたてる
  • 9.1.4 →導入規則と→除去規則
  • 9.1.5 演繹の攻略法
  • 9.1.6 演繹・定理・証明

9.2 他の結合子のための推論規則

  • 9.2.1 ∧の導入と除去
  • 9.2.2 ←→の導入と除去
  • 9.2.3 ¬の導入と除去
  • 9.2.4 連限は簡単だったのに選言はややこしい
  • 9.2.5 最後の手段としての間接証明

9.3 矛盾記号を導入した方がよいかも

  • 9.3.1 超絶技巧の演繹?
  • 9.3.2 矛盾記号の導入

9.4 述語論理への拡張

  • 9.4.1 ∀除去規則と∃導入規則
  • 9.4.2 ∀導入規則
  • 9.4.3 ∃除去規則はさらに面倒
  • 9.4.4 ド・モルガンの法則に挑む

9.5 同一性記号を含む自然演繹


10章 シンタクスの視点から論理学のゴールに迫る

10.1 公理系という発想

  • 10.1.1 論理的真理をすべて数え上げる
  • 10.1.2 命題論理の公理系
  • 10.1.3 公理系に関して定義される諸概念
  • 10.1.4 仮定からの演繹
  • 10.1.5 演繹定理
  • 10.1.6 deduction 中での theorem の利用と派生規則
  • 10.1.7 自然演繹も公理系の一種である

論理学をつくる

戸田山和久『論理学をつくる』

名古屋大学出版会


私が『論理学をつくる』で論理学の勉強をする。

IPL(同一性を含む述語論理)。8章は短い。

同一性記号を使うと、「○○先生の作品が読めるのはジャンプだけ!」を記号化できる。「○○先生の作品が読めるのはジャンプだけ!」を記号化できるのは IPL だけ!(←だけじゃない)

Rxy: x では y が読める
a: ○○先生の作品
j: ジャンプ

Rja ∧ ¬∃x(¬(x=j) ∧ Rxa)

(ジャンプでは○○先生の作品が読め、かつ、ジャンプ以外で、○○先生の作品が読めるものは存在しない)

あるいは、

Wxy: x が y を描いた
a: ○○先生

として、

Ex(Rjx ∧ Wax) ∧ ¬∃x∃y(¬(x=j) ∧ Rxy ∧ Way)

(ジャンプで読める○○先生の描いたものが存在する。かつ、ジャンプ以外で、○○先生の描いたものが読めるものは存在しない)

右半分は「∀x∀y((Rxy ∧ Way)→(x=j))」(a 先生の描いたものが読めるならば、ジャンプである)でもいいはず。


8 章 さらにさらに論理言語を拡張する

8.1 同一性を含む述語論理 IPL

  • 8.1.1 同一性記号を導入する
  • 8.1.2 論理式の定義とセマンティクスの手直し
  • 8.1.3 同一性をタブローで扱う

8.2 個数の表現と同一性記号

  • 8.2.1 「~個ある」を表現する
  • 8.2.2 確定記述句の理論

論理学をつくる

戸田山和久『論理学をつくる』

名古屋大学出版会


私が『論理学をつくる』で論理学の勉強をする。

論理学をはじめてから体調がよい。夜は眠れるし、朝も7時半には起きている。外食の回数も減った。これまで面倒くさがっていた洗濯などもまめにするようになった。論理学って実は健康にいいんじゃないだろうか(←妥当でない推論)。

今日は PPL (多重量化)。無理矢理 1 日で終わらせた。話としては難しくないが、非常にややこしい(「すべての x は、すべての y について、y が愛するような z が存在するならば y を愛する」とか)。計算もむずかしい。「タブローを書き間違える→計算つまる→やりなおし→また間違える→1時間経過」という、このパターン。


7 章 さらに論理言語を拡張する

7.1 MPL の限界

  • 7.1.1 MPL にとっての難問
  • 7.1.2 MPL の限界はどこにあるか
  • 7.1.3 個体と個体の関係を表現するには
  • 7.1.4 多重量化
  • 7.1.5 あ・れ・も・愛, これも愛―愛の論理学
  • 7.1.6 言語 PPL の定義

7.2 PPL のセマンティクス

  • 7.2.1 愛の世界
  • 7.2.2 モデルの定義の手直し
  • 7.2.3 真理の定義の手直し
  • 7.2.4 述語論理のセマンティクスについて成り立ついくつかの定理

7.3 PPL にタブローを使ってみる

  • 7.3.1 マリンバに挑む
  • 7.3.2 タブローを活用して関係を科学する
  • 7.3.3 タブローの信頼性
  • 7.3.4 「閉鎖タブローが生じたら矛盾している」の証明
  • 7.3.5 「矛盾した集合から出発するタブローは閉鎖タブローになる」の証明

7.4 論理学者を責めないで―決定問題と計算の理論

  • 7.4.1 PPL の決定不可能性
  • 7.4.2 決定問題
  • 7.4.3 アルゴリズムの概念とチャーチの提案

論理学をつくる

戸田山和久『論理学をつくる』

名古屋大学出版会


私が『論理学をつくる』で論理学の勉強をする。

論理学ばっかりやってても論文が進まないことおびただしいので、2/10 あたりで一旦論理学にはケリをつけようかと思った。しかし、10日までに、目標である様相論理まで終わりそうにない(今6章が終わったとこ。様相論理は11章)。

とりあえずペースを早めるために、ブログで復習するのは後回し。

メモ。

むすかしかったのは、「6.2 セマンティクスとモデル」。

ここでは、アサインメントを使わない方法 (方針 T) と使う方法 (方針 S) の2種類が解説される。アサインメントを使わない場合 (方針 T)、そもそも開いた論理式については考えないので、モデルだけあればいい。アサインメントを使う場合 (方針 S)、モデルとアサインメントを与えることで、開いた論理式の真偽についても考えることができる。

「6.3 存在措定と会話の含意」。

「すべての日本人が体罰を容認する。従って、体罰を容認する日本人が存在する」は妥当な論証ではない、というのがおもしろかった。なぜ妥当ではないかというと、「日本人が存在しない」場合、「すべての日本人は体罰を容認する」が、「体罰を容認する日本人は存在しない」から。この論証は、「日本人が存在する」という条件を織り込んだ場合のみ、妥当な論証となるそうな。

「6.4 伝統的論理学をちょっとだけ」。

伝統的論理学では、妥当な三段論法を九九のような覚え歌で覚えていたらしい。これもおもしろかった。


第6章 おおっと述語論理のセマンティクスがまだだった

6.1 述語論理のセマンティクスをつくらなければ

  • 6.1.1 論理式の真偽は解釈で決まる
  • 6.1.2 翻訳から世界の直接描写へ

6.2 セマンティクスとモデル

  • 6.2.1 数学の助けを借りて形式化をすすめる
  • 6.2.2 モデル
  • 6.2.3 モデル M のもとでの論理式の真理をきっちり定義しよう
  • 6.2.4 方針 T に基づいて「M のもとでの真理」をきちんと定義する
  • 6.2.5 方針 S に基づいて「M のもとでの真理」をきちんと定義する
  • 6.2.6 方針 S における真理の定義
  • 6.2.7 矛盾・論理的帰結・妥当式
  • 6.2.8 反証モデル

6.3 存在措定と会話の含意

  • 6.3.1 同じ論証が妥当になったりならなかったりする怪
  • 6.3.2 食い違いの原因はどこにあるか
  • 6.3.3 会話の含意

6.4 伝統的論理学をちょっとだけ

  • 6.4.1 4つの基本形とその相互関係
  • 6.4.2 伝統的論理学はどのように論証関係をあつかったのか

論理学をつくる

戸田山和久『論理学をつくる』

名古屋大学出版会


私が『論理学をつくる』で論理学の勉強をする。

ギリシア文字について。本書では、図式記号などにギリシア文字を使っている。本ブログではこの方針に従ったり従わなかったりしてきたが、そろそろギリシア文字の分量も増えてきたので方針を決めることにしたい。

  • メタ記号に対象言語と同じ種類の文字を使いたくない、という方針は理解できる。
  • しかしギリシア文字なんか Web で使いたくない(論理記号を使っている時点でどうかという話はあるが)。

よって以後本ブログでは戸田山の記述を以下のように置き換えるものとする。

  • ギリシア小文字については、日本語のカタカナを使う。しかも、小文字であることを示すためになるべく「ャ、ュ、ョ」など小さい文字をあてることにしたい。
  • ギリシア大文字については、日本語の漢字を使う。「甲乙丙」など。

5章は一気に終わった。むしろ6章の述語論理のセマンティクスがむずかしい。


第5章 論理学の対象言語を拡張する

5.1 なぜ言語の拡張が必要なのか

述語論理(predicate logic)
命題の内部構造を問題にする論理だよ。
命題論理(propositional logic)
これまで学んできたような、単純命題の内部構造を問わない論理だよ。

5.2 述語論理での命題の記号化

  • 5.2.1 命題の内部構造とは?
  • 5.2.2 個体指示表現を主語とする文の記号化
  • 5.2.3 普通名詞が主語になっている命題の記号化
  • 5.2.4 もう1つの量化子
  • 5.2.5 翻訳練習をたっぷりやっとこう

命題のことを、「●は■である」という構造をもったものだということにするよ。

●は主語(subject)、■は述語(predicate)と呼ばれることがあるね。

主語になることができる表現には個体指示表現(singular term)、一般名辞(general term)などがあるね。

個体指示表現にはいろんなものがあるけど、代表的なのは次の3種だよ。

  • (1)固有名(proper name): 「吉田戦車」など。
  • (2)確定記述句(definite description): 「日本で一番長い川」など。
  • (3)指示詞(demonstrative): 「これ」など。

(2)と(3)はむずかしいから、ここでは扱わないよ。

命題は次のように記号化するよ。

[Interpretation]

D: は映画監督である
s: スティーブン・スピルバーグ
Ds: スティーブン・スピルバーグは映画監督である
個体定項(individual constant)
命題のうち、個体指示表現を記号化したものだよ。小文字のアルファベットをあてるよ。
述語記号
命題の述部を示す記号だよ。大文字のアルファベットをあてるよ。

述部は個体定項を入れないと完成しないよ。未完成であることを示すために、とりあえず一般化した記号を入れて、Dx などと記号化することにするよ。

Dx は x に個体定項を入れると命題を返す関数だよ。

命題関数(propositional function)
個体の集合から命題の集合への関数のことだよ。述語は命題関数だよ。
全称記号/全称量化子(限量子)/普遍量化子/universal quantifier
∀のことだよ。すべての x について Dx ということを「∀xDx」と書くよ。すべての x について Dx→Mx は「∀x(Dx→Mx)」だよ。
存在記号/存在量化子/existential quantifier)
∃のことだよ。「Dx であるような x がある」ということを「∃xDx」と書くよ。
ド・モルガンの法則
(同値は「==」で表すことにした)
∀x¬Px == ¬∃xPx
¬∀Px == ∃x¬Px

つまり、「すべての x について Px でない」==「Px である x は存在しない」。「すべての x について Px であるわけではない」==「Px でない x が存在する」。

これを使えば、∃で∀を表現することも、∀を∃で表現することもできるよ。

翻訳の際の注意。

「●だけが△する」は「△するのはすべて●」として記号化する。


5.3 述語論理のための言語をつくる

  • 5.3.1 言語 MPL の定義
  • 5.3.2 量化子の作用域と変項の自由な現れ・束縛された現れ

述語論理を展開するための人工言語を定義しよう。この言語を MPL(Monadic Predicate Logic)と呼ぶよ。

【MPLの語彙】

(1)項(term)
個体定項: a, b, c, ...
個体変項: x, y, z, ...
(2)述語記号
P, Q, R, S, ...
(3)論理定項
結合子: →、∧、∨、¬
量化子: ∀、∃
(4)補助記号
(, )

【MPLの文法】

(1)1つの述語記号の後ろに1つの項をおいたものは論理式だよ。これを原子式と呼ぶよ。
(2)A, B を論理式とすると、(A∧B)、(A∨B)、(A→B)、(¬A)はおのおの論理式だよ。
(3)A を論理式、「ャ」を個体変項とすると、∀ャA, ∃ャA はおのおの論理式だよ。
(4)(1)(2)(3)によって論理式とされるもののみが論理式だよ。

これは帰納的定義だよ。帰納的証明が使えるよ。

図式文字について。

本書では個体変項を表す図式文字にギリシア小文字を使っている。

(1)x、y、z などの個体変項を表すために、クシー、ゼータなど。これについて、本ブログでは、「ャ、ュ、ョ」など日本語のカタカナ小文字をあてる。

(2)a,b などの個体定項を表すために、アルファ、ベータなど。これについて、本ブログでは「ァ、ィ、ゥ」など日本語のカタカナ小文字の最初の方をあてる。

(3)項(個体変項 + 個体定項)を表すために、タウ。これについて、本ブログでは「ヵ」をあてる。


上記の文法は下のような不自然な論理式を許容してしまう。

(a)∀xPy など量化子の個体変項と述語記号の後ろの個体変項がずれているもの。

(b)∃yQa など量化子がついているが述語記号の後ろに個体変項がないもの("a" は定項)。

(c)∃x∀xPx のように余分な量化子がついているもの。

これらに対しては、認めてしまう「おおらか路線」と、認めないように定義を縛る「神経質路線」の2つがありうる。本書ではおおらか路線を採用し、これらの論理式を認めることにする。


現れ/作用域などの定義

(1)個体変項ャの現れ(occurrence)
∃ャPャ∧Qャ や ∃ャ(Pャ∧Qャ) のように同じ個体変項が何カ所にも現れることがある。このそれぞれの出現箇所を、個体変項ャの現れというよ。ただし量化子直後のもの(∃ャの「ャ」など)はのぞくよ。
(2)量化子の作用域(scope)
形成の木において、その量化子が結合する相手になった部分論理式のことだよ。∀xDx→Mx において、∀の作用域は Dx。∀x(Dx→Mx)において∀の作用域は(Dx→Mx)だよ。
(3)ャを束縛する量化子
∀ャや∃ャのように量化子の直後にある個体変項がャであるとき、その量化子はャを束縛する量化子であるという。例えば∃x の∃は x を束縛する量化子。
(4)個体変項の自由な現れ(free occurence)
個体変項ャの表れが自由である ⇔ その表れがャを束縛する量化子のなかにない。
現れが自由でないとき、束縛されている(bound)と言う。
(5)閉じた式と開いた式
閉じた式(closed formula)とは、個体変項のいかなる自由な現れも含まない論理式のことだよ。そうでない論理式を開いた式(open formula)というよ。人によっては閉じた式を文と呼ぶけれど、本書ではその言い方は採用しないよ。
(6)量化子の空虚な現れ(vacuous occurrence)
量化子の現れ∀ャまたは∃ャが空虚である ⇔ その量化子の作用域に変項ャが自由に現れない。

5.4 タブローの方法を拡張する

  • 5.4.1 具体例からヒントを得る
  • 5.4.2 展開規則とその使い方

述語論理についてもタブローを使えるようにするよ。

量化子の展開規則。

量化子の作用域に、個体定項をガンガン代入してやったらいいんだよ。

∃について。

∃の展開規則を、存在例化(EI: existential instantiation)というよ。

EI
∃ャA
A[ァ/ャ]
(ただし、ァはその経路にこれまで現れていない個体定項)
(A[ァ/ャ]は、論理式 A に含まれる個体変項「ャ」の自由な現れに一斉に個体定項「ァ」を代入した結果得られる式のことだよ)

∀について。

∀の展開規則を、普遍例化(UI: universal instantiation)というよ。

UI
∀ャA
A[ァ/ャ]
(ただし、ァは任意の個体定項とする)
[UI]は同じ式に何度も繰り返し適用される。つまり、新しい個体定項が現れるたびにその定項を代入したものを書き足さねばならないよ。
【攻略法】
[EI] はなるべく [UI] の前に適用すること。そうすれば何度も個体定項を代入する手間も省ける。

論理学をつくる

戸田山和久『論理学をつくる』

名古屋大学出版会


私が『論理学をつくる』で論理学の勉強をする。4章終わり。次からようやっと述語論理。


4.2 タブローの信頼性

  • 4.2.1 なぜ信頼性を確認しなければならないか
  • 4.2.2 タブローの決定可能性
  • 4.2.3 閉鎖タブローが生じたならば矛盾している
  • 4.2.4 矛盾した集合はいつでも閉鎖タブローを生む

タブローが信頼できるためには、次のことが必要だよ。

(1)決定可能性(decidability):有限集合からはじめたタブローが有限のステップで手続きを終了させる。

(2)どのような論理式の有限集合を出発点としてタブローを書いても、閉鎖タブローが生じたならばその集合は矛盾している。

(3)どのような論理式の有限集合を出発点としてタブローを書いても、それが矛盾した集合ならばいつでも閉鎖タブローが生じる。

これを証明していくよ。

【定理22】
タブローの方法は決定可能である。

証明省略。書き足される式が段々短くなることを利用する。

【定理23】
式の有限集合Τからは閉鎖タブローが生じる ⇒ Τは矛盾している

証明省略。次の2つの補助定理を使う。

【補助定理23-1】
タブローのある経路(途中でも可)が充足可能可能なら、その経路は閉じていない。

対偶を示して証明する。

【補助定理23-2】
タブローの展開規則はすべて次の性質をもっている。
(1)枝分かれのない規則: 上段の論理式が真理値割り当てVのもとで1であるならば、下段の論理式もVのもとで1である。
(2)枝分かれのある規則: 上段の論理式が真理値割り当てVのもとで1であるならば、下段の論理式のうち少なくともどちらかがVのもとで1である。

これは結合子の展開規則により明らか。

定理23を証明するには、2つの補助定理を使って対偶を示してやればいい。

(Τが充足可能なら、Tを充足する真理値割り当てVが存在する。経路は閉じていない。23-2より、経路の一本はVのもとで1となる、云々)

【定理24】
式の有限集合Τは矛盾している ⇒ Τからは閉鎖タブローが生じる

やっぱり対偶をしめせばよい。

対偶をしめすのは簡単だが、ここでヒンティッカ集合を使う。

ヒンティッカ集合(Hintikka set) / モデル集合(model set)
次の条件を満たす論理式の集合Kのことだよ。
(¬) :いかなる原子式Pについても、Pと¬Pの両方がKに属することはない。
(¬¬) :¬¬A∈K ⇒ A∈K
(∧) :A∧B∈K ⇒ A∈K かつ B∈K
(¬∨) :¬(A∧B)∈K ⇒ ¬A∈K かつ ¬B∈K
(¬→) :¬(A→B)∈K ⇒ A∈K かつ ¬B∈K
(¬∧) :¬(A∧B)∈K ⇒ ¬A∈K または ¬B∈K
(∨) :A∨B∈K ⇒ A∈K または B∈K
(→) :A→B ⇒ ¬A∈K または B∈K
(←→) :A←→B ∈K ⇒ (A∈K かつ B∈K) または (¬A∈K かつ ¬B∈K)
(¬←→) :¬(A←→B)∈K ⇒ (A∈K かつ ¬B∈K) または (¬A∈K かつ B∈K)

これらの条件は、結合子の展開規則に対応している。タブローを書くと、開放経路はヒンティッカ集合になる。つまり、タブローを書くとは、論理式集合の部分論理式を書きだし、もとの論理式を包含するようなヒンティッカ集合へと拡大する作業であった。

定理25
いかなるヒンティッカ集合も充足可能である

ヒンティッカ集合は原子式がすべて1のとき、充足される。これは帰納法で証明できる。

論理学をつくる

戸田山和久『論理学をつくる』

名古屋大学出版会


私が『論理学をつくる』で論理学の勉強をする。

(↑やっと Youtube をやめた)

タブロー描きは楽しいなっと。


第4章 機械もすなる論理学

4.1 意味論的タブローの方法

  • 4.1.1 機械的な判定法を作ろう
  • 4.1.2 タブローのルーツ
  • 4.1.3 機械的方法にしてゆくためのヒント
  • 4.1.4 タブローを汎用的な方法にする
  • 4.1.5 閉鎖経路と閉鎖タブロー
  • 4.1.6 人間らしくタブローを描こう ― タブロー構成の攻略法
  • 4.1.7 妥当性、トートロジー性、論理的同値性の判定とタブロー

妥当性、矛盾、トートロジーなどを判定する決定手続き(decision procedure)はアルゴリズムでなければならないよ。

アルゴリズム(algorithm)
次の条件を満たす手続きのことだよ。
(1)明確性。次の操作が1つに決まるよ。
(2)汎用性。どのような論証や論理式に対しても使えるわ。
(3)有限性。手続きの実行が有限数のステップで終わらなければならないよ。
真理の木(truth tree), 意味論的タブロー(semantic tableau), 分析タブロー(analytic tableau)
真理表よりも使いやすいアルゴリズムだよ。ヒンティッカのモデル集合の考え方を応用し、スマリヤンらが広めたんだって。
タブローの書き方
(1)はじめに、チェックする論理式を縦に列挙してね。
(2)∧で結ばれた論理式は縦に並べる。∨で結ばれた論理式は2つに分岐するよ。
(3)¬Aはそのまま書いてね。
(4)他の結合子は∧∨¬の組合せで表現するよ。結合子をタブロー上に表現する方法を展開規則というよ。
(5)ある経路にAと¬Aがともに現れた場合は末端に×をつけてね。この経路は矛盾するの。
経路(path)
タブローのてっぺんからひとつの末端までをたどり、そこに含まれる論理式を集めてつくった式集合のことだよ。
閉鎖経路(closed path)
末端に×のついた経路だわ。双でない経路は「開放経路(open path)というわ。
閉鎖タブロー(closed tableau)
すべての経路が閉鎖経路であるようなタブローのことだよ。また、そのタブローは閉じて終わる、というよ。
適用可能な展開規則をすべて適用し終わった段階で、まだ1つでも開放経路が残っているタブローを開放タブロー(open tableau)というの。またそのタブローは開いて終わる、というの。
判定基準(矛盾)
論理式の集合{A1, A2,...,A3}が矛盾している ⇔ A1, A2, ..., An を縦に並べてはじめたタブローが閉鎖タブローになるんだって。
判定基準(妥当)
前提 A1, ..., An から結論 C を導く論証が妥当である ⇔ A1, ..., An および ¬C を縦に並べたものからはじめたタブローが閉鎖タブローになる。
判定基準(トートロジー)
論理式 A がトートロジーである ⇔ ¬A からはじめたタブローが閉鎖タブローになる。

論理学をつくる

戸田山和久『論理学をつくる』

名古屋大学出版会


私が『論理学をつくる』で論理学の勉強をする。

コンパクト性定理の証明が3章のクライマックス。論理式→論理式の集合ときて、ついに論理式の無限集合になった。むずかしい。一応ここだけは、証明を写経しておくことにする。

ようやっと3章が終わった。

3.11 コンパクト性定理

  • 3.11.1 コンパクト性定理とは
  • 3.11.2 コンパクト性定理の証明・パートⅠ
  • 3.11.3 コンパクト性定理の証明・パートⅡ
【定理20】コンパクト性定理(compactnesstheorem)
論理式の集合Tが充足可能である⇔Tのすべての有限部分集合が充足可能である。

以下ではこれを証明するよ。


前置き

Tが有限集合のとき、上記が成り立つのは自明であることを示す。

  • Tの有限部分集合のうち、最大のものがTになる。
  • ならば「Tのすべての有限部分集合が充足可能である⇒Tが充足可能である」は明らか(T自身が「Tのすべての有限部分集合」に含まれる)。
  • また「論理式の集合Tが充足可能である⇒Tのすべての有限部分集合が充足可能である。」も明らか(「Tのすべての有限部分集合」はTを充足する真理値割り当てのもとで、充足される)

またTが無限集合であっても、「論理式の集合Tが充足可能である⇒Tのすべての有限部分集合が充足可能である」は自明である(「Tのすべての有限部分集合」はTを充足する真理値割り当てのもとで、充足される)。

よって証明すべきことは、

「Tのすべての有限部分集合が充足可能である ⇒ 論理式の集合Tが充足可能である」

ということのみである。

また「すべての有限部分集合が充足可能である」は長いので、以下縮めて「有限充足可能(finitely sastisfiable)である」ということにする。


証明方針

証明すべきことは、「Tのすべての有限部分集合が充足可能である⇒論理式の集合Tが充足可能である」

言い換えれば、

  • 「論理式の無限集合Tについて」
  • 「どのような有限部分集合をとってもそれぞれを充足する真理値割り当てが見つかる」ならば、
  • 「T全体を充足するような真理値割り当てが存在する」

以下ではこれを以下のような手順で証明する。

  1. 有限充足可能な論理式の集合Tは、ある都合のよい性質を持つ集合△に拡大できることを示す。
  2. △を使うと簡単にTを充足する真理値割り当てをつくれることを示す。

証明その1

  • 1.有限充足可能な論理式の集合Tは、ある都合のよい性質を持つ集合△に拡大できることを示す。

論理式の集合Tが有限充足可能であると仮定する。

すべての論理式をA1, A2, A3, ..., Anのような形で順番に並べる。

論理式の無限集合{K0, K1, K2, ..., Kn}を以下のように定義する。

Kの定義
(1)K0=T
(2)Kn∪{An+1}が有限充足可能なら、Kn+1=Kn∪{An+1}とする。
Kn∪{An+1}が有限充足可能でないなら、Kn+1=Kn∪{¬An+1}とする。

この時、すべてのKnについて以下が成り立つことを証明しよう。

【補助定理20-1】
どのKnも有限充足可能である。
【補助定理20-1の証明】
(1) Tについての仮定よりK0(T)は有限充足可能である。
(2) Knが有限充足可能であると仮定する。このとき、
Kn+1(「Kn∪{An+1}」または「Kn∪{¬An+1}」)が有限充足可能である(☆)
と示せば、帰納法により補助定理20-1を証明することができる。
(3) (☆)の証明には、背理法を用いる。すなわち、(a)Knが有限充足可能であるのに、(b)Kn∪{An+1}が有限充足可能ではなく、(c)Kn∪{¬An+1}も有限充足可能ではないと仮定する。
(4) (b)より、Kn∪{An+1}の有限部分集合に充足可能でないものがあることになる。それはKnの有限部分集合Kn'に{An+1}を合わせた集合であるはずだ。なぜならば、{An+1}を含まないKnの有限部分集合は(a)より充足可能だからである。
(5) 従って、Kn'∪{An+1}が矛盾するようなKnの有限部分集合Kn'が存在する。
(6) 同様に(c)より、Kn''∪{¬An+1}が矛盾するようなKnの有限部分集合Kn''が存在する。
(7) (5)および(6)を変形すれば、「Kn'|=¬An+1」「Kn''|=An+1」を得られる。これは「Kn'∪Kn''」矛盾することを示している。
(8) しかし、Kn'∪Kn''はKnの部分集合なので、これは仮定(a)に反する。
(9) 仮定が誤りであったため、(☆)および補助定理20-1が証明された。■

以上より、論理式の無限集合{K0, K1, K2, ..., Kn}について、どのKnも有限充足可能であることが証明された。

ここでさらに{K0, K1, K2, ..., Kn}の合併集合を△とおく。△は以下のような性質を持つ。

【△の性質】
(1)T⊆△
(2)すべての論理式Aについて、Aか¬Aのいずれかが△に属す。
(3)△は有限充足可能である。

このうち(3)だけは証明しておく。

【(3)の証明】
△のどの有限部分集合△'も、それが含むAnのうち、番号が最大のものがあるはずである。その番号を仮にnとすると、△'はKnの部分集合である。補助定理20-1よりKnは有限充足可能であるから、Knの部分集合である△'も充足可能である。したがって△のどの有限部分集合も充足可能である。

証明その2

  • 2. △を使うと簡単にTを充足する真理値割り当てをつくれることを示す。

先に導入した△をもとにして、次のような原子式への真理値割り当てVをつくる。

【Vの定義】
原子式PiがVのもとで真である ⇔ Pi∈△

つまり、Vは△に含まれるすべての原子式だけに真を割り当てるような真理値割り当てである。このようなVについて以下が成り立つことを示す。

【補助定理 20-2】
任意の論理式Aについて、AがVのもとで真である ⇔ A∈△

これを示せば、Vは△に属するすべての式を充足することになる。T⊆△だから、Vは同時にTに属するすべての式を充足する。

【補助定理 20-2 の証明】
[Basis] Aが0個の結合子を含むとき、つまりAが原子式のとき、
AがVのもとで真である ⇔ A∈△ はVの定義より明らか。

[Induction step] (1) K個以下の結合子を含む論理式については、AがVのもとで真である ⇔ A∈△ が成り立っていると仮定する。
(2) このとき、K+1個の結合子を含む論理式についても、AがVのもとで真である ⇔ A∈△ が成り立っていることを言う。 Subcase 1. K+1個の結合子を含む論理式Aが¬Bという形のとき、 ¬BがVのもとで真である ⇔ K個の結合子を含む論理式BがVのもとで偽である ⇔ B∈△ ではない(帰納法の仮定より) ⇔ ¬B∈△ (△の性質(2)より) Subcase 2. K+1個の結合子を含む論理式AがB∧Cという形のとき、 B∧CがVのもとで真である ⇔ K個の結合子を含む論理式B, Cについて、BがVのもとで真であり、かつCがVのもとで真である ⇔ B∈△かつC∈△(帰納法の仮定より) このとき、B∧C∈△でないとすると、△の性質(2)より、¬B∧C∈△となる。 すると、{B, C, ¬B∧C}が△の部分集合となるが、この集合は矛盾している。これは△が有限充足可能であることに反する。 したがって B∈△かつC∈△ ⇔ B∧C∈△ である。 Subcase 3. AがB∨Cという形のとき、 B∨CがVのもとで真である ⇔ K個の結合子を含む論理式B, Cについて、BがVのもとで真であるか、またはCがVのもとで真である ⇔ B∈△あるいはC∈△(帰納法の仮定より) このとき、B∨C∈△でないとすると、△の性質(2)より、¬(B∨C)∈△となる。 ド・モルガンの法則より、¬(B∨C) は ¬B∧¬C と同値。 すると、{B, C, ¬B∧¬C)}が△の部分集合となるが、この集合は矛盾している。これは△が有限充足可能であることに反する。 したがって B∈△あるいはC∈△ ⇔ B∨C∈△ である。 Subcase 4. AがB→Cという形のとき、 B→CがVのもとで真である ⇔ K個の結合子を含む論理式B, Cについて、BがVのもとで偽であるか、またはCがVのもとで真である ⇔ B∈△でないか、あるいはC∈△ (帰納法の仮定より) ⇔ ¬B∈△、あるいはC∈△ (△の性質(2)より) このとき、B→C∈△でないとすると、△の性質(2)より、¬(B→C)∈△。 ¬B∈△、あるいはC∈△の場合、{¬B, ¬(B→C)}{C, ¬(B→C)}のいずれかが△の部分集合となる。しかし、これらはどちらも矛盾する。これは△が有限充足可能であることに反する。 したがって ¬B∈△、あるいはC∈△ ⇔ B∨C∈△ である。
(3) 以上より、すべての論理式Aについて、AがVのもとで真である ⇔ A∈△ が言えた。■

証明終わり

上記により、次のことが言えた。

有限充足可能な論理式の集合Tは以下のような性質を持つ△に拡大できる。

【△の性質】
(1)T⊆△
(2)すべての論理式Aについて、Aか¬Aのいずれかが△に属す。
(3)△は有限充足可能である。

また以下のようなVについて、補助定理 20-2が言える。

【Vの定義】
原子式PiがVのもとで真である ⇔ Pi∈△
【補助定理 20-2】
任意の論理式Aについて、AがVのもとで真である ⇔ A∈△

Vは△を充足するため、△の部分集合であるTも充足する。

従って、「Tのすべての有限部分集合が充足可能である⇒論理式の集合Tが充足可能である」を証明することができた。

【定理20】コンパクト性定理(compactnesstheorem)
論理式の集合Tが充足可能である⇔Tのすべての有限部分集合が充足可能である。

は証明された。■


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

  • 3.12.1 メタ言語と対象言語を区別しよう
  • 3.12.2 意味論的に閉じた言語とパラドクス
  • 3.12.3 タルスキによる言語の階層化とうそつきのパラドクスについての最近の考え方
対象言語(object language)
論理の研究のためにつくられた人工言語Lのことだよ。Lには「P、Q、R」などの原子式や「∧、∨、¬、→」などの結合子が含まれているよ。
メタ言語(meta-language)
対象言語について話をするための言語だよ。本書では日本語や、「A、B」などの図式文字や、「⇔」などの便利な記号のことだよ。

この本では、対象言語とメタ言語を分けているから、両者を混同してはいけないよ。

意味論的に閉じた言語
対象言語としてもメタ言語としても使われる言語のこと。例えば日本語は意味論的に閉じた言語であるよ。意味論的に閉じた自己言語では、自己言及(self-reference)が可能になるよ。
自己言及はときに、意味論的パラドクス(semantic paradox)を生み出すよ。意味論的パラドクスの代表例は、うそつきのパラドクス(Liar paradox)だよ。

タルスキはうそつきのパラドクスを回避するために、意味論的に閉じた言語を考察の対象から外したよ。言語Lにおける真理の定義を別の言語ですることにしたよ。

こんな風な言語の階層化によってパラドクスは回避できたけど、最近はこれはやりすぎだったかもしれないと言われているよ。

(1)自己言及には無害なものも数多くあるよ。

(2)また、自己言及的な文を用いなくてもパラドクスをつくることができるよ。

つまり、パラドクスは文ではなく、文の使い方によって生み出されるってことだよ。

そこで最近の論理学者は意味論的に閉じた言語でパラドクスを回避する方法を模索しているよ。でも本書ではそこまでフォローできないよ。

論理学をつくる

戸田山和久『論理学をつくる』

名古屋大学出版会


私が『論理学をつくる』で論理学の勉強をする。

しだいに証明問題がむずかしくなる。証明問題の解答はむずかしい。受験参考書のように、「これが書けていれば5点」など、採点の指示を与えてほしいものだ。


3.9 真理関数という考え方:前

  • 3.9.1 真理関数とは何か
  • 3.9.2 真理関数は何通りあるか
真理関数(truth-function)
真理値の集合の直積から {1, 0} への関数のことだよ。
実現(realize), 表現(express)
真理関数を論理式によって表すこと。ひとつの真理関数を実現する論理式は複数ある。例えば、input が{1} output が{1} の真理関数は、P∧¬P, P, P→P などによって実現されるよ。
真理関数の一般的定義
{1, 0}^n から {1, 0} への関数を n 変数の真理関数と呼ぶよ。
ちなみに n 変数の真理関数は 2^2^n 個あるよ。

3.9 真理関数という考え方:後

  • 3.9.3 真理関数の表現定理
  • 3.9.4 どのような結合子の組み合わせが十全なのか
  • 3.9.5 シェーファーの魔法の棒
定理17(表現定理 / 関数的完全性の定理)
¬, ∧, ∨ のみを結合してして含む論理式によって、n 変数の真理関数はすべて表せる。
十全(adequate) / 関数的に完全(functionally complete)
これは結合子の集合に対して使う言葉だよ。その結合子集合で n 変数の真理関数はすべて表せるという意味だよ。

{¬, ∧}, {¬, ∨}, {¬, →} は十全だよ。

シェーファーの棒(Sheffer stroke)
A | B は ¬(A∧B) と同値だよ。これは"nand" と読むよ。シェーファーの棒とも呼ぶよ。この結合子は1つだけで十全だよ。
シェーファー関数
1つで十全であるような真理関数のことだよ。
定理19
2変数のシェーファー関数は、| と ↓だけだよ。

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

  • 3.10.1 「→」に感じる違和感
  • 3.10.2 「→」の定義の正当化

「→」は「ならば」の近似だけど、だいぶ違和感があるよ。

関連性(relevance)にかかわる違和感
日本語の「ならば」は前件と後件の間に内容上の関連性があるよ。「→」は真理値の組合せだけを問題にするよ。このような現象を関連性にかかわる違和感というよ。

しかし「→」は「ならば」の重要な特徴を反映しているよ。

(1)逆は必ずしも真ならず
「A ならば B」が成り立つからといって、「B ならば A」が成り立つとはかぎらない。
(2)推移性
「A ならば B でありしかも B ならば C であるならば、A ならば C である」がトートロジーだよ。

論理学をつくる

戸田山和久『論理学をつくる』

名古屋大学出版会


私が『論理学をつくる』で論理学の勉強をする。

だんだん難しくなってきた。対象が論理式から論理式の集合へとシフトしてきたのだが、頭がついていけない。今日は丁寧めに復習する。テキストで書くのが無理になってきたので早く TeX を覚えようと思った。


3.7 論証の正しさとは何か

  • 3.7.4「矛盾からは何でも出てくる」の怪
  • 3.7.5 論理学の3つの顔は1つである

論証の妥当性、矛盾、形式的真理という論理学の3つの顔が同じであることを示すよ。

妥当性とトートロジー

定理9
前提 A1, ..., An から結論 C を導く論証が妥当である ⇔ 論理式 (A1∧...∧An)→ C がトートロジーである。
証明
前提 A1, ..., An から結論 C を導く論証が妥当である
⇔ この論証には反例がない (妥当な論証とは反例のない論証である*)
⇔ A1, ..., An を同時に 1 とし、なおかつ C を 0 とするような真理値割り当ては存在しない(反例の定義より)
⇔ (A1∧...∧An) を 1 とし、なおかつ C を 0 とするような真理値割り当ては存在しない(結合詞∧の性質より)
⇔ (A1∧...∧An)→ C を 0 とするような真理値割り当ては存在しない(結合詞→の性質より)
⇔ (A1∧...∧An)→ C はトートロジーである(トートロジーとは真理値がつねに 1 である論理式のことである*)

妥当性と論理的同値性

定理10
A と B が論理的に同値 ⇔ 論証(A ⇒ B)と論証(B ⇒ A)がともに妥当。
証明
A と B が論理的に同値
⇔ A と B の真理値がつねに一致する(論理的に同値とは真理値がつねに一致するということである*)
⇔ A ←→ B がトートロジー(結合詞 ←→ の性質より)
⇔ (A → B)∧(B → A)がトートロジー
⇔ A → B がトートロジー、かつ B → A がトートロジー(結合詞∧の性質より)
⇔ 論証(A ⇒ B)と論証(B ⇒ A)がともに妥当(先の定理9より)

3.8 論理的帰結という関係

  • 3.8.1 論理的帰結を定義する
  • 3.8.2 論理的帰結関係について成り立つ定理

論理的帰結の定義

論理的帰結とは
妥当な論証から導き出された結論のことだよ。
2重ターンスタイル(double turnstile)とは
論理的帰結を示す記号「|=」のことだよ。
T |= C*1 ⇔ T に含まれている式と C を構成しているすべての原子式への真理値割り当てのうち、T に含まれるすべての式を同時に 1 とし、なおかつ C を 0 とするような真理値割り当ては存在しない。
トートロジー
|= C ⇔ C はトートロジーである。
矛盾
T |= ⇔ T は矛盾している。

定理

定理14
(1)A |= A
(2)もし T |= A ならば、 T, B |= A
(3)もし T |= A 、A, K |= B ならば T, K |= B
単調性(monotonicity)、またはthinning
(2)のことだよ。前提に余計なものを付け加えても論証の妥当性は変わらないよ。単調性を持たない論理のことを非単調論理(non-monotonic logics)というよ。
cutting
(3)のことだよ。
cutting の特殊なやつ
B が存在しないとき。
T |= A、 A, K |= ならば T, K |=
T, K が空集合のとき。
|= A、 A |= B ならば |= B

定理15
(4)A, ¬A |= B
(5)T, ¬A |= ⇔ T |= A
T, A |= ⇔ T |= ¬A
(6)T |= A∧B ⇔ T |= A かつ T |= B
(7)T, A∨B |= ⇔ T, A |= かつ T, B |=
(8)T, A |= B ⇔ T |= A → B
定理16
(a) T |= A ⇒ T |= A∨B
(b)T |= A∨B、 A, K |= C、 B, K |= C ⇒ T, K |= C
(c)A, T |= C、 B, T |= C ⇒ T, A∨B |= C

  • *1: T は論理式の集合

論理学をつくる

戸田山和久『論理学をつくる』

名古屋大学出版会


私が『論理学をつくる』で論理学の勉強をする。

結構ハマってきた。

あまり進まなかったので今回は用語の整理が一瞬で終わった。細切れに書くとあとから参照しづらくてよくないが、あとでまたまとめることにしよう。

3.7 論証の正しさとは何か

  • 3.7.1 論証の妥当性を理解する鍵は反例にある
  • 3.7.2 論証の妥当性を定義する
  • 3.7.3 構成的両刀論法と場合分けによる証明
反例(counterexample)とは
論証の前提がすべて真になるが、結論は偽になる場合のことだお。

妥当な論証とは反例の存在しない論証のことだお。

論理学をつくる

戸田山和久『論理学をつくる』

名古屋大学出版会


私が『論理学をつくる』で論理学の勉強をする。3.5 はむずかしかった。


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

  • 3.5.1 真理値分析とは何をやることだったのか
  • 3.5.2 真理値割り当て
真理表を書くとは
原子式への真理値の割り当てを複合的な論理式への真理値割り当てへと拡張するということ。
真理値割り当ての定義
L の原子式からなる或る集合を F とする。F に対する真理値割り当て(truth assingment) V を次のような関数とする。
V:F→{1, 0}

これは原子式の数を限定せず、任意の集合 F とした場合の定義。式は V が「F から {1, 0} への関数」であることを表す。

要するに F のどの要素にも 1 または 0 が割り当てられるということ。これは、二次関数 y=f(x) でどの x にも f(x) がひとつ割り当てられるのと同じこと*1。真理表においては、各行がそれぞれ異なる V に対応することになる。

付置関数(valuation function)
V のことをこう呼ぶこともある。
真理値分析でやっていること
F に含まれる原子式からスタートし、帰納的に定義される論理式のすべてからなる集合を ~F とする。真理値分析で行われるのは、F への真理値割り当て V を拡張し、~F に含まれる各論理式への「拡大版真理値割り当て ~V:~F→{1, 0}」をつくることである。

付録 A-2 集合論についての基礎知識

    • 2.1 集合とその表記法
    • 2.2 集合のアイデンティティは何か
    • 2.3 集合に対する演算
    • 2.4 順序対とデカルト積
    • 2.5 同値関係と同値類

集合の話が出てきてむずかしかったのでここを先にやった。


3.6 矛盾とは何か

    • 3.6.1 論理式の矛盾の集合を定義する
矛盾(inconsistent)
論理式の集合Γが矛盾している ⇔ Γのすべての論理式を同時に真にする真理値割り当てが存在しない。
充足可能(satisfiable)/整合的(consistent)
矛盾していないこと。
  • *1: y=f(x) を F:x→f(x) と書いてもよい

論理学をつくる

戸田山和久『論理学をつくる』

名古屋大学出版会


私が『論理学をつくる』で論理学の勉強をする。

3.5.1 まで進んだ(昨日)。

とにかく真理表をつくって真理値分析を行ってみる(といろんなことがわかる)、ということを学んだ。

余談

Everything That Linguists Have Always Wanted to Know About Logic but Were Ashamed to Ask

James D. McCawley, "Everything That Linguists Have Always Wanted to Know About Logic but Were Ashamed to Ask"

巻末のブックガイドで紹介されている本。id:shim に教えてもらった。


タイトルの元ネタになっている本。

"Everything You Always Wanted to Know About Sex but Were Afraid to Ask"

ウディ・アレン監督の映画版。

"Everything You Always Wanted to Know About Sex"

映画の日本語版。

ウディ・アレンの誰でも知りたがっているくせにちょっと聞きにくいSEXのすべてについて教えましょう

ウディ・アレンの誰でも知りたがっているくせにちょっと聞きにくいSEXのすべてについて教えましょう

映画の邦題をふまえて邦訳すると『言語学者なら誰でも知りたがっているくせにちょっと聞きにくい Logic のすべてについて教えましょう』。

直訳すると『言語学者がいつも Logic について知りたがっているすべてのこと。でもちょっと聞くのは恥ずかしい』。

恥じる言語学者がかわいい。


用語の整理(3章途中まで)

3.4 までの用語を整理しておく。

真理表

真理表(truth table)
結合詞で結ばれた命題とそれぞれの命題の真理値の関係を表す表のことだよ。人工言語 L では、結合詞の意味は真理表によって与えられるよ。
真理値(truth value)
真/偽(真理表では1,0)のことだよ。
2値原理
論理式はすべて真・偽いずれかの真理値を持つという原理のことだよ。二つ以上の真理値を持つ論理学は多値論理学(many-valued logic)というよ。
排他的選言(exclusive disjunction)/非排他的選言(non-exclusive disjunction)
排他的選言は「AまたはBをプレゼント」というときの「または」のこと。非排他的選言は「日本国籍を持つかまたは日本国籍を持つ者と結婚している者」というときの「または」のこと(両方の条件を満たしていてもよい)。
真理値分析
論理式の真理条件を分析すること。
真理条件(truth condition)
論理式がどんなときに真になるのか。
双条件法(biconditional)
「←→」のことだよ。英語では「A iff B」とも書く。「A, if and only if B」と読む。

トートロジー

トートロジー(tautology)
原子式の真理値にかかわらず常に 1 となる式のことだよ。T で表すよ。
事実式(contingency)
原子式の真理値の取り方によって 1 にも 0 にもなる式のことだよ。
矛盾式(inconsistent wff.)
原子式の真理値にかかわらず常に 0 となる式のことだよ。逆さまの T で表すよ
充足可能式(satisfiable wff.)
1 になることができる式だよ。トートロジー + 事実式のことでもある。

代表的なトートロジー

省略。


トートロジーとは

理性の真理/分析的真理
経験によって確かめる必要がなく、言葉の上だけで正しいことがわかってしまう真理のことだよ。必然的真理とも言うよ。
事実の真理/経験的真理
世界のたまたまの事情によって真になっている真理のことだよ。偶然的真理ともいうよ。
形式的真理/論理的真理
分析的真理のうちで、論理定項の意味だけによって真であるもののことだよ。論理定項以外の言葉の意味によって真理である命題は含まれないよ。
トートロジーとは
形式的真理を論理学的に表現したものだよ。
トートロジーはつねに真だけど、情報量が 0 だよ。

論理的同値

論理的同値(logically equivalent)
原子式の真理値のいかなる組合せに対しても真理値が同じだってことだよ。
定理5
二つの論理式 A, B が論理的同値であるならば、A←→B はトートロジーであり、A←→B がトートロジーならば A, B は論理的同値である。
同値変形
論理的同値である別の式に変形すること。
置き換えの定理(replacement theorem)
A, B が論理的同値ならばC[A], C[B] も論理的同値である。
強い置き換えの定理
(A←→B)→(C[A]←→C[B]) はトートロジーである。

同値変形の例

省略。

論理学をつくる

戸田山和久『論理学をつくる』

名古屋大学出版会


私が『論理学をつくる』で論理学の勉強をする。

第1章から第2章までの用語を整理するよ。


論理学の対象

論理学の対象は以下の三つだよ。

  • 論理的帰結/論証の妥当性
  • 矛盾
  • 形式的真理
形式的真理とは
「~は…であるかないかいずれかである」のような、形式だけで真理であることが自明な命題のことだよ。

上記の三つは実は同じところに通じるよ。


論証の正しさ

論証の正しさと命題の正しさを区別しよう。

真(true) / 偽(false)とは
命題が正しいかどうかについては真 / 偽という語を使おう。
妥当(valid) / 非妥当(invalid)とは
論証が正しいかどうかについては妥当 / 非妥当という語を使おう。

論理学が扱うのは論証の妥当 / 非妥当の方だよ。

妥当性は論理の形式に関わるよ。

論理形式とは
論理定項だけを残し、他を一般化したもの。
論理定項(logical constant)とは
接続詞(「または」など)、量化詞(「すべて」など)、否定詞(「でない」など)など論理に関わる語のことだよ。論理定項とそれ以外の区別は一概に言えないよ。

人工言語 L

自然言語の場合、論理形式と文法形式が一致しないことがある。人工言語を使うことにしよう。

単純命題とは
肯定文の単文の命題だよ。
複合命題とは
単純命題を組み合わせた命題だよ。

ただし何が単純命題であるかは論証によって異なるよ。

原子式(atomic formula)とは
単純命題を記号化したものだよ。
論理結合詞(logical connective)とは
∧、∨、¬、→のことだよ。

∧、∨、¬、→。これらの結合詞は真理関数的だよ。

真理関数的とは(truth-functional)
要素の真偽が決まれば、その結合詞で結ばれた全体の真偽も決まるようなタイプの結合詞のことだよ。この本では真理関数的な結合詞のみを使うよ。

人工言語 L の定義

語彙
(1)原子式
⇒P, Q, R または P1, P2, P3
(2)結合詞
(3)補助記号
⇒(,)
文法
(1) 原子式は論理式だよ。
(2) A, B が論理式のとき、(A∧B)(A∨B)(A→B)(¬A)は論理式だよ。
(3) (1)(2)によって論理式とされるものだけを論理式とするよ。

このような定義を帰納的定義(inductive definition)または回帰的定義(recursive definition)というよ。

形成の木(formation tree)とは
論理式がどのように作られたかを示す図のことだよ。
変数記号(variable)とは
上の文法定義では A, B という記号を使った。これらはいろいろなものを一括して指し示すための記号で変数記号というよ。人工言語 L について自然言語で話すための記号だよ。
このような記号をメタ論理的変項(meta-logical variable)または図式文字(schematic letter)というよ。

帰納的証明

式の長さについての帰納法による証明
人工言語 L の文法を帰納的に定義したから、帰納的証明が可能になったよ。論理学で使う帰納的証明を「式の長さについての帰納法による証明」と呼ぶよ。
Unique Readability Theoram
論理式が一通りにしか読めないということの証明のことだよ。

いくつかの用語

部分論理式(subformula)
論理式 A の形成の木に現れる A 以外の論理式のこと。
主結合詞(main connective)
形成の木の最後に導入された結合詞のこと。
主部分論理式(main subformula)
主結合詞が結ぶ部分論理式のこと。
選言肢(disjunct)
A∨B の A と B のこと。
連言肢(conjunct)
A∧B の A と B のこと。
前件(antecedent)
A→B の A のこと。
後件(consequent)
A→B の B のこと。
リテラル(literal)
P, Q, ¬P, ¬Q のこと。
正リテラル(positive literal)
P, Q のこと。
負リテラル(negative literal)
¬P, ¬Q のこと。

論理学をつくる

戸田山和久『論理学をつくる』

名古屋大学出版会


私が『論理学をつくる』で論理学の勉強をする。とりあえず読みはじめたところ、冒頭にいきなり素晴らしい記述があった。

日本語には連濁という現象がある。例えば、「小屋(こや)」という語の頭に修飾語をつけて、例えば「山小屋」にすると、「やまごや」という具合に下の語が濁る。(…)しかし、「きつね」+「そば」は「きつねぞば」にならないし、「ファミコン」+「通信」は「ふぁみこんづうしんにならない」(吉田戦車氏の指摘による)。



これは...! 『ゴッドボンボン』ではないか。

※参考

ゴッドボンボン』p55


私は以前からこのネタが大好きだったので、戸田山和久氏もこの四コマが好きだと知ることができて大変うれしい。論理学をはじめて本当によかった

また、必要なときに『ゴッドボンボン』を引用することができたので大変うれしい。スキャナーを買って本当によかった

戸田山氏はつづけてこう言った。

我々は連濁するかしないかを判定するに当たって、何らかの規則に従っているらしい。そして初めてのケースにもその規則をあてはめているに違いない。しかも、この規則は、日本語の話し手であればおおむね共有しているはずだ。しかし、自分が従っているその規則をきちんと取り出して述べることのできる人はいるだろうか。

吉田戦車が天才であるゆえんは、このように、暗黙の規則を見事に取り出してみせる点にあるのだと思う。

例えば、

  • アリは群生する
  • 蜂は群生する

ならば「妻」が群生してもいいはずだ。

(火星妻は、アリや蜂のように群生する。『火星ルンバ』参照)


「妻」と「群生」を結びつける飛躍は単純にすごいなと思う。

こんな風に、吉田戦車の発想はよく「どうしてこの語とこの語は結びつかないのか」というところに向かう。哲学者のする概念分析に近く思えることもある。



たのもしき日本語

川崎ぶら、吉田戦車『たのもしき日本語』

この本は言語分析家、概念分析家としての吉田戦車がかいま見られる本だった。

「モテる」の用法を分析する吉田。

吉田●動詞ではなく、状態を表している形容動詞的な語だから活用法が違うのかも知らんな。「昨日9時から10時半までモテた」などとはあまり言わないし、ツッパリが因縁つける際に「モテてんじゃねーよ」などとは言わないのさ。


慧眼だと思う。確かこういうのをアスペクト分析とか言うんだった気がする。

検索していたらこんなサイトを発見した。

自発構文の逆使役用法の意味的特徴と統語的特徴

調査の頁にこんな記述があった。

動詞は内在アスペクトによって

  • 状態(state)
  • 動作(activity)
  • 達成(achievement)
  • 完成(accomplishment)

の四種類のいずれかに分類されます。

2005年7月1日の調査(札幌学院大学にて)

「昨日9時から10時半まで~した」という言い方が可能なのは、動作動詞?だろうか。「モテる」は状態動詞なのでこういう言い方はしない、ということなのだと思う。


ところでまったく関係ないが、この調査は「北海道方言の「動詞+ラサル」についての調査」らしい。

そう言えば中学生の頃、古文の「自発」の助動詞を学んだとき、先生が、北海道弁の「~らさる」が自発の助動詞なのだと教えてくれた。

例:「ウニいくらでも食べささる」