ブログ「サイバー少年」

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

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

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

昨日は命題論理について勉強したことのまとめとして、記事「命題論理の意味論まとめ (前編)」を書きましたが、

今回はより話が本格的になってくる後編を書いてまいります。


なお前編で、集合{ T, F }の要素としてのT, Fと、論理式の構成要素としてのT, Fは別物だということに注意しなければならないと触れましたが、

今回はそれを区別するために、論理式の構成要素として使うのはT, Fなんですが、
命題論理で使う集合の{ T, F }のほうは{ 1, 0 }に改めます。

もちろん1が真で0が偽なので、そのように読みかえてください。



前編で言った∨, ∧, ¬の三種類の演算があれば、実は残りの→, ↔は代用可能であるということの、理由については言及しませんでしたが、

まずa→bは、aならばbであり、aでなければあらゆる場合に真ということでしたからaかつb、またはaでないのどちらかで、(a∧b)∨¬aといえます。

つまり代用可能です。

しかしよく考えれば、(a∧b)¬aは満たす条件が排他的ですが、わざわざ排他的にする必要もありません。

つまり、aがなんであれbが真ならばこの演算は真であって、ようするにb∨¬aというふうに、よりスリム化できます。


今、日本語でグダグダと説明しましたが、もちろん厳密にそれを言うためには、前編で触れたように表を用いて確認します。

ただ、今の話のように、演算子の日本語としてのイメージを捉えたうえでわかることというのを考えて、最後に表で確認するという方法は悪くないですね。


まあこの先、それでどんどん法則が増えていって、ほとんど法則とかで同値変形していく感じになって、今後は日本語を使うことなんてほぼないですが…。


なお、a↔bについては、aならばbだしbならばa、ということになるので、これも日本語的に考えて(a→b)∧(b→a)となります。

二つの演算は前述のようにで代用できるので、それをで結んでいるだけなので、結局も三つの演算で代用できることになりますね。





というわけで、本当は∨,∧,¬の三種類で事足りるのですが、
さらに、より絞ろうと思えば、がひとつと、のどちらかひとつがあれば、残りのも代用可能です。


これはドモルガンの法則によるものです。

ドモルガンの法則は集合論とかにも似たようなものがありますが、命題論理においても基本的かつ重要な法則です。

どういう法則かというと、原子命題a, bについて
¬(a∨b) ≡ ¬a∧¬b¬(a∧b) ≡ ¬a∨¬bという法則です。


ちょうど逆になったように、同値な式が二組ありますが、
論理式φについて二重否定の除去法則: ¬¬φ ≡ φ
というのも命題論理では成り立つので、これを使えば片方から片方を式的に導くこともできます。


ドモルガンの法則と二重否定の除去法則によれば、
(a∨b) ≡ ¬(¬(a∨b)) ≡ ¬(¬a∧¬b)および
(a∧b) ≡ ¬(¬(a∧b)) ≡ ¬(¬a∨¬b)なので、
で代用できていることになります。


もちろんドモルガンの法則うんぬん抜きに、モデルの表を作っていきなり、これらが同値であることを確認することもできますが、

先ほど発想段階では日本語的に考えるのもいいと言ったように、こちらでもそもそも法則を使わないとそんな発想すらでませんよね。



ドモルガンの法則は原子命題だけでなく、二つの論理式φ, ψについても成り立ちます。

論理式φ, ψについて
¬(φ∨ψ) ≡ ¬φ∧¬ψ¬(φ∧ψ) ≡ ¬φ∨¬ψ

まあ原子命題であっても論理式であっても、最終的に全体が10であることに変わりないので、式の構造も同じようになりますよね。

φψを原子命題とみなしても、同じことであるということです。




標準形


ある論理式は、ここまでの話のように非常に多種多様な形に同値変形できてしまいます。

そういえば言い忘れていましたが、まあお気づきになっていればいいんですが、
論理的に同値である式というのは、互いにまったく同じことを主張しているということです。

つまり、ある論理式を同値な式と置き換えてしまっても、状況は変化しません。


さて、そのようにバラバラな形の論理式が混在していると、論理式に対して統一的なものの見方をすることがなかなか難しいです。

あらゆる論理式を、あるひとつの書式に基づいた論理式に変形できるなら、論理式を全てその形で扱うようにすることで得られる恩恵はあるはずです。


これは数学でも同じことが起きています。

式の項の次数ごとにまとめる、たとえば
xについての2次式を変形してax^2 + bx + cという形に統一させることで、解の公式などを一般的に考えられるわけですね。

このような統一的な形を標準形といいます。


しかし、命題論理の論理式において標準形と呼ばれるものは二種類あります。

それは命題論理の論理式には双対性と呼ばれる性質があり、詳しいことは後述しますが、すべての論理式にそれと一対一で特別に対応している別の論理式が存在するのです。

よって、ある論理式が標準形ならば、それと対応している論理式も同じようなポジション、標準形で扱わないとおかしいだろうということです。


その二つの標準形は、選言標準形(DNF)と呼ばれるものと、連言標準形(CNF)と呼ばれるものです。

それぞれの説明の前にリテラルというものを定義しておきます。
リテラルとは、原子命題aにおいてaまたは¬aのこと、またはTまたはFです。


選言標準形

選言標準形にはまず、∧節と呼ばれるものがあります。
有限個のリテラルをすべてで接続した論理式を∧節といいます。
a∧¬b∧cみたいな感じです。

そして、有限個の∧節をすべてで接続した論理式を選言標準形と呼びます。
つまり、(.∧.∧.∧.)∨(.∧.∧.∧.)∨(.∧.∧.∧.)という形になっています。


連言標準形


連言標準形には同じく、∨節と呼ばれるものがあります。
有限個のリテラルをすべてで接続した論理式を∨節といいます。
完全に上の文章のコピーですが…。a∨¬b∨cみたいなものです。

そして、有限個の∨節をすべてで接続した論理式を連言標準形と呼びます。
つまり、(.∨.∨.∨.)∧(.∨.∨.∨.)∧(.∨.∨.∨.)という形になっています。




表による標準形への変形


ある論理式をそれと同値な、選言標準形および連言標準形に変形したいときは、法則を使って同値変形していくというのもありますが、

それぞれの標準形が意味しようとしているものが何なのかを考えると、モデルの表を介して変形することも可能であることがわかります。


たとえば、(a→b)∧cの考えうるすべてのモデルにおいて、この式の真偽はどうであるかを表にしてみます。

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

0,0,0 : 0
0,0,1 : 1
0,1,0 : 0
0,1,1 : 1
1,0,0 : 0
1,0,1 : 0
1,1,0 : 0
1,1,1 : 1

となります。


つまりこの式が真となるのは、
a=0, b=0, c=1a=0,b=1,c=1a=1,b=1,c=1
の3つの場合だということです。

それぞれの場合について、そのような条件であるようなことを言うような論理式は作れないでしょうか。

考えてみると、最初のケースでいうと、これはa=0かつb=0かつc=1だということですね。


まず任意のxにおいて、x=1であるとき真になる論理式は、ズバリxです。
逆にx=0であるとき真になる論理式は、上の逆で¬xとなります。

それで、それらをすべて満たす、という条件ですからで結べばいいですね。

よって、最初のケースは¬a∧¬b∧cと表せます。


そうです、これはまさに選言標準形の∧節であります。
同じように残り2つのケースにおいても、∧節を作れますね。

そして、この3つの∧節のどれかを満たしていれば論理式は真であるということですから、この∧節をすべてで結んでやればいいのです。

これはまさに選言標準形であり、論理式(a→b)∧cを選言標準形に変形できたということです。



一方、表からこの論理式が偽になる場合を考えてみます。

a=0, b=0, c=0、a=0, b=1, c=0、a=1, b=0, c=0、a=1, b=0, c=1、a=1, b=1, c=0

の5つの場合が考えられます。


これら論理式が偽になるような条件に、いずれも当てはまらない状態であることを論理式で表現できたら、すなわちこの論理式が真であることと同じことがいえるのではないでしょうか。

いずれも当てはまらないというのは、1件目の偽になる条件に当てはまらない、かつ2件目の偽になる条件に当てはまらない、かつ3件目…というように、

まず、それぞれの偽になる条件について、それを満たしていないということを表す論理式を作って、それをで結べばいいということになります。


では、それぞれの条件について、そうでないということを表す論理式はどうなるでしょうか。

たとえばa=1, b=0, c=1でない、というケースでは、この3つのうち少なくとも1つは満たしていないということで、
満たしてないというのは、その否定を満たしているということです。


任意のxにおいて、x=1でないとき真になる論理式は、¬xです。
逆にx=0でないときに真になる論理式は、xとなります。

よって、このケースだと¬ab¬cのいずれかが満たされていたら、この条件にはならないということになります。

つまり¬a∨b∨¬cであって、これは連言標準形でいうところの∨節です。


同じようにそれぞれの論理式が偽になってしまう条件を、満たしていないということを表す∨節をすべて作って、

それら満たしていないということをすべて満たしているということですから、∨節をすべてで結べばいいことになります。

すなわちこれは連言標準形であり、(a→b)∧cを連言標準形に変形できたということです。



このようにモデルの表を用いたりして、任意の論理式を必ず二種類の標準形に変形することが可能です

しかし表を用いるのは、前編の記事でも触れたように、論理式にn個の原子命題があれば、考えうるモデルは2のn乗通りになるので、それをすべて列挙しなければならないということになります。

これは原子命題が増えると、とても膨大になります。


そこで、法則による同値変形を繰り返していって、選言標準形および連言標準形の形に持っていくという手段を用いることのほうが、実際は多いかなと思いますね。

ただ、みなさんはすでに表の方法で変形できると思うので、ここでは後者の方法は省略してしまうのですが、

概要を述べるとまず、∨,∧,¬で代用した形に変形して、
ドモルガンの法則によってが登場するのはリテラルのときだけという状態にします。

あとは分配法則というのがあるので、それで∨または∧で節を作っていくようにまとめるという感じになります。




双対性定理


先ほど、あらゆる論理式には、それと一対一の関係になっている別の論理式が存在していると書きました。

そのような式を双対式と呼びます。
論理式φに対して双対式ψがどのような関係になっているのかというと、

φの中に登場するに、に置き換えたものがψとなります。


なので、選言標準形の論理式の双対式は連言標準形に、
連言標準形の論理式の双対式は選言標準形になります。

別にこれらが論理的に同値であるといっているわけではありません。


ドモルガンの法則

ここで急ですがドモルガンの法則の話を蒸し返します。
ドモルガンの法則: ¬(a∨b) ≡ ¬a∧¬b¬(a∧b) ≡ ¬a∨¬b

a, bは原子命題です。
ちなみにこの二組の同値関係は、左辺と右辺がそれぞれ、もうひと組と双対式になっていますね。

まあそれはいいとして、括弧の中が三つになった¬(a∨b∨c)はどうなるのか考えてみます。


まずa∨b∨cを、2対1に分割します。
2通りの分割ができるでしょうが、ここではa∨bをひとつのものとして見ることにします。

2通りの分割ができるというのは、結合法則というのが存在していて、先にb∨cという順番で演算していく場合も同値になるのです。

さて、すると上のドモルガンの法則を全体に適用して、さらにもう一回適用できるということになります。

¬((a∨b)∨c) ≡ ¬(a∨b)∧¬c ≡ ¬a∧¬b∧¬c
となります。これはもうひとつの双対式の方でも同様です。

ドモルガンの法則の三項バージョンが存在するとでも言えましょう。


では、こんどは四項で、¬(a∨b∨c∨d)はどうなるでしょうか。

これは、まず先ほどのように四項を三項と一項に分割して、
もし三項のほうの括弧を外してバラバラにできると仮定したら、
三項のものと一項のものにドモルガンの法則を適用すれば少なくともその二つをバラバラにすることは可能なので、
さらに仮定より三項のほうもバラバラにできる。

さらに現に三項のものがバラバラにできるという仮定が正しいことは先ほど示したので、実際に全体もバラバラにできるだろう、という推測がつきます。

¬(a∨b∨c∨d) ≡ ¬((a∨b∨c)∨d) ≡ ¬((a∨b)∨c)∧¬d
≡ ¬(a∨b)∧¬c∧¬d ≡ ¬a∧¬b∧¬c∧¬d


となるので、実際にこの推測は正しいです。
双対式のほうでも同様です。


上の推測のように、論理式の木構造(再帰構造)を利用して、
常に¬(X∧Y)という形にもっていって議論していく証明法を構造的帰納法と呼ぶそうです。


さて、その構造的帰納法を用いて証明できる定理として、双対性定理があるのですが、証明は省略して内容だけ述べます。

先ほどの例から、
¬(a∨b) ≡ ¬a∧¬b
¬(a∨b∨c) ≡ ¬a∧¬b∧¬c
¬(a∨b∨c∨d) ≡ ¬a∧¬b∧¬c∧¬d
となっていたわけですよね。

これは項が5つ以上になっても同じことになるんじゃないでしょうか。
それを証明するのは省略するということですが。

また、さらにもっと複雑な式を観察してみると、
¬(a∧(b∨c)∧¬d) ≡ ¬a∨¬(b∨c)∨¬¬d ≡ ¬a∨(¬b∧¬c)∨d
なんていうような、ドモルガンの法則の繰り返しもあります。

このように様々のものに対してド繰り返しモルガンの法則を適用していくと、
最終的に発生する論理式は、最初の論理式とある関係があるということです。

何度も言いますが、その証明は省略するということです。


その関係とは、最初の論理式を¬φとしたなら、最終的な式はφの中に登場するに、に置き換えたもの、すなわちφの双対式に、

さらにそれのすべての原子命題をx¬xに、¬xxにと、否定で反転させた論理式となる。

という関係です。チェックしてみてください。

その式をψとしたら、ようするに言い方を変えれば、¬φ ≡ ψとなる、というのが双対性定理です。


ただし、φの中にがあったら成り立たないので、それを∨, ∧, ¬で代用したうえで考えなければなりません。

命題論理においては完全にあとの三つの省略記法みたいなものであって、仕組みの話をするときはこれらはアウトオブ眼中なのかなという印象はありますね。

一応、あとの三つと同じレベルの演算および記号ではあるのですが。



また、ある連言標準形の論理式φは、双対性定理によれば¬φは選言標準形で表せることになるし、逆も然りですね。

このようにして、最初に連言標準形と選言標準形の話をしたときに触れましたが、この二つの標準形は一対一の対応になっているのです。


ただもちろん、表から標準形に変形したところで赤字で話したとおり、必ず任意の論理式は二種類の標準形のどちらにも変形できるので、
φ¬φの両方を、連言標準形でも選言標準形でも表すことができます。




恒真性、恒偽性の判定


前編で話しましたが、ある論理式φが、どのようなモデルMで解釈してもM[φ] = Tならばφは恒真、M[φ] = Fならφは恒偽と呼ぶのでした。

なお、φが恒真ということは¬φは恒偽であり、φが恒偽であれば¬φは恒真ということになりますね。


では、任意の論理式φが恒真であるか、はたまた恒偽であるかを確認するためにはどのような方法があるでしょうか。

それは、前編で書いたように、まず考えうるすべてのモデルを考えてみて、すべてのモデルにおいてφが真ならば恒真です。

また、書いていませんでしたが同じように、すべてのモデルにおいてφが偽ならば恒偽です。

というわけで、論理式の恒真性と恒偽性を判定する方法のひとつとしてモデルの表を使う方法があります。



また、選言標準形というのは、それぞれの∧節の内容がまさに、論理式が真になる条件を、ひとつひとつ表していると書きましたね。

ということで、論理式が恒偽であるならば、選言標準形の中身は空になってしまうのです。

空というか、真になる条件がひとつもないということで、Fになります。
なんかFになるみたいなTVドラマありましたね、関係ないのでしょうか…。

ただ、Fというのはひとつの∧節と見なしていいので、これは∧節がひとつの立派な選言標準形であります。


しかし、別の論理式を同値変形して選言標準形にするという方法を取ると、本当は恒偽であってもFになってくれない場合があります。

というか、式の同値変形から標準形を作成した場合、最初はFにならないのは当然です。

∧節が発生してしまった場合も、その∧節をよく見てみるとそこには、任意の原子命題x¬xが両方入ってしまっているはずです。

交換法則があるので、それでx¬xを隣り合わせにすれば、x∧¬x ≡ Fであることは大原則レベルの当然なことなので、それをFとします。

Fはなにとで結んでもFなので、節全体もFになります。


よってこのような処理も行えば、恒偽であるなら選言標準形はFになります。

そして、式が選言標準形になっているからこそ、Fへの変形を機械的に行うことができるのです。


また、それでも選言標準形に∧節が残ったということは、その∧節が示している条件下において論理式が真にあるということですね。

どういうときに真になるかという問題を解くのにも使えるのです。

ただし、原子命題a, b, cがあるのに、(a∧b)という∧節があるなど、複数の条件がまとまっていることも普通にありえます。

これはcはなんでもいいということです。
なお、後述の連言標準形にも同様のことはあります。

また、複数の∧節で、重複して同じ条件を出すこともあるので、そこらへんの処理は面倒です。



一方で、恒真性を判定するには連言標準形を使います。

連言標準形の∨節は、それぞれ論理式が偽になる条件をひとつひとつ表していて、そうならないようなものであるか確認するものでした。

つまり、論理式が恒真であれば、偽になる条件は存在しないので、連言標準形は空になります。

連言標準形においてこれはTということですね。


ただ前述の選言標準形と同じく、恒真なのにTにならないこともあります。

しかし残った∨節のなかにそれぞれ、任意の原子命題x¬xが入っているはずなので、同じように交換法則でx¬xを隣り合わせにして、
x∨¬x ≡ Tになるので、あとはTと何を∨で結んでもTですから、その∨節はTになります。

ということで恒真であるなら式全体がTになりますね。

このように、式が連言標準形になっているから、機械的にTへと変形できるわけです。




導出原理というのがあって、これは上記とは逆に選言標準形から恒真性を確認したり、
連言標準形から恒偽性を確認したりできるのですが、長いので書くのは諦めます。

あと、私が読んでいるサイトの説明は非常に独特なものと思われるので、私もちゃんと理解できているかは微妙なところがありますからね。


というわけで、命題論理のまとめはここまでとなります。
非常に書くのは大変でした。

しかも相変わらずのクソ解説で、伝わっているかは非常に気になりますが…。

この知識をプログラムの条件式などで応用できる機会は、なかなか多いと思います。

そもそも、コンパイラが論理式を最適化したりするときは、今回書いたことよりもっと少し高度なことでしょうけども、論理学に基づいて最適化するわけですからね。


私が見ているサイトはまだまだ続きがあって、
これから放送大学で見たときは数学的な話を飛ばした例の述語論理に数学的に立ち向かうのと、
そのあとは論理の形式化、つまり構文論の話がだいぶ続くみたいです。

なかなか時間がかかりますが、頑張ります。

もしかしたら構文論についてまとめることもあるかもしれません。

tag: 数学 論理学 法則 標準形 論理式 命題 命題論理 意味論

コメント

コメントの投稿

トラックバック

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

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