ある条件を満たすものの集まりを「集合 (set)」といいます。集合に属しているものを「要素」または「元」といいます。要素 \(a\) が集合 \(A\) に属していることを \(a \in A\) と表示します。逆に、\(A\) の要素でないときは \(a \notin A\) と表示します。集合の表し方は、次の 2 つが代表的です。
要素の数が有限個の集合を「有限集合」といい、要素の数が無限個の集合を「無限集合」といいます。集合を扱うとき、その対象の全体を「全体集合」といい、\(U\) と表示することが一般的です。また、要素が無い集合を「空集合」といい、本ページでは \(\varnothing\) と表示することにします。\(\phi\) や \(\varphi\) で空集合を表している教科書や Web サイトもあります。
2 つの集合 \(A, \ B\) があるとき、\(A\) の要素のすべてが \(B\) に属しているとき、\(A\) は \(B\) の「部分集合 (subset)」であるといい、\(A \subset B\) または \(A \subseteqq B\) と書きます。このとき、「\(A\) は \(B\) に含まれる」または「\(B\) は \(A\) を含む」といいます。\(A \subset B\) かつ \(B \subset C\) ならば、\(A \subset C\) が成り立ちます。
\(A\) の要素がすべて \(B\) の要素であり、\(B\) の要素がすべて \(A\) の要素であるとき、つまり \(A \subseteqq B \ \land \ B \subseteqq A\) であるとき、\(A\) は \(B\) と等しいといい、\(A = B\) と書きます。ここで \(\land\) は論理積を表します。\(A \subset B \ \land \ A \ne B\) であるとき、\(A\) は \(B\) の「真部分集合」であるといいます。空集合はすべての集合の部分集合とみなします。つまり、\(\varnothing \subset A\) が成り立ちます。
全体集合 \(U\) の要素で \(A\) に含まれていないものの集合を \(A\) の「補集合」といい、\(A^c\) や \(\overline{A}\) で表します。補集合の場合、形式的に \(\overline{U} = \varnothing\), \(\overline{\varnothing} = U\) と定義します。
2 つの集合 \(A\) と \(B\) の、少なくとも一方に属している要素全体の集合を「和集合 (union set)」といい、\(A \cup B\) で表します。
2 つの集合 \(A\) と \(B\) のどちらにも属している要素全体の集合を「共通集合」または「積集合 (intersection set)」といい、\(A \cap B\) で表します。
和集合と積集合には以下の演算法則が成り立ちます。
プログラミング言語 Python には集合を表すデータ構造 Set が用意されています。Set は { ... } で生成し、和集合と積集合は演算子 |, & で計算することができます。簡単な実行例を示します。
>>> a = {1,2,3,4}
>>> b = {3,4,5,6}
>>> c = {4,6,8,10}
>>> u = {1,2,3,4,5,6,7,8,9,10}
>>> a & b
{3, 4}
>>> b & a
{3, 4}
>>> a | b
{1, 2, 3, 4, 5, 6}
>>> b | a
{1, 2, 3, 4, 5, 6}
>>> (a & b) & c
{4}
>>> a & (b & c)
{4}
>>> (a | b) | c
{1, 2, 3, 4, 5, 6, 8, 10}
>>> a | (b | c)
{1, 2, 3, 4, 5, 6, 8, 10}
>>> a | (b & c)
{1, 2, 3, 4, 6}
>>> (a | b) & (a | c)
{1, 2, 3, 4, 6}
>>> a & (b | c)
{3, 4}
>>> (a & b) | (a & c)
{3, 4}
>>> a | a
{1, 2, 3, 4}
>>> a & a
{1, 2, 3, 4}
>>> a | (a & b)
{1, 2, 3, 4}
>>> a & (a | b)
{1, 2, 3, 4}
>>> a & u
{1, 2, 3, 4}
>>> a | u
{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
>>> a & set()
set()
>>> a | set()
{1, 2, 3, 4}
補集合を求める場合、Python では差集合を使います。差集合は演算子 - で求めることができます。たとえば、a - b は a から b の要素を取り除いた集合を返します。簡単な実行例を示します。
>>> a
{1, 2, 3, 4}
>>> b
{3, 4, 5, 6}
>>> a - b
{1, 2}
>>> b - a
{5, 6}
>>> u
{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
>>> u - a
{5, 6, 7, 8, 9, 10}
>>> u - b
{1, 2, 7, 8, 9, 10}
任意の集合 \(A, B\) において、以下の式が成り立ちます。
\(A, B\) の積集合の補集合は、それぞれの集合の補集合の和集合になります。もしくは、\(A, B\) の和集合の補集合は、それぞれの集合の補集合の積集合になります。これを「ド・モルガンの法則 (公式)」といい、とても有名な公式です。「ベン図」を使うと簡単に証明できるので、興味のある方は試してみてください。ここでは Python を使って、公式が成り立つことを示します。
>>> a
{1, 2, 3, 4}
>>> b
{3, 4, 5, 6}
>>> u
{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
>>> u - (a & b)
{1, 2, 5, 6, 7, 8, 9, 10}
>>> (u - a) | (u - b)
{1, 2, 5, 6, 7, 8, 9, 10}
>>> u - (a | b)
{8, 9, 10, 7}
>>> (u - a) & (u - b)
{8, 9, 10, 7}
ところで、ド・モルガンの法則は 3 つ以上の集合についても成立します。3 つの集合の例を示します。
興味のある方はベン図や Python などで公式が成立することを確かめてみてください。
有限集合 \(A, B, C\) の要素数を \(n(A), \ n(B), \ n(C)\) とすると、以下の式が成り立ちます。
\(A \cap B \ne \varnothing\) の場合、\(A, B\) には共通要素があるので、\(n(A) + n(B)\) とするだけでは、共通要素を二重にカウントしてしまいます。そこで、共通要素の数 \(n(A \cap B)\) を引き算することで、二重にカウントした分を修正しています。
集合が 3 つあると複雑になります。\(- n(A \cap B) - n(A \cap C) - n(B \cap C)\) を計算すると、\(n(A \cap B \cap C)\) を 3 回カウントし、3 回引くことになるので、1 回余分に引いています。帳尻を合わせるため。最後に \(n(A \cap B \cap C)\) を足し算しています。
Python の場合、集合の要素数は関数 len() で求めることができます。簡単な実行例を示します。
>>> a
{1, 2, 3, 4}
>>> b
{3, 4, 5, 6}
>>> c
{8, 10, 4, 6}
>>> u
{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
>>> len(a | b)
6
>>> len(a) + len(b) - len(a & b)
6
>>> len(a | b | c)
8
>>> len(a) + len(b) + len(c) - len(a & b) - len(a & c) - len(b & c) + len(a & b & c)
8
>>> len(u - a)
6
>>> len(u) - len(a)
6
>>> len((u - a) & (u - b))
4
>>> len(u - (a | b))
4
>>> len(u) - len(a | b)
4
命題とは、その真偽が明確にわかる文や式のことです。たとえば、「ソクラテスは人間である」とか「5 - 3 = 2」などは命題になります。「3 は小さな数である」は、小さい基準が曖昧なので真偽を判定することができません。この場合、命題にはなりません。「3 は 10 より小さい」は常に正しいので命題になります。「3 は 1 より小さい」は常に誤りです。真偽を明確に判定できるので、これも命題になります。
個々の命題を「単純命題」とか「基本命題」といい、\(p, \ q, \ r\) などの文字で表すのが一般的です。命題の真偽を表す場合、真を 1 (または T)、偽を 0 (または F) などで示します。
2 つ以上の命題は「論理積」と「論理和」で連結することができます。前者を「連言命題」といい、\(p \land q\) と書きます。後者を「選言命題」といい、\(p \lor q\) と書きます。命題を否定したものを「否定命題」といい、\(\lnot p\) または \(\overline{p}\) と書きます。2 つの命題が仮定と結論の立場で連結されたもの、つまり「\(p\) ならば、\(q\) である」ことを表す命題を「条件命題」といい、\(p \implies q\) とか \(p \Rightarrow q\) と書きます。
これらの操作で作られる命題を「合成命題」と呼ぶことがあります。また、\(\land, \ \lor, \ \lnot, \ \Rightarrow\) などの記号は「論理記号」といい、論理積、論理和、否定、論理包含 (含意) と呼ばれています。
2 つの命題 \(p, \ q\) の真偽の組み合わせと、それに対応する合成命題の真偽を一覧表にしたものを「真理表」といいます。\(\land, \ \lor, \ \lnot, \ \Rightarrow\) の真理表を以下に示します。
\(p \Rightarrow q\) は \(p\) が真ならば \(q\) の結果に、\(p\) が偽ならば \(q\) の結果にかかわらず真となります。他の合成命題と比べて、条件命題は直感に反するところがあるので、ちょっと分かりにくいかもしれません。「\(p\) ならば、\(q\) である」という命題は、「\(p\) が真ならば、\(q\) の値で真偽を判定する」と考えることができます。プログラミングの視点でみると、条件命題は連言命題と一緒に使うとき便利です。次の例を見てください。
命題 \(r\) は 5 つの命題を連言でつないでいるので、すべての命題が真のとき、\(r\) は真になります。3 番目の条件命題は、\(p_3\) が真で \(q_3\) が偽のとき偽になるので、命題 \(r\) は偽になります。\(q_3\) が真のときは真になるので、次の命題へ進みます。
\(p_3\) が偽の場合、条件を満たしていないので、\(q_3\) の真偽を判定する必要はありません。\(p_3 \Rightarrow q_3\) は真を返すので、次の命題に進むことができます。ここで、論理積 \(p_3 \land q_3\) を使うと、\(p_3 \land q_3\) は偽になるので、命題 \(r\) が偽になってしまいます。このように、\(p_3\) が偽のとき、\(q_3\) を真偽を判定せずに次の命題に進みたい場合、条件命題が適しています。
論理包含のより詳しい説明は 論理包含 - Wikipedia をお読みくださいませ。
命題を \(p, \ q, \ r\) で表すと、以下の法則が成り立ちます。
これらの法則は真理表を作成すると証明することができます。
命題にもド・モルガンの法則があります。
命題 \(p, q\) の論理積の否定は、それぞれの命題の否定の論理和になります。もしくは、命題 \(p, q\) の論理和の否定は、それぞれの命題の否定の論理積になります。これも真理表を作成すると簡単に証明することができます。
ある命題 \(p \Rightarrow q\) に対して、以下の命題を考えることができます。
各命題の真理表を以下に示します。
命題 \(p \Rightarrow q\) が真ならば、対偶 \(\overline{q} \Rightarrow \overline{p}\) も真になりますが、逆と裏は必ずしも真にはなりません。\(p \Rightarrow q = 1\) であるとき、\(p\) を \(q\) であるための「十分条件」といい、\(q\) を \(p\) であるための「必要条件」といいます。\((p \Rightarrow q) \land (q \Rightarrow p) = 1\) のとき、\(p\) と \(q\) は「同値 (equivalence)」であるといい、\(p\) と \(q\) は互いに「必要十分条件」になります。
同値の論理記号は \(\iff\) や \(\Leftrightarrow\) で表されます。真理表は以下のようになります。
同値は \(p\) と \(q\) が同じ値 (0 と 0 または 1 と 1) のとき真となります。同値は「if and only if」を略して iff と表記されることもあります。詳しい説明は 同値 - Wikipedia をお読みくださいませ。