論理式の図形表現での整理(記号論理学)

命題論理

命題とは、真か偽のどちらかになる主張になります。

具体例がないと分かりにくいので具体例です。
以下のような主張は命題になります。

• 犬は動物である
• タンポポは動物である
• 1は奇数である
• 4は奇数である
• 3は2よりも大きい

命題論理の対象は具体的な命題ではなく、命題を抽象化した命題変数と呼ばれる概念です。
真偽どちらかが入る変数を用意し、それを使って推論していくアプローチをとります。

何が嬉しいのかという話ですが、例えば推移律（三段論法のうちの1つのこと）「『AならばB』『BならばC』の2つが成り立っているのなら『AならばC』も成り立つ」ということをしっかりと記述出来たり、
計算方法（整理方法）を知っていると複雑な述語が出てきたときに出来る限り簡単な状態に調整したりできるようになります。

もう少し詳細を書くと、命題という状態で考えると、例えば以下のような3つの命題があります。（日本語として自然にするために「ならば」という言い方ではないですが同じ意味だと思ってください。）
P:犬である、Q:哺乳類である、R:肺呼吸をする　という3つの主張に対して上2つが成り立つから3番目が成り立つということを言っています。

• P → Q :　犬は哺乳類である
• Q → R :　哺乳類ならば肺呼吸をする
• P → R :　犬は肺呼吸をする

ではなぜ3つ目が成り立つの？という証明をするためにどう対応しようかということになります。

使い道ですが、例えばチェッカーなど条件文がどうしても複雑になってしまうところに使うとコードがすっきりします。
もちろんコメントアウトは必要になるとは思いますが、すっきりしている条件文の方が不具合なども少ないのではないでしょうか？
述語を数式化する対象に論理積、論理和、否定、などよく条件文に使うものも含まれるので、十分式整理に使えると思います。

この記事ではこれらの式変形を図形として表現していきます。

論理の最小単位

論理を表すうえで、単位となる単位は「否定」と「論理積」の2つのみです。

否定とは、$\rm{not} P, \neg P, \bar{P}$ などと表される、Pが偽であるときに真、Pが真であるときに偽となる演算です。この記事では ￢P と表します。（ヒテイと打って変換をすると出てくる記号です。）

論理積とは、 $P \rm{and} Q, P \land Q, P \cap Q$ などと表される、P,Qともに真のときのみ真、少なくともどちらかが偽なら偽となる演算です。この記事では P ∧ Q と表します。（カツと打って変換すると出てくる記号です。）

他の論理式はどうするのかというと、この2つを組み合わせることで表すことが出来ます。
例えば、論理和の場合は、「少なくともどちらかが真」の言い換えで「『どちらも偽』ということではない」となるので、 P ∨ Q = ￢(￢P ∧ ￢Q) と表せますし、
論理含意の場合は「『Pが真なのにQが偽になっている』ことはない」となるので、 P → Q = ￢(P ∧ ￢Q) と表せます。

ちなみに記号論理学以外の場所では主張が偽である論理含意がほぼ出てこないのですが、「 タンポポである → 動物である 」のような偽である主張もこの記事では検討の範囲内です。
論理積や論理和、排他的論理和などと同じような2つの命題を使う論理演算ぐらいに思っておいてください。
└こうすることで、例えば「栓が閉まっているのに水が出ているぞ」みたいなチェッカの話もスムーズに入ってきます。

記法

数式の状態で記載する場合は前の章の通り ￢P、P ∧ Q と表しますが、以降では基本的に図形表現で数式を表します。
図示できるということは一目でわかりやすいということでもありますし、整理も慣れると図の方がやりやすいです。
見た目としてベン図に似ているのですが違うものだと思ってください。

まず、P という命題のみの場合、ただただPと書くだけになります。
どこに図があるのかが分かりにくいのでこの記事では見やすさのため記載をしていく範囲を四角で囲みますが、特に囲む必要はないので紙に書いて計算するときなどでは四角の中身だけ書いてくれればOKです。

とてもシンプルですがこれだけです。
ちなみにPを書く場所についてはどこでもOKです。大きさもどこでも良いです。以下の図は全部 P を表します。

否定　￢

否定は線で囲みます。普通はちゃちゃっと書くので丸で囲みますが、角ばっていても構わないです。
また、先ほどと同じく大きさや囲む場所については、囲んだ線の中に入っていればどこでもOKです。
4つ注意点があります。簡単に言うと「綺麗に囲めよ」です。

• 線は交わらない。
• 線は枝分かれしない。
• いきなり現れたり枠の外から出てきたりしない。
• 文字を分断しない。

次の3つは全て ￢P を表します。

論理積　∧

論理積は同じところに並べて書きます。同じところというのは線で囲まれた範囲内で同じところ、という意味です。
線で囲まれたというのは否定のための丸のことです。
普通は紙のスペース的に横に並べていきますが、大きさや並べる場所については、同じ囲んだ線の中に入っていればどこでもOKです。
3つ注意点があります。簡単に言うと「綺麗に並べろよ」です。

• 線の上に乗らない
• 他の命題とぶつからない。
• 枠に引っ掛からない。

次の3つは全て P ∧ Q を表します。

他の論理演算は否定と論理積で表せるということで、以降はこの「囲む」「並べる」だけの表現で表していきます。
また、囲み方と並べ方は自由ということで、以降では私の主観で分かりやすいだろうと思う1つの図だけで表します。
式から図にするときは括弧の中から順番に囲っていくと良いです。
図から式にするときは一旦括弧だらけで良いので、囲っていたら否定にして、並んでいたら論理積にして、というのを内側から行います。

論理和　∨

論理和は P ∨ Q = ￢(￢P ∧ ￢Q) だったということで、以下のような図になります。

論理含意　→

論理含意は P → Q = ￢(P ∧ ￢Q) だったということで、以下のような図になります。
ベン図で書く場合とちょうど逆になってしまいますが、ベン図と勘違いしないようにしてください。

排他的論理和　XOR

排他的論理和はPとQのどちらかのみ真のときに真になります。
XOR(P, Q) = (P ∧ ￢Q) ∨ (￢P ∧ Q) ということなので、論理和の時の書き方を参考にして以下のような図になります。
赤い線で描いているところがちょうど論理和になっています。

こう見てみるとただただ否定と論理積のみに書き下したものにもできますし、青や緑の線に注目してみることで論理含意を使った式に式変形が出来ることが分かります。
XOR(P, Q)
= ￢(￢(P ∧ ￢Q) ∧ ￢(￢P ∧ Q))
= (P ∧ ￢Q) ∨ (￢P ∧ Q)
= ￢((P → Q) ∧ (Q → P))
= (P → Q) → (￢P ∧ Q))
3つ目の等式の Q → P の部分で「他と左右逆の図なのに？」と思った方は図での並べ方はどこでも良かったことを思い出してみてください。

今回だと結局は一番最初に図を作るために使った (P ∧ ￢Q) ∨ (￢P ∧ Q) が一番分かりやすく、演算回数も2番目に少ないのでこれを採用しますが、ものによってはもっと短くなるかもしれないということになります。
図の確認の仕方だけでも演算の整理や式変換が出来ることは理解できたでしょうか？

式変形

式を変形していく際、先ほどのようにただただ視点を変えるだけでも構わないのですが、真偽が変わらない状態なら図自体を変形していっても構いません。
同値な変形と非可逆な変形とがありますが、それぞれ変形時に = と ⇒ を使うことにします。

二重の囲み

二重否定は消すことが出来ます。
二重になっている囲みは消したり追加することが出来ます。ただし、その二重線の間に何かが書いてある場合は消すことが出来ません。

除去

囲みがちょうど偶数個の場所ならどこでも、好きな図形を消してOKです。
偶数個というのは囲みが0個、つまり囲まれていない場所も含みます。
3つ目のように奇数個の場所では消してはいけません。

挿入

囲みがちょうど奇数個の場所ならどこでも、好きな図形を書きこんでOKです。
3つ目のように偶数個の場所では追加してはいけません。

反復・脱反復

既に存在する図形は、その図形が含まれる囲みとその内側の囲みであれば全く同じ図形を追加してOKです。
また、逆にその図形と全く同じ図形が同じ囲みかその内側に存在するのならば削除してもOKです。
追加場所は囲みが偶数個でも問題なく、削除場所も囲みが奇数個でも問題ないので、挿入のところで出来ないと書いていたRの追加も、外に R があるならば追加可能です。

補足として、図に何も書き込まない場合は真であるとみなします。
任意の仮定から除去を行うことで何も書いていない図形が出来るので、自然な定義だと考えられます。また、その何もない部分を囲んだ場合は偽とみなします。

式変形いくつか

実際にいくつか式変形をして、どのように変形していくのかを見ていきます。

• P ∨ P = P

論理和の冪等律です。

• (P → Q) ∧ (Q → R) ⇒ P → R

冒頭にもあった三段論法の内容です。
反復したものがどれなのかが分かりにくいかもしれないので赤く書いています。
除去を行っているので左辺から右辺は推論できますが、右辺から左辺は推論できません。

• (P ∨ Q) ∨ R = P ∨ (Q ∨ R)

論理和の結合律です。
読み取る部分が分かりにくいため赤で補助的に色を付けています。
結合律が成り立つので括弧は省略しても問題ないです。また、図形表現としても、2番目の図を見てわかるように3つの要素が同等に並んでいることが分かります。

• P → Q = ￢Q → ￢P

待遇は真偽が同じことを示しています。
並び替えはしなくても問題ないのですが、ここでは分かりやすさのため書き換えています。

• AllMatch([P1, P2, P3, ...]) と AllMatch([])

AllMatchはリストの中身が全て真という関数とします。
例えば3つの要素を持つリストの場合、AllMatchは以下のように表すことが出来ます。
AllMatch([P1, P2, P3]) = P1 ∧ P2 ∧ P3
図形表現としてはただただ並べるだけで問題ないです。4個の場合もそれが増えていくだけなので、 AllMatch([]) なら0個を並べたものと考えるのが自然です。

ここで何も書いていない場合は真であるとみなすはずなので、 AllMatch([]) = True と考えるのが自然な定義になります。

• AnyMatch([P1, P2, P3, ...]) と AnyMatch([])

AnyMatchはリストの中身の少なくとも1つが真という関数とします。
例えば3つの要素を持つリストの場合、AnyMatchは以下のように表すことが出来ます。
AnyMatch([P1, P2, P3]) = P1 ∨ P2 ∨ P3
図形表現としては各要素の否定を並べてその全体をさらに囲む形になります。3つ以上の場合、左から順に図形表現で表していくと良いのですが、3個の場合のように二重の囲みが大量に出てくるので、それを外していくときれいな形になります。
4個の場合も整理をした後のみ記載していますが、3個の場合と比べて4つ目の要素の否定が増えているだけですね。日本語で読み取っても「各要素全てが偽ということはない」という説明になるので、AnyMatchの説明として違和感はありません。
こう考えると AnyMatch([]) なら0個を並べたものの否定と考えるのが自然です。

ここで何も書いていないものを囲った場合は偽であるとみなすはずなので、 AnyMatch([]) = False と考えるのが自然な定義になります。

最後に

整理の仕方はいかがだったでしょうか？
文字で表した数式を使って整理していく式変形に慣れていると癖の強い式整理に見えたかもしれませんが、慣れるとぱっと見で理解しやすく、ややこしくなりがちな論理式をスマートにできる強力な方法だと思います。

条件文の中身の調整だけでなく、 if(P) { check(Q); } といったチェッカなら、単純に check(P → Q) という論理式のチェックをしていると考えると、使えるかもしれない場所が見えてくるのではないでしょうか？
面白い体系を持つ分野なので興味を持った場合はぜひ記号論理学を調べてみてください。

参考文献

https://wiis.info/math/logic/propositional-logic/value-of-formula/
http://www2.yukawa.kyoto-u.ac.jp/~kanehisa.takasaki/edu/logic/logic3.html
https://www.virtualinvader.com/predicate-logic/
https://doshisha.repo.nii.ac.jp/?action=repository_uri&item_id=21694&file_id=28&file_no=1