离散数学/吴秀兰

第3章集合集合论是现代数学的基础，它的起源可以追溯到16世纪末期.为了追寻微积分的坚实的基础，人们只进行了有关数集的研究.直到1876—1883年，康托发表了一系列有关集合论的文章，对任意元素的集合进行了深入的探讨，提出了关于基数、序数和良序集等理论，奠定了集合论的深厚基础.但是，随着集合论的发展，以及它与数学哲学密切联系所作的讨论，在1900年前后出现了各种悖论，使集合论的发展一度陷入僵滞的局面.1904—1908年，策墨罗列出了**个集合论的公理系统，他的公理，使数学哲学中产生的一些矛盾基本上得到统一，在此基础上逐步形成了公理化集合论和抽象集合论，使该学科成为数学中发展*为迅速的一个分支.本章介绍集合的一些基本知识. 3.1集合的基本概念 在研究问题时，通常把具有某种性质的事物作为一个整体来研究，这个整体称为集合，其中的每个事物称为集合的元素.常用英文大写字母A,B,C等表示集合，以英文小写字母a,b,c等表示集合的元素.a∈A表示a是A的元素，aA表示a不是A的元素. 定义3.1.1一个集合若由有限个元素组成，则称为有限集，否则称为无限集.特别地，元素个数为零的集合称为空集，记作“”.用符号“|A|”表示有限集A的元素个数. 常见的集合表示法分为枚举法和特性描述法.枚举法是将集合的元素一一列出.如集合A由元素a,b,c,d组成，可记为A={a,b,c,d}.特性描述法是用集合的元素所具有的共同性质来刻画集合.如A={x|x是正偶数}.一般集合可用A={x|P(x)}表示，其中P(x)表示事物x满足性质P，集合A由满足性质P的所有元素组成. 注（1） 集合的元素具有确定性，即元素a∈A或aA二者必居且仅居其一. （2） 集合的确定不应引起悖论.如A={x|xA}不能定义成为一个集合. （3） 集合中的元素具有无序性.如{a,b}={b,a}. 定义3.1.2集合间的关系有如下定义： （1） 设A，B为集合，AB表示A是B的子集，即如果a∈A，则a∈B. （2） 设A，B为集合，AB表示A是B的真子集，即AB且存在b∈B使bA. （3） 设A，B为集合，A=B表示AB且BA，即A和B元素相同，称作A与B相等. （4） 称P(X)={A|AX}为X的幂集，即X的所有子集组成的集合，有时也记为2X. 根据讨论问题的需要，常设一个充分大的集合为全集，也称为基本集，所讨论的集合均为这个集合的子集.[3]第3章集合[3][1]3.2集合的基本运算[3]注（1） X含有n个元素，则X有2n个子集，即P(X)含有2n个元素. （2） 空集是任一集合的子集. （3） 包含关系满足以下性质： ① AA；（自反性） ② 若AB,BA，则A=B； （反对称性） ③ 若AB,BC，则AC. （传递性） 例3.1.1设A={a,b},求P(A). 解P(A)={,{a},{b},{a,b}}. 注2={}，要区分与{}，其中表示空集，其中没有任何元素，而{}则表示以空集为元素的一个集族，即∈{}. 一般用N,Z,Q,R,C分别表示自然数集、整数集、有理数集、实数集、复数集，它们满足NZQRC. 3.2集合的基本运算 集合有并、交、差、补、对称差等运算. 定义3.2.1设A,B为集合，A与B的并集记作A∪B，其定义式为 A∪B={x|x∈A或x∈B}. 定义3.2.2设A,B为集合，A与B的交集记作A∩B，其定义式为 A∩B={x|x∈A且x∈B}. 定义3.2.3设A,B为集合，A与B的差集记作A－B或A\\B，其定义式为 A－B={x|x∈A且xB}. 定义3.2.4设X为基本集，集合A的补集记作Ac或，其定义式为 Ac=X－A={x|xA且x∈X}. 定义3.2.5设A，B为集合，A与B的对称差记作AB，其定义式为 AB=(A－B)∪(B－A). 对称差也称为布尔和. 以上定义的并和交运算称为初级并和初级交.下面考虑推广的并和交运算，即广义并和广义交. 定义3.2.6设A为集合，A的元素的元素构成的集合称作A的广义并，记作∪A，符号化表示为 ∪A=x|zz∈A∧x∈z. 例3.2.1设A=a,b,c,a,c,d,a,e,f，B=a，C=a,c,d.则 ∪A={a,b,c,d,e,f}，∪B=a， ∪C=a∪c,d，∪= 根据广义并定义，我们有，若A=A1,A2,…,An，则∪A=A1∪A2∪…∪An. 定义3.2.7设A为集合，A的元素的元素构成的集合称作A的广义交,记作∩A，符号化表示为 ∩A=x|zz∈A→x∈z. 考虑例3.2.1中的集合，有 ∩A=a,∩B=a,∩C=a∩c,d. 但空集不可以进行广义交，因为∩不是集合，在集合论中是没有意义的.和广义并类似，若A=A1,A2,…,An，则∩A=A1∩A2∩…∩An. 例3.2.2设A={{a},a,b},计算∪∪A,∩∩A和∩∪A∪∪∪A－∪∩A. 解∪A={a,b},∩A=a,∪∪A=a∪b, ∩∪A∪∪∪A－∪∩A=a∩b∪a∪b－a =a∩b∪b－a =b. 所以∪∪A=a∪b，∩∩A=a, ∩∪A∪∪∪A－∪∩A=b. [3][1]3.3集合中元素的计数[3]3.3集合中元素的计数 集合的运算可以用文氏图表示.文氏图的构造方法如下： E是全集，圆A,B的内部为集合A,B，如果没有关于集合不交的说明，任何两圆应彼此相交.图中的阴影区域表示集合A,B在相应运算下组成的集合.具体见图3.3.1. 图3.3.1 X为集合，A,B,C为X的子集，∪,∩,c为集合的并、交、补运算，有以下性质： （1） A∪B=B∪A,A∩B=B∩A；（交换律） （2） (A∪B)∪C=A∪(B∪C), (A∩B)∩C=A∩(B∩C)； （结合律） （3） A∪=A,A∩X=A； （同一律） （4） A∪Ac=X,A∩Ac=； （互补律） （5） A∪(A∩B)=A,A∩(A∪B)=A； （吸收律） （6） A∪(B∩C)=(A∪B)∩(A∪C)， A∩(B∪C)=(A∩B)∪(A∩C)； （分配律） （7） A∪A=A,A∩A=A； （幂等律） （8） A∪X=X,A∩=； （零律） （9） (Ac)c=A； （双重否定律） （10） A∪Bc=Ac∩Bc,(A∩B)c=Ac∪Bc. （德摩根律） 由以上性质知，在任何集合运算的公式中，将∪与∩互换，公式仍然成立.这就是集合论的对偶原则. 定理3.3.1（包含排斥原理）设S为有限集合，P1,P2,…,Pm是m个性质. S中的任何元素x或者具有性质Pi或者不具有性质Pi(i=1,2,…,m)两种情况必居其一.令Ai表示具有性质Pi的元素构成的子集，则S中不具有性质P1,P2,…,Pm的元素个数为 |A1∩A2∩…∩Am|=|S|－∑mi=1|Ai|+∑1≤i－∑1≤i+…+(－1)m|A1∩A2∩…∩Am|. 推论S中至少具有一条性质的元素数为 |A1∪A2∪…∪Am| =∑mi=1|Ai|－∑1≤i－…+(－1)m－1|A1∩A2∩…∩Am|. 当m=2时，有 |A1∪A2|=|A1|+|A2|－|A1∩A2|. 当m=3时，有 |A1∪A2∪A3|=|A1|+|A2|+|A3|－|A1∩A2|－|A1∩A3| －|A2∩A3|+|A1∩A2∩A3|. 一般包含排斥原理又称为容斥原理. 例3.3.1有120个学生参加考试，这次考试有3道题A,B,C，考试结果如下： 12个学生3道题都做对了，20个学生做对A,B两道题，16个学生做对A,C两道题，28个学生做对B,C两道题，做对A题的有48个学生，做对B题的有56个学生，还有16个学生一道题也没做对.求做对C题的学生有多少个？ 解设做对A题的学生为P1,做对B题的学生为P2,做对C题的学生为P3,由题意，根据容斥原理可知 |P1∩P2∩P3|=12,|P1∩P2|=20,|P1∩P3|=16,|P2∩P3|=28， |P1|=48,|P2|=56,|P1∪P2∪P3|=16,所以|P1∪P2∪P3|=120－16=104， 而 |P1∪P2∪P3|=|P1|+|P2|+|P3|－|P1∩P2|－|P1∩P3| －|P2∩P3|+|P1∩P2∩P3|， 因此|P3|=52，所以做对了C题的学生有52人. [3][1]习题3[3]习题3 1. 设A,B为集合，试确定下列各式成立的充分必要条件： (直接写结论就可以) (1) A－B=B; (2) A－B=B－A; (3) A∩B=B∪A; (4) AB=A. 2. 证明(A∪B=A∪C)∧(A∩B=A∩C)B=C. 3. 求下列集合的幂集: (1) A={a,b,c}，则P(A)=; (2) B={1,{2,3}}，则P(B)=; (3) C={}，则P(C)=; (4) D={,{}}，则P(D)=. 4. 设E=1,2,3,4,5,6,A=1,4,B=1,2,5,C=2,4，求下列集合(用枚举法写出集合的具体元素): （1） A∩BC； （2） (A∩B)∪CC； （3） (A∩B)C； （4） P(A)∩P(B)； （5） P(A)－P(B). 5. 用枚举法表示下面的集合： （1） S1=x|x=2∨x=5； （2） S2=x|x∈Z∧3（3） S3=x|x∈R∧x2－1=0∧x>3; （4） S4=〈x,y〉|x,y∈Z∧0≤x≤2∧－1≤y≤0. 6.设A=2,a,3,4,B=,4,a,3,C=1,2,1.求:(1) AB=; (2) P(C)=. 7. 设S={2,a,{3},4}，R={{a},3,4,1},指出下面的写法哪些是对的，哪些是错的. （1） {a}∈S;（2） {a}∈R;（3） {a,4{3}}S; （4） {{a},1,3,4}R;（5） S=R;（6） {a}S; （7） {a}R;（8） R;（9） {{a}}R; （10） {}S;（11） ∈R;（12） {{3},4}.第4章二元关系和函数第3章讨论了集合及集合的运算，本章研究集合内元素的关系以及集合间元素的关系，这就是关系和函数.关系和函数是很重要的数学概念，它在计算机科学技术中的许多方面有着重要的应用，如数据结构、数据库、情报检索、算法分析等.本章主要讨论二元关系理论. 4.1集合的笛卡儿积与二元关系 定义4.1.1由两个元素x和y(允许x=y)按一定顺序排列成的二元组，称为一个有序对或序偶，记作〈x,y〉，其中x是它的**元素，y是它的第二元素. 有序对〈x,y〉具有如下性质： 1. 当x≠y时，〈x,y〉≠〈y,x〉. 2. 〈x1,y1〉=〈x2,y2〉 的充要条件是x1=x2 且 y1=y2. 上述两条性质是二元集x,y所不具备的.例如，当x≠y时，有x,y=y,x.原因在于集合中的元素是无序的，而有序对中的元素是有序的. 例4.1.1已知〈x+2,3〉=〈3,2x+y〉，求x和y. 解由有序对相等的充要条件，有x+2=3, 2x+y=3.解得x=1，y=1. 定义4.1.2设A，B为两个集合，所有**元素属于A,第二元素属于B的序偶所组成的集合,称为集合A和集合B的笛卡儿乘积.记作A×B,即 A×B={〈x,y〉|x∈A∧y∈B}. 例4.1.2设A={a,b},B=0,1,C=,试求A×B,B×A,A×A,B×B,C×C,A×B×C和A×B×C. 解A×B=〈a,0〉,〈a,1〉,〈b,0〉,〈b,1〉,B×A=〈0,a〉,〈1,a〉,〈0,b〉,〈1,b〉, A×A=〈a,a〉,〈a,b〉,〈b,b〉,〈b,a〉, B×B=〈0,0〉,〈0,1〉,〈1,0〉,〈1,1〉, C×C=〈,〉, A×B×C=〈〈a,0〉,〉,〈〈a,1〉,〉,〈〈b,0〉,〉,〈〈b,1〉,〉, B×C=〈0,〉,〈1,〉, A×(B×C)={〈a,〈0,〉〉,〈a,〈1,〉〉,〈b,〈0,〉〉,〈b,〈1,〉〉}.[3]第4章二元关系和函数[3][1]4.1集合的笛卡儿积与二元关系[3]如果A=m，B=n，则A×B=mn.从例4.1.2不难看出笛卡儿积具有如下性质: 性质1对任意集合A，根据定义有 A×=，×A=. 性质2一般地说，笛卡儿积元素不满足交换律，即 A×B≠B×A(当A≠∧B≠∧A≠B时). 性质3笛卡儿积运算不满足结合律，即 A×B×C≠A×B×C(当A≠∧B≠∧C≠时). 性质4笛卡儿积运算对并和交运算满足分配律，即 A×(B∪C)=A×B∪A×C， (B∪C)×A=B×A∪C×A， A×(B∩C)=A×B∩A×C， (B∩C)×A=B×A∩C×A. 证明我们只证明**个等式.任取〈x,y〉∈A×B∪C，则有 〈x,y〉∈A×B∪Cx∈A∧y∈B∪C x∈A∧(y∈B∨y∈C) (x∈A∧y∈B)∨(x∈A∧y∈C) 〈x,y〉∈A×B∨〈x,y〉∈A×C 〈x,y〉∈A×B∪A×C, 所以有A×(B∪C)=A×B∪A×C. 类似地可以证明其他情形. 性质5AC∧BDA×BC×D. 采用命题演算的方法，可以证明性质5.该证明留给读者考虑. 值得注意的是,性质5的逆命题不成立,分以下几种情况讨论: (1) 当A=B=时,显然有AC且BD成立. (2) 当A≠且B≠时,也有AC且BD成立.具体证明如下: 任取x∈A,由于B≠,则存在y∈B.所以有〈x,y〉∈A×BC×D.由笛卡儿积的定义有x∈C且y∈D. (3) 当A=但B≠时,有AC成立,但不一定有BD成立.例如,取A=,B={1},C={2},D={3}. (4) 当A≠但B=时，有BD成立，不一定有AC成立.例如，A={1}，B=，C={2}，D={3}. 例4.1.3设A=1,2，求PA×A. 解P(A)={,1,{2},{1,2}},P(A)×A={〈,1〉,〈,2〉,〈{1},1〉,〈{1},2〉,〈{2},1〉,〈{2},2〉,〈{1,2},1〉,〈{1,2},2〉}. 例4.1.4设A，B，C，D为任意集合，判断以下命题是否为真，并说明理由. (1) A×B=A×CB=C; (2) A－B×C=(A－B)×(A－C); (3) A=B∧C=DA×C=B×D; (4) 存在集合A，使得AA×A. 解(1) 不一定为真，当A=,B={1},C={2}时,有A×B==A×C，但是B≠C. (2) 不一定为真，当A=B={2}，C={3}时,有 A－(B×C)=2－〈2,3〉={2}， A－B×(A－C)=×{2}=. (3) 为真. (4) 为真.取集合A=时，有AA×A. 定义4.1.3如果一个集合满足下列条件之一：