【記号論理】1 命題論理の基礎～「ならば」の意味～

こんにちは、これが315本目の記事となったすうじょうです。今日は、大学数学の解説記事です。今回の内容は、大学数学の基礎となる記号論理より命題論理の基礎を解説します。

記号論理の重要性

記号論理は、大学数学を理解するために重要な知識の一つで、線形代数や集合論の基礎とともに大学１年生のはじめに学ぶべき内容の一つである。最も有名だと思われる例としては、微分積分における極限の厳密な定義があげられる。

まずは、高校数学でなされる一般的な説明から確認する。

関数$${f(x)}$$において、変数$${x}$$が$${a}$$と異なる値をとりながら$${a}$$に限りなく近づくとき、$${f(x)}$$が一定の値$${\alpha}$$に限りなく近づく。このとき、

$$
\lim_{x\to a} f(x)=\alpha
$$

と書き、$${f(x)}$$は$${\alpha}$$に収束するという。

この説明には曖昧な部分がある。「限りなく近づく」という部分だ。大学数学では、厳密な定義が教えられる。（大学の講義や教科書によっては、高校と同様に定義してそのまま無視している場合もあるかもしれない）以下に、関数の極限の厳密な定義を示す。

$$
\forall \varepsilon > 0, \exists \delta >0 \space s.t. \space \forall x \in \R,0 < |x-a| < \delta \to |f(x) - \alpha| < \varepsilon
$$

が成り立つとき、

$$
\lim_{x\to a} f(x)=\alpha
$$

と書き、$${f(x)}$$は$${\alpha}$$に収束するという。

本などによって、表現がやや異なるかもしれないが、ここでは記号を用いて簡潔に定義を書いた。(ちなみにこの定義は$${\varepsilon-\delta}$$論法と呼ばれている)

記号の意味を理解している人からすれば、この定義の理解は容易であろう。しかし、初めて見る人からすれば意味が分からないだろう。少し古い文化だが、∀は顔文字でしか見たことがない人もいるかもしれないが、これは数学の記号である。

このシリーズでは、大学以降の数学において当たり前に使われるこれらの記号や、高校数学でも扱った命題について解説する。具体的には「命題論理」と「述語論理」の2つで構成する。

命題論理

命題とは

数学において、真偽が判断できる文のことを命題という。つまり、正しい(真である)か間違っている(偽である)かが判断できるような文のことである。命題は論理式によって表現される。

以降、単文の命題を$${p,q}$$などの小文字の英字で表し、命題変数(基本命題)とよぶ。単文の命題というのは、次のような主語と述語の対応が1つしかない文のこととする。

$${1 \neq 2}$$
$${2}$$は素数である
$${11}$$は奇数である

ただし、ここでは変数を含むような単文は含めない。これについては、述語論理のときに説明する。

命題変数について、真(True)であるとき$${\textrm{T}}$$または$${1}$$と表し、偽(False)であるとき$${\textrm{F}}$$または$${0}$$と表す。この$${\textrm{T}}$$や$${\textrm{F}}$$のことを真理値という。また、常に真の命題を$${\textrm{T}}$$または$${1}$$、常に偽の命題を$${\textrm{F}}$$または$${0}$$で表し、これらのことを命題定数という。

命題論理式とは

数学ではよく「でない」、「かつ」。「または」などの表現が使われるが、これを論理記号(論理結合子)で表し、命題変数と論理記号のみで命題を表現したものを命題論理式(複合命題)という。その定義は以下のように帰納的に定義される。

命題論理式の帰納的定義

1. 命題変数は論理式である

2. 命題定数は論理式である

3. $${P,Q}$$が論理式のとき, $${(\lnot P), (P \land Q), (P \lor Q), (P \to Q), (P \leftrightarrow Q)}$$は論理式である

4. 以上で定義されるもののみが論理式である

※$${\to}$$と$${\leftrightarrow}$$は、それぞれ$${\Rightarrow}$$,$${\Leftrightarrow}$$と書かれることもある。

論理記号の説明に入る前に、上の定義の説明をする。
上の説明は、1と2によって、$${p,q,\textrm{T},\textrm{F}}$$などが論理式であると定義している。そして、3によって$${(\lnot p), (p \land \textrm{T}), (\textrm{F} \to q)}$$などが論理式であると定義されている。そして、3で$${P,Q}$$は論理式であるとしているので、1,2,3を帰納的(ここでの帰納は数学的帰納法と同様の意味)に繰り返すことで、例えば$${((\lnot(p \land q)) \to (p \lor q))}$$も論理式であることになる。最後に、4により1,2,3が論理式の定義だと限定している。
注意点として、3の$${P,Q}$$は命題変数と区別するために大文字の英字にしている。

一般的に、論理記号の優先順位が$${\lnot, \land, \lor, \to, \leftrightarrow}$$とされていて、実際に書くときは誤読されないように論理式を書けばよい。なので、論理式には読み間違えられないように必要な部分だけ()を付ければよい。これを踏まえた上で、論理式の例を以下に示す。

$${\lnot p}$$
$${p \land \lnot q}$$
$${ \lnot p \to q}$$
$${(p \land q) \lor (\textrm{T} \land r)}$$
$${\lnot(p \land q) \to (p \lor q)}$$
$${(p \lor q) \leftrightarrow r}$$

論理記号の意味

命題論理式の真偽、つまり真理値は論理式を構成する各命題変数の真理値によって決まる。一般の命題論理式について、それを構成する命題変数がとる真理値のすべての組み合わせと、そのときの論理式の真理値を表にしたものを真理値表という。

ここからは、単純な論理式を例にして、各論理記号の意味を理解するために真理値表を示していく。

否定

例えば、$${\lnot p}$$のように書き、$${p}$$でないと読む。

表1:$${\lnot p}$$の真理値表

$$
\begin{array}{cc}
p& \lnot p \\
\hline
\textrm{F}&\textrm{T}\\
\textrm{T}&\textrm{F}\\
\hline
\end{array}
$$

論理積(連言)

例えば、$${p \land q}$$のように書き、$${p}$$かつ$${q}$$と読む。

表2:$${p \land q}$$の真理値表

$$
\begin{array}{ccc}
p&q&p \land q\\
\hline
\textrm{F}&\textrm{F}&\textrm{F}\\
\textrm{F}&\textrm{T}&\textrm{F}\\
\textrm{T}&\textrm{F}&\textrm{F}\\
\textrm{T}&\textrm{T}&\textrm{T}\\
\hline
\end{array}
$$

論理和(選言)

例えば、$${p \lor q}$$のように書き、$${p}$$または$${q}$$と読む。

表3:$${p \lor q}$$の真理値表

$$
\begin{array}{ccc}
p&q&p \lor q\\
\hline
\textrm{F}&\textrm{F}&\textrm{F}\\
\textrm{F}&\textrm{T}&\textrm{T}\\
\textrm{T}&\textrm{F}&\textrm{T}\\
\textrm{T}&\textrm{T}&\textrm{T}\\
\hline
\end{array}
$$

※真理値表からもわかるが、数学においての「または」と日常会話で使われる「または」は意味が異なるので注意する。

含意

例えば、$${p \to q}$$のように書き、$${p}$$ならば$${q}$$と読む。また、この論理式において$${p}$$を前提または仮定、$${q}$$を結論、$${p \to q}$$を含意式という。

表4:$${p \to q}$$の真理値表

$$
\begin{array}{ccc}
p&q&p \to q\\
\hline
\textrm{F}&\textrm{F}&\textrm{T}\\
\textrm{F}&\textrm{T}&\textrm{T}\\
\textrm{T}&\textrm{F}&\textrm{F}\\
\textrm{T}&\textrm{T}&\textrm{T}\\
\hline
\end{array}
$$

※高校数学においては、意識しなかったかもしれないが「ならば」の前提が偽のとき命題は真となる。これを覚えていると、「なぜ空集合は部分集合なのか」の証明など、使える場面がある。

※真理表を比べるとわかるが、$${p \to q}$$は$${\lnot p \lor q}$$と考えてもよい。

$${p \to q}$$が成り立つ(真)とき、$${q}$$を$${p}$$であるための必要条件、$${p}$$を$${q}$$であるための十分条件という。

$${P \to Q}$$を証明したいときは、$${P}$$が真であるときに$${Q}$$が真であることを証明すればよい。（$${P}$$が偽であるときは、$${P \to Q}$$は真なので考えなくてよい）

同値

例えば、$${p \leftrightarrow q}$$のように書き、$${p}$$と$${q}$$は同値であると読む。英語では、「$${p}$$if and only if$${q}$$」の略として「$${p}$$iff$${q}$$」と呼ばれることもある。

表5:$${p \leftrightarrow q}$$の真理値表

$$
\begin{array}{ccc}
p&q&p \leftrightarrow q\\
\hline
\textrm{F}&\textrm{F}&\textrm{T}\\
\textrm{F}&\textrm{T}&\textrm{F}\\
\textrm{T}&\textrm{F}&\textrm{F}\\
\textrm{T}&\textrm{T}&\textrm{T}\\
\hline
\end{array}
$$

※真理表を比べるとわかるが、$${p \leftrightarrow q}$$は$${(p \to q) \land (q \to p)}$$と考えてもよい。

$${p \leftrightarrow q}$$が成り立つ(真である)とき、$${p}$$と$${q}$$を互いに必要十分条件という。

$${P \leftrightarrow Q}$$を証明したいときは、$${P \to Q}$$が真であることと$${Q \to P}$$が真であることを証明すればよい。

恒真式・恒偽式

命題論理式で、それを構成する命題変数がどんな真理値であるときも論理式が常に真となるとき、その論理式を恒真式またはトートロジーという。また、論理式が常に偽となるとき、その論理式を恒偽式という。

以下にそれぞれの例とその真偽表を示す。

表6:恒真式$${p \lor \lnot p}$$の真理値表

$$
\begin{array}{ccc}
p&\lnot p&p \lor \lnot p\\
\hline
\textrm{F}&\textrm{T}&\textrm{T}\\
\textrm{T}&\textrm{F}&\textrm{T}\\
\hline
\end{array}
$$

表7:恒偽式$${p \land \lnot p}$$の真理値表

$$
\begin{array}{ccc}
p&\lnot p&p \land \lnot p\\
\hline
\textrm{F}&\textrm{T}&\textrm{F}\\
\textrm{T}&\textrm{F}&\textrm{F}\\
\hline
\end{array}
$$

演習問題1

問題1 次の(a)~(g)のうち、論理式であるものをすべて選べ。
(a)$${p \lor q}$$
(b)$${\lnot p \land \textrm{F}}$$
(c)$${p \lor \land q}$$
(d)$${p \lnot \land q}$$
(e)$${\textrm{T} \to (p \lor q)}$$
(f)$${\land q}$$
(g)$${p \lnot q}$$

[方針]
論理式の定義にしたがっていなければならない
[解答]
(a),(b),(e)

問題2 次の論理式の真偽値表をそれぞれ書け。
(1)$${\lnot p \land q}$$
(2)$${\textrm{T} \to p}$$
(c)$${(p \lor q) \land r}$$

[解答]
(1)

$$
\begin{array}{cccc}
p&q&\lnot p&\lnot p \land q\\
\hline
\textrm{F}&\textrm{F}&\textrm{T}&\textrm{F}\\
\textrm{F}&\textrm{T}&\textrm{T}&\textrm{T}\\
\textrm{T}&\textrm{F}&\textrm{F}&\textrm{F}\\
\textrm{T}&\textrm{T}&\textrm{F}&\textrm{F}\\
\hline
\end{array}
$$

(2)

$$
\begin{array}{cccc}
\textrm{T}&p&\textrm{T} \to p\\
\hline
\textrm{T}&\textrm{F}&\textrm{F}\\
\textrm{T}&\textrm{T}&\textrm{T}\\
\hline
\end{array}
$$

(3)

$$
\begin{array}{ccccc}
p&q&r&p \lor q&(p \lor q) \land r\\
\hline
\textrm{F}&\textrm{F}&\textrm{F}&\textrm{F}&\textrm{F}\\
\textrm{F}&\textrm{F}&\textrm{T}&\textrm{F}&\textrm{F}\\
\textrm{F}&\textrm{T}&\textrm{F}&\textrm{T}&\textrm{F}\\
\textrm{F}&\textrm{T}&\textrm{T}&\textrm{T}&\textrm{T}\\
\textrm{T}&\textrm{F}&\textrm{F}&\textrm{T}&\textrm{F}\\
\textrm{T}&\textrm{F}&\textrm{T}&\textrm{T}&\textrm{T}\\
\textrm{T}&\textrm{T}&\textrm{F}&\textrm{T}&\textrm{F}\\
\textrm{T}&\textrm{T}&\textrm{T}&\textrm{T}&\textrm{T}\\
\hline
\end{array}
$$

※真理値表で、すべてのパターンを漏れなくあげるコツとして、真を$${1}$$、偽を$${0}$$で表したとき、命題変数を2進数として考え、0から順に書き並べていくという方法がある。

最後に

今回は、大学数学・記号論理の解説記事として、命題論理の基礎について解説しました。今回の内容は、大学数学を理解するための基礎となる大事な内容です。次回は、論理的同値の解説記事となる予定です。では。

この記事の続きは以下の記事です。