命題論理

Section 3.3 命題論理

数学では、式や文を命題という形で扱う命題論理(propositional logic)の論理が、最も基本的な枠組みである。

Subsection 3.3.1 命題

数学が基盤とする論理学では、客観的な分析が可能な文を命題(proposition)として扱い、複数の命題を推論で接続することで論理を展開する。

定義 3.18. 命題.

「正しい」か「正しくない」かが明確に定まる式や文のことを命題(proposition)という。命題\(p\)が「正しい」とき、\(p\)は真(true)であるという。また、\(p\)が真でないとき、\(p\)は偽(false)であるという。命題\(p\)が真であることを\(p\)が成り立つ、命題\(p\)が偽であることを\(p\)が成り立たないともいう。

特に、真である命題を定理(theorem)という。ただし、一般的に「定理」という場合は、「真である命題」のうち「何らかの基準に照らして重要なもの」を指すことが多い。

命題を文字で表す場合、propositionの頭文字の\(p\)を用い、複数の命題を文字で表すときは\(q\)や\(r\)も用いることが多い。流儀によっては、命題を大文字の\(P\)や\(Q\)で表すことも多い。

例 3.19. 命題の例.

「富士山は高い山である」という文は、「高い」という形容詞に対する解釈が人によって異なるため、命題でない。富士山の近辺に住んでいる人は「富士山は高い」と解釈する可能性が高いが、エベレストの近辺に住んでいる人は「富士山は高くない」と解釈する可能性が高い。一方、「富士山は天保山より高い山である」という文にも、同じように「高い」という形容詞が含まれる。だがこの文では、「富士山(の標高)」と「天保山(の標高)」という数値で大小比較可能なものを比べているため、誰が判断しても真になると考えられ、命題だといえる。

Subsection 3.3.2 「かつ」「または」「でない」

命題についての基本的な操作には、1つの命題に対する否定や、2つ以上の命題に対する「かつ(連言)」「または(選言)」がある。

定義 3.20. 連言・選言・否定.

\(p, q\)を命題とするとき、\(p, q\)の両方が真のときに真となり、それ以外のときに偽となる命題を「\(p\)かつ\(q\)」といい、\(p \land q\)と表すことがある。また、\(p, q\)の少なくとも一方が真のときに真となり、それ以外のときに偽となる命題を「\(p\)または\(q\)」といい、\(p \lor q\)と表すことがある。更に、\(p\)が偽のときに真となり、真のときに偽となる命題を「\(p\)の否定」といい、\(\overline{p}\)と表す。

数学における「または」は、「どちらか一方が成り立つ」という意味ではなく「 少なくとも一方が成り立つ」という意味であることに注意が必要である。

Subsection 3.3.3 命題に関する計算法則

「または」や「かつ」、「でない」については、次のような等式が成り立つ。

定理 3.21. 命題に関する計算法則.

\(p, q, r\)が命題のとき、次の等式が成り立つ。

\begin{align*} p \lor q &= q \lor p & (\text{交換法則})\\ p \land q &= q \land p & (\text{交換法則})\\ (p \lor q) \lor r &= p \lor (q \lor r) & (\text{結合法則})\\ (p \land q) \land r &= p \land (q \land r) & (\text{結合法則}) \end{align*}

命題に関する分配法則も成り立つが、数の分配法則と異なる部分もある。

定理 3.22. 命題に関する分配法則.

\(p, q, r\)が命題のとき、次の等式が成り立つ。

\begin{gather*} (p \lor q) \land r = (p \land r) \lor (q \land r)\\ (p \land q) \lor r = (p \lor r) \land (q \lor r) \end{gather*}

2番目の式は数の分配法則とは異なるので、注意が必要である。

さらに命題については、次のde Morganの法則が成り立つ。

定理 3.23. de Morganの法則.

\(p, q\)が命題のとき、次の等式が成り立つ。

\begin{align*} \overline{p \land q} & = \overline{p} \lor \overline{q}\\ \overline{p \lor q} & = \overline{p} \land \overline{q} \end{align*}

証明.

真理値表を用いて示す。

Subsection 3.3.4 推論「ならば」

命題を用いてより高度な命題を表すには、次の推論(inference)を表す規則が必要となる。

定義 3.24. 推論.

\(p, q\)を命題とするとき、「もし\(p\)が成り立つならば、\(q\)も成り立つ」という命題を「\(p\)ならば\(q\)」といい、\(p \implies q\)と表す。命題\(p \implies q\)は、「\(p\)が偽のとき」か「\(p\)も\(q\)も真のとき」に真となる。

\begin{gather*} [ p \implies q ] = [ \overline{p} \lor (p \land q) ] = [ (\overline{p} \lor p) \land (\overline{p} \lor q)] (\text{分配法則}) = [ \overline{p} \lor q ] (\text{排中律}) \end{gather*}

命題\(p \implies q\)について、\(p\)を\(p \implies q\)の仮定、\(q\)を\(p \implies q\)の結論という。また、\(q\)を\(p\)の必要条件(necessary condition)、\(p\)を\(q\)の十分条件(sufficient condition)という。

必要条件と十分条件は、「\(p \implies q\)」の「\(\implies\)」を矢に見立てて、「矢の先は必要」と覚えるとよい。

例 3.25. 推論の例.

「宝くじに当たったら家を買う」という命題では、命題「宝くじに当たる」が仮定、命題「家を買う」が結論である。この命題の真偽について考えると、宝くじに当たった場合には、家を買った場合には真、そうでなければ偽となる。一方、宝くじに当たらなかった場合には、家を買おうと買うまいと、この命題では何も言っていないので、偽だとは言えず真となる。

Subsection 3.3.5 同値

この推論規則を用いて、2つの命題が「同じ」であるという関係を定義する。

定義 3.26. 同値.

\(p, q\)を命題とするとき、\(p \implies q\)かつ\(q \implies p\)であれば、\(p\)と\(q\)は同値であるといい、\(p \iff q\)と表す。

\begin{gather*} [ p \iff q ] = [ p \implies q ] \land [ q \implies p ] \end{gather*}

このとき、\(q\)を\(p\)の必要十分条件であるといい、\(p\)も\(q\)の必要十分条件であるという。

同値の記号「\(\iff\)」は数の比較に用いる等号「\(=\)」と同様の記号で、2つの命題が「同じ」ことを表せる便利な記号である。ただし「\(\iff\)」を使う際は、「\(\implies\)」方向だけでなく「\(\impliedby\)」方向についても命題が成り立っていることを確認する必要がある。「\(\impliedby\)」方向が成り立つと言い切れない場合には、「\(\implies\)」記号を使うべきである。

Subsection 3.3.6 逆・裏・対偶

更に、推論を用いた命題について、逆や裏、対偶を定義できる。

定義 3.27. 逆・裏・対偶.

\(p, q\)を命題とするとき、命題\(p \implies q\)に対し、\(q \implies p\)を元の命題の逆、\(\overline{p} \implies \overline{q}\)を元の命題の裏、\(\overline{q} \implies \overline{p}\)を元の命題の対偶という。

このうち、命題\(p \implies q\)と逆\(q \implies p\)について、前者は\(\overline{p} \lor q\)、後者は\(\overline{q} \lor p\)であるので、命題とその逆の真偽は一致しない。また、命題\(p \implies q\)と対偶\(\overline{q} \implies \overline{p}\)については、次の定理が成り立つ。

定理 3.28. 命題とその対偶.

命題とその対偶の真偽は一致する。つまり、\(p, q\)を命題とするとき、

\begin{gather*} [ \overline{q} \implies \overline{p} ] = [ p \implies q ] \end{gather*}

証明.

\begin{gather*} [ \overline{q} \implies \overline{p} ] = [\overline{\overline{q}} \lor \overline{p}] = [ q \lor \overline{p}] = [ \overline{p} \lor q] = [ p \implies q ] \end{gather*}