集合と論理

そのグループに属すかが明確に判断できるものの集まりを、集合といい、集合に属する1つ1つを要素といいます。

$a$が集合$A$の要素であることを$a \in A$、そうでないことを$a \notin A$ と表します。
競技プログラミングでも結構制約で出てきますね。

$|A|$ は、集合$A$ の要素の個数を表していると認識しておきましょう。
これも競技プログラミングで結構見かけます。

$x \in A$ ならば必ず $x \in B$ であることを AはBの部分集合である といい、$A \subset B$ と表します。

$A \subset B, B \subset A$ が成り立つとき、$A$と$B$は等しく、 $A = B$ と表せます。

$A \subset B, A \ne B$ であるとき、AはBの 真部分集合 であるといえて $A \subsetneqq B$ と表します。

要素を1つももたない集合を 空集合 といい、$\varnothing$ と表します。
そして、空集合はすべての集合の部分集合です。

1~5の自然数の集合$A$を表現するには、以下の様に記します。

$A = \lbrace 1, 2, 3, 4, 5 \rbrace$ (要素をすべて書く)
$A = \lbrace n|nは自然数, 1 \leq n \leq 5 \rbrace$ (要素が満たす条件を書く)

共通部分・和集合

共通部分 : $A,B$両方に属する要素全体の集合で、 $A \cap B$ と表します。(AかつB)
和集合 : $A,B$少なくとも一方に属する要素全体の集合で、$A \cup B$ と表します。(AまたはB)

共通部分を表すベン図

和集合を表すベン図

補集合

とある集合の部分集合を考えるときの元の集合のことを 全体集合 とよび、$U$と表します。
また、$U$の要素のうち、$A$に属さない要素全体の集合を 補集合 とよび、$\overline{A}$ と表します。

このような用語が出てくる競技プログラミングの問題はある程度存在します。
https://atcoder.jp/contests/abc179/tasks/abc179_d?lang=ja

補集合の補集合は元の集合であるため、$\overline{\overline{A}} = A$ が成り立ちます。
また、$A,\overline{A}$の共通部分は空集合で、和集合は$U$です。

また、$A \subset B$ならば、$\overline{A} \supset \overline{B}$ が成り立ちます。

ド・モルガンの法則

以下の関係が成り立つことを ド・モルガンの法則 といいます。

$\overline{A \cup B} = \overline{A} \cap \overline{B}$

$\overline{A \cap B} = \overline{A} \cup \overline{B}$

この法則は集合の数が3つ以上の場合にも適用でき、1つ目の法則は$U$以外の集合に属さない部分が黒くなり、2つ目の法則はすべての集合に属す部分以外が黒くなります。

また、集合の数が3つ以上の場合、結合法則と交換法則が適用できます。
結合法則は、$(A \cap B) \cap C = A \cap (B \cap C)$
分配法則は、$A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$
が成り立ちます。($\cap$と$\cup$が逆な場合でも成り立ちます。)

命題

命題とは、真偽が明確に定まる文章や数式のことです。
命題は、反例(pならばqが成り立たない場合)が1つでも存在すれば偽です。
条件とは、変数によって真偽が変わる文章や数式のことです。
「xは正の数」という文章はxの値によって真偽が変わるので、「xに関する条件」といえます。

pならばqという命題があったとき、pをこの命題の仮定といい、qをこの命題の結論といいます。
(pならばqという命題は、$p \implies q$ と表せます。)

pならばqが真である場合、$P \subset Q$も成り立ちます。(逆も然り)

条件pの否定は$\overline{p}$ と表され、この命題の話は集合のド・モルガンの法則に当てはめることができます。

必要十分条件

命題 $p \implies q$ が真であるとき

qはpであるための 必要条件 である
pはqであるための 十分条件 である
といいます。

$p \implies q, q \implies p$ が両方成り立つとき、 $p \iff q$ と表せて、
pはqであるための 必要十分条件 であり、pとqは同値であるといえます。(逆も然り)

対偶

命題$p \implies q$ に対して、

$q \implies p$ を逆
$\overline{p} \implies \overline{q}$ を裏
$\overline{q} \implies \overline{p}$ を対偶
といいます。

元の命題と命題の対偶の 真偽は一致します。

背理法

背理法 とは、命題は偽であるという仮定をし、その矛盾を導き出すことで、元の命題を証明するという方法である。
無理数であることの証明によく用いられる。