条件と集合の対応 | 集合と論理

1 真理集合

条件を、それを満たすものの集まりへ置き換えます。

定義 1.1 (真理集合). ある条件を真にする値をすべて集めた集合を、その条件の真理集合という²。条件 $p(x)$ の真理集合を $P$ と書くと、「 $x$ が条件 $p$ を満たす」ことと「 $x \in P$ 」とは同じ意味である。

この対応を通すと、論理の演算がそのまま集合の演算に読み替わります。

条件の側	集合の側
$p$ かつ $q$	$P \cap Q$ （共通部分）
$p$ または $q$	$P \cup Q$ （和集合）
$p$ でない	$\overline{P}$ （補集合）³
$p$ ならば $q$	$P \subset Q$ （包含）

「かつ」「または」「でない」の計算は、共通部分、和集合、補集合の計算に対応します。「 $p$ ならば $q$ 」がすべての値について成り立つことは、 $P$ のどの要素も $Q$ の要素である、すなわち $P \subset Q$ が成り立つことと同じです。

2 例：整数についての条件

例 2.1 (倍数の条件を集合で読む). 全体集合を整数全体とし、二つの条件を次のように置く。

$p(x)$ ： $x$ は $4$ の倍数である。真理集合を $P$ と書く。
$q(x)$ ： $x$ は $2$ の倍数である。真理集合を $Q$ と書く。

$4$ の倍数はすべて $2$ の倍数なので $P \subset Q$ が成り立つ。これは条件の言葉では「 $p(x)$ ならば $q(x)$ 」がすべての整数について成り立つことにあたる。逆向きの包含 $Q \subset P$ は成り立たない。 $x = 2$ は $Q$ に属して $P$ に属さないからである。

図は、二つの条件がこの包含関係にある場合を1枚描いたものです。包含が成り立つ根拠は、 $x$ が $4$ の倍数であれば $x = 4k$ と書くことができ、 $x = 2\cdot(2k)$ より $2$ の倍数である、という議論のほうにあります。

同じ全体集合のもとで、共通部分と和集合も読み替えることができます。 $P \cap Q = P$ であり、これは「 $4$ の倍数かつ $2$ の倍数」が「 $4$ の倍数」と同じ条件であることに対応します。 $P \cup Q = Q$ であり、これは「 $4$ の倍数または $2$ の倍数」が「 $2$ の倍数」と同じ条件であることに対応します。

3 補集合は全体集合の取り方で変わる

条件の否定を補集合として読み替えるときは、全体集合が何であるかを先に決めておきます。同じ条件であっても、全体集合を変えると補集合が変わるからです。

例 3.1 (全体集合を変えると補集合が変わる). 条件 $p(x)$ ： $x^2 = 1$ を考える。

全体集合を整数全体とすると、 $P = \{-1, 1\}$ なので、 $\overline{P}$ は $-1$ と $1$ を除く整数全体である。 $0$ 、 $2$ 、 $-3$ などが $\overline{P}$ に属する。
全体集合を正の整数全体とすると、 $P = \{1\}$ なので、 $\overline{P}$ は $2$ 以上の整数全体である。 $-1$ はそもそも全体集合に属さないため、 $\overline{P}$ の要素にならない。
全体集合を $\{1\}$ とすると、 $P = \{1\}$ なので、 $\overline{P} = \varnothing$ である。このとき「 $x^2 \ne 1$ 」を満たす要素は一つも無い。

三つの場合で、条件 $x^2 = 1$ そのものは変わっていません。変わったのは、 $x$ が動く範囲としてどの集合を取るかだけです。「この条件を満たさないもの」と言うときは、何の中で満たさないのかを指定しなければ、集合が定まりません。

閑話休題：論理の、もう一つの対応先 本記事では、論理を集合へ対応させました。「かつ」は共通部分、「または」は和集合、「ならば」は包含です。では、対応先は集合だけでしょうか。実は、もう一つの対応先があります。型です。

プログラミングでは、値に「整数型」「文字列型」といった型というラベルを付けます（型は、その型が取りうる値の集合のようなものだと考えてください）。驚くべきことに、論理と型のあいだにも、集合のときと同じ対応表を引くことができます。本記事の表に、右の1列を加えます。

論理	集合（本記事）	型
かつ $P \land Q$	$P \cap Q$	直積型（ペア） $P \times Q$
または $P \lor Q$	$P \cup Q$	直和型 $P + Q$
ならば $P \Rightarrow Q$	$P \subset Q$	関数型 $P \to Q$

決定的なのは、命題を証明することができることが、その型のプログラムを書くことができることに対応するという点です。証明とプログラムが同じものの別の姿であるというこの対応を、カリー・ハワード対応と呼びます。

ここから先が興味深いところです。私たちが論理と聞いて思い浮かべるのは、一度正しいと分かった事実を何度でも使い回すことができる論理です。ところが、事実は高々一度しか使うことができない（捨てるのは自由であるが、複製はできない）という、一見すると何の役に立つのか分からない論理を考えることができます。アフィン論理です。カリー・ハワード対応によってこの論理を型の世界へ移すと、値を高々一度しか使うことができない型システム、すなわち Affine 型が現れます。

この「一度きり」という制約が、現実の場面で決定的に効きます。メモリの一区画に持ち主が一人しかいなければ、解放済みのメモリを二度使う（use-after-free）という古典的なバグが原理的に起こりません。プログラミング言語 Rust は、この考え方をもとに所有権システムを設計し⁴、メモリ安全性をガベージコレクタではなく型のレベルで保証します。型検査が通れば、その時点でメモリ安全が確保されているということです⁵。

型のレベルでメモリ安全性を保証することがどれほどのことかを考えてみます。サイバー攻撃に悪用される脆弱性のうち約7割はメモリ安全性のバグが原因であると報告されています。コンパイル時にそれを根絶することができれば、従来は取り切ることができなかった脆弱性の大半を原理的に排除することができます。使い回すことのできない事実の論理という、役に立つのかどうかも怪しい抽象理論が、世界のソフトウェアの安全性を支える土台になっています。本記事で扱った論理と集合の対応から、一続きにたどることのできる話です。

4 つまずいたら

命題（真偽が定まっている）と条件（値によって真偽が変わる）を区別してください。真理集合が意味を持つのは条件のほうです。
ド・モルガン則も、集合の言葉では $\overline{P \cap Q} = \overline{P} \cup \overline{Q}$ となり、論理の $\lnot(p \land q) \equiv \lnot p \lor \lnot q$ と一致します。一方を確かめれば、他方も同じ手順で確かめることができます。
補集合を書く前に、全体集合を決めてください。全体集合を書かずに「 $p$ でない」の真理集合を求めようとすると、答えが定まりません。

正確には、「 $x$ は整数であり、さらに $x > 3$ である」のように、 $x$ がそもそもどういう類の値であるのかを条件づける必要があります。たとえば、 $x$ の取りうる値として $\{ 5 \}$ のような集合があり得てしまうと、条件「 $\{ 5 \} > 3$ 」は真か偽かという以前に無意味になります。一方、論理学では、条件に現れる変数がどういう類の値であるのかを必ずしも指定せず、単なる記号として導入します。その代わり、有意味な文字列がどのように組み立てられるのかを明示する必要があり、論理そのものも記号の操作として定義されることになります。詳細は「数理論理・モデル理論」が扱います。 ↩
正確には、条件に含まれている変数がそもそもどういう集合の要素であるのかが明記されている必要があります。集合 $X$ が変数 $x$ の動く範囲であるならば、条件 $p(x)$ の真理集合は $\{ x \,|\, (x\in X) \land p(x)\}\subset X$ という部分集合です。 ZFC（といくつかの追加公理）を基礎とする現代数学では、分出公理スキーマによって真理集合の存在が公理化されています。詳細は「公理的集合論」が扱います。 ↩
このような補集合の説明は世間でよく見られるものですが、実際には、前の脚注のとおり、変数 $x$ がどの集合の要素であるのかが指定されていなければ、真理集合は意味を持ちません。そして補集合という概念自体も、 $P$ の外側が何であるのかが指定されなければ意味を持ちません。 $x$ の動く範囲が指定されないという暗黙さは、 $P$ の外側が何であるのかが不明瞭であるという暗黙さと対応しています。変数 $x$ が集合 $X$ の要素であることが明示されているのであれば、補集合は $X\setminus P$ のように、全体集合を明記して書くものです。なお、補集合を $X-P$ のように引き算の記号を用いて書く人もいます。大学で数学を学んだ人の中には、全体集合を明記せず $\overline{P}$ と書くことに抵抗のある人も多いでしょう。 ↩
正確には、Rust の所有権は借用や Drop を持つため、純粋な Affine 型そのものではありません。あくまでもそれをもとにした型システムです。 ↩
unsafe を使えば、この保証の外に出ることができます。安全が保証されるのは unsafe を用いない場合にかぎります。 ↩

§A3.4条件と集合の対応

1 真理集合

2 例：整数についての条件

3 補集合は全体集合の取り方で変わる

例題

演習

前提記事