数学勉強会：2017-02-09 集合と命題

ただいま社内でこちらの本を使って数学勉強会を開催中。

論理と集合から始める数学の基礎

振り返りを兼ねて、内容を記録しておきます。 ものすごく端折って書くので、きちんと勉強する方は上記の書籍や自分がわかりやすい書籍を購入するなどして学ぶことをオススメします。

集合

「集合(Set)」は要素の集まり。 $\{1\}$ や $\{1,3,5,\dots\}$ のように要素を列挙して表現する方法を外延的記法、 $\{x \mid 1 < x <5\}$ のように要素の満たす条件で表現する方法を内包的記法という。

内包的記法はリスト内包表記として使用可能なプログラミング言語もあり、例えば Pythonのリスト内包表記やHaskellのリスト内包表記がある。

ある要素 $a$ が集合 $A$ に含まれることを $a \in A$ と書く。

$\{x \mid 1 < x <5\}$ のように $x$ がそもそも自然数なのか実数なのか明らかになっていないと齟齬が発生するので、通常は $\{x \mid 1 < x <5, x \in \mathbb{N} \}$ と書いたり、「$\mathbb{N}$ を普遍集合とする」として前提となる集合を述べる。普遍集合は $U$ で表現されることが多い。 ここで、よく使われる集合を表す記号として次のようなものがある。

$\mathbb{N}$ : 自然数(natural number) 、 $\mathbb{Z}$ : 整数(integer, ドイツ語のZahlenから)、$\mathbb{R}$ : 実数(real number)

２つの集合 $A,B$ について $A$ に含まれる要素が全て $B$ にも含まれているとき「 $A$ は $B$ に含まれる ($A \subset B$) 」といい、 $A \subset B$ と $B \subset A$ が同時に成立するとき「 $A$ と $B$ は同じ集合 ($A=B$) 」とみなされる。 このとき、順序や同じ要素の重複は考慮しない。 例えば、 $\{3,2,1\}$ や $\{1,2,3,2,1\}$ という集合は $\{1,2,3\}$ と同じ集合である。

集合の演算

$A \cup B$ : 和集合。 $x \in A \cup B$ であるとは、 $x \in A$ または $x \in B$ であること。集合 $A,B$ を足し合わせたもの。和に対して積を連想するが、またそれは後ほど直積として。

$A \cap B$ : 共通部分。 $x \in A \cap B$ であるとは、 $x \in A$ かつ $x \in B$ であること。集合 $A,B$ の共通した部分。

空集合 $\emptyset$ は要素を持たない集合のこと。 $A \cup \emptyset = A$ であるし、 $A \cap \emptyset = \emptyset$ となる。

定義から明らかに任意の集合 $A, B \subset U$ について、$\emptyset \subset A \cap B \subset A \subset A \cup B \subset U$ となる。

命題

「命題(proposition)」とは真偽を判定できる文のことで、「リンゴは赤い」や「 $1+1=3$ 」などは命題であるが、 「リンゴの色」や「 $x = 1$ 」 などは命題ではない。

命題 $p, q$ において、以下の演算を定める。

• $p \land q$ : 「$p$ かつ $q$」。 $p$ と $q$ がどちらも真であるとき真。それ以外の場合は偽。
• $p \lor q$ : 「$p$ または $q$」。 $p$ が真、あるいは $q$ が真であれば真。どちらも偽の場合のみ偽。
• $\lnot p$ : 否定。 $p$ が真のとき偽、偽のときは真となる。

真を $T$ (True)、偽を $F$ (False)と書き、 $p, q$ の真偽の組み合わせについて演算結果を列挙した以下の表を真理値表という。

$p$	$q$	$p \land q$	$p \lor q$
$T$	$T$	$T$	$T$
$T$	$F$	$F$	$T$
$F$	$T$	$F$	$T$
$F$	$F$	$F$	$F$

$p$	$\lnot q$
$T$	$F$
$F$	$T$

プログラミングでは真偽値(Bool, Boolean) やビット演算で馴染みが深い人も居ると思う。 例えば排他的論理和(XOR)は $(p \lor q) \land (\lnot p \lor \lnot q)$ などのようになる。

$p \rightarrow q$ を含意(implication)といい以下の真理値表で定義される。

$p$	$q$	$p \rightarrow q$
$T$	$T$	$T$
$T$	$F$	$F$
$F$	$T$	$T$
$F$	$F$	$T$

「$p$ ならば $q$」というとき、文章的には $p$ が真である場合のみ考慮しているが、 $p$ が偽のときは $q$ の真偽に関わらず命題が成立しているものとする。

上記の真理値表は $\lnot (p \land \lnot q)$ とも一致するためこれを $p \rightarrow q$ の定義としても良い。

命題 $p \rightarrow q$ に対し、 $q \rightarrow p$ を逆、 $\lnot p \rightarrow \lnot q$ を裏、 $\lnot q \rightarrow \lnot p$ （裏の逆）を対偶という。

命題 $p, q$ について $p \rightarrow q$ と $q \rightarrow p$ が同時に成り立つとき、 $p \leftrightarrow q$ と書き「 $p$ と $q$ は論理同値」であるという。