文献あり

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

数学を勉強していると, 時々目にする $\exists$ , $\forall$ の論理記号ですが, これらは量化子(あるいは量化記号)と呼ばれ, 特にそれぞれ特称記号, 全称記号と言います。
論理記号と言えば, 例えば"かつ"を表す $\land$ や, "または"を表す $\lor$ がありますね。これらで結ばれた $p \land q$ , $p \lor q$ をそれぞれ論理積, 論理和と言いました。 $p, q$ は任意の命題です。
これらについて, 次に示すような分配律が一般に成り立ちます。

論理和と論理積の分配律

$p$ , $q$ , $r$ を命題として
$\begin{array}{r} {\begin{cases} p \land (q \lor r) ⟺ (p \land q) \lor (p \land r) \\ p \lor (q \land r) ⟺ (p \lor q) \land (p \lor r) \end{cases} \end{array}$
が成り立つ。

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

さしあたり必要な知識

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

量化記号の定義

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

量化記号の定義

$p (x)$ を $x$ に関する条件として,
$\begin{aligned} \exists_{x} [p (x)] & \overset{def}{⟺} p (x) をみたす x が存在する \\ \forall_{x} [p (x)] & \overset{def}{⟺} 任意の x で p (x) が成立する \end{aligned}$
と定義する。
また, $x$ 全体の集合が決まっている場合, それが仮に集合 $A$ であるとき $\exists_{x \in A}$ , $\forall_{x \in A}$ などと書く。

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

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

さて, 量化記号の定義をおさらいしたところで, これらの記号を命題論理, つまり $\land$ , $\lor$ , $\neg$ などで表してみることにします。
$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)] ⟺ p (x_{1}) \lor p (x_{2}) \lor p (x_{3}) \lor \dots \lor p (x_{n})$

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

$\forall_{x \in A} [p (x)] ⟺ p (x_{1}) \land p (x_{2}) \land p (x_{3}) \land \dots \land p (x_{n})$

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

対偶をとってみる

ここでは, 今確認した命題 $2$ に対して, 対偶律を用いてみます。
同値文の対偶律は, 両辺の否定をとるということです。
$\begin{aligned} \neg (\exists_{x \in A} [p (x)]) & ⟺ \neg (p (x_{1}) \lor p (x_{2}) \lor p (x_{3}) \lor \dots \lor p (x_{n})) \\ ⟺ \neg p (x_{1}) \land \neg p (x_{2}) \land \neg p (x_{3}) \land \dots \land \neg p (x_{n}) & (∵ de Morgan律) \\ ⟺ \forall_{x \in A} [\neg p (x)] & (∵ 命題 3) \end{aligned}$
実際これは, 命題 $2, 3$ がわかっていれば単なるde Morgan律に過ぎませんので, これもde Morgan律とします。

量化記号のde Morgan律

$\neg (\exists_{x \in A} [p (x)]) ⟺ \forall_{x \in A} [\neg p (x)]$
$\neg (\forall_{x \in A} [p (x)]) ⟺ \exists_{x \in A} [\neg p (x)]$

記号の導入

先に見た論理結合子 $p (x_{1}) \lor p (x_{2}) \lor p (x_{3}) \lor \dots \lor p (x_{n})$ などは少々長ったらしいので次のような記号を定義しておきます。

添字域を $I_{n} = {i \in N; 1 \leq i \leq n}$ とする下で
$\underset{i \in I_{n}}{⋁} p (a_{i}) \overset{def}{⟺} p (a_{1}) \lor p (a_{2}) \lor \dots \lor p (a_{n})$
$\underset{i \in I_{n}}{⋀} p (a_{i}) \overset{def}{⟺} p (a_{1}) \land p (a_{2}) \land \dots \land p (a_{n})$
のように表記する。

量化記号の分配律

以上に見た論理関係を用いて, 目的である「量化記号の分配律」を導いてみることにします。
$n$ 個の元を持つ有限集合 $A$ に対し, $i$ 番目の元を $a_{i}$ のように表記することにすると次が成り立ちます。
$\begin{aligned} \exists_{x \in A} [p (x) \lor q (x)] & ⟺ \underset{x \in A}{⋁} (p (x) \lor q (x)) \\ ⟺ (p (a_{1}) \lor p (a_{2}) \lor \dots \lor p (a_{n})) \lor (q (a_{1}) \lor q (a_{2}) \lor \dots \lor q (a_{n})) & (∵ 交換律) \\ ⟺ (\underset{x \in A}{⋁} p (x)) \lor (\underset{x \in A}{⋁} q (x)) \\ ⟺ \exists_{x \in A} [p (x)] \lor \exists_{x \in A} [q (x)] \end{aligned}$
したがって, 次に示す分配律が導けました。

特称記号の分配律1

$\exists_{x} [p (x) \lor q (x)] ⟺ \exists_{x} [p (x)] \lor \exists_{x} [q (x)]$

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

特称記号の分配律1

$\exists_{x} [p (x) \lor r] ⟺ \exists_{x} [p (x)] \lor r$

ここで, 特称記号の分配律 $1$ に対して対偶をとれば,
$\begin{aligned} 特称記号の分配律 1 & ⟺ (\neg (\exists_{x} [p (x) \lor q (x)]) ⟺ \neg (\exists_{x} [p (x)] \lor \exists_{x} [q (x)])) \\ ⟺ ((\forall_{x} [\neg p (x) \land \neg q (x)]) ⟺ (\forall_{x} [\neg p (x)] \land \forall_{x} [\neg q (x)])) & (∵ de Morgan律) \end{aligned}$
ここに $\neg p (x)$ , $\neg q (x)$ を $p (x)$ , $q (x)$ と置き換えても一般性を失いませんから, 今度は次に示す全称記号に関する分配律が導けました。

全称記号の分配律1

$\forall_{x} [p (x) \land q (x)] ⟺ \forall_{x} [p (x)] \land \forall_{x} [q (x)]$

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

全称記号の分配律1

$\forall_{x} [p (x) \land r] ⟺ \forall_{x} [p (x)] \land r$

このように, 論理和の集合体 $\exists$ は論理和について, また論理積の集合体 $\forall$ は論理積についての分配は同値変形が可能であることがわかりました。
ではさらに, 「 $\exists$ の論理積についての分配」, 「 $\forall$ の論理和についての分配」についてはどうでしょうか。
ということで, 「 $\exists$ の論理積についての分配」から見ていくことにしますが, これが意外にも大変面倒な導出になります。 $\underset{―}{下線部}$ は取り除く部分の意味です。
$\begin{aligned} \exists_{x \in A} [p (x) \land q (x)] & ⟺ {p (a_{1}) \land q (a_{1})} \lor {p (a_{2}) \land q (a_{2})} \lor \dots \\ ⟺ ([p (a_{1}) \lor {p (a_{2}) \land q (a_{2})}] \land [q (a_{1}) \lor {p (a_{2}) \land q (a_{2})}]) \lor \dots \\ ⟺ ([{p (a_{1}) \lor p (a_{2})} \land {p (a_{1}) \lor q (a_{2})}] \land [{q (a_{1}) \lor p (a_{2})} \land {q (a_{1}) \lor q (a_{2})}]) \lor \dots & (∵ 分配律) \\ ⟺ [{p (a_{1}) \lor p (a_{2})} \land {q (a_{1}) \lor q (a_{2})} \underset{―}{\land {p (a_{1}) \lor q (a_{2})} \land {q (a_{1}) \lor p (a_{2})}}] \lor [{p (a_{3}) \lor p (a_{4})} \land {q (a_{3}) \lor q (a_{4})} \underset{―}{\land {p (a_{3}) \lor q (a_{4})} \land {q (a_{3}) \lor p (a_{4})}}] \lor \dots & (∵ 交換律) \\ ⟹ [{p (a_{1}) \lor p (a_{2})} \land {q (a_{1}) \lor q (a_{2})}] \lor [{p (a_{1}) \lor p (a_{2})} \land {q (a_{1}) \lor q (a_{2})}] \lor \dots \\ ⟺ {({p (a_{1}) \lor p (a_{2})} \lor [{p (a_{3}) \lor p (a_{4})} \land {q (a_{3}) \lor q (a_{4})}]) \land ({q (a_{1}) \lor q (a_{2})} \lor [{p (a_{3}) \lor p (a_{4})} \land {q (a_{3}) \lor q (a_{4})}])} \lor \dots & (∵ 分配律) \\ ⟺ [{p (a_{1}) \lor p (a_{2})} \lor {p (a_{3}) \lor p (a_{4})}] \underset{―}{\land [{p (a_{1}) \lor p (a_{2})} \lor {q (a_{3}) \lor q (a_{4})}]} \underset{―}{\land [{q (a_{1}) \lor q (a_{2})} \lor {p (a_{3}) \lor p (a_{4})}]} \land [{q (a_{1}) \lor q (a_{2})} \lor {q (a_{3}) \lor q (a_{4})}] \lor \dots & (∵ 分配律) \\ ⟹ [{p (a_{1}) \lor p (a_{2}) \lor p (a_{3}) \lor p (a_{4})} \land {q (a_{1}) \lor q (a_{2}) \lor q (a_{3}) \lor q (a_{4})}] \lor \dots \\ ⟺ ⋮ \\ ⟹ \exists_{x \in A} [p (x)] \land \exists_{x \in A} [q (x)] \end{aligned}$
よって, これより次の定理が導かれました。

特称記号の分配律2

$(\exists_{x} [p (x) \land q (x)]) ⟹ (\exists_{x} [p (x)] \land \exists_{x} [q (x)])$

このように $\exists_{x}$ 内部(に束縛された $x$ についての条件)の論理積 $p (x) \land q (x)$ は外部に分配することはでき, その逆は不成立であることが導かれたわけです。
また, さらにこれの対偶をとれば,
$\begin{aligned} 特称記号の分配律 2 & ⟺ (\neg {(\exists_{x} [p (x) \land q (x)]) ⟹ (\exists_{x} [p (x)] \land \exists_{x} [q (x)])}) & (∵ 対偶律) \\ ⟺ ((\forall_{x} [\neg p (x) \lor \neg q (x)]) ⟸ (\forall_{x} [\neg p (x)] \lor \forall_{x} [\neg q (x)])) & (∵ de Morgan律) \end{aligned}$
これも $\neg p (x)$ , $\neg q (x)$ を $p (x)$ , $q (x)$ としても一般性を失わないので, まとめると次の定理が導かれます。

全称記号の分配律2

$(\forall_{x} [p (x) \lor q (x)]) ⟸ (\forall_{x} [p (x)] \lor \forall_{x} [q (x)])$

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

最後に

以上で, 量化記号の分配に関する分配律は導かれました。
最後の二つは特に重要で, 忘れやすいですが量化記号の本質的な意味として, 命題 $2, 3$ をイメージとして持っていることで導出とともに印象に残しておくと忘れにくいと思います。
お疲れさまでした。

参考文献

[1]

長岡亮介, 論理学で学ぶ数学, 旺文社

投稿日：2月8日

更新日：2月8日

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。

バッチを贈って投稿者を応援しよう

バッチを贈ると投稿者に現金やAmazonのギフトカードが還元されます。

投稿者

276

数学初心者です。

他の人のコメント

コメントはありません。

読み込み中

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

さしあたり必要な知識
量化記号の定義
特称記号と全称記号の論理関係
記号の導入
量化記号の分配律
最後に
参考文献