離散数学入門

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

Download Report