文献あり

量化記号の分配則を導いてみる

135

この著者は初心者として投稿しています。間違いや考慮が足りていない点が含まれている可能性が高いです。見つけたらコメント欄で優しく指摘してあげましょう。

数学を勉強していると, 時々その姿を現す$\exists$, $\forall$があります。
これらは, 論理記号であり, 量化子(あるいは量化記号)と呼ばれる$\exists$, $\forall$は, それぞれ特称記号, 全称記号と言います。

論理記号と言えば, 例えば"かつ"を表す$\land$や, "または"を表す$\lor$がありますね。これらで結ばれた$p \land q$, $ p \lor q$をそれぞれ論理積, 論理和と言いました。$p, q$は任意の命題です。
これらについて, 次に示すような分配則(分配律)が一般に成り立ちます。

論理和と論理積の分配則(分配律)

$p$, $q$, $r$を命題として

$\begin{eqnarray} \left\{ \begin{array}{l} p \land (q \lor r) \Longleftrightarrow (p \land q) \lor (p \land r) \\ p \lor (q \land r) \Longleftrightarrow (p \lor q) \land (p \lor r) \end{array} \right. \end{eqnarray}$

が成り立つ。

量化記号に関しても, このような分配則が存在します。
この記事では, それについて導いてみることにします。

さしあたり必要な知識

既にお分かりかと思いますが, この記事では量化記号の分配則について議論しますから, 論理記号を多用します。
さしあたっては, 基礎的な論理記号の意味とその定義, 論理和・積の分配則のような基本的な定理は既に分かっているものとして扱いますのでご了承願います。

量化記号の定義

まず量化記号の定義を簡単におさらいしておきます。

量化記号の定義

$p(x)$を$x$に関する条件として,

\begin{align} \exists_x [p(x)] &\stackrel{\mathrm{def}}{\Longleftrightarrow} p(x)\text{をみたす}x\text{が存在する}\\ \forall_x [p(x)] &\stackrel{\mathrm{def}}{\Longleftrightarrow} \text{任意の}x\text{で}p(x)\text{が成立する} \end{align}

と定義する。
また, $x$全体の集合が決まっている場合, それが仮に集合$A$であるとき$\exists_{x \in A}$, $\forall_{x \in A}$などと書く。

特称記号と全称記号の論理関係

量化記号を命題論理で表現してみる

さて, 量化記号の定義をおさらいしたところで, これらの記号を命題論理, つまり$\land$, $\lor$, $\lnot$などで表してみることにします。
$A$を元の総数が$n$個の有限集合として任意の元を$x \in A$, $p(x)$を$x$の条件とします。

「$p(x)$をみたす$x$が存在する」とは, 「ある$x$で条件$p(x)$が成り立つ」でありますから, そのような$x$をしらみつぶしに探せばよいのです。したがって, 次のように表せることがわかります。$x_n$は$n$番目の集合$A$の元です。

$\exists_{x \in A}[p(x)] \Longleftrightarrow p(x_1) \lor p(x_2) \lor p(x_3) \lor \cdots \lor p(x_n)$

また, 「任意の$x \in A$で$p(x)$が成り立つ」とは, 「すべての$x \in A$で$p(x)$が成り立つ」であり, これも同様にしらみつぶしに成立を確かめてゆけばよいことがわかります。

$\forall_{x \in A}[p(x)] \Longleftrightarrow p(x_1) \land p(x_2) \land p(x_3) \land \cdots \land p(x_n)$

今, 有限集合の場合でこのように論理式で定式化をしましたが, これを無限集合に拡張することを考えると, 単純な論理結合子の組み合わせのみで表現できないだけで本質的な意味は変わらず, 無限集合の場合にも同様の議論をすることになります。
したがって, この命題$2, 3$は無限集合の場合にも成り立つとして良いでしょう。

対偶をとってみる

ここでは, 今確認した命題$2$に対して, 対偶則を用いてみます。
同値文の対偶則は, 両辺の否定をとるということです。

\begin{align} \lnot(\exists_{x \in A}[p(x)]) &\Longleftrightarrow \lnot(p(x_1) \lor p(x_2) \lor p(x_3) \lor \cdots \lor p(x_n))\\ &\Longleftrightarrow \lnot p(x_1) \land \lnot p(x_2) \land \lnot p(x_3) \land \cdots \land \lnot p(x_n) &(\because \text{de Morgan則})\\ &\Longleftrightarrow \forall_{x \in A}[\lnot p(x)] &(\because \text{命題}3) \end{align}

実際これは, 命題$2, 3$がわかっていれば単なるde Morgan則に過ぎませんので, これもde Morgan則とします。

量化記号のde Morgan則

$\lnot(\exists_{x \in A}[p(x)]) \Longleftrightarrow \forall_{x \in A}[\lnot p(x)]$
$\lnot(\forall_{x \in A}[p(x)]) \Longleftrightarrow \exists_{x \in A}[\lnot p(x)]$

記号の導入

先に見た論理結合子$p(x_1) \lor p(x_2) \lor p(x_3) \lor \cdots \lor p(x_n)$などは少々長ったらしいので次のような記号を定義しておきます。
(※専門的にこれらの記号が認められているかは, 自分の知る限り定かではないので, さしあたってはここだけで用いる記号として考えてください。)

$\displaystyle \bigvee_{i=1}^n p(a_i) \stackrel{\mathrm{def}}{\Longleftrightarrow} p(a_1) \lor p(a_2) \lor \cdots \lor p(a_n)$
$\displaystyle \bigwedge_{i=1}^n p(a_i) \stackrel{\mathrm{def}}{\Longleftrightarrow} p(a_1) \land p(a_2) \land \cdots \land p(a_n)$

量化記号の分配則

以上に見た論理関係を用いて, 目的である「量化記号の分配則」を導いてみることにします。
$n$個の元を持つ有限集合$A$に対する任意の元を$x$, $p(x)$, $q(x)$を$x$の条件とします。
\begin{align} \exists_{x \in A}[p(x) \lor q(x)] &\Longleftrightarrow \displaystyle \bigvee_{i=1}^n \left(p(a_i) \lor p(a_i) \right)\\ &\Longleftrightarrow \left( p(a_1) \lor p(a_2) \lor \cdots \lor p(a_n) \right) \lor \left( q(a_1) \lor q(a_2) \lor \cdots \lor q(a_n) \right) &(\because \text{交換則})\\ &\Longleftrightarrow \left( \bigvee_{i=1}^n p(a_i) \right) \lor \left( \bigvee_{i=1}^n q(a_i) \right)\\ &\Longleftrightarrow \exists_{x \in A} [p(x)] \lor \exists_{x \in A} [q(x)] \end{align}

したがって, 次に示す分配則が導けました。

特称記号の分配則1

$\exists_x [p(x) \lor q(x)] \Longleftrightarrow \exists_x [p(x)] \lor \exists_x [q(x)]$

また, この定理の系として$x$に関係のない命題$r$との論理和に対しては次が成り立つことが直ちに導かれます。

特称記号の分配則1

$\exists_x [p(x) \lor r] \Longleftrightarrow \exists_x [p(x)] \lor r$

ここで, 特称記号の分配則$1$に対して対偶をとれば,

\begin{align} \text{特称記号の分配則}1&\Longleftrightarrow (\lnot (\exists_x [p(x) \lor q(x)]) \Longleftrightarrow \lnot (\exists_x [p(x)] \lor \exists_x [q(x)]))\\ &\Longleftrightarrow ((\forall_x [\lnot p(x) \land \lnot q(x)]) \Longleftrightarrow (\forall_x [\lnot p(x)] \land \forall_x [\lnot q(x)])) &(\because \text{de Morgan則}) \end{align}

ここに$\lnot p(x)$, $\lnot q(x)$を$p(x)$, $q(x)$と置き換えても一般性を失いませんから, 今度は次に示す全称記号に関する分配則が導けました。

全称記号の分配則1

$\forall_x [p(x) \land q(x)] \Longleftrightarrow \forall_x [p(x)] \land \forall_x [q(x)]$

特称記号のときと同様に, $x$に関係のない命題$r$との論理積に対して次が成り立つことが直ちに導かれます。

全称記号の分配則1

$\forall_x [p(x) \land r] \Longleftrightarrow \forall_x [p(x)] \land r$

このように, 論理和の集合体$\exists$は論理和について, また論理積の集合体$\forall$は論理積についての分配は同値変形が可能であることがわかりました。

ではさらに, 「$\exists$の論理積についての分配」, 「$\forall$の論理和についての分配」についてはどうでしょうか。
ということで, 「$\exists$の論理積についての分配」から見ていくことにしますが, これが意外にも大変面倒な導出になります。$\underline{\text{下線部}}$は取り除く部分の意味です。

\begin{align} \exists_{x \in A} [ p(x) \land q(x) ] &\Longleftrightarrow \left\{ p(a_1) \land q(a_1) \right\} \lor \left\{ p(a_2) \land q(a_2) \right\} \lor \cdots\\ \\ &\Longleftrightarrow \left( \left[ p(a_1) \lor \left\{ p(a_2) \land q(a_2) \right\} \right] \land \left[ q(a_1) \lor \left\{ p(a_2) \land q(a_2) \right\} \right] \right) \lor \cdots\\ \\ &\Longleftrightarrow ( [ \left\{ p(a_1) \lor p(a_2) \right\} \land \left\{ p(a_1) \lor q(a_2) \right\} ] \land [ \left\{ q(a_1) \lor p(a_2) \right\} \land \left\{ q(a_1) \lor q(a_2) \right\} ] ) \lor \cdots &(\because \text{分配則})\\ \\ &\Longleftrightarrow [ \left\{ p(a_1) \lor p(a_2) \right\} \land \left\{ q(a_1) \lor q(a_2) \right\} \underline{\land \left\{ p(a_1) \lor q(a_2) \right\} \land \left\{ q(a_1) \lor p(a_2) \right\}} ] \lor [ \left\{ p(a_3) \lor p(a_4) \right\} \land \left\{ q(a_3) \lor q(a_4) \right\} \underline{\land \left\{ p(a_3) \lor q(a_4) \right\} \land \left\{ q(a_3) \lor p(a_4) \right\}} ] \lor \cdots &(\because \text{交換則})\\ \\ &\Longrightarrow \left[ \left\{ p(a_1) \lor p(a_2) \right\} \land \left\{ q(a_1) \lor q(a_2) \right\} \right] \lor \left[ \left\{ p(a_1) \lor p(a_2) \right\} \land \left\{ q(a_1) \lor q(a_2) \right\} \right] \lor \cdots\\ \\ &\Longleftrightarrow \{( \left\{p(a_1) \lor p(a_2) \right\} \lor \left[ \left\{ p(a_3) \lor p(a_4) \right\} \land \left\{ q(a_3) \lor q(a_4) \right\} \right] ) \land ( \left\{q(a_1) \lor q(a_2) \right\} \lor \left[ \left\{ p(a_3) \lor p(a_4) \right\} \land \left\{ q(a_3) \lor q(a_4) \right\} \right] ) \} \lor \cdots &(\because \text{分配則})\\ \\ &\Longleftrightarrow \left[ \left\{p(a_1) \lor p(a_2) \right\} \lor \left\{p(a_3) \lor p(a_4) \right\} \right] \underline{\land \left[ \left\{p(a_1) \lor p(a_2) \right\} \lor \left\{q(a_3) \lor q(a_4) \right\} \right] } \underline{\land \left[ \left\{q(a_1) \lor q(a_2) \right\} \lor \left\{p(a_3) \lor p(a_4) \right\} \right]} \land \left[ \left\{q(a_1) \lor q(a_2) \right\} \lor \left\{q(a_3) \lor q(a_4) \right\} \right] \lor \cdots &(\because \text{分配則})\\ \\ &\Longrightarrow \left[ \left\{ p(a_1) \lor p(a_2) \lor p(a_3) \lor p(a_4) \right\} \land \left\{ q(a_1) \lor q(a_2) \lor q(a_3) \lor q(a_4) \right\} \right] \lor \cdots\\ \\ &\Longleftrightarrow \vdots\\ \\ &\Longrightarrow \exists_{x \in A} [p(x)] \land \exists_{x \in A} [q(x)] \end{align}

よって, これより次の定理が導かれました。

特称記号の分配則2

$(\exists_x [p(x) \land q(x)]) \Longrightarrow (\exists_x [p(x)] \land \exists_x [q(x)])$

このように$\exists_x$内部(に束縛された$x$についての条件)の論理積$p(x) \land q(x)$は外部に分配することはでき, その逆は不成立であることが導かれたわけです。

また, さらにこれの対偶をとれば,

\begin{align} \text{特称記号の分配則}2 &\Longleftrightarrow (\lnot \left\{ (\exists_x [p(x) \land q(x)]) \Longrightarrow (\exists_x [p(x)] \land \exists_x [q(x)]) \right\}) &(\because \text{対偶則})\\ &\Longleftrightarrow ((\forall_x [\lnot p(x) \lor \lnot q(x)]) \Longleftarrow (\forall_x [\lnot p(x)] \lor \forall_x [\lnot q(x)])) &(\because \text{de Morgan則})\\ \end{align}

これも$\lnot p(x)$, $\lnot q(x)$を$p(x)$, $q(x)$としても一般性を失わないので, まとめると次の定理が導かれます。

全称記号の分配則2

$(\forall_x [p(x) \lor q(x)]) \Longleftarrow (\forall_x [p(x)] \lor \forall_x [q(x)])$

今度は, $\forall_x$内部(に束縛された$x$についての条件)の論理和$p(x) \lor q(x)$は外部に分配することができず, その逆は成立することが導かれました。