数理論理学 命題論理（１）

数理論理学の基礎について書いてみます。

一般的に、数理論理学の学習は「命題論理→一階述語論理」というステップを踏むものですが、「命題論理はバカみたいに簡単だったが、述語論理に入ってから途端についてけなくなった」というのがよくあるケースです。なので、命題論理については、それほど深入りしません。

そもそも命題論理は、論理学を知らなくても、「OR」だの「AND」だの見れば、常識の範囲内でどういう意味かわかりますからね。若干難しいのは、排他的論理和と条件法ぐらいでしょうか。

さっそく、論理結合子の真理値表を眺めながら、各結合子の特徴を見て行きます。

論理和（OR）

P	Q	P OR Q	Description
1	1	1
1	0	1
0	1	1
0	0	0	←この場合のみ0

論理積（AND）

P	Q	P AND Q	Description
1	1	1	←この場合のみ1
1	0	0
0	1	0
0	0	0

否定（NOT）

P	NOT P	Description
1	0
0	1

排他的論理和（P XOR Q）

P	Q	P XOR Q	Description
1	1	0
1	0	1
0	1	1
0	0	0

「異なるときのみ真」、と覚えましょう（決して「ORの反転」ではありません！）。

これの使用例として、レジスタR1の値を0に初期化する時に、

XOR R1, R1

という定石がありますが、R1とR1は同じ値なので（当たり前）、上の式は常に0に評価されますよね。
その演算結果0が、レジスタR1にロードされるので、R1はつねに0に初期化されることになります。

条件法（P⇒Q）

P	Q	P ⇒ Q	Description
1	1	1
1	0	0	←この場合のみ0
0	1	1
0	0	1

条件法については、直観に反するところがありますが、基本は「丸暗記」です。*1 *2

前件が偽であるか、または後件が真である場合において、論理式はつねに真と評価される。
それ以外はつねに偽と評価される。

あるいは

(P,Q)=(1,0)の場合のみ0、それ以外はすべて1

と丸暗記してしまいましょう（条件法の論理式P⇒Qにおいて、Pを「前件」、Qを「後件」と言います）。

同値（双条件法）（P⇔Q）

P	Q	P ⇔ Q	Description
1	1	1
1	0	0
0	1	0
0	0	1

これは読んで字のごとく、「前件と後件の真理値が同じ場合のみ、論理式は真と評価される」演算子です。

否定論理積（P NAND Q）

P	Q	P NAND Q	Description
1	1	0
1	0	1
0	1	1
0	0	1

ANDの反転（NOT(P AND Q)）に等しいです。

論理結合子については以上です。
次回以降は、「シェファーの棒記号」「恒真命題（トートロジー）」「恒偽命題（矛盾式）」について語りたいと思います。

*1:よく論理学の教科書では、命題論理の「ならば」と、日本語の「ならば」との違いについて説明されることが多いですが、不毛なのでここでは説明しません。なぜなら、「”⇒”はそのように定義された演算子だから、そうなっている」からです。論理学では、たまたまニュアンスが近い「ならば」という日本語を”⇒”に当てている（訳している）だけで、論理学の「ならば」と日本語の「ならば」は、本質的には異なるものです。条件法は、あくまで「そういう演算子」です。

*2:もう一点。条件法は、プログラミング言語のIF文とは違います。IF文は、双条件法です。

数理論理学 命題論理（2）

引数の組み合わせに対応する真理値のマッピングパターンについて

前回に出てきた論理結合子の真理値表をまとめると、以下になります。

P	Q	P OR Q	P AND Q	¬P	P⇒Q	P⇔Q	P XOR Q
1	1	1	1	0	1	1	0
1	0	1	0	0	0	0	1
0	1	1	0	1	1	0	1
0	0	0	0	1	1	1	0

見ての通り、論理結合子というのは、「任意の二項の引数の組み合わせに、その評価結果を割り当てる二項演算子」（¬は一項演算子）ですが、二項演算子の各引数の組み合わせに対する評価結果の組み合わせは、上の5通りだけではないはずです。

例えば、論理結合子「○」というのを擬似的に考えてみます。

P	Q	P ○ Q
1	1	1
1	0	1
0	1	0
0	0	0

先の表には出て来ませんでしたが、こういう演算子だってアリではないでしょうか。
では、二項演算子の場合、引数の組み合わせに対応する真理値のマッピングは、最大で何通りのパターンが考えられるのでしょうか。

答えは、

2^4 = 16通り

です。

P	Q	P ○ Q
1	1	$1
1	0	$2
0	1	$3
0	0	$4

上の通り、ひとつの演算子において、引数の組み合わせとその真理値のマッピングは、4箇所（$1〜$4）で出てくるわけですから、

$1(0/1の2通り) x $2(0/1の2通り) x $3(0/1の2通り) x $4(0/1の2通り) = 2^4 = 16通り

となるわけです。

この16通りのうち、汎用性の高い便利なマッピングをピックアップして、ORだのANDだのといったシンボルを与えているんですね。

前回、「論理学における条件法の「ならば」は、日本語の”ならば”とは本質的に無関係であり、そういう演算子なのだ」と書きましたが、”⇒”に便宜上「ならば」という訳を当てているだけです。

シェファーの棒記号（Sheffer's stroke）

あまり役に立たないので、シェファーの棒記号については深入りしません。教養程度に。

シェファーの棒記号というのは論理結合子の一つですが、以下の真理値表を見ても分かるように、ようはNANDのことです。

P	Q	P｜Q
1	1	0
1	0	1
0	1	1
0	0	1

この特徴は、「論理式をシェファーで結合すれば、シェファー1本だけで、すべての真理値割り当てを再帰的に構成することができる」というものです。

「え、どういうこと！？」と思った方は、ググってみて下さい（笑）

数理論理学 命題論理（3）

論理式の本質を一言で表すと、

P={0,1} Q={0,1}の真理値割り当て({1,1}{1,0}{0,1}{0,0}の4通り)に対して、評価結果{0,1}を割り当てるパターン

となります。

この割り当て方のパターンを、大まかに分類すると、

パターン	名称
どんな真理値割り当てに対しても、つねに1となる	恒真式（トートロジー）
どんな真理値割り当てに対しても、つねに0となる	恒偽式（矛盾式）
恒偽式でない	充足可能式

3つ目の「充足可能式」とは、4通りの真理値割り当てのうち、いずれかにおいて評価結果が1となるケースが少なくとも1つは存在する、というものです。当然、恒真式はこれに包含されます。

なので、評価結果の割り当てパターンが16通りある場合、うち1通りが「恒真式」、うち1通りが「恒偽式」、うち（恒真式を含む）15通りが「充足可能式」となります。

例を挙げると、

P	Q	P○Q	P□Q	…	P◆Q	P△Q
1	1	1	1	…	0	0
1	0	1	1	…	0	0
0	1	1	1	…	0	0
0	0	1	0	…	1	0

P○Qが「恒真式」
P△Qが「恒偽式」
P○Q、P□Q…P◆Qが「充足可能式」

ということになります。

これは、「論理式の集合」という概念が出てきた時に、非常に重要となるカテゴライズです。