第二篇集合与关系
集合论是现代各科数学的基础，它是德国数学家康托（Geog Cantor, 1845～1918）于1874年创立的，1876～1883年康托一系列有关集合论的文章，对任意元的集合进行了深入的探讨，提出了关于基数、序数和良序集等理论，奠定了集合论深厚的基础，19世纪90年代后逐渐为数学家们采用，成为分析数学、代数和几何的有力工具。
随着集合论的发展，以及它与数学哲学密切联系所作的讨论，在1900年前后出现了各种悖论，使集合的发展一度陷入僵滞的局面。1904～1908年，策墨罗（Zermelo）列出了第一个集合论的公理系统，它的公理，使数学哲学中产生的一些矛盾基本上得到了统一，在此基础上以后就逐渐形成了公理化集合论和抽象集合论，使该学科成为在数学中发展最为迅速的一个分支。
现在，集合论已经成为内容充实、实用广泛的一门学科，在近代数学中占据重要地位，它的观点已渗透到古典分析、泛函、概率、函数论、信息论、排队论等现代数学各个分支，正在影响着整个数学科学。集合论在计算机科学中也具有十分广泛的应用，计算机科学领域中的大多数基本概念和理论几乎均采用集合论的有关术语来描述和论证，成为计算机科学工作者必不可少的基础知识。集合论可作为数学学科的通用语言，一切必要的数据结构都可以利用集合这个原始数据结构而构造出来，计算机科学家或许也可以利用这种方法。
本篇介绍集合论的基础知识，主要内容包括集合及其运算、性质、序偶、关系、映射、函数、基数等。
第2-1章集合及其运算
§2-1-1 集合的概念及其表示
一、集合的概念
“集合”是集合论中的一个原始的概念，因此它不能被精确地定义出来。一般地说，把具有某种共同性质的许多事物，汇集成一个整体，就形成一个集合。构成这个集合的每一个事物称为这个集合的一个成员（或一个元素），构成集合的这些成员可以是具体东西，也可以是抽象东西。例如：教室内的桌椅；图书馆的藏书；全国的高等学校；自然数的全体；程序设计语言C的基本字符的全体等均分别构成一个集合。通常用大写的英文字母表示集合的名称；用小写的英文字母表示元素。若元素a属于集合A记作
A a ∈，读作“a 属于A ”。否则，若a 不属于A ，就记为A a ?，读作“a 不属于A ”。一个集合，若其组成集合的元素个数是有限的，则称作“有限集”，否则就称作“无限集”。
集合的表示方法有两种：一种是列举法又称穷举法，它是将集合中的元素全部列出来，元素之间用逗号“，”隔开，并用花括号“{ }”在两边括起来，表示这些元素构成整体。
例2-1-1.1 A ＝｛a , b , c , d ｝； B ＝｛1 ，2 ，3 ，…｝ ；
D ＝｛桌子，台灯，钢笔，计算机，扫描仪，打印机｝；},,,{32 a a a
E =。 集合的另一种表示方法叫做谓词法又叫叙述法，它是利用一项规则，概括集合中元素的属性，以便决定某一事物是否属于该集合的方法。设x 为某类对象的一般表示，)(x P 为关于x 的一个命题，我们用})({x P x 表示“使)(x P 成立的对象x 所组成的集合”，其中竖线“|”前写的是对象的一般表示，右边写出对象应满足（具有）的属性。
例2-1-1.2 全体正奇数集合表示为 }{1是正奇数x x S =，
所有偶自然数集合可表示为 }2{N m m m E ∈=且 其中 2|m 表示2能整除m 。
[0,1]上的所有连续函数集合表示为 }]10[)()({]1,0[上连续，在x f x f C =
集合的元素也可以是集合。例如}}{,,}2,1{,{q p a S =，
但必须注意：}{q q ∈，而S q ?，同理}2,1{1∈，S ∈}2,1{，而S ?1。
两个集合相等是按下述原理定义的。外延性原理：两个集合相等，当且仅当两个集合有相同的元素。两个集合A ，B 相等，记作B A =，两个集合不相等，记作B A ≠。
集合中的元素是无次序的，集合中的元素也是彼此不相同的。
例如： },4,2,2,1{}4,2,1{},2,4,1{}4,2,1{==
}{},5,3,1{},4,2,1{}4}2,1{{是正奇数，x x =≠ 。
集合中元素可以是任何事物（如例2-1-1.1）。不含任何元素的集合称为空集，记为Φ。例如，方程 012=+x 的实根的集合是空集。
二、集合与集合间的关系 S a {q } {1，2} p
1 2 q
“集合”、“元素”、元素与集合间的“属于”关系是三个没有精确定义的原始概念，对它们仅给出了直观的描述，以说明它们各自的含义。现利用这三个概念定义集合间的相等关系，集合的包含关系，集合的子集和幂集等概念。
定义2-1-1.1设A，B是任意两个集合，如果A中的每一个元素都是B的元素，则称A是B的子集，或A包含于B内，或B包含A。记作B
B?。
A?，或A
即)
→
∈
?
A∈
?
?
(B
x
A
x
x
B
可等价地表示为)
A?
→
?
?
?
?。
x
B
x
(A
x
B
例2-1-1.3设N为自然数集合，Q为一切有理数组成的集合。R为全体实数集合，C为全体复数集合，则C
?
N?
?，
Q
R
{
,
}1{π。
,2
,
}9.9,2.1,1{
Q
N?
R
?}
?
如果A不是B的子集，则记为B
A?（读作A不包含在B内），显然，
B
A?
∧
∈
?
?
?。
A
))
x
(
)
x
x
((B
集合间的包含关系“?”具有下述性质：
A?；
2-1-1. 自反性A
2. 传递性)
A?
B
B
?
?。
∧
?
(C
)
(
(
)
A
C
证明：采用逻辑演绎的方法证明。
A?P
⑴B
⑵))
x∈
→
x
?T(1)E
∈
A
(
)
x
((B
⑶)
a∈
→
∈US(2)
A
(
)
(B
a
B?P
⑷C
⑸))
x∈
x
∈
?T(4)E
→
B
(
)
((C
x
⑹)
a∈
→
∈US(5)
B
a
)
(C
(
⑺)
A
a∈
→
∈T(3)(6)I
a
(C
(
)
⑻))
→
x∈
?UG(8)
x
∈
x
(
A
)
((C
A?T(8)E
⑼C
定义2-1-1.2 如果集合A 的每一元素都属于集合B ，而集合B 中至少有一元素不属于A ，则称A 为B 的真子集，记作B A ?。
即 ))()(())()((A x B x x B x A x x B A ?∧∈?∧∈→∈???
例如：},{b a 是},,{c b a 的真子集；N 是Q 的真子集，Q 是R 的真子集；R 是C 的真子集。
注意符号“∈”和“?”在概念上的区别，“∈”表示元素与集合间的“属于”关系，“?”表示集合间的“包含”关系。
定理2-1-1.1 集合A ＝B 的充分必要条件是：B A ?且A B ?。（外延性原则） 证明：必要性， 即证：)()(A B B A B A ?∧??=
)()()))()((()))()(((A B B A A x B x x B x A x x B A ?∧??∈→∈?∧∈→∈??= 充分性，即证：B A A B B A =??∧?)()(
F B A B A B A B x A x x B A ??∧????∧∈??≠∴)()())()((
或 F A B A B A B A x B x x B A ??∧????∧∈??≠∴)()())()(( # 定理2-1-1.2 对于任一集合A ，A ?Φ，且空集是唯一的。
证明： 假设A ?Φ为假，则至少存在一个元素x ，使Φ∈x 且A x ?，因为空集Φ不包含任何元素，所以这是不可能的。
设Φ'与Φ都是空集，由上述可知，Φ?Φ'且Φ'?Φ，根据定理2-1-1.1知Φ=Φ'，所以，空集是唯一的。
注意：}{Φ≠Φ，})()({x P x P x ?∧=Φ P(x )是任一谓词。
例2-1-1.4 设 B A },3,2{=为方程 0652=+-x x 的根组成的集合，则 A ＝B 。
定理2-1-1.1指出了一个重要原则：要证明两个集合相等，即要证明每一个集合中的任一元素均是另一集合的元素。这种证明是靠逻辑推理理论，而不是靠直观。证明两个集合相等是应该掌握的方法。
定义2-1-1.3 在一定范围内，如果所有集合均为某一集合的子集，则称该集合为全
集，记作E 。对于任一A x ∈，因E A ?，所以E x ∈，
也即 )(E x x ∈? 恒为真
故 })()({x P x P x E ?∨= ， )(x P 为任一谓词。
注意：全集的概念相当于论域，只包含与讨论有关的所有对象，并不一定包含一切对象与事物。例如：在初等数论中，全体整数组成了全集；方程012=+x 的解集合，在全集为实数集时为空集，而全集为复数集时解集合就不再是空集，此时解集合为1},{2=-i i i ，。
三、幂集
定义2-1-1.4 给定集合A ，由集合A 的所有子集为元素组成的集合，称为集合A 的幂集。记为P (A)（或记为A 2）。即 P (A)＝{X |X ?A}。
例2-1-1.5 A = {0 , 1 , 2 }，则 P (A) ＝ {Φ , {0} , {1} , {2} , {0 , 1} , {0 , 2} , {1 , 2} , {0 , 1 , 2 } }；
P (Φ)＝{Φ}；P ({a })={Φ,{a }}；P ({Φ}) = {Φ,{Φ}}。
定理2-1-1.3 设},,,{21n a a a A =，则 |P (A)|＝n 2。
其中：|P (A)|表示集合P (A)中元素的个数。
证明：集合A 的m (m = 0 , 1 , 2 ,… , n )个元素组成的子集个数为从n 个元素中取m
个元素的组合数，即m n C ，故P (A)的元素个数为：
|P (A)|＝∑==+++n m m n n n
n n C C C C 0
10
根据二项式定理 ∑=-=+n
m m n m
m
n n y x C y x 0)( 令x = y = 1得 ∑==n
m m n n C 02 故 |P (A)|＝n 2。
四、集合的数码表示
在中学学习集合时，特别强调了集合中元素的无序性，但是，为了用计算机表示集合及其幂集，需要对集合中元素规定次序，即给集合中元素附上排列指标，以指明一个元素关于集合中其他元素的位置。如A 2= {计算机，打印机}是二个元素的集合，令“计算机”为集合A 的第一个元素，“打印机”为集合A 2的第二个元素。改记为A 2 = { x 1 ,
x 2 } ，则P (A 2)的四个元素，可记为，00S =Φ，101}{S x =，012}{S x =，1121},{S x x =，其中S 的下标，从左到右分别记为第一位，第二位，它们的取值是1还是0由第一个和第二个元素是否在该子集中出现来决定，如果第i 个元素出现在该子集中，那么S 下标的第i 位取值为1，否则取值为0（i = 0 , 1）。即令J = {00 , 01 , 10 , 11 } = { i | i 是二位二进制数，00 ≤ i ≤11 }，则P (A 2) ＝ { S i | i ∈J }。类似地，三个元素集合 A 3 = { x 1 , x 2 , x 3 }的幂集P (A 3) ＝ { S i | i ∈J , J = { i | i 二进制数，000 ≤ i ≤ 111} }，因此，
S 010 = {x 2 } ， S 101 = {x 1 , x 3 }。上述幂集中元素表示法实际上是一种编码，可以推广到n 个元素的集合A n 的幂集上，P (A n )的2 n 个元素可以表示为
S i ，i ∈J={i | i 是二进制数，0 0 … 0 ≤ i ≤ 1 1 … 1 }
如果},,,,,{6543216x x x x x x A =，P (A 6)的62个元素记为 12106,,,-S S S ，此时S
的下标是十进制整数，如何求出127,S S 是A 6的那些元素组成的子集呢？将下标转换为二进制的整数，不足六位的在左边补入需要个数的零，使之成为六位的二进制整数，由排列的六位二进制整数推断出，含有那些元素。凡第i 位为0，表示x i 不在此子集中，凡第i 位为1表示x i 在此子集中，故
},,{6540001111117x x x B B B ===，},{4300110012x x B B ==。
这种方法可以推广到一般情况，即将十进制整数转换为二进制整数，在左边补入需要个数的零使之成为n 位的二进制数，若第i 位为0，表示x i 不在此子集中，若第i 位为1表示x i 在此子集中。
子集的这种编码法，不仅给出了一个子集含那些元素的判别方法，还可以用计算机表示集合、存贮集合以供使用。
§2-1-2 集合的基本运算
集合的运算，就是以集合为对象，按照确定的规则得到另外一些新集合的过程。给定集合A ，B ，可以通过集合的并（∪）、交（∩）、相对补（－）、绝对补（ˉ）和对称差（⊕）等运算产生新的集合。
一、集合并（∪）运算
定义2-1-2.1 设A ，B 为任意两集合，所有属于集合A 或属于集合B 的元素组成n n
的集合，称为集合A 和B 的并集。记作 A ∪B
})()({B x A x x B A ∈∨∈=?
并集的文氏（英国数学家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) 。
⑺的证明：必要性证明 )()()(B x x B A x x A x x B B A ∈???∈??∈?=? 所以 A ?B 。 充分性证明 由⑹知B ?A ∪B ，现证明 A ∪B ?B
)()(B x x B A x x B A ∈???∈??
所以有 A ∪B = B 。
例2-1-2.2 设 A ?B ，C ?D ，则 A ∪C ?B ∪D
证明： )}()({})()({}{,D x B x x C x A x x C A x x C A D C B A ∈∨∈?∈∨∈=?∈=??? ＝D B D B x x ?=?∈}{ 即 A ∪C ?B ∪D 成立。
同理可证 C B C A B A ?????。
因为集合的并运算满足结合律，对n 个集合A 1 , A 2 ,…, A n 的并集n A A A ??? 21定义为至少属于A 1 , A 2 ,…, A n 之一的那些元素构成的集合。n A A A ??? 21通常缩写成 n
i i A 1=。
},{121n n n n A x N n x A A A A ∈∈?==????∞
= 其中N 是自然数集合。 一般地，},{k I
k k A x I k x A ∈∈?=∈ 。
集合的并运算，就是把给定集的那些元素放到一起合并成一个集合，在这个合并中相同的元素只要一个。如设}6,3,2{,}8,3{,}3,2,1{321===A A A 则 }8,6,3,2,1{31== i i A
。
二、集合的交（∩）运算
定义2-1-2.2 设任意两个集合A 和B ，由集合A 和B 共
同元素组成的集合，称为集合A 和B 的交集，记作 A ∩B 。
})()({B x A x x B A ∈∧∈=?。
交集的文图
例2-1-2.3 设},,,{,},,,,{f e c a B e d c b a A == 则 },,{e c a B A =?。
例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）的证明：
必要性的证明：)()()(B x x B A x x A x x A
B A ∈???∈??∈?=? 即得A ∩B = A ? A ?B 充分性得证明：由性质（6）知A ∩B ?A , 现证 A ?A ∩B
采用逻辑演绎推理法
(1) )(A x x ∈? P(附加前提)
（2） A a ∈ US(1)
(3) A ?B P
(4) ))()((B x A x x ∈→∈? T(3)E
(5) )()(B a A a ∈→∈ US(4)
(6) B a ∈ T(2 , 5) I
(7) )()(B a A a ∈∧∈ T(2 , 6) I
(8) ))()((B x A x x ∈∧∈? UG(7)
(9) )(B A x x ?∈? 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 ,…的交集，分别记为
}},,,2,1{{121i n
i i n A x n i x A A A A ∈∈==???=
}},,,,2,1{{121n n n n A x n n x A A A A ∈∈==????∞
=
一般地，集合族{A k }k ∈I 中各集的交记成 I k k A
∈其定义为
},{l I k k A x I l x A
∈∈?=∈ 。
若序列A 1 , A 2 ,…, A n ,…任意两集合A i , A j (j i ≠) 不相交，则称
A 1 , A 2 ,…, A n ,…是两两不相交的集序列。
三、交运算与并运算之间的联系
定理2-1-2.3 （分配律） 设A , B , C 为任意三个集合，则
（1）交运算对并运算的分配律
)()()(C A B A C B A ???=??
（2）并运算对交运算的分配律
)()()(C A B A C B A ???=??
证明：（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 为任意两集合，则
（1） A ∪(A ∩B) = A ；
（2）A ∩(A ∪B) = A ；
证明： 由分配律可得
（1） A ∪(A ∩B) = (A ∩E)∪(A ∩B) = A ∩(E ∪B) = A ∩E = A
（2） A ∩(A ∪B) = (A ∪Φ)∩(A ∪B ) = A ∪(Φ∩B) = A ∪Φ = A ﹟
四、集合的补运算
定义2-1-2.3 设A , B 为任意两集合，由属于A 而不属于B 的一切元素构成的集合，称为A 与B 的差运算（又称B 对于A 的补运算，或相对补），记为A-B ，A-B 称为A 与B 的差集（或B 对于A 的补集）。
})()({})()({B x A x x B x A x x B A ∈?∧∈=?∧∈=-
若A = E ，对任意集合B 关于E 的补集
E-B ，称为集合B 的绝对补，记作B 。 })()({B x E x x B E B ?∧∈=-=
例2-1-2.6 设A = {1 , 2 , 3 , 4 , 5} ，
B = {1 , 2 , 4 , 7 , 9 } ，则 A-B = {3 , 5 }。
例2-1-2.7 设A 是素数集合，B 是奇数集合，则A-B = {2}。
例2-1-2.8 设E = {X 高校计算机专业学生}，A = {X 高校校计算机专业本科学生}， 则A = {X 高校计算机专业研究生}。
由集合补运算的定义知，补（差）集合有如下性质
定理2-1-2.5 设A , B , C 为任意三集合，则
（1） 对合律 A A =；
（2） Φ=E ；
（3） E =Φ；
（4） 排中律 E A A =?；
（5） 矛盾律 Φ=?A A ；
（6） （D e . M organ 定理）
① B A B A ?=? , ② B A B A ?=? ；
（7） ① B A B A ?=- ， ② )(B A A B A ?-=-；
（8） )()()(C A B A C B A ?-?=-?；
（9）若B A ?，当且仅当 ① A B ? ； ② B A A B =?-)(。
证明：由补运算的定义立即可得性质（1）～（5）。
A-B A
（6）的证明：
① B A B A x x B x A x x B x A x x B A x x B A x x B A ?=?∈=∈∧∈=?∧?=??=?∈=?}{})()({}
)()({}{}{
②的证法与①类似，请读者自行证明。
（7）的证明：
① B A B A x x B x A x x B x A x x B A ?=?∈=∈∧∈=?∧∈=-}{)}()({})()({； ② B A B A B A A A B A A B A A B A A -=?=???=??=??=?-)()()()(。
（8）的证明：
)()()()()()(C A B A C A B A C A B A ???=???=?-?
)()()(C B A C B A C B A A B A -?=??=?????=。
（9）的证明：
证明①
必要性 )()()()(A x x A x x B x x B x x B A ∈????????∈?? 即 A B ?；
充分性 )()()()(B x x B x x A x x A x x A
∈????????∈?? 即 B A ?。
证明②
必要性 B A B A A A B A A B A A B B A ?=?=???=??=?-)()()()(；
充分性 B A A B A B A A =?-=-??)()(。﹟
五、集合的对称差运算
定义2-1-2.4 设A , B 为任意两集合，由“属于A 而不属于
B ”或“属于B 而不属于A ”的一切元素构成的集合，称为A , B
的对称差,记作A ⊕B 。 }
()(({})()({)()(A x x B x A x x A B B A B A ∨∈=∈∨∈=-?-=⊕对称差运算的性质
定理2-1-2.6 设A , B , C 为任意三集合，则
（1） A B B A ⊕=⊕；
（2） A A =Φ⊕；
（3） Φ=⊕A A ；
B A ⊕
（4） )()(B A B A B A ???=⊕；
（5） )()(C B A C B A ⊕⊕⊕⊕＝；
（6）交关于对称差的分配律 )()()(C A B A C B A ?⊕?=⊕?；
（7） 若C A B A ⊕=⊕，则 B = C 。
证明：
由对称差的定义立即可得（1），（2），（3），（4）的证明。
（5）的证明
)
()()()()
()())()(()
))()((())()(())()(()(C B A C B A C B A C B A C B A C B A C B A B A C B A B A C B A B A C
B A B A
C B A ???????????=??????????=?????????=⊕???=⊕⊕
)
()()()())
()(())()(()))
()((()))()((())
()(()(C B A C B A C B A C B A C B A C B A C B C B A C B C B A C B C B A C B C B A C B A ???????????=??????????=?????????=???⊕=⊕⊕ 所以 )()(C B A C B A ⊕⊕⊕⊕＝。
（6）的证明 )
())
()(()
()())
()(())()(())
()(())()(()()(C B A C B C B A C B A C B A C A B A C A B A C A B A C A B A C A B A ⊕?=????=?????=???????=???????=?⊕?
（7）的证明
C B C B C A A B A A C A A B A A C A B A =?⊕Φ=⊕Φ?⊕⊕=⊕⊕?⊕⊕=⊕⊕?⊕=⊕)()()()()()( 从对称差定义或文图容易看出
)()()()()(B A B A B A B A B A B A ??⊕=?????=?，
)()(B A B A B A ?-?=⊕。
§2-1-3 集合中元素的计数
一、两个基本原理
加法原理：若一个事件以m 种方式出现（这些方式构成集合A ），另一个事件以n 种方式出现（这些方式构成集合B ），这两个事件完成一件即能达到目的（构成集合A ∪B ），则达到目的的方式数为m +n 。
例2-1-3.1 假设从城市A 到城市B 有铁路两条，公路三条，航线一条，那么按加法原理，从城市A 到城市B 有2＋3＋1＝6种走法。
乘法原理：若一个事件以m 种方式出现（这些方式构成集合A ），另一个事件以n 种方式出现（这些方式构成集合B ），这两个事件同时完成才能达到目的（构成集合A ∩B ），则达到目的的方式数为m n 。
例2-1-3.2 一位学生想从图书馆借离散数学和C# 语言书各一本，书架上有三种不同作者的离散数学书，有两种不同作者的C# 语言书，那么这位学生共有3×2＝6种不同的选法。
二、排列、组合
中学里已学过的计数公式是排列组合公式。从n 个元素的集合中每次取m 个的排列和组合的公式分别为：
!)(!)1()1(m n n m n n n P m
n
-=+--= ，!)(!!!m n m n m P C m n m n -== 对排列m n P ：若m = n 时称为全排列，m < n 时称为选排列。排列和组合的最基本恒等式有：
111,,!----+===m n m n m n m n n m n m n m n C C C C C C m P
例2-1-3.3 将computer 的字母全部取出进行全排列，其中c 不在第一位，r 不在末位，问共有多少种排法？
解：computer 字母的全排列数为!888=P ，其中c 排在第一位的排法共有7！种，r 排在末位的排法共有7！，除去这些不合要求的排法，还有8！-（7！＋7！）= 30240种，然而这还不是答案，因为c 在第一位的7！种排法中r 可能排至末位的7！中c 可能排在第一位，即c 在第一位，r 在末位的排法被减去了两次，实际上应该只减一次，故把不应该减的加回去才能得到正确的答案。所求的答案为：
309602667788=+-P P P （种）
。
这种分析问题的方法称为“多退少补法”，这种思想在“包含排斥原理”中还要用到。
例2-1-3.4 将1 , 2 , 3三个数字排成2行3列的矩阵，要求同行和同列上都没有相同的数字，问这样的数字矩阵有多少？（实际上这就是集合{1 , 2 , 3 }到自身上的一些双射或置换，这些双射不允许一个元素以自身为像）
解： 先排矩阵的第一行共有6!333==P 种排法，如果不管题目的要求，第二行也有6种排法，由乘法原理，知共有6×6＝36种矩阵。这些矩阵包含了有一列数字相同的情况，有两列因而就有三列数字相同的情况，按题目要求这些矩阵都应该除去，这些矩阵
的个数可如下计算：一列数字相同其余两列数字不同的矩阵数有221313P C C 种；有两列数
字相同从而就有三列数字相同的矩阵数有3！＝6个，因此所求的矩阵个数为
12332213133333=--?P P C C P P 。
m n P 与m n
C 是从n 个元素中任意取m 个元素（不重复抽取）的排列与组合，但是有些实际问题需要在n 个元素中重复抽取若干个元素来排列，如用0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9这十个数字来编制代码，，每个号码就可以重复使用某个数字。一般地，从n 个元素的集合中抽取m 个元素，允许重复的排列数为：m n 。实际上可以设想有m 个位子，每个位子都可以放上n 个元素中的任一个，允许
重复，由乘法原理即知有n ×n ×…×n = n m 种排法。
例2-1-3.5 求电子计算机中的6位二进制数。
解：电子计算机中的数码第一位数不能为0，故首位必须为1，后面五位每位都可选0或1，固有3225=种排法，因而6位二进制数有32个。
例2-1-3.6 考试时有25个正确或错误的问题，学生也可能不作答，问有多少种不同的考试结果？
解：对每一问题的回答有三种情况：正确、错误和不作答，因而考试结果共有253个。
关于重复组合数m n H 的计算问题。先从一个实例来研究它的计算公式，从{1 , 2 , 3}
中每次取出两个（允许重复抽取）的组合按自然数顺序写出来（即枚举）为：
11 , 12 , 13 , 22 , 23 , 33 (a )
现将各种组合分别加上01，就得到
12 , 13 , 14 , 23 , 24 , 34 (b )
m
(b )中的6个组合恰好是从{1 , 2 , 3 , 4}中任取两个元素不重复的组合情况。反之从(b )中的组合中分别减去01即得(a )，说明(a ) 与(b )存在1—1对应关系（双射），因而从三个相异元素中任取两个的重复组合数可化为从四个相异元素中任取两个不重复的组合数
来计算，即6242)12(323===-+C C H 得到。
一般地计算m n H 仿上面的讨论，即从{1 , 2 , … , n }中任取m 个允许重复的每一个组合，将其元素分别加上0 , 1 , 2 , … , m -1即变成从{1 ,
2 , … , n , n +1 , … , n + (m -1) }中任取m 个不重复的组合，故m m n m n C H 1-+=。
例2-1-3.7 求成自然序的四位数码个数。
解：四位数码是从{0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9}中选四个数字组成，数字可以重复使用，由于规定自然顺序，故只有一种排法，因而变为10个相异元素中任取四个允许
重复的组合问题，所求个数为 7154134)14(10410===-+C C H 。
关于环状排列问题，由于环状排列旋转后仍是同一种排列，故可以令其中任一个元素固定位置，不让它移动，其余n -1个元素任意排列，因而n 个相异元素的环状排列数为（n -1）!，它恰好为n 个相异元素的全排列数n !被n 除的结果，这种想法可以推广到不尽相异元素的排列情形。
例2-1-3.8 8为朋友围圆桌而坐，若座位不编号有多少种坐法？座位编号又有多少种坐法？
座位不编号为环状排列问题，有
7！= 5040种坐法。
座位编号为非环状排列问题，故有
8！= 40320 种坐法。
例2-1-3.9 5颗红珠，3颗白珠穿在一个项链上，有多少种方法？
解：如果只穿在一条线上就是不尽相异元素的全排列问题。排列数为
56!3!5!8=。现在项链上是环状排列问题，因而穿法为
78
56=种。 三、容斥原理
设集合A = { a 1 , a 2 , … , a n }，它含有n 个元素，可以说集合A 的基数是n ，记作CardA = n 。基数是表示集合中所含元素多少的量。如果集合A 的基数是n ，可记为|A | = n , 这时称A 为有穷集，显然空集的基数是0，即|Φ| = 0。如果A 不是有穷集，则称A 为无穷集。
容斥原理也称包含与排斥原理或逐步淘汰原则，它也是“多退少补”计数思想的应用。
定理2-1-3.1 (容斥原理) 设A , B 为有限集合，则
B A B A B A ?-+=?。
证明：① 当A , B 不相交，即Φ=?B A 时，B A B A +=?
② 当Φ≠?B A 时
B A B A A ?+?= ， B A A B B ?+?= 所以，B A B A B A B A ?+?+?=+2
但是， B A B A B A B A ?=?+?+?
因此， B A B A B A ?-+=?
定理2-1-3.2 设A , B 是有限集合，则 B A B A B A ?-+=⊕2。
证明：
B A B A B A B A B A B A B A B A ?-?-+=?-?=?-?=⊕)()()(
B A B A ?-+=2
例2-1-3.10 假设10名青年中有5名是工人，7名是学生，其中既是工人又是学生的青年有3名，问既不是工人又不是学生的青年的有几名？
解：设该10名青年组成集合Y ，|Y |=10,其中工人集合设为W ，|W |=5；学生集合设为S ,| S |=7。|W ∩S |=3，又因为)()(S W S W Y ???=
所以 10=?+?=S W S W Y
即 1)375(10)(1010=-+-=?-+-=?-=?S W S W S W S W 因此，既不是工人又不是学生的青年有1人。
这个例子的计算过程用到了容斥原理。一般，令有限集A 的元素具有m 个不同的性质P 1 , P 2 , … , P m 。A 中具有性质P i 的元素组成子集记为A i i = 1 , 2 ,… , m ；A i ∩A j （i ≠j ）表示A 中同时具有性质P i 和P j 的元素组成的子集；A i ∩A j ∩A k （i ≠j ≠k ）表示A 中同时具有性质P i , P j , P k 的元素组成的子集；…；A 1 ∩ A 2 ∩ …∩A m 表示A 中同时具有性质P 1 , P 2 , … , P m 的元素组成的子集。i A 表示A 中不具有性质P i 的元
素组成的子集。那么包含排斥原理可以叙述为
定理2-1-3.3 （容斥原理的推广）A 中不具有性质P 1 , P 2 ,… , P m 的元素数是，
m
m m k j i k j i m j i j
i m i i m A A A A A A A A A A A A A ???-++??-
?+
-=???∑∑∑≤<<≤≤<≤= 2111121)1( 注意：上式右边共 m m m m m C C C 2121=++++ 项
证明：等式左边是A 中不具有性质P 1 , P 2 , … , P m 的元素数。下面我们要证明：对A 中的任何元素a ，如果它不具有这m 条性质，那么它对等式右边的贡献是1；如果a 至少具有这m 条性质中的一条，那么它对等式右边的贡献是0。
设a 不具有性质P 1 , P 2 , … , P m ，那么m i A a i ,,2,1, =?。对任何整数i 和j ，m j i ≤<≤1，都有j i A A a ??。对任何整数i 、j 和k ，m k j i ≤<<≤1，都有k j i A A A a ???，…，m A A A a ???? 21。但是A a ∈，所以在等式右边的计数中它的贡献是： 1 – 0 + 0 – 0 +…+ (-1) m · 0 = 1 。
设a 具有这m 条性质中的k 条性质，m k ≤≤1，则a 对|A |的贡献是1；对∑=m
i i A 1的
贡献是k C k =1；对∑≤<≤?m j i j i A A 1的贡献是2k C ；…；对m A A A ??? 21的贡献是m k C ,
所以a 对等式右边计数的总贡献是：
)()1(121m k C C C m k m k k ≤-+-+-
0)11()1()1(0
210
=-=-=-+-+-=∑=k j k k j j k
k k
k k k C C C C C ﹟ 推论 A 中至少具有m 个性质之一的元素个数为
m
m m k j i k j i m j i j
i m i i m A A A A A A A A A A A A ???-+-??+
?-
=???-≤<<≤<≤=∑∑∑ 21111121)1( 证明： 因为 )()(212121m m m A A A A A A A A A A A ???-=???-=??? 所以 ∑∑≤<≤=?-
=???-=???m j i j i m i i m m A A A A A A A A A A 112121
m m m j i k j i A A A A A A ???-+-??+
-≤<<≤∑ 2111)1( 。
例2-1-3.11 试求不超过1000的自然数中能被2或3或5整除的数的个数。 解：设A = {1 , 2 , … , 1000 }，这是研究对象的集合，在A 上定义性质P 1 , P 2 , P 3 。对任意n ∈A ，若n 具有性质P 1 (P 2 , P 3) 当且仅当2|n (3|n , 5|n )。令A i 为A 中具有性质P i 的数组成的子集，i = 1 , 2 , 3，则
A 1 = {2 , 4 , 6 ,…, 1000 } = {2 k | k = 1 , 2 , , 500 }，
A 2 = {3 , 6 , 9 , , 999 } = {3 k | k = 1 , 2 ,… , [
3
1000] }， A 3 = {5 , 10 , 15 , …, 1000 } = { 5 k | k = 1 , 2 , …, ]51000[ }。 于是，|A 1 |=??????21000= 500 ，|A 2| = ??????31000= 333 ，|A 3| = ??
????51000 = 200 。 而 16661000}61000,,2,16{21=??
????=??????==? k k A A ； 100101000}101000,,2,110{31=??
????=??????==? k k A A ； 66151000}151000,,2,115{32=??
????=??????==? k k A A ； 33301000}301000,,2,130{321=??
????=??????==?? k k A A A 。 由定理2-1-3.3推论知
|A 1 ∪A 2∪ A 3 | = (500 + 333 + 200 ) - ( 166 + 100 + 66 ) + 33 = 1033 – 332 + 33 = 734。
所以，不超过1000的自然数中，至少能被2，3，5之一整除的数共有734个。
例2-1-3.12 某汽车工厂装配了三十辆汽车，可供选择的设备是收录机，空调器，防盗器，三十辆汽车中有15辆汽车装有收录机，8辆装有空调器，8辆装有防盗器，三种设备都具有的汽车有3辆，问这三种设备都没有的汽车有几辆？
解： 设 A 1 , A 2 , A 3 分别表示具有收录机，空调器，防盗器的汽车的集合。由题设知
|A 1 | = 15 ，|A 2 | = 8，|A 3 | = 8，| A 1∩A 2∩ A 3 | = 3。
由定理2-1-3.3推论知，
| A 1∪A 2∪ A 3 | = 15 + 8 + 8 - ( |A 1∩A 2| + |A 1∩A 3 | + |A 2∩ A 3 | ) + 3
= 34- ( |A 1∩A 2| + |A 1∩A 3 | + |A 2∩ A 3 | ) 。
|A 1∩A 2| ≥|A 1∩A 2∩ A 3 |＝3，
|A 1∩A 3 | ≥|A 1∩A 2∩ A 3 |＝3，
|A 2∩ A 3 | ≥|A 1∩A 2∩ A 3 |＝3，
所以，| A 1∪A 2∪ A 3 | ≤ 34 - (3 + 3 + 3) ＝25，
故 52530321321=-≥??-=??A A A A A A A ，
即三种设备都没有的汽车至少有5辆。
第2-2章 二元关系
在现实世界中，事物不是孤立的，事物之间都有联系，单值依赖联系是事物之间联系中比较简单的，比如说日常生活中事物的成对出现，而这种成对出现的事物具有一定的顺序，例如，上、下；大、小；左、右；父、子；高、矮等等。通过这种联系，研究事物的运动规律或状态变化。世界是复杂的，运动也是复杂的，事物之间的联系形式是各种各样的，不仅有单值依赖关系，更有多值依赖关系。“关系”这个概念就提供了一种描述事物多值依赖的数学工具。这样，集合，映射关系等概念是描述自然现象及其相互联系的有力工具，为建立系统的、技术过程的数学模型提供了描述工具和研究方法。映射是关系的一种特例。
系统地研究“关系”这个概念及其数学性质，是本章的任务。本章将通过笛卡尔积的给出关系的数学定义，特别给出关系的几种等价定义和常用性质、二元关系的运算，特别研究了计算机科学中具有重要应用的关系闭包运算、等价关系和偏序关系。等价关系和偏序关系不仅在计算机科学中，而且在数学中都是极为重要的。
§2-2-1 集合的笛卡尔积
一、 序 偶
定义2-2-1.1 由两个元素x 和y （允许x = y ）按一定的顺序排列成的二元组叫做有序对（也称序偶），记作< x , y > 。其中x 是它的第一元素，y 是它的第二元素。
上述例子可表示为<上，下>；<大，小>；<左，右>；<父，子>；<高，矮>等。平面直角坐标系中点的坐标就是有序对，如<1 , -1> , <-1 , 1> , <1 , 1> , <2 , 0> ,… 代表着不同的点。
第三章集合论基础 1、设A={a,{a},{a,b},{{a,b},c}}判断下面命题的真值。 ⑴{a}∈A T ⑵?({a}? A) F ⑶c∈A F ⑷{a}?{{a,b},c} F ⑸{{a}}?A T ⑹{a,b}∈{{a,b},c} T ⑺{{a,b}}?A T ⑻{a,b}?{{a,b},c} F ⑼{c}?{{a,b},c} T ⑽({c}?A)→(a∈Φ) T 2、证明空集是唯一的。（性质1：对于任何集合A，都有Φ?A。） 证明：假设有两个空集Φ1 、Φ2 ，则 因为Φ1是空集，则由性质1得Φ1 ?Φ2 。 因为Φ2是空集，则由性质1得Φ2 ?Φ1 。 所以Φ1=Φ2 。 3、设A={Φ},B=P(P(A)).问：(这道题要求知道幂集合的概念) a)是否Φ∈B?是否Φ?B? b)是否{Φ}∈B? 是否{Φ}?B? c)是否{{Φ}}∈B? 是否{{Φ}}?B? 解：设A={Φ}，B=P(P(A)) P(A)= {Φ,{Φ}} 在求P(P(A))时，一些同学对集合{Φ,{Φ}}难理解，实际上你就将{Φ,{Φ}}中的元素分别看成Φ=a ,{Φ}=b, 于是{Φ,{Φ}}={a,b} B=P(P(A))=P({a,b}) ={B0, B1 , B2 , B3 }={B00, B01,B10 ,B11}={Φ, {b}, {a}, {a,b}} 然后再将a,b代回即可B=P(P(A))=P({Φ,{Φ}})={Φ,{Φ} ,{{Φ}}, {Φ,{Φ}}} 以后熟悉后就可以直接写出。 a) Φ∈B Φ?B b) {Φ}∈B {Φ} ? B c) {{Φ}}∈B {{Φ}}?B a)、b)、c)中命题均为真。 4、证明A?B ? A∩B=A成立。 证明：A∩B=A ??x(x∈A∩B ?x∈A) ??x((x∈A∩B → x∈A)∧(x∈A→ x∈A∩B)) ??x((x?A∩B∨x∈A)∧(x?A∨x∈A∩B)) ??x((?(x∈A∧x∈B)∨x∈A)∧(x?A∨(x∈A∧x∈B)) ??x(((x?A∨x?B)∨x∈A)∧(x?A∨(x∈A∧x∈B))) ??x(T∧(T∧( x?A∨x∈B))) ??x( x?A∨x∈B)??x(x∈A→x∈B)? A?B 5、(A-B)-C=(A-C)-(B-C) 证明：任取x∈(A-C)-(B-C) ?x∈(A-C)∧x?(B-C) ?(x∈A∧x?C)∧?(x∈B∧x?C) ?(x∈A∧x?C)∧(x?B∨x∈C) ?(x∈A∧x?C∧x?B)∨(x∈A∧x?C∧x∈C) ?x∈A∧x?C∧x?B?x∈A∧x?B∧x?C ?(x∈A∧x?B)∧x?C ?x∈A-B∧x?C?x∈(A-B)-C 所以(A-B)-C=(A-C)-(B-C)
离散数学常考题型梳理 第2章关系与函数 一、题型分析 本章主要介绍关系的概念及运算、关系的性质与闭包运算、等价关系、相容关系和偏序关系三个重要关系、函数以及函数相关知识等内容。常涉及到的题型主要包括： 2-1关系的概念理解以及关系的并、交、补、差以及复合和逆关系等运算2-2关系自反和反自反、对称和反对称等性质的概念理解与判定；自反、对称和传递闭包运算。 2-3等价关系 2-4偏序关系和哈斯图 2-5 函数的概念和性质 因此，在本章学习过程中希望大家要清楚地知道： 1．有序对和笛卡尔积 （1）有序对：所谓有序对就是指一个有顺序的数组，如< x , y >，x , y的位置是确定的，且< a , b >< b , a >。 （2）笛卡尔积：把集合A，B合成集合A×B，规定： {,|} ?=<>∈∈ 且 A B x y x A y B 由于有序对< x , y >中x，y 的位置是确定的，因此A×B 的记法也是确定的，不能写成B×A 。 笛卡儿积的运算一般不满足交换律。 2．二元关系的概念和表示、几种特殊的关系和关系的运算 （1）二元关系的概念：二元关系是一个有序对集合，设集合A，B ，从集合A 到B的二元关系 R∈ x ∈ < y =且 > } , x {B | y A 记作xRy。 二元关系的定义域：A Ram? R ) (。 ) R Dom? (；二元关系的值域：B 二元关系R 是一个有序对组成的集合．因此，一个二元关系是一个集合，可以用集合形式表示；反过来说，一个集合未必是一个二元关系，仅当集合是由有序对元素组成的，才能当做二元关系。 常用关系的表示法包括了集合表示法、列举法、描述法、关系矩阵法和关系图法。关系矩阵和关系图是有限集合上的二元关系的表示方法。
《离散数学》单元测试（集合论） 3.1集合的基本概念 1.设Ａ、Ｂ、Ｃ是集合，确定下列命题是否正确，说明理由。 （1）Ф?Ф （2）Ф∈Ф （3）Ф?{Ф} （4）Ф∈{Ф} （5）如果A∈B与B?C,则A?C （6）如果A∈B与B?C,则A∈C （7）如果A?B与B∈C,则A∈C （8）如果A?B与B∈C,则A?C 2.有n个元素的集合Ａ的幂集ρ(A)的元素个数为多少？求下列集合的幂集合。 （1）Ф （2）{Ф} （3）{Ф,{Ф}} （4）{a,b} （5）{a,b,{a,b}} （6）{1，{1}，2，{2}} 3.2 集合的运算 1.设A，B是两个集合，A={1，2，3}，B={2，3，4}，则B－A= ，ρ（B）－ ρ（A）= 。 2.全集E={a，b，c，d，e}，A={a，d}，B={a，b，e}，C={b，d}，求 ，ρ（A）∩ρ（B） A B C= () = 。 3.下列命题正确的是（）。 A．φ∩{φ}=φB．φ∪{φ}=φC．{a}∈{a，b，c} D．φ∈{a，b，c} 4.确定下列各式的值： Ф∩{Ф}＝ {Ф,{Ф}}－Ф＝ {Ф,{Ф}}－{Ф}＝ 6.证明下列各等式： A∩(B－A)＝Ф A∪(A∩B)＝A 3.3 有穷集合的计数问题 掌握文氏图和容斥原理求解有穷集合的计数问题的方法，并会简单应用。以教材的示例为基础。
第4章 二元关系 4.1二元关系的定义、表示方法与特性 1. A 和B 是任意两个集合，若序偶的第一个元素是A 的一个元素，第二个元素是B 的一个 元素，则所有这样的序偶集合称为集合A 和B 的 ， 记作A ?B ，即A ?B= 。A ?B 的子集R 称为A 到B 的一个 。若|A|=m ， B|=n ，则A 到B 共有 个不同的二元关系。 2. 设集合A ＝{a,b},B ＝{x,y},求笛卡尔乘积A ×B,B ×A,,A ×ρ(B)。 3. 证明： (1) (A ∩B)×C=(A ×C)∩(B ×C) (2) (A ∪B)×C=(A ×C)∪(B ×C) 4. 设A={a,b},B={x,y},则从A 到B 的二元关系共有多少个？请分别列出。 5. 设集合A={a,b,c,d},B={1,2,3},R 是A 到B 的二元关系，R={
离散数学集合论部分测试题
离散数学集合论部分综合练习 本课程综合练习共分3次，分别是集合论部分、图论部分、数理逻辑部分的综合练习，这3次综合练习基本上是按照考试的题型安排练习题目，目的是通过综合练习，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握。本次是集合论部分的综合练习。 一、单项选择题 1．若集合A={a，b}，B={ a，b，{ a，b }}，则（）． A．A?B，且A∈B B．A∈B，但A?B C．A?B，但A?B D．A?B，且A?B 2．若集合A＝{2，a，{ a }，4}，则下列表述正确的是( )． A．{a，{ a }}∈A B．{ a }?A C．{2}∈A D．?∈A 3．若集合A＝{ a，{a}，{1，2}}，则下列表述正确的是( )． A．{a，{a}}∈A B．{2}?A C．{a}?A D．?∈A 4．若集合A={a，b，{1，2 }}，B={1，2}，则（）． A．B? A，且B∈A B．B∈ A，但B?A C．B ? A，但B?A D．B? A，且B?A 5．设集合A = {1, a }，则P(A) = ( )． A．{{1}, {a}} B．{?,{1}, {a}} C．{?,{1}, {a}, {1, a }} D．{{1}, {a}, {1, a }} 6．若集合A的元素个数为10，则其幂集的元素个数为（）． A．1024 B．10 C．100 D．1 7．集合A={1, 2, 3, 4, 5, 6, 7, 8}上的关系R={
第二篇集合与关系 集合论是现代各科数学的基础，它是德国数学家康托（Geog Cantor, 1845～1918）于1874年创立的，1876～1883年康托一系列有关集合论的文章，对任意元的集合进行了深入的探讨，提出了关于基数、序数和良序集等理论，奠定了集合论深厚的基础，19世纪90年代后逐渐为数学家们采用，成为分析数学、代数和几何的有力工具。 随着集合论的发展，以及它与数学哲学密切联系所作的讨论，在1900年前后出现了各种悖论，使集合的发展一度陷入僵滞的局面。1904～1908年，策墨罗（Zermelo）列出了第一个集合论的公理系统，它的公理，使数学哲学中产生的一些矛盾基本上得到了统一，在此基础上以后就逐渐形成了公理化集合论和抽象集合论，使该学科成为在数学中发展最为迅速的一个分支。 现在，集合论已经成为内容充实、实用广泛的一门学科，在近代数学中占据重要地位，它的观点已渗透到古典分析、泛函、概率、函数论、信息论、排队论等现代数学各个分支，正在影响着整个数学科学。集合论在计算机科学中也具有十分广泛的应用，计算机科学领域中的大多数基本概念和理论几乎均采用集合论的有关术语来描述和论证，成为计算机科学工作者必不可少的基础知识。集合论可作为数学学科的通用语言，一切必要的数据结构都可以利用集合这个原始数据结构而构造出来，计算机科学家或许也可以利用这种方法。 本篇介绍集合论的基础知识，主要内容包括集合及其运算、性质、序偶、关系、映射、函数、基数等。 第2-1章集合及其运算 §2-1-1 集合的概念及其表示 一、集合的概念 “集合”是集合论中的一个原始的概念，因此它不能被精确地定义出来。一般地说，把具有某种共同性质的许多事物，汇集成一个整体，就形成一个集合。构成这个集合的每一个事物称为这个集合的一个成员（或一个元素），构成集合的这些成员可以是具体东西，也可以是抽象东西。例如：教室内的桌椅；图书馆的藏书；全国的高等学校；自然数的全体；程序设计语言C的基本字符的全体等均分别构成一个集合。通常用大写的英文字母表示集合的名称；用小写的英文字母表示元素。若元素a属于集合A记作
离散数学集合论部分综合练习 本课程综合练习共分3次，分别是集合论部分、图论部分、数理逻辑部分的综合练习，这3次综合练习基本上是按照考试的题型安排练习题目，目的是通过综合练习，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握。本次是集合论部分的综合练习。 一、单项选择题 1．若集合A={a，b}，B={ a，b，{ a，b }}，则（）． A．A?B，且A∈B B．A∈B，但A?B C．A?B，但A?B D．A?B，且A?B 2．若集合A＝{2，a，{ a }，4}，则下列表述正确的是( )． A．{a，{ a }}∈A B．{ a }?A C．{2}∈A D．?∈A 3．若集合A＝{ a，{a}，{1，2}}，则下列表述正确的是( )． A．{a，{a}}∈A B．{2}?A C．{a}?A D．?∈A 4．若集合A={a，b，{1，2 }}，B={1，2}，则（）． A．B? A，且B∈A B．B∈ A，但B?A C．B ? A，但B?A D．B? A，且B?A 5．设集合A = {1, a }，则P(A) = ( )． A．{{1}, {a}} B．{?,{1}, {a}} C．{?,{1}, {a}, {1, a }} D．{{1}, {a}, {1, a }} 6．若集合A的元素个数为10，则其幂集的元素个数为（）． A．1024 B．10 C．100 D．1 7．集合A={1, 2, 3, 4, 5, 6, 7, 8}上的关系R={
【半群】G非空，·为G上的二元代数运算，满足结合律。 【群】（非空，封闭，结合律，单位元，逆元）恰有一个元素1适合1·a=a·1=a,恰有一个元素a-1适合a·a-1=a-1·a=1。 【Abel群/交换群】·适合交换律。可能不只有两个元素适合x2=1 【置换】n元置换的全体作成的集合Sn对置换的乘法作成n 次对称群。 【子群】按照G中的乘法运算·,子集H仍是一个群。单位子群{1}和G称为平凡子群。 【循环群】G可以由它的某元素a生成,即G=（a）。a所有幂的集合an，n=0，±1，±2，…做成G的一个子群，由a生成的子群。若G的元数是一个质数，则G必是循环群。 n元循环群（a）中,元素ak是（a）的生成元的充要条件是（n，k）=1。共有?（n）个。【三次对称群】{I（12）（13）（23）（123）（132）} 【陪集】a，b∈G，若有h∈H，使得a =bh，则称a合同于b（右模H），a≡b（右mod H）。H有限，则H的任意右陪集aH的元数皆等于H的元数。任意两个右陪集aH和bH或者相等或者不相交。 求右陪集：H本身是一个；任取a?H而求aH又得到一个；任取b?H∪aH而求bH又一个。G=H∪aH∪bH∪… 【正规子群】G中任意g，gH=Hg。（H=gHg-1对任意g∈G都成立） Lagrange定理G为有限群，则任意子群H的元数整除群G的元数。 1有限群G的元数除以H的元数所得的商，记为（G：H），叫做H在G中的指数，H的指数也就是H的右（左）陪集的个数。 2设G为有限群,元数为n,对任意a∈G，有an=1。 3若H在G中的指数是2，则H必然是G的正规子群。证明：此时对H的左陪集aH，右陪集Ha，都是G中元去掉H的所余部分。故Ha=aH。 4G的任意多个子群的交集是G的子群。并且，G的任意多个正规子群的交集仍是G的正规子群。 5 H是G的子群。N是G的正规子群。命HN为H的元素乘N的元素所得的所有元素的集合，则HN是G的子群。 【同态映射】K是乘法系统，G到K的一个映射σ（ab）=σ（a）σ（b）。 设（G，*），（K，+）是两个群，令σ：x→e，?x∈G，其中e是K的单位元。则σ是G到K 内的映射，且对a，b∈G，有σ（a*b）=e=σ（a）+ σ（b）。即，σ是G到K的同态映射，G～σ（G）。σ（G）={e}是K的一个子群。这个同态映射是任意两个群之间都有的。 【同构映射】K是乘法系统，σ是G到σ（G）上的1-1映射。称G与σ（G）同构，G?G′。同构的群或代数系统，抽象地来看可以说毫无差别。G和G′同态，则可以说G′是G的一个缩影。 【同态核】σ是G到G′上的同态映射，核N为G中所有变成G′中1′的元素g的集合，即N=σ-1（1′）={g∈G∣σ（g）=1′}。 N是G的一个正规子群。对于Gˊ的任意元素aˊ，σ-1(aˊ)={x|x∈G ,σ(x)= aˊ}是N在G 中的一个陪集。Gˊ的元素和N在G中的陪集一一对应。 设N是G的正规子群。若A，B是N的陪集，则AB也是N的陪集。 【环】R非空，有加、乘两种运算 a+b=b+a2）a+（b+c）=（a+b）+c， 3）R中有一个元素0，适合a+0=a， 4）对于R中任意a,有-a,适合a+(-a)=0， 5）a（bc）=（ab）c，
集合论期末复习题 1. 求(())P P φ 答：(()){,{}}P P φφφ= 2. 设||A n =，求|()|P A 答：|()|2n P A = 3. {,{}}________φφφ-=，{,{}}{}________φφφ-= 答：{,{}}φφ，{{}}φ 4. 证明：()()()A B C A B A C ?⊕=?⊕? 证明： () [()()] (~)(~) (~)(~) (~)(~)(~)(~)[()(~~)][()(~~)] [()~()][()~()] [()()][()()] ()() A B C A B C C B A B C C B A B C A C B A B A A B C A C B A C A A B A C A C B A A B A C A C A B A B A C A C A B A B A C ?⊕=?-?-=????=?????=???????????=???????=???????=?-???-?=?⊕? 5. 200人中，有67人学数学，47人学物理，95人学生物，26人学数学和生物，28人学数学和物理，27人学生物和物理，50人三门都不学，问：三门都学的人数和单学一门的人数？ 解：设三门都学的人数和单学数学、物理、生物的人数分别为x ，y1,y2,y3，则如下图： (26)(28)167(27)(28)247(26)(27)395 (26)(27)(28)12350200 x x x y x x x y x x x y x x x x y y y +-+-+=??+-+-+=??+-+-+=??-+-+-+++++=? 求解得到：1132228135342214123269364 y x x y x y y x y y y y x y -==????-=-=?????-==????++-==?? 6. 集合S={0,1,2,3,4,5,6}，R 为S 上的关系。R={ 离散数学集合论综合练习作业辅导 （10秋） 离散数学作为信息科学和计算机科学的数学基础，是教育部指定的计算机科学与技术学科核心课程，也是电大计算机科学与技术专业的统设必修学位课程，因此它也是该专业的一门很重要的基础课程，也是该专业的许多专业课程（包括数据结构、操作系统、网络编程技术、数据库应用技术等）的先修课程．本课程4学分，课内72学时，第二学期开设，主要是介绍离散量的结构及其相互关系，其包含的理论与方法在各学科领域都有着广泛的应用．本课程的主要内容包括：集合论、图论、数理逻辑三个部分． 本课程的学习目标：通过本课程的学习，使学生具有现代数学的观点和方法，并初步掌握处理离散结构所必须的描述工具和方法．同时，也要培养学生抽象思维和慎密概括的能力，使学生具有良好的开拓专业理论的素质和使用所学知识，分析和解决实际问题的能力，为学生以后学习计算机基础理论与专业课程打下良好的基础． 本次教学活动是本学期的第一次综合作业辅导活动，主要是针对集合论单元的重点学习内容进行辅导，方式是通过讲解一些典型的综合练习题目，帮助大家进一步理解和掌握集合论的基本概念和方法，也使大家尽早地了解本课程期末考试的题型． 下面是本学期第2，3次形考作业中的部分题目． 一、单项选择题 单项选择题主要是第2次形考作业的部分题目。 第2次作业由10个单项选择题组成，每小题10分，满分100分。在每次作业关闭之前，允许大家反复多次练习，系统将保留您的最好成绩，希望大家要多练几次，争取好成绩。需要提醒大家的是每次练习的作业题目可能不一样，请大家一定要认真阅读题目。 1．若集合A＝{ a，{a}，{1，2}}，则下列表述正确的是( )． A．{a，{a}}∈A B．{1，2}?A C．{a}?A D．?∈A 正确答案：C 2．若集合A={1，2}，B={1，2，{1，2}}，则下列表述正确的是( )． A．A?B，且A∈B B．B?A，且A∈B C．A?B，且A?B D．A?B，且A∈B 正确答案：A 注意：这两个题是重点，大家一定要掌握，还有灵活运用，譬如，将集合中的元素作一些调整，大家也应该会做． 例如，2010年1月份考试的试卷的第1题 作业答案：集合论部分 P90:习题六 5、确定下列命题是否为真。 （2）?∈? （4）{}?∈? （6）{,}{,,,{,}}a b a b c a b ∈ 解答：（2）假（4）真（6）真 8、求下列集合的幂集。 （5）{{1,2},{2,1,1},{2,1,1,2}} （6）{{,2},{2}}? 解答： （5）集合的元素彼此互不相同，所以{2,1,1,2}{1,2}=，所以该题的结论应该为 {,{{1,2}},{{2,1,1}},{{1,2},{2,1,1}}}? （6）{,{{,2}},{{2}},{{,2},{2}}}??? 9、设{1,2,3,4,5,6}E =，{1,4}A =，{1,2,5}B =,{2,4}C =,求下列集合。 （1）A B （2）()A B 解答： （1）{1,4}{3,4,6}{4}A B == （2）(){1}{2,3,4,5,6}A B == 31、设A,B,C 为任意集合，证明 () ()()()A B B A A B A B --=- 证明： ()() {|}{|()()}{|()()()()} {|()()}{|()()}{|()()} {|()()}{|()(A B B A x x A B x B A x x A x B x B x A x x A x B x B x B x A x A x B x A x x A x B x B x A x x A B x A x B x x A B x A x B x x A B x B x x A B x A --=∈-∨∈-=∈∧?∨∈∧?=∈∨∈∧?∨∈∧∈∨?∧?∨?=∈∨∈∧?∨?=∈∧?∨?=∈∧∈∨∈=∈∧∈=∈∧∈)} B A B A B =- 离散数学集合论部分形成性考核书面作 业 本课程形成性考核书面作业共3次，内容主要分别是集合论部分、图论部分、数理逻辑部分的综合练习，基本上是按照考试的题型（除单项选择题外） 安排练习题目，目的是通过综合性书面作业，使同学自己检验学习成果，找出 掌握的薄弱知识点，重点复习，争取尽快掌握。本次形考书面作业是第一次作业，大家要认真及时地完成集合论部分的综合练习作业。 要求：将此作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有 解答过程，要求本学期第11周末前完成并上交任课教师（不收电子稿）。并在 03任务界面下方点击“保存”和“交卷”按钮，完成并上交任课教师。 一、填空题 1．设集合{1,2,3},{1,2} ==，则P(A)-P(B )= {{3}，{1,3}，{2,3}， A B {1,2,3}} ，A?B= {<1,1>,<1,2>,<2,1>,<2,2>,<3,1>,<3.2>} ．2．设集合A有10个元素，那么A的幂集合P(A)的元素个数为 1024 ．3．设集合A={0, 1, 2, 3}，B={2, 3, 4, 5}，R是A到B的二元关系， 则R的有序对集合为 {<2, 2>，<2, 3>，<3, 2>}，<3,3> ．4．设集合A={1, 2, 3, 4 }，B={6, 8, 12}，A到B的二元关系 R＝} ∈ y x∈ y < > = {B , , x , 2 y A x 那么R－1＝ {<6,3>,<8,4>} 5．设集合A=｛a, b, c, d｝，A上的二元关系R={ 集合论练习题 一、选择题 1．设B = { {2}, 3, 4, 2}，那么下列命题中错误的是（ ）． A ．{2}∈ B B ．{2, {2}, 3, 4}B C ．{2}B D ．{2, {2}}B 2．若集合A ={a ，b ，{ 1，2 }}，B ={ 1，2}，则（ ）． A ． B A ，且BA B ．B A ，但BA C ．B A ，但BA D ．B A ，且BA 3．设集合A = {1, a }，则P (A ) = ( )． A ．{{1}, {a }} B ．{?,{1}, {a }} C ．{?,{1}, {a }, {1, a }} D ．{{1}, {a }, {1, a }} 4.已知AB ={1,2,3}, AC ={2,3,4},若2 B,则（ ） A ． 1?C B ．2? C C ．3?C D ．4?C 5. 下列选项中错误的是( ) A ． ??? B ． ?∈? C ． {}??? D ．{}?∈? 6. 下列命题中不正确的是（ ） A ． x {x }-{{x }} B ．{}{}{{}}x x x ?- C ．{}A x x =?,则xA 且x A ? D ． A B A B -=??= 7. A , B 是集合，P (A ),P (B )为其幂集，且A B ?=?，则()()P A P B ?=( ) A ． ? B ． {}? C ． {{}}? D ．{,{}}?? 8. 空集?的幂集()P ?的基数是( ) A ． 0 B ．1 C ．3 D ．4 9．设集合A = {1，2，3，4，5，6 }上的二元关系R ={a , b ∈A , 且a +b = 8}，则R 具有的性质为（ ）． A ．自反的 B ．对称的 C ．对称和传递的 D ．反自反和传递的 第 1 页 共 4 页 2015 - 2016学年第一学期 《离散数学》（集合论部分）自测试题 一、单项选择题(本大题共8小题，每小题2分，共16分) 在每小题列出的四个备选项中只有一个是最符合题目要求的，请将其代码填写在题后的括号内。错选、多选或漏选均不得分。 1）等价关系一定不是．．【 】 A. 对称的 B. 自反的 C. 可传递的 D. 反自反的 2）设{,{1}}A a =，则下列描述中正确．．的是【 】 A. {1}A ∈ B. {1}A ? C. {a}A ∈ D. A ?∈ 3）设A 、B 是两个任意集合，则A B -=??【 】 A. A B = B. A B ? C. A B ? D. B =? 4）设{{},{},{}}X a b =?，则其幂集()P X 的元素总个数为【 】 A. 4 B. 8 C. 16 D. 32 5）设R 是实数集合，:f R R →,()21f x x =+，则f 【 】 A. 是关系，但不是函数 B. 仅是满射函数 C. 仅是单射函数 D. 是双射函数 6）设R 是A 上的二元关系，r 、s 、t 分别指关系的自反闭包、对称闭包、传递闭包、则下列描述不正确．．．的是【 】 A. ()A r R R I = B. 2()t R R R = C. 1 ()s R R R -= D. -1-1 R R =（） 7）如果R 1和R 2是集合A 上的自反关系，则R 1∪R 2, R 1∩R 2, R 1―R 2中自反关系有【 】个 A. 0 B. 1 C. 2 D. 3 8）设集合A=｛a,b,c ｝，B=｛1,2,3,4｝，作f ：A →B ，则不同的函数个数为【 】个 A. 12 B. 81 C. 64 D. 以上均不正确 二、填空题(本大题共12空，每空2分，共24分) 请在每小题的空格中填上正确答案。错填、漏填均不得分。 7）设集合A={1,2,3,4}，则A 中的划分有_____________个. 8）设=<1,2>,<1,3>,<2,4>,<4,3>R ｛｝，那么fld R =_____________. 9）设集合A =｛1，2，3，4｝，则A A ⊕= _____________. 10）设关系F ={<3,3>,<6,2>},G ={<2,3>}，则F G = _____________. ----------------------------------------第-------------------1---------------------装--------------------------------线--------------------------------------- 离散数学 当前位置： 离散数学在线教程 首页 学习空间 课程教学 离散数学绪论集合论初步关系与映射 代数系统基础无限集重言式 布尔代数及应用群论基础半群 图论基本概念图的矩阵表示Euler,Hamilton图通路，回路，连通性命题及连接词命题公式 基本逻辑等价式 离散试卷 习题讲解 离散问题（集合论初步）离散问题（函数，无限集）离散问题（二元关系） 离散问题（代数系统）离散问题（图论） 指导老师：李志林 离散数学绪论 1．计算机科学与离散数学 计算机科学是与计算机软件硬件有关的各学科的总称,特点是离散性,离散数学是研究离散量的结构及其相互间关系的一门学科。 【实例1】布尔代数({0,1},+,*,~)在电子科学和数理逻辑中可得到具体解释。 【实例2】计算机中鼓轮的设计用到图论知识。 2．离散数学的特征 （1）研究离散量 （2）重视能行性的研究 3．离散数学的内容 集合论初步 第一节集合理论基础 1．集合的概念 一般认为，集合是一些确定的对象的全体，对象称为元素，若a是集合A的元素，则记为a ∈A 集合的表示方法： （1）列举法：列举出元素。 （2）描述法：把元素的共同性质描述出来。 （3）谓次表示法：{x|P(x)}（借助一些逻辑记号）. 常见的集合： （1）空集：{ }或 （2）单元素集合：只含一个元素 （3）全集：所考虑的对象的全体 （4）常用记号：N, Z, Q, R等 2．集合的关系 【DEF1】若集合A, B的元素相同，则称A, B是相等的，记为A=B，否则A和B是不相等的，记为A≠B 【DEF2】若a∈A一定有a∈B，则称A是B的子集，记为，若，但是A≠B，则称A是B的真子集，记为. 3．集合的运算 【DEF1】集合A与B的交集A∩B={x|x∈A或x∈B} 【DEF2】并集A∪B={ x|x∈A和x∈B} 【DEF3】A, B是分离的，若A∩B= 【DEF4】集合A对B的差A-B={ x|x∈A和x B } 【DEF5】集合A的补集为全集E与A的差，记为A’ 【DEF6】集合A与B的对称差A⊕B=（A-B）∪（B-A） 离散数学疑难解析——集合论部分 第一章 集合 [集合的知识点] 1、集合、元素、集合的表示方法、子集、空集、全集、集合的包含、相等、幂集 2、集合的交、并、差、补等运算及其运算律（交换律、结合律、分配律、吸收律、 De Morgan 律等），文氏（Venn ）图 3、序偶与迪卡尔积 [集合的疑难解析] 1．集合的概念 因为集合的概念大家在中学阶段已经学过，这里只多介绍了一个幂集的概念，所重点要对幂集加以掌握，一是掌握幂集的构成，一个集合A 的幂集是由A 的所有子集组成的集合。二是掌握幂集元数为2n ，其中n 是集合A 的元素个数。 2．集合恒等式的证明 通过对集合恒等式证明的练习，既可以加深对集合性质的理解与掌握；又可以为第三章命题逻辑中公式的基本等价式的应用打下良好的基础。实际上，本章做题是一种基本功训练，尤其要求学生重视吸收律和重要等价式在B A B A ~?=-证明中的特殊作用。 第二章 关系与映射 [二元关系的知识点] 1、关系、关系矩阵与关系图 2、复合关系与逆关系 3、关系的性质（自反性、对称性、反对称性、传递性） 4、关系的闭包（自反闭包、对称闭包、传递闭包） 5、等价关系与等价类 6、偏序关系与哈斯图（Hasse ）、极大/小元、最大/小元、上/下界、最小上界、最大下界 7、函数及其性质（单射、满射、双射） 8、复合函数与反函数 [二元关系疑难解析] 1．关系的概念 关系的概念是第二章全章的基础，又是第一章集合概念的应用。因此，大家应该真正理解并熟练掌握二元关系的概念及关系矩阵、关系图表示。 2．关系的性质及其判定 关系的性质既是对关系概念的加深理解与掌握，又是关系的闭包、等价关系、半序关系的基础。对于四种性质的判定，可以依据教材中P49上总结的规律。这其中对传递性的判定，难度稍大一点，这里要提及两点：一是不破坏传递性定义，可认为具有传递性。如空关系具有传递性，同时空关系具有对称性与反对称性，但是不具有自反性。另一点是介绍一种判定传递性的“跟踪法”，即若()()()R a a R a a R a a i i ∈∈∈-,, ,,,,13221 ，则()R a a i ∈,1。如若()()R a b R b a ∈∈,,,，则有()R a a ∈,，且()R b b ∈,。 3．关系的闭包 2017年11月上交的离散数学形考任务一 本课程的教学内容分为三个单元，其中第三单元的名称是（ A ）． 选择一项： A. 数理逻辑 B. 集合论 C. 图论 D. 谓词逻辑 题目2 答案已保存 满分10.00 标记题目 题干 本课程的教学内容按知识点将各种学习资源和学习环节进行了有机组合，其中第2章关系与函数中的第3个知识点的名称是（ D ）． 选择一项： A. 函数 B. 关系的概念及其运算 C. 关系的性质与闭包运算 D. 几个重要关系 题目3 答案已保存 满分10.00 标记题目 题干 本课程所有教学内容的电视视频讲解集中在VOD点播版块中，VOD点播版块中共有（B）讲． 选择一项： A. 18 B. 20 C. 19 D. 17 题目4 答案已保存 满分10.00 标记题目 题干 本课程安排了7次形成性考核作业，第3次形成性考核作业的名称是（C）．选择一项： A. 集合恒等式与等价关系的判定 B. 图论部分书面作业 C. 集合论部分书面作业 D. 网上学习问答 题目5 答案已保存 满分10.00 标记题目 题干 课程学习平台左侧第1个版块名称是：（C）． 选择一项： A. 课程导学 B. 课程公告 C. 课程信息 D. 使用帮助 题目6 答案已保存 满分10.00 标记题目 题干 课程学习平台右侧第5个版块名称是：（D）． 选择一项： A. 典型例题 B. 视频课堂 C. VOD点播 D. 常见问题 题目7 答案已保存 满分10.00 标记题目 题干 “教学活动资料”版块是课程学习平台右侧的第（ A ）个版块． 选择一项： A. 6 B. 7 C. 8 D. 9 题目8 答案已保存 满分10.00 标记题目 题干 课程学习平台中“课程复习”版块下，放有本课程历年考试试卷的栏目名称是：（D ）．选择一项： A. 复习指导 B. 视频 C. 课件 D. 自测 请您按照课程导学与章节导学中安排学习进度、学习目标和学习方法设计自己的学习计划，学习计划应该包括：课程性质和目标（参考教学大纲）、学习内容、考核方式，以及自己的学习安排，字数要求在100—500字．完成后在下列文本框中提交． 解答：学习计划 学习离散数学任务目标： 集合论部分 第三章、集合的基本概念和运算 3.1 集合的基本概念集合的定义与表示 集合与元素 集合没有精确的数学定义 理解：一些离散个体组成的全体组成集合的个体称为它的元素或成员集合的表示 列元素法A={ a, b, c, d } 谓词表示法B={ x | P(x) } B 由使得P(x) 为真的x构成常用数集 N, Z, Q, R, C 分别表示自然数、整数、有理数、 实数和复数集合，注意0 是自然数. 元素与集合的关系：隶属关系 属于∈，不属于? 实例 A={ x | x∈R∧x2-1=0 }, A={-1,1} 1∈A, 2?A 注意：对于任何集合A 和元素x (可以是集合)， x∈A和x?A 两者成立其一，且仅成立其一. 集合之间的关系 包含（子集）A?B??x (x∈A→x∈B) 不包含A?B??x (x∈A∧x?B) 相等A = B?A?B∧B?A 不相等A≠B 真包含A?B?A?B∧A≠B 不真包含A?B 思考：≠和?的定义 注意∈和?是不同层次的问题 空集?不含任何元素的集合 实例{x | x2+1=0∧x∈R} 就是空集 定理空集是任何集合的子集 ??A??x (x∈?→x∈A) ?T 推论空集是惟一的. 证假设存在?1和?2，则?1??2 且?1??2，因此?1=?2全集E 相对性 在给定问题中，全集包含任何集合，即?A (A?E ) 幂集定义P(A) = { x | x?A } 实例 P(?) = {?}， P({?}) = {?,{?}} P({1,{2,3}})={?,{1},{{2,3}},{1,{2,3}}} 计数 如果|A| = n，则|P(A)| = 2n 3.2 集合的基本运算 集合基本运算的定义??-~⊕ 并A?B = { x | x∈A∨x∈B } 交A?B = { x | x∈A∧x∈B } 相对补A-B = { x | x∈A∧x?B } 对称差A⊕B = (A-B)?(B-A) = (A?B)-(A?B) 绝对补~A = E-A 文氏图（John Venn） 集合论练习题 一、选择题 1.设B = { {2}, 3, 4, 2},那么下列命题中错误的就是( ). A.{2}∈B B.{2, {2}, 3, 4}?B C.{2}?B D.{2, {2}}?B 2.若集合A ={a ,b ,{ 1,2 }},B ={ 1,2},则( ). A.B ? A ,且B ∈A B.B ∈ A ,但B ?A C.B ? A ,但B ?A D.B ? A ,且B ?A 3.设集合A = {1, a },则P (A ) = ( ). A.{{1}, {a }} B.{?,{1}, {a }} C.{?,{1}, {a }, {1, a }} D.{{1}, {a }, {1, a }} 4、已知A ⊕B ={1,2,3}, A ⊕C ={2,3,4},若2∈ B,则( ) A. 1∈C B.2∈C C.3∈C D.4∈C 5、 下列选项中错误的就是( ) A. ??? B. ?∈? C. {}??? D.{}?∈? 6、 下列命题中不正确的就是( ) A. x ∈{x }-{{x }} B.{}{}{{}}x x x ?- C.{}A x x =?,则x ∈A 且x A ? D. A B A B -=??= 7、 A , B 就是集合,P (A ),P (B )为其幂集,且A B ?=?,则()()P A P B ?=( ) A. ? B. {}? C. {{}}? D.{,{}}?? 8、 空集?的幂集()P ?的基数就是( ) A. 0 B.1 C.3 D.4 9.设集合A = {1,2,3,4,5,6 }上的二元关系R ={?a , b ∈A , 且a +b = 8},则R 具有的性质为( ). A.自反的 B.对称的 C.对称与传递的 D.反自反与传递的 10、 设集合A ={1 , 2 , 3 , 4}上的二元关系 【2019年新版】电大离散数学作业3答案资料(集合论部分) 离散数学作业3 离散数学集合论部分形成性考核书面作业 本课程形成性考核书面作业共3次，内容主要分别是集合论部分、图论部分、数理逻辑部分的综合练习，基本上是按照考试的题型（除单项选择题外）安排练习题目，目的是通过综合性书面作业，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握。本次形考书面作业是第一次作业，大家要认真及时地完成集合论部分的综合练习作业。 一、填空题 1．设集合{1,2,3},{1,2} A B ==，则P(A)-P(B )= {{1,2},{2,3},{1,3},{1,2,3}}，A?B= {<1,1>,<1,2>,<2,1>,<2,2>,<3,1>,<3,2>}． 2．设集合A有10个元素，那么A的幂集合P(A)的元素个数为1024 ． 3．设集合A={0, 1, 2, 3}，B={2, 3, 4, 5}，R是A到B的二元关系， ∈ ∈ R? x ∈ < 且 =且 y > {B A , , } y x A y B x 则R的有序对集合为{<2,2>,<2,3>,<3,2>,<3,3>}． 4．设集合A={1, 2, 3, 4 }，B={6, 8, 12}，A到B的二元关系 R＝} x∈ ∈ y = < > y x 2 , , , {B A y x 那么R－1＝{<6,3>,<8,4>} 5．设集合A=｛a, b, c, d｝，A上的二元关系R={离散数学习题1
离散数学及其应用集合论部分课后习题答案
离散数学作业答案
离散数学集合论练习题
《离散数学》(集合论部分)自测试题
离散数学
离散数学疑难解析——集合论部分
离散数学形考任务1-7试地题目及问题详解完整版
离散数学第三章集合的基本概念和运算知识点总结
离散数学集合论练习题
【2019年新版】电大离散数学作业3答案资料(集合论部分)
相关主题
文本预览