离散数学之集合论(2)

n n

Si ，i∈J={i| i是二进制数， ≤ i ≤ }

如果A6 {x1,x2,x3,x4,x5,x6}，P (A 6)的26个元素记为 S0,S1, ,S26 1，此时S

的下标是十进制整数，如何求出S7,S12是A 6的那些元素组成的子集呢？将下标转换为二进制的整数，不足六位的在左边补入需要个数的零，使之成为六位的二进制整数，由排列的六位二进制整数推断出，含有那些元素。凡第i位为0，表示x i不在此子集中，凡第i位为1表示x i在此子集中，故

这种方法可以推广到一般情况，B7 B111 B000111 {x4,x5,x6}，B12 B001100 {x3,x4}。

即将十进制整数转换为二进制整数，在左边补入需要个数的零使之成为n位的二进制数，若第i位为0，表示x i不在此子集中，若第i位为1表示x i在此子集中。

子集的这种编码法，不仅给出了一个子集含那些元素的判别方法，还可以用计算机表示集合、存贮集合以供使用。

§2-1-2 集合的基本运算

集合的运算，就是以集合为对象，按照确定的规则得到另外一些新集合的过程。给定集合A，B，可以通过集合的并（∪）、交（∩）、相对补（－）、绝对补（¯）和对称差（⊕）等运算产生新的集合。

一、集合并（∪）运算

定义2-1-2.1 设A ，B为任意两集合，所有属于集合A或属于集合B的元素组成

离散数学四大核心：代数系统、集合论、数理逻辑、图论。

的集合，称为集合A和B的并集。记作 A∪B

A B {x(x A) (x B)}

并集的文氏（英国数学家Johan Wenn (1834~1883)）图

例2-1-2.1 设A = {1 , 2 , 3 , 4 }，B = {2 , 4 , 5 , 6 }

则 A∪B = {1 , 2 , 3 , 4 , 5 , 6 }。注意：集合是由互不相同元素组成的，在A∪B中2，4各写一次，不能重写。

由集合并运算的定义知，并运算具有如下性质：

定理2-1-2.1 设A，B，C为任意三个集合，则

⑴ 幂等律 A∪A=A；

⑵ 交换律 A∪B = B∪A；

⑶ 结合律 (A∪B)∪C = A∪(B∪C)；

⑷ 同一律 A∪Φ= A；

⑸ 零 律 A∪E = E；

⑹ A A∪B，B A∪B；

⑺ A∪B = B A B。

证明：性质⑴，⑵，⑷，⑸，⑹由定义2-1-2.1立即可以得到。

⑶的证明

(A∪B)∪C ＝ {x | x∈(A∪B)∪C } = { x | (x∈A∪B)∨(x∈B) }

＝ { x | ((x∈A)∨(x∈B))∨(x∈B)}={ x|(x∈A)∨((x∈B)∨(x∈C))}

= { x |( x∈A)∨(x∈B∪C)} = { x | x∈A∪(B∪C)} = A∪(B∪C) 。

⑺的证明：必要性证明 x(x A) x(x A B) x(x B) 所以 A B。 充分性证明 由⑹知B A∪B，现证明 A∪B B

x(x A B) x(x B)

所以有 A∪B = B。

例2-1-2.2 设 A B，C D，则 A∪C B∪D

证明： A C {xx A C} {x(x A) (x C)}A B,C DA BA B B {x(x B) (x D)} ＝{xx B D} B D 即 A∪C B∪D成立。

离散数学四大核心：代数系统、集合论、数理逻辑、图论。

同理可证 A B A C B C。

因为集合的并运算满足结合律，对n个集合A1 , A2 , , A n 的并集A1 A2 An定义为至少属于A1 , A2 , , A n之一的那些元素构成的集合。A1 A2 An通常缩写成 Ai。

i 1n

A1 A2 An An {x n N,x An}其中N是自然数集合。 n 1

一般地， Ak {x k I,x Ak}。

k I

集合的并运算，就是把给定集的那些元素放到一起合并成一个集合，在这个合并中相同的元素只要一个。如设A1 {1,2,3},A2 {3,8},A3 {2,3,6}则 A

i 13i {1,2,3,6,8}。

二、集合的交（∩）运算

定义2-1-2.2 设任意两个集合A 和B，由集合A和B共

同元素组成的集合，称为集合A和B的交集，记作 A∩B。

A B {x(x A) (x B)}。

交集的文图

例2-1-2.3 设A {a,b,c,d,e},B {a,c,e,f} 则 A B {a,c,e}。

例2-1-2.4 设A = {X高等学校的本科学生}，B = {X高等学校计算机专业的学生}，则

A∩B = {X高等学校计算机专业的本科学生}

例2-1-2.5 设A是所有能被k整除的整数集合，B是所有能被l 整除的整数集合，则A∩B是所有能被k与l最小公倍数整除的整数集合。

由集合交运算的定义知，集合交运算具有如下性质：

定理2-1-2. 2 设A , B , C是任意三个集合，则

(1) 幂等律 A∩A = A ；

(2) 交换律 A∩B = B∩A ；

(3) 结合律 (A∩B)∩C = A∩(B∩C) ；

离散数学四大核心：代数系统、集合论、数理逻辑、图论。

(4) 零 律 Φ∩A = Φ；

(5) 同一律 E∩A = A ；

(6) A∩B A , A∩B B ；

(7) A∩B = A A B。

证明：根据定义2-1-2.2，性质(1) , (2) , (4) , (5) , (6)立即可以得到。

性质（3）的证明：

(A∩B)∩C = { x | x∈(A∩B)∩C } = { x|(x∈A∩B)∧(x∈C)}

= {x|((x∈A)∧(x∈B))∧(x∈C)} = {x | (x∈A)∧((x∈B)∧(x∈C)}

= {x|(x∈A)∧(x∈B∩C)} = {x | x∈A∩(B∩C)} = A∩(B∩C)

性质（7）的证明：

x(x A) x(x A B) x(x B) 即得A∩B = A A B 必要性的证明：A B A

充分性得证明：由性质（6）知A∩B A , 现证 A A∩B

采用逻辑演绎推理法

(1) x(x A) P(附加前提)

（2） a A US(1)

(3) A B P

(4) x((x A) (x B)) T(3)E

(5) (a A) (a B) US(4)

(6) a B T(2 , 5) I

(7) (a A) (a B) T(2 , 6) I

(8) x((x A) (x B)) UG(7)

(9) x(x A B) T(8)E

（10） A A∩B CP

若集合A , B没有共同的元素，则可记为A∩B = Φ,这时称A , B不相交。

由集合的交运算具有结合律，同样可以定义n个集合A 1 , A 2 , , A n的交集，也可以定义集序列A 1 , A 2 , , A n , 的交集，分别记为

离散数学四大核心：代数系统、集合论、数理逻辑、图论。

A1 A2 An Ai {xi {1,2, ,n},x Ai}

i 1n

A1 A2 An An {xn {1,2, ,n, },x An}

n 1

一般地，集合族{A k}k∈I 中各集的交记成 A

k Ik其定义为

A

k Ik {x l I,x Al}。

若序列A 1 , A 2 , , A n , 任意两集合A i , A j (i j) 不相交，则称

A 1 , A 2 , , A n , 是两两不相交的集序列。

三、交运算与并运算之间的联系

定理2-1-2.3 （分配律） 设A , B , C为任意三个集合，则

（1）交运算对并运算的分配律

A (B C) (A B) (A C)

（2）并运算对交运算的分配律

A (B C) (A B) (A C)

证明：（1）A∩(B∪C) = {x |x∈A∩(B∪C)} = {x |(x∈A)∧(x∈B∪C)}

= {x |(x∈A)∧(（x∈B）∨(x∈C))}

= { x |(( x∈A)∧(x∈B))∨((x∈A)∧(x∈C))}

= {x |(x∈A∩B)∨(x∈A∩C)}

= {x |x∈(A∩B)∪(A∩C)} = (A∩B)∪(A∩C)

当然可以仿照（1）的证明方法证明（2）的成立，现在采用（1）来证明（2），注意到 A A∪B，A∩C A，由（1）可得

(A∪B)∩(A∪C) =( (A∪B)∩A)∪((A∪B)∩C) = A∪(A∩C)∪(B∩C) = A∪(B∩C) 。 同理可以利用（2）证得（1）成立（读者自行完成），于是（1）成立 （2）的成立。

定理2-1-2.4 （吸收律）设A , B为任意两 …… 此处隐藏：3334字，全部文档内容请下载后查看。喜欢就下载吧 ……