離散数学入門 （集合論、ベン図） 情報システム学科 中田豊久
1～10の数字の中で、次の2つの集合を考える 集合A 集合B 10 3 2 1 6 4 4 2 8 p ∈ A pは、集合Aの要素である。 偶数 4以下 p ∈ A pは、集合Aの要素である。 集合と要素の関係 p ∈ A pは、集合Aの要素ではない。 例えば、上の集合A、Bの場合には、 6 ∈ A 6は集合Aの要素である。 4 ∈ B 4は集合Bの要素である。 7 ∈ A 7は集合Aの要素ではない。 5 ∈ B 5は集合Bの要素ではない。
集合の表し方 特別な集合 1.すべての要素を記述する。 U 普遍集合 2.要素の性質を記述する。 Ø 空集合 ひとつも要素がない集合 集合A = {1, 2, 3, 4, 5} 集合B = {2, 4, 6} U 普遍集合 対象とするすべての要素を含んでいる集合 2.要素の性質を記述する。 集合A = {x : xは偶数} 集合B = {x : xは整数, x > 0} Ø 空集合 ひとつも要素がない集合
A ∩ B A ∪ B A - B U - A = Ac 2つの集合から、新しい集合を計算する。 集合A 集合B 2 7 1 7 10 4 8 2 10 A ∩ B 積集合: 共通する要素の集合 {2, 7} A ∪ B 和集合: すべての要素を持つ集合 {1,2,4,7,8,10} A - B 補集合: AにあってBにない要素の集合 {4,8} U - A = Ac 補集合: A以外の要素の集合 普遍集合U={1～10}としたときの補集合 {1,3,5,6,9}
部分集合 集合Pの要素をすべてQが持っているときに、集合Pは集合Qの部分集合という。 集合B 集合A 集合C A = {2,4} B = {2,4,6,8,10} C = {10, 11} 2 4 6 8 10 11 Aは、Bの部分集合である。 A⊂B Cは、Bの部分集合ではない。 C⊂B 集合と集合の関係 普遍集合Uと、空集合Øの部分集合 ある集合Pについて、以下は必ず成り立つ。 Ø ⊂ P ⊂ U 空集合Øは、全ての集合の部分集合であり、かつ、 普遍集合Uは、全ての集合を部分集合とする。
ベン図 図によって、推論が妥当であるかを検証する方法 日本人 日本人 日本人 金持ち 金持ち 金持ち 共通部分がある場合 共通部分がない場合 日本人でも 金持ちでもない。 金持ち 金持ち 金持ち 日本人であり、かつ、金持ち、は居ない。 日本人ならば、金持ちでない。 金持ちならば、日本人でない。 日本人で金持ちが居る。 日本人であり、かつ、金持ちである。 日本人であるか、または、金持ちである。 共通部分がある場合 共通部分がない場合 日本人ならば、金持ちである。 すべての日本人は金持ちである。 金持ちでないならば、日本人ではない。 日本人 日本人 金持ち 金持ちではない 金持ち 日本人であり、かつ、金持ちである。 日本人ではない、かつ、金持ちである。 金持ちでない人は、日本人ではない？ => YES 片方の集合を含む場合 ベン図による推論
集合の等号 集合の定理 すべての要素が一致するときに 2つの集合は同じである。 1. 任意の集合Aに対して、 Ø⊂A⊂U 2. 任意の集合Aに対して、A⊂A 3. A⊂BかつB⊂Cならば、A⊂C 4. A=Bと、A⊂BかつB⊂Aは、同値である 集合A = {1, 2, 3, 4, 5} 集合B = {1, 2, 3, 4, 5} 集合A = 集合B 集合A = {} 集合B = {} 集合A = 集合B 集合A = {1,2,3} 集合B = {1,2} 集合A ≠ 集合B 集合A = {1,2,3} 集合B = {2,3,4} 集合A ≠ 集合B