1.命題論理事始め

　まず命題論理が扱うものを確認しておきましょう。
　命題論理は命題を扱います。命題を論理的に扱うのが命題論理です。
　ここで二つのキーワードが出てきます。命題と論理的です。この二つのキーワードの意味を確かめておきます。

1.1.命題ってなんだ？

　命題とは真偽の判断の対称になる文や式を言います。
　真偽の判断と書いたとおり真か偽で答えられる必要があります。通常「AはBである」と言う形の文になります。プログラマにおなじみの表現で言うなら if(A == B) ですね。
　通常数学の文脈では数学的な問題について述べるのでどんな文でも現れる訳ではないですが、論理学ではどのような文でも真か偽で答えられるなら命題です。

1.2.論理ってなんだ？

　では論理的、ひいては論理とは何でしょうか。
　論理的を辞書で調べると「論理にかなっている様、筋道を立てて考える様」などと書かれています。と言うことは論理にかなっているというのは筋道を立てていることと同じことの様です。
　論理学は筋道を立てて述べられた物事の、筋道の立てられかた、立て方について考える学問なのです。

1.3.結局命題論理ってなんだ？

　命題論理は命題を扱う論理です。先ほど確かめた意味を含めて言うと、

　真偽で答えられる文について筋道を立てて考えるもの

　と言うことになります。この筋道を立てて考えると言う部分はもうちょっとちゃんと決めていく必要がありますが、命題論理は真偽で答えられる文を扱うものだと言うことが言えました。
　次節からはどのように扱うかについて述べていきます。

2.命題論理の規則

　命題論理では命題に対していくつか決めごとがあります。
　次節以降で以下の三つについて述べていきます。

1. 命題変数
2. 論理結合子
3. 書き換え規則

2.1.命題変数

　命題変数というのは命題を表す記号です。
　具体的な文として命題を表すこともできます (実際数学では具体的な命題を扱います) が、論理学の視点で言うと特定の命題について述べたいのではなく、対象の系がどのような論理構造を持っているのかを述べたいので、特定の文によらない抽象的な記号で命題を表します。
　言い換えると同じ構造の論理であれば具体的な命題は何でも良いことになります。長月は男であるか？　と今の天気は晴れであるか？　はどちらも真か偽で答えられる単純な命題なのでどちらでもいいのです。命題変数で表せばどちらも同じです。
　注意しなければならないのは、今後扱う述語論理では量化と言って複数の対象に対しての命題を考えていくことになりますが、そこでの変数とは考え方が違うと言うことです。
　命題変数はその論理構造がどのような命題に対しても適用できることを表していますが、述語に与えられる変数は

2.2.論理結合子

　φ,ψを命題変数とする (今後φとψは多用されるので慣れてください) と次の三つも命題として扱います。

1. φ∨ψ　φまたはψ
2. φ∧ψ　φかつψ
3. ￢φ　φではない

　これらを論理結合子と呼びます。
　∨の意味として「または」と書いていますが、これは排他的ではありません、φ∨ψは「φとψのどちらか一方だけが成り立つならば真」ではなく「φとψの少なくとも一方が成り立つならば真」です。
　真理値表で表すと以下のようになります。

　命題変数ψ,φ,χがある時φは命題です。ψ∨χも命題です。φは命題なのでψ∨χと置いてもいいわけです。詰まり命題は再帰的な構造を持つことができます。
　例えばA∧χのAが￢Cであることもあり得ます。A∧χ=￢C∧χですね。Cがまたφ∨ψであることもありえることです。￢(φ∨ψ)∧χと言うことですね。このように組み合わせられた論理式でも一番内側の結合子から考えていくことで真偽が決定できます。
　真理値表で見てみましょう。

　もう一つ複合的な論理結合子として含意を用意します。
　命題変数φとψがあるとき、含意はφ→ψと表します。(教科書によっては⇒も使う)
　他の論理結合子と同様に文として日本語で読む場合～ならば～に相当するものです。ただし前提が偽の時に日本語のならばとは語感が異なるので注意しましょう。
　含意の真理値表をいかに示します。

　ついでに示しましたが、含意→は￢φ∨ψと同等です。～ならば～と覚えるよりは￢φ∨ψと覚えておいたほうが誤解がないかもしれませんね。

2.3.書き換え規則

　ある形の命題論理の式を同等の意味に別の形に変形することができます。それらの変形を端的にまとめたものを書き換え規則として以下に示します。

• 二重否定　￢￢φ⇔φ
• 交換則　φ∨ψ⇔ψ∨φ φ∧ψ⇔ψ∧φ
• 結合則　(φ∨ψ)∨χ⇔φ∨(ψ∨χ) (φ∧ψ)∧χ⇔φ∧(ψ∧χ)
• 分配則　φ∧(ψ∨χ)⇔(φ∧ψ)∨(φ∧χ) φ∨(ψ∧χ)⇔(φ∨ψ)∧(φ∨χ)
• ド・モルガンの法則　￢(φ∧ψ)⇔￢φ∨￢ψ ￢(φ∨ψ)⇔￢φ∧￢ψ)

　更に二重否定と含意の定義から以下のように対偶を定義できます。

• 対偶　(φ→ψ)⇔(￢ψ→￢φ)

　分解して考えてみましょう。
　φ→ψは￢φ∨ψです。￢ψ→￢φは￢￢ψ∨￢φです。
　二重否定の書き換え法則から￢￢ψ∨￢φはψ∨￢φになります。
　順番を入れ替えると￢φ∨ψとなりますね。これは最初に示した￢φ∨ψと同じ形ですね。つまりφ→ψと同じです。
　￢￢ψ∨￢φは￢ψ→￢φですから、￢ψ→￢φはφ→ψと同じであることが示せました。

締めと次回予告

　今回は命題論理について書きました。命題論理は現代的な論理学の基礎中の基礎です。全ての論理体系は命題論理を基本としています。プログラマの立場で見ても必修科目と言えるでしょう。プログラマが見たり触れたりするプログラムの多くは条件判断を行います。つまり真か偽で答えられる質問をさせて、真の時の答えと偽の時の答えを用意するわけです。
　実際にはプログラムに現れる問題は命題論理で扱えない範囲で有ることも多く、それは多くの場合述語論理の範囲に属しているのですが、そこらへんの話は次回以降取り扱います。

　わからないことや聞いてみたいことがあったら気軽にコメントしてください。次回以降でフォローします。
　大切な事なのでもう一度書きますが、わからないことや聞いてみたいことがあったら気軽にコメントしてください。

　さて次回 (があれば) ですが、次回は一階の述語論理のお話です。二階以上の述語論理の話をするかどうかはわかりませんが、一階の述語論理について書こうと思います。長くなるようなら前後編にするかもです。
　次回以降で触れようと思っているトピックを列挙します。他にも聞いてみたいトピックがあったらコメントください。

• 一階の述語論理
• 数学基礎論 (的な何か)
• 様相論理
• 時相論理
• 内包論理
• 形式手法
• 計算論 (主にλ計算)
• 計算複雑性理論