論理と命題
ここでは初歩的な集合論を説明するために必要な論理と命題を扱う。ただし数理論理学のような厳密な形では扱わない。
命題と真偽表
数学的な主張で正しいか正しくないか、いずれか一方だけ成立するものを命題という。 正しいときはその命題は真であるといい、正しくないときはその命題は偽であるという。 以下、命題 $P$、$Q$ が与えれられたとする。このとき次のような「命題を結合する演算」を考える。
| 論理式 | 読み方 | 意味 |
|---|---|---|
| $\lnot P$ | $P$ ではない | $P$ の真偽を逆にする |
| $P \land Q$ | $P$ かつ $Q$ | $P$ と $Q$ がともに真のときのみ真。それ以外は偽 |
| $P \lor Q$ | $P$ または $Q$ | $P$ か $Q$ が少なくとも一方が真のとき真。それ以外（両方偽のとき）は偽 |
| $P \Rightarrow Q$ | $P$ ならば $Q$ | $P$ が真でありかつ $Q$ が偽のときのみ偽。それ以外は真 |
$P \Rightarrow Q$のとき $P$ は $Q$ の十分条件といい、 $Q$ は $P$ の必要条件という。上記の定義で次の2点に注意せよ。
- 日常の言葉では「または」というとどちらか一方のみという意味でとられがちであるが、論理的には$P \lor Q$ は真であるとき $P$、$Q$ がともに真であってもよい。
- $P$ が偽ならば $Q$ の真偽にかかわらず $P \Rightarrow Q$ は真。（仮定を満たさなければすべて真）
命題の真偽は次のように $P$、$Q$ の真偽に応じて、それらを使って得られた命題の真偽をまとめた真偽表を作成するとわかりやすい。ここでは〇を真、×を偽の意味で略記している。
| $P$ | $Q$ | $\lnot P$ | $P \land Q$ | $P \lor Q$ | $P \Rightarrow Q$ |
|---|---|---|---|---|---|
| 〇 | 〇 | × | 〇 | 〇 | 〇 |
| 〇 | × | × | × | 〇 | × |
| × | 〇 | 〇 | × | 〇 | 〇 |
| × | × | 〇 | × | × | 〇 |
$P$、$Q$ に対して $(P \Rightarrow Q ) \land ( Q \Rightarrow P$) （ つまり「 $P$ ならば $Q$ 」かつ「 $Q$ ならば $P$ 」）
を $P \Leftrightarrow Q$ と略記し、 $P$ と $Q$ は必要十分条件であるとか同値であるという。次のように真偽表を書くとわかるように、 $P \Leftrightarrow Q$ は「 $P$ と $Q$ の真偽が一致しているとき真になり、そうでないとき偽」となる。
| $P$ | $Q$ | $P \Rightarrow Q$ | $Q \Rightarrow P$ | $P \Leftrightarrow Q$ |
|---|---|---|---|---|
| 〇 | 〇 | 〇 | 〇 | 〇 |
| 〇 | × | × | 〇 | × |
| × | 〇 | 〇 | × | × |
| × | × | 〇 | 〇 | 〇 |
具体例
- 具体的に存在する $A$ 君に対して、「 $A$ 君は身長170cm以上である」は命題である。しかし「 $A$ 君は背が高い」は「高い」の定義があいまいで真偽を確定できないので命題ではない。
- 「平面上の直角三角形において斜辺の長さの2乗は、残りの2辺の長さの2乗和と等しい」真の命題である。
- 「 $1+1=3$ である」は通常の数の範囲では偽の命題である。
基本的な結果
以下、基本的な結果を列挙する。これらの結果は証明の基礎であったり、集合の最も基本的な性質の基礎になっている。証明は真偽表を書けば容易にわかる。 $P,Q,R$は命題とする。このとき、 $P,Q,R$ の真偽にかかわらず次の命題はすべて真。
- $ P \land Q \Leftrightarrow Q \land P$
- $ P \lor Q \Leftrightarrow Q \lor P$
これにより「 $X$ を集合、$A,B$ を $X$ の部分集合としたとき、$A \cap B = B \cap A$ 」等を証明することができる。 実際、$x \in A \cap B \Leftrightarrow $「$(x \in A) \land (x \in B)$」$\Leftrightarrow$ 「 $(x \in B) \land (x \in A)$ 」$\Leftrightarrow x \in B \cap A$
- $\lnot ( \lnot P) \Leftrightarrow P$
- $P \lor \lnot P$ は $P$ の真偽によらず常に真（排中律）
排中律が常に成り立つことが背理法の根拠になっている。
- $(P \Rightarrow Q) \Leftrightarrow (\lnot Q \Rightarrow \lnot P )$ （対偶）
与えられた命題を証明するために、その命題の対偶を示すのも基本的な方法である。
- $ P \lor ( Q \land R ) \Leftrightarrow ( (P \lor Q ) \land (P \lor R))$
- $ P \land ( Q \lor R ) \Leftrightarrow ( (P \land Q ) \lor (P \land R))$
- $ \lnot (P \land Q) \Leftrightarrow (\lnot P \lor \lnot Q)$~
$ \lnot (P \lor Q) \Leftrightarrow (\lnot P \land \lnot Q)$ （De Morgan の定理）
集合論の初歩
論理と命題 / 集合の基本的な用語、集合の演算 / 全称記号と存在記号 / 写像、像、逆像、写像のグラフ / 写像の合成、写像の拡大と制限 / 選択公理について / 単射、全射、全単射、逆写像 / 部分集合族、べき集合 / （ 演算と代数構造 ） / （ 関係、同値関係、商集合 ） / （ 初歩的な順序集合 ） / （ Zornの補題 ） / （ 集合の濃度 ）
