集合と論理
集合の記号
$A$，$B$ を集合とする．
- $a\in A\,\,\cdots$ $a$ は $A$ の要素， $b\notin A\,\,\cdots$ $b$ は $A$ の要素ではない
- $A\subset B\,\,\cdots$ $A$ は $B$ の部分集合 $\Longleftrightarrow$ 「$x\in A$ ならば $x\in B$」
- $A=B\,\,\cdots$ $A$ と $B$ は等しい $\Longleftrightarrow$ 「$A\subset B$ かつ $B\subset A$」
- $A$ は $B$ の真部分集合 $\Longleftrightarrow$ 「$A\subset B$かつ$A\neq B$」
- 空集合 $\phi\,\,\cdots$ 要素をもたない集合
空集合は任意の集合の部分集合となる． - $A\cap B=\{x\mid\text{$x\in A$ かつ $x\in B$}\}$ $\cdots$ $A$ と $B$ の共通部分
- $A\cup B=\{x\mid\text{$x\in A$ または $x\in B$}\}$ $\cdots$ $A$ と $B$ の和集合
集合の演算
$A$，$B$，$C$ を集合とする．
- 交換法則 $\cdots$ $A\cap B=B\cap A$，$A\cup B=B\cup A$
- 結合法則 $\cdots$ $(A\cap B)\cap C=A\cap(B\cap C)=A\cap B\cap C$，
$(A\cup B)\cup C=A\cup(B\cup C)=A\cup B\cup C$ - 分配法則 $\cdots$ $A\cap(B\cup C)=(A\cap B)\cup(A\cap C)$，
$A\cup(B\cap C)=(A\cup B)\cap(A\cup C)$
補集合の性質
$U$ を全体集合，$A$，$B$，$C$ を $U$ の部分集合とする．
- $\overline{A}=\{x\mid x\in U$ かつ $x\notin A\}\,\,\cdots\,\,A$ の補集合
- $\overline{(\overline{A})}=A$
- $A\cap\overline{A}=\phi$
- $A\cup\overline{A}=U$
- $A\subset B\,\,\Longleftrightarrow\,\,\overline{B}\subset\overline{A}$
- $\overline{A\cap B}=\overline{A}\cup\overline{B}$，$\overline{A\cup B}=\overline{A}\cap\overline{B}$（ド・モルガンの法則）
- $\overline{A\cap B\cap C}=\overline{A}\cup\overline{B}\cup\overline{C}$，$\overline{A\cup B\cup C}=\overline{A}\cap\overline{B}\cap\overline{C}$
要素の個数
有限集合 $A$ の要素の個数を $n(A)$ で表す．
- $A$ が有限集合 $U$ の部分集合のとき，$n(\overline{A})=n(U)-n(A)$
- $A$，$B$，$C$ が有限集合のとき，
$n(A\cup B)=n(A)+n(B)-n(A\cap B)$，
$n(A\cup B\cup C)=n(A)+n(B)+n(C)$
$-n(A\cap B)-n(B\cap C)-n(C\cap A)$ $+\,\,n(A\cap B\cap C)$
部分集合の総数
有限集合 $A$ に対し，$A$ の部分集合は，$A$ 自身と空集合を含めて，全部で $2^{n(A)}$ 個ある．
必要条件・十分条件
$p$，$q$ を条件とする．
- 「 $p\,\Rightarrow\,q$ 」が真であるとき，$q$ は $p$ であるための必要条件
$p$ は $q$ であるための十分条件という． - 「 $p\,\Rightarrow\,q$ 」と「 $q\,\Rightarrow\,p$ 」がともに真であるとき，
$p$ は $q$ であるための必要十分条件であるといい，「 $p\,\Longleftrightarrow\,q$ 」と表す．
逆・裏・対偶
$p$，$q$ を条件とする．$p$ の否定を $\overline{p}$ と表す．
命題「 $p\,\Rightarrow\,q$ 」に対し，
「 $q\,\Rightarrow\,p$ 」をもとの命題の逆，
「 $\overline{p}\,\Rightarrow\,\overline{q}$ 」をもとの命題の裏，
「 $\overline{q}\,\Rightarrow\,\overline{p}$ 」をもとの命題の対偶という．
一般に，命題とその対偶の真偽は一致する．
命題「 $p\,\Rightarrow\,q$ 」に対し，
「 $q\,\Rightarrow\,p$ 」をもとの命題の逆，
「 $\overline{p}\,\Rightarrow\,\overline{q}$ 」をもとの命題の裏，
「 $\overline{q}\,\Rightarrow\,\overline{p}$ 」をもとの命題の対偶という．
一般に，命題とその対偶の真偽は一致する．
| $\boxed{\,\,p\Rightarrow q\,\,\vphantom{\big(}}$ | $\leftarrow$ | 逆 | $\rightarrow$ | $\boxed{\,\,q\Rightarrow p\,\,\vphantom{\big(}}$ |
| $\uparrow$ | $\nwarrow$ | $\nearrow$ | $\uparrow$ | |
| 裏 | 対偶 | 裏 | ||
| $\downarrow$ | $\swarrow$ | $\searrow$ | $\downarrow$ | |
| $\boxed{\,\,\overline{p}\Rightarrow\overline{q}\,\,\vphantom{\big(}}$ | $\leftarrow$ | 逆 | $\rightarrow$ | $\boxed{\,\,\overline{q}\Rightarrow\overline{p}\,\,\vphantom{\big(}}$ |
否定
$p$，$q$ を条件とする．
- 「 $p$ かつ $q$ 」の否定 $\longrightarrow$ 「 $\overline{p}$ または $\overline{q}$ 」
- 「 $p$ または $q$ 」の否定 $\longrightarrow$ 「 $\overline{p}$ かつ $\overline{q}$ 」
- 「すべての $x$ に対し $p$ である」の否定 $\longrightarrow$ 「$\overline{p}$ を満たす $x$ が存在する」
- 「$p$ を満たす $x$ が存在する」の否定 $\longrightarrow$ 「すべての $x$ に対し $\overline{p}$ である」
真理集合
全体集合 $U$ に属する $x$ に関する条件 $p(x)$ に対し，$p(x)$ が真となるような $x\in U$ 全体の集合を $p(x)$ の真理集合という．
条件 $p$，$q$ の真理集合をそれぞれ $P$，$Q$ とする．
条件 $p$，$q$ の真理集合をそれぞれ $P$，$Q$ とする．
- 「 $p\,\Rightarrow\,q$ が真」 $\Longleftrightarrow$ 「 $P\subset Q$ 」
- 否定 $\overline{p}$ の真理集合は補集合 $\overline{P}$
- 「 $p$ かつ $q$ 」の真理集合は $P\cap Q$
- 「 $p$ または $q$ 」の真理集合は $P\cup Q$
いろいろな証明
| 背理法 $\cdots$ | 「 $p\,\Rightarrow\,q$ 」を証明するのに，「 $p$ かつ $\overline{q}$ 」と仮定して矛盾を導くことにより，「$p\,\Rightarrow\,q$」を証明する方法 |
| 対偶法 $\cdots$ | 「 $p\,\Rightarrow\,q$ 」を証明するのに，対偶「 $\overline{q}\,\Rightarrow\,\overline{p}$ 」を示すことにより，「 $p\,\Rightarrow\,q$ 」を証明する方法（命題とその対偶の真偽は一致する） |