ブログ「サイバー少年」

ブログ「サイバー少年」へようこそ!
小学六年生ごろからプログラミングを趣味にしている高校生のブログです。
勉強したことについての記事などを書いています。フリーソフトも制作、公開しています。
(当ブログについて詳しくは「ブログ概要紹介」を参照)

サイバー少年が作ったフリーソフトは「サイバー少年の作品展示場」へ

命題論理の意味論まとめ (前編)

記事「集合と写像の勉強まとめ」なんかも書きましたが、
昨年末から論理学の勉強を継続的にしていて、京都大学の教授の方のサイトをずっと見ています。

そういえばこの前、このサイトが書籍化されたらしい本を見かけました。


今回、命題論理、とくに意味論について書かれてある部分を、ようやく読破しましたので、そのまとめとしてお書きしようと思います。


そういえば昔も論理学について放送大学で学んで、記事「記号論理学という学問を知ってみたが」を書いたことがありました。

あのときは今回の命題論理よりハイグレードな述語論理だったんですが、数学的で厳密な定義はおいといて実用的な論理学をやるみたいなものでしたので、

今回は厳密な部分をとばさずに再挑戦しているみたいな感じですね。

記事の書き方も、あの記事ではトップダウン的な説明でしたが、今回はボトムアップ的であると思います。


ところで、意味論とか構文論ってどういうことなのかイマイチ入ってこないのですが、“命題論理の意味論”なのか“意味論の命題論理”なのか、どっちなんでしょうか。

一応、“命題論理の意味論”と書いてあったので、そういうことにしておきますが…。


あと、記事「集合と写像の勉強まとめ」と続編記事「続・集合と写像の勉強まとめ ~ブール代数も~」、
で書いた数学の知識は正直ほとんど使わなかったと思うのですが、最初の根源的な定義をするところで少しその知識がいりますね。


少なくとも演算というのが何なのか理解する必要がありますし、演算というのがなんのか理解するには写像についての理解、ひいては集合とは何か…

数学は少しずつ積み上げる学問なので、学校で嫌われるんですね。


今回、ひとつの記事に収めるつもりだったのですが、すごく基本的な話をしただけで無駄に長くしてしまったので、これを前編として次回、後編を書こうと思います。

お楽しみにしていてください。





まず、そもそも命題論理というのは命題を扱います。

命題とはなにかというと、これはもはや説明の必要はないでしょうが、
「今日は雨である」、「リンゴは赤い」みたいに、ある特定の世界において真であるか偽であるかが決まる言明のことです。


この命題の内容を数学の言葉で書こうということから話が始まりまして、述語と個体にわける述語論理なんてものもあるわけですが、

現在話している命題論理では、上のような命題は真であるか偽であるかのどちらかなんだから、
真であるという値と、偽であるという値だけで構成された数を作ろうじゃないかという考えになります。

数というのはすなわち集合です。
ようするにまず、真という要素 T と偽という要素 F を持つ集合{ T, F }を定義します。


これで「今日は雨である」などの命題と、{ T, F }中のひとつの要素が対応するわけです。

このとき「今日は雨である」という命題が命題論理の中での最小単位であり、この命題自体は数学的にこれ以上は考察できません。

つまり、命題論理の世界において「今日は雨である」という言明の意味は扱えず、これは{ T, F }中のひとつの要素を表すシンボルでしかありません。

そしてそのシンボルはaとかbとかいうアルファベットに置き換えられます。


このような命題論理における命題の最小単位を原子命題といいます。

原子命題が真(T)であるか偽(F)であるかという問題は数学の世界からは判断できないので、人間が現実世界と対応させて決めます。



さて、しかし「今日は雨、または今日は雪である」とか、「今日は晴れで、今日は雲はない」みたいな、
あきらかに二つの命題を接続したものは、それを二つに分解して命題論理で扱えるようになれば便利ですよね。


そこで、命題論理ではある二つの命題を
「または、OR」の関係で接続、「かつ、AND」の関係で接続することができます。

そして、ある一つの命題に対して、その否定が真であるという命題、つまり「でない、NOT」の関係の命題を作りだすこともできます。


この三種類のものは、数学の世界で、ある命題を元に新しい命題を作りだしているので、そうやって作られた命題は原子命題ではありません。


原子命題を元に新しい命題を作って、またそれを元に新しい命題を作ることができます。

しかしそれを数学的に判別できる範囲で分解していくと、最終的に原子命題ひとつひとつと、それを接続したり編集する数学的な“モノ”に分解できるのです。


それを接続したり編集する数学的な“モノ”とはなんでしょうか。

まず接続するモノについて考えますが、これは二つの命題から命題を作るモノであり、命題というのは命題論理においては{ T, F }の要素だったわけなので、

ようするに二つの{ T, F }の要素から一つの{ T, F }の要素を作りだすこと、つまり{ T, F }上の二項演算です。


同じく編集するモノは、一つの命題から新しい命題を作るので、{ T, F }上の一項演算となります。



というわけで命題論理には、{ T, F }という集合と、いくつかの演算が存在します。

「または、OR」に相当する二項演算は
「かつ、AND」に相当する二項演算は
「でない、NOT」に相当する一項演算はとなります。

実はさらに
含意という二項演算のと、同値という二項演算のがあります。

この二つは、上の三つから同等の演算を作れるので正直いらないんですが、あったほうが短いし直感的なのであるんでしょう。

含意というのはa→bにおいて、aならばbということです。
同値というのはa↔bにおいて、abの真偽が同じであるということです。


しかし、今まで日本語で演算の意味を解説してきましたが、それは数学においてありえないことです。

そこでもう一度、数学的にどういう演算か定義します。
今までの解説は忘れてください。

以下で解説する数学的な定義を日本語で読み解くなら上記だということです。


さて、数学的に演算を定義するというのは、ようするに演算は写像なので写像のグラフとなる集合を定義するということです。

つまり、一項演算なら入力がTの場合とFの場合にそれぞれTなのかFなのかを決めます。

二項演算ならT,Tの場合、F,Fの場合、T,Fの場合、F,Tの場合についてそれぞれTなのかFなのかを決めます。

というわけで以下のように定義します。
(演算)の定義 … (入力):(出力)、...

の定義 … T:F、F:T
の定義 … T,T:T、F,F:F、T,F:T、F,T:T
の定義 … T,T:T、F,F:F、T,F:F、F,T:F
の定義 … T,T:T、F,F:T、T,F:F、F,T:T
の定義 … T,T:T、F,F:T、T,F:F、F,T:F

となります。

注意しなければならないのは、いわゆる「または、OR」であったは、入力が両方とも真であっても真になるということと、

aならばbという説明をしたは、aでないならばbが何であれ真になるということです。

日本語での説明は関係なしに数学的な定義が絶対、たった今そのように数学的に定義したのですから文句のつけようはないですね。


ここまでの話で最終的に、命題論理における基本的な登場人物、つまり集合{ T, F }といくつかの演算が定義できました。


ちなみにこれは記事「続・集合と写像の勉強まとめ ~ブール代数も~」で書いたブール代数としての性質を満たしています。

命題論理の性質は、ブール代数の性質を継承していることがほとんどだと思うのですが、ブール代数は集合の要素が二つとは限らないのに対して、
命題論理では真(T)と偽(F)の二つしかありえないので、それ特有の事柄も諸所あるんでしょうか。

 

さて、今までの話だと、不便なことがあります。

それは、上の定義でいくと命題というものは{ T, F }の要素をいろいろと演算したものであり、それは命題を書いた時点でTなのかFなのかが決まらないといけないということです。

どういうことかというと、命題を書いた時点でそれは{ T, F }の要素をひとつ書いたことと同じになってしまいます。


つまり、ある命題が真であるか偽であるかという題材は、上の話からいくとありえないことです。

結局はTだとかFだとか直接書いて、それがTなのかFなのかを問うていることと同じだからです。


命題というのはそもそも主張であります。

その主張が正しいのかどうかは現実世界がどうなのかということで変わってきます、しかし主張自体は変わりません。


論理学ではわりと、現実世界がどうなっているのかはおいといて、ある主張の特性を考えるということがメインになります。

たとえば、その主張が正しくなるような世界はあるのかとか、この主張が正しい世界においてあの主張も正しいみたいなことです。

しかし、今までのやり方だと現実世界ありきなので、そのような考え方は無理だということです。



そこで新たに論理式というものを作ります。

今までa∧bは、abTならばTで、それ以外ならFという要素を表すものでしたが、

a∧bにたいして論理式という観点で見ると、これは式ということになります。


式とはどういうことかというと、式においてa∧bは、aというものとbというものをという記号で結んだもの、ということしか考えません。

abがそれぞれTなのかFなのかも考えず、全体としてa∧bTなのかFなのかとか、そういう概念もありません。


変な感じですが、四則演算の数学と同じです。

(x+1)(y+1)xy+x+y+1と等しいなんていうのは、両者の式を式でなく数として見てしまうと、11が等しい、22が等しいなんて言ってるようなものです。

しかし式として見れば、両者がどのように解釈しても同じになるという式であると考えることができるでしょう。


いま解釈と言いましたが解釈とはなんでしょうか。
論理学でもそのまま解釈ということを論理式に行います。

解釈とは、a∧bなどの論理式で、実際にabの値を割り当てて、演算して式全体としてTなのかFなのかを出すということです。


式を解釈するためには、まずabの値の割り当てをしますが、これらabは原子命題です。

先ほど論理式じゃなくて集合と演算の側面での話のときに原子命題という用語を使いましたが、
これは本当は誤りで、原子命題とは論理式においてabなどのシンボルを表すものです。


原子命題の真偽がそれぞれ決まれば、式全体はそれを演算したものなので、式全体が解釈できる、つまりTなのかFなのかも決まります。

それぞれの原子命題の真偽がどうであるかという情報をモデルと呼びます。

式を解釈するにはモデルを決めなければならないということになります。


モデルというのはようするに現実世界ではどうなっているのかという情報であり、モデルが論理式と現実世界の架け橋となります。


ある論理式φをモデルMで解釈したときの{ T, F }となる要素を、M[φ]と書きます。


たとえば、a∧bを演算として見たときa = T, b = Fならa∧b = Fです。

これを論理式としてみたとき、a∧b = Fというように論理式と集合の要素をイコールするのはおかしいです。

a = T, b = FとなるようなモデルMにおいてM[a∧b] = Fとなります。



そして一般に、ある論理式φがあるモデルMにおいてM[φ] = Tとなるなら、M ⊧ φと書きます。
φのところは、ひとつだけじゃなくて集合でもありえます。

また、ある論理式の集合Γにおけるひとつひとつの論理式xがすべてM[x] = TとなるようなすべてのモデルMにおいて、
ある論理式φM[φ] = TとなるならΓ ⊧ φと書きます。


さらに、ある論理式φψが、あらゆるモデルMにおいてM[φ] = M[ψ]であるなら、φψは論理的に同値であるといって、φ ≡ ψと書きます。

φ ≡ ψφ ⊧ ψかつψ ⊧ φ、と同じことであるともいえます。


これでようやく論理学の大事な所に踏み込みました。

先ほども書きましたが、論理学では基本的に論理式を対象に考察します。

論理式を解釈して{ T, F }という集合の要素にするという話は、論理式の話をするための土台になっているものと思っていいでしょう。


ただ、集合{ T, F }の要素としてのT, Fと、論理式の構成要素としてのT, Fがあることに注意してください。

前者を赤字で、後者を黒字で書くと、当然、
M[T] = T, M[F] = Fでありますが、T = T, F = Fではありません。
T ⊧ T, F ⊧ Fとするのは適切ですが、TT, FFはおかしいです。




ある論理式の集合Γにおけるひとつひとつの論理式xがすべてM[x] = TとなるようなすべてのモデルMにおいて、
ある論理式φM[φ] = TとなるならΓ ⊧ φと書く

と前述しましたが、Γが空である場合、いきなり⊧φと書けます。

これはモデルに制限がないということなので、あらゆるモデルMにおいてM[φ] = Tということです。

これを論理式φは恒真であるといいます。
ちなみに恒偽というのもあります。


逆に、ある論理式φが恒真であるかを確かめたいなら、考えうるすべてのモデルMにおいて、M[φ] = Tであるかを確かめればよいということになります。

モデルとはそもそも、式に登場する原子命題の真偽がそれぞれどうであるかという情報でしたので、
原子命題がn個あれば、それぞれの原子命題でTまたはFの2通りなので、2のn乗通りのモデルが考えうることになります。


つまり、((a∨b)∧¬b)→aが恒真であるかを確かめたいなら、考えうるモデルの表とその中での論理式の真偽を見ます。

a,b : ((a∨b)∧¬b)→aという形式で書いていきます。

T,T : T
F,F : T
T,F : T
F,T : T

よって考えうる全てのモデルで論理式の解釈がTなので、この式は恒真だということがわかりました。


原子命題がたくさんあるときは、恒真であるかを確かめるときに表を作るのは効率が悪すぎるので、他にも論理式が恒真であるかどうかを確かめる方法はいろいろあるのですが、

原子命題が1個とか2個のときはたいした労力もなく恒真であることを証明できます。


ここであえて最後に証明といったのは、そもそも色々な恒真性を確かめる方法は、いくつかの法則を基本にして構築されているわけですが、

その法則が正しいかどうかを確かめる方法は、出発段階ではこの表を作る方法しかないからです。

まあその法則というのは主に恒真というより、の同値性についてですが、同値性の確認も表を作る方法で行うことになりますよね。


よって、次回書く予定の後編記事では、すごく論理学っぽくなるのですが、この地味な作業も大事にしておいてください。




今回、これだけでもメチャクチャ時間かけて書いています。

まあ好きでブログ書いているわけですが、給料がもらえるならもらいたいくらいですね…。

膨大な解説のサイトを作っている人は、非常に尊敬すべき人なんですね。


後編もなるべく早いこと書きたいところですが。

tag: 数学 論理学 演算 論理式 命題 命題論理 集合 意味論

コメント

コメントの投稿

トラックバック

トラックバック URL
http://cyberboy6.blog.fc2.com/tb.php/446-cbb6f857
この記事にトラックバックする(FC2ブログユーザー)

当ブログをご利用(閲覧等)になる場合は必ず「当ブログの利用規定」をお守りください。