ちょっとした思いつきとか都合で数学的 (というか論理学的) な話をいくつか書いていこうと思います。
長月はわんくま勉強会で論理の話をしているんですが、ちょこちょこ何か書いていかないと急に資料作るの大変だとか、多分これまでのセッションでぽかーんになったままの人が沢山居るだろうからフォローしないとなとか例示が足りてなかったなとか口頭でフォローするからいいやとそれだけでわかる資料になってないなとか思うところがあります。
なので数学なお話をしばらく書いていこうかなと思います。計算理論や論理学の本に書いてあるような説明から、わんくま勉強会で話しているときにポロポロと漏らしていた長月の感想的な部分など、長月の言葉で論理学を見ていきましょう。
第一回の今回は命題論理について。
# 目次
- 1.命題論理事始め
- 1.1.命題ってなんだ？
- 1.2.論理って何だ？
- 1.3.結局命題論理ってなんだ？
- 2.命題論理の規則
- 2.1.命題変数
- 2.2.論理結合子
- 2.3.書き換え規則
# 1.命題論理事始め
まず命題論理が扱うものを確認しておきましょう。
命題論理は命題を扱います。命題を論理的に扱うのが命題論理です。
ここで二つのキーワードが出てきます。命題と論理的です。この二つのキーワードの意味を確かめておきます。
## 1.1.命題ってなんだ？
命題とは真偽の判断の対称になる文や式を言います。
真偽の判断と書いたとおり真か偽で答えられる必要があります。通常「AはBである」と言う形の文になります。プログラマにおなじみの表現で言うなら if(A == B) ですね。
通常数学の文脈では数学的な問題について述べるのでどんな文でも現れる訳ではないですが、論理学ではどのような文でも真か偽で答えられるなら命題です。
## 1.2.論理ってなんだ？
では論理的、ひいては論理とは何でしょうか。
論理的を辞書で調べると「論理にかなっている様、筋道を立てて考える様」などと書かれています。と言うことは論理にかなっているというのは筋道を立てていることと同じことの様です。
論理学は筋道を立てて述べられた物事の、筋道の立てられかた、立て方について考える学問なのです。
## 1.3.結局命題論理ってなんだ？
命題論理は命題を扱う論理です。先ほど確かめた意味を含めて言うと、
***真偽で答えられる文***について***筋道を立てて考える***もの
と言うことになります。この筋道を立てて考えると言う部分はもうちょっとちゃんと決めていく必要がありますが、命題論理は真偽で答えられる文を扱うものだと言うことが言えました。
次節からはどのように扱うかについて述べていきます。
# 2.命題論理の規則
命題論理では命題に対していくつか決めごとがあります。
次節以降で以下の三つについて述べていきます。
1. 命題変数
2. 論理結合子
3. 書き換え規則
## 2.1.命題変数
命題変数というのは命題を表す記号です。
具体的な文として命題を表すこともできます (実際数学では具体的な命題を扱います) が、論理学の視点で言うと特定の命題について述べたいのではなく、対象の系がどのような論理構造を持っているのかを述べたいので、***特定の文によらない抽象的な記号***で命題を表します。
言い換えると同じ構造の論理であれば具体的な命題は何でも良いことになります。長月は男であるか？ と今の天気は晴れであるか？ はどちらも真か偽で答えられる単純な命題なのでどちらでもいいのです。命題変数で表せばどちらも同じです。
注意しなければならないのは、今後扱う述語論理では量化と言って複数の対象に対しての命題を考えていくことになりますが、そこでの変数とは考え方が違うと言うことです。
命題変数はその論理構造がどのような命題に対しても適用できることを表していますが、述語に与えられる変数は
## 2.2.論理結合子
$\phi$,$\psi$を命題変数とする (今後$\phi$と$\psi$は多用されるので慣れてください) と次の三つも命題として扱います。
1. $\phi \lor \psi$ $\phi$または$\psi$
2. $\phi \land \psi$ $\phi$かつ$\psi$
3. $\lnot \phi$ $\phi$ではない
これらを論理結合子と呼びます。
$\lor$の意味として「または」と書いていますが、これは排他的ではありません、$\phi \lor \psi$は「$\phi$と$\psi$のどちらか一方だけが成り立つならば真」ではなく「$\phi$と$\psi$の少なくとも一方が成り立つならば真」です。
真理値表で表すと以下のようになります。
| $\phi$ | $\psi$ | $\phi \lor \psi$ | $\phi \land \psi$ | $\lnot \phi$ |
|---|---|---|---|---|
| Ｔ | Ｔ | Ｔ | Ｔ | Ｆ |
| Ｔ | Ｆ | Ｔ | Ｆ | Ｆ |
| Ｆ | Ｔ | Ｔ | Ｆ | Ｔ |
| Ｆ | Ｆ | Ｆ | Ｆ | Ｔ |
命題変数$\psi$,$\phi$,χがある時$\phi$は命題です。$\psi \lor$χも命題です。$\phi$は命題なので$\psi \lor$χと置いてもいいわけです。詰まり命題は再帰的な構造を持つことができます。
例えばA$\land$χのAが$\lnot$Cであることもあり得ます。A$\land$χ=$\lnot$C$\land$χですね。Cがまた$\phi \lor \psi$であることもありえることです。$\lnot ( \phi \lor \psi ) \land$χと言うことですね。このように組み合わせられた論理式でも一番内側の結合子から考えていくことで真偽が決定できます。
真理値表で見てみましょう。
| $\phi$ | $\psi$ | χ | $\phi \lor \psi$ | $\lnot ( \phi \lor \psi$) | $\lnot ( \phi \lor \psi ) \land$χ |
|---|---|---|---|---|---|
| Ｔ | Ｔ | Ｔ | Ｔ | Ｆ | Ｆ |
| Ｔ | Ｔ | Ｆ | Ｔ | Ｆ | Ｆ |
| Ｔ | Ｆ | Ｔ | Ｔ | Ｆ | Ｆ |
| Ｔ | Ｆ | Ｆ | Ｔ | Ｆ | Ｆ |
| Ｆ | Ｔ | Ｔ | Ｔ | Ｆ | Ｆ |
| Ｆ | Ｔ | Ｆ | Ｔ | Ｆ | Ｆ |
| Ｆ | Ｆ | Ｔ | Ｆ | Ｔ | Ｔ |
| Ｆ | Ｆ | Ｆ | Ｆ | Ｔ | Ｆ |
もう一つ複合的な論理結合子として含意を用意します。
命題変数$\phi$と$\psi$があるとき、含意は$\phi \to \psi$と表します。(教科書によっては⇒も使う)
他の論理結合子と同様に文として日本語で読む場合～ならば～に相当するものです。ただし前提が偽の時に日本語のならばとは語感が異なるので注意しましょう。
含意の真理値表をいかに示します。
| $\phi$ | $\psi$ | $\phi \to \psi$ | $\lnot \phi \lor \psi$ |
|---|---|---|---|
| Ｔ | Ｔ | Ｔ | Ｔ |
| Ｔ | Ｆ | Ｆ | Ｆ |
| Ｆ | Ｔ | Ｔ | Ｔ |
| Ｆ | Ｆ | Ｔ | Ｔ |
ついでに示しましたが、含意$\to$は$\lnot \phi \lor \psi$と同等です。～ならば～と覚えるよりは$\lnot \phi \lor \psi$と覚えておいたほうが誤解がないかもしれませんね。
## 2.3.書き換え規則
ある形の命題論理の式を同等の意味に別の形に変形することができます。それらの変形を端的にまとめたものを書き換え規則として以下に示します。
- 二重否定 $\lnot \lnot \phi \Leftrightarrow \phi$
- 交換則 $\phi \lor \psi \Leftrightarrow \psi \lor \phi$
$\phi \land \psi \Leftrightarrow \psi \land \phi$
- 結合則 ($\phi \lor \psi ) \lor$χ$\Leftrightarrow \phi \lor ( \psi \lor$χ)
($\phi \land \psi ) \land$χ$\Leftrightarrow \phi \land ( \psi \land$χ)
- 分配則 $\phi \land ( \psi \lor$χ)$\Leftrightarrow ( \phi \land \psi ) \lor ( \phi \land$χ)
$\phi \lor ( \psi \land$χ)$\Leftrightarrow ( \phi \lor \psi ) \land ( \phi \lor$χ)
- ド・モルガンの法則 $\lnot ( \phi \land \psi ) \Leftrightarrow \lnot \phi \lor \lnot \psi$
$\lnot ( \phi \lor \psi ) \Leftrightarrow \lnot \phi \land \lnot \psi$)
更に二重否定と含意の定義から以下のように対偶を定義できます。
- 対偶 ($\phi \to \psi ) \Leftrightarrow ( \lnot \psi \to \lnot \phi$)
分解して考えてみましょう。
$\phi \to \psi$は$\lnot \phi \lor \psi$です。$\lnot \psi \to \lnot \phi$は$\lnot \lnot \psi \lor \lnot \phi$です。
二重否定の書き換え法則から$\lnot \lnot \psi \lor \lnot \phi$は$\psi \lor \lnot \phi$になります。
順番を入れ替えると$\lnot \phi \lor \psi$となりますね。これは最初に示した$\lnot \phi \lor \psi$と同じ形ですね。つまり$\phi \to \psi$と同じです。
$\lnot \lnot \psi \lor \lnot \phi$は$\lnot \psi \to \lnot \phi$ですから、$\lnot \psi \to \lnot \phi$は$\phi \to \psi$と同じであることが示せました。
# 締めと次回予告
今回は命題論理について書きました。命題論理は現代的な論理学の基礎中の基礎です。全ての論理体系は命題論理を基本としています。プログラマの立場で見ても必修科目と言えるでしょう。プログラマが見たり触れたりするプログラムの多くは条件判断を行います。つまり真か偽で答えられる質問をさせて、真の時の答えと偽の時の答えを用意するわけです。
実際にはプログラムに現れる問題は命題論理で扱えない範囲で有ることも多く、それは多くの場合述語論理の範囲に属しているのですが、そこらへんの話は次回以降取り扱います。
わからないことや聞いてみたいことがあったら気軽にコメントしてください。次回以降でフォローします。
大切な事なのでもう一度書きますが、わからないことや聞いてみたいことがあったら気軽にコメントしてください。
さて次回 (があれば) ですが、次回は一階の述語論理のお話です。二階以上の述語論理の話をするかどうかはわかりませんが、一階の述語論理について書こうと思います。長くなるようなら前後編にするかもです。
次回以降で触れようと思っているトピックを列挙します。他にも聞いてみたいトピックがあったらコメントください。
- 一階の述語論理
- 数学基礎論 (的な何か)
- 様相論理
- 時相論理
- 内包論理
- 形式手法
- 計算論 (主にλ計算)
- 計算複雑性理論