离散数学精讲-第四到第六章

离散数学讲义之第二部分集合论2集合论简介•集合是数学中最基本的概念，又是数学各分支、自然科学及社会科学各领域的最普遍采用的描述工具。•集合论在开关理论、形式语言、有限状态机、编译原理、数据库原理等领域中有着广泛的应用。•本篇介绍集合论的基础知识，主要内容包括集合的基本运算、序偶、关系、函数、基数等。3主要知识点关联图有序化集合性质互异性无序性确定性集合关系集合闭包关系等价关系范式元素计数表示方法哈斯图集合运算笛卡尔积二元关系关系图序偶相容关系范式偏序关系合取范式集合分划商集关系性质等价式函数等价类集合基数等势优势函数性质不可数集合一满射可数集双射单射关系矩阵闭包运算复合函数函数运算逆函数运算规律容斥原理特殊二元关系覆盖幂集4第二篇集合论目录第4章集合及其运算4.1集合的概念及其表示4.2集合的基本运算4.3集合中元素的计数4.4集合的应用习题四实验四集合的基本运算第5章二元关系5.1集合的笛卡尔积5.2二元关系5.3等价关系与集合的划分5.4相容关系与集合的覆盖*5.5偏序关系5.6关系的应用习题五实验五求关系的闭包第6章函数6.1函数的概念6.2逆函数与复合函数习题六实验六函数的图形可视化第7章集合的基数**7.1集合的等势与优势7.2基数、可数集与不可数集习题七实验七：自然数性质的可视化表示5第4章集合及其运算主要内容：集合的基本概念（属于、包含、幂集、空集、文氏图等）；集合的基本运算（并、交、补、差等）；集合恒等式（集合运算的算律、恒等式的证明方法）。教学要求：理解集合的概念，掌握集合的各种运算，掌握集合的恒等式证明方法。重点：集合恒等式难点：集合恒等式的证明实践活动：集合运算的实现64.1集合的概念及其表示4.1.1集合的概念集合的定义•集合(Set)是指具有共同性质的或适合一定条件的事物的全体。•组成集合的对象称为集合的成员（member）或元素（elements）。7常见的数的集合•N—自然数集合•Z—整数集合•Q—有理数集合•R—实数集合•C—复数集合8集合的表示法•枚举法----通过列出全体元素来表示集合•谓词法----通过谓词概括集合元素的性质•图示法----用一个圆来表示集合,圆中的点表示集合中的元素.实例：枚举法自然数集合N={0,1,2,3,…}谓词法S={x|x是实数，x21=0}9集合的元素三个重要的性质：•互异性-集合的元素是彼此不同的，如果同一个元素在集合中多次出现应该认为是一个元素。例如：{1，1，2，2，3}＝{1，2，3}•无序性-集合的元素是无序的。例如：{1，2，3}＝{3，1，2}•确定性-集合的元素是确定的10例4.1.1（1）一个班级里的全体学生构成一个集合；（2）平面上的所有点构成一个集合；（3）方程x2-1=0的实数解构成一个集合；（4）自然数的全体（包含0）构成一个集合，用N表示；（5）整数的全体构成一个集合，用Z表示；（6）有理数的全体构成一个集合，用Q表示；（7）实数的全体构成一个集合，用R表示；（8）复数的全体构成一个集合，用C表示；（9）还有正整数集合Z+，正有理数集合Q+，正实数集合R+；（10）还有非零整数集合Z*，非零有理数集合Q*，非零实数集合R*。（11）所有n阶实矩阵构成一个集合，用表示，即而所有n阶可逆实矩阵也构成一个集合，用表示。111212122212()|1nnnijnnnnaaaaaaaijnaaa，，RRM()nMRˆ()nRM11元素和集合之间的关系•元素和集合之间的关系是隶属关系，即属于或不属于，属于记作∈，不属于记作。•例如：A＝{a，{b，c}，d，{{d}}}a∈A，{b，c}∈A，d∈A，{{d}}∈A，bA，{d}A。b和{d}是A的元素的元素。•可以用一种树形图表示集合与元素的隶属关系。隶属关系可以看作是处在不同层次上的集合之间的关系。规定：对任何集合A都有AA。Aa{b,c}d{{d}}bc{d}d说明12集合与集合之间的关系定义4.1.1设A，B为集合，如果B中的每个元素都是A中的元素，则称B是A的子集合，简称子集(subset)。这时也称B被A包含，或A包含B，记作BA。包含的符号化表示:BAx(x∈B→x∈A)如果B不被A包含，则记作BA。例如：NZQRC，但ZN。显然对任何集合A都有AA。13隶属和包含的说明•隶属关系和包含关系都是两个集合之间的关系，对于某些集合可以同时成立这两种关系。•例如A＝{a，{a}}和{a}既有{a}∈A，又有{a}A。前者把它们看成是不同层次上的两个集合，后者把它们看成是同一层次上的两个集合。14集合相等(equal)定义4.1.2设A，B为集合，如果AB且BA，则称A与B相等，记作A＝B。•相等的符号化表示为：A＝BAB∧BA•如果A与B不相等，则记作A≠B。15真子集定义4.1.3设A，B为集合，如果BA且B≠A，则称B是A的真子集，记作BA。•真子集的符号化表示为BABA∧B≠A•如果B不是A的真子集，则记作BA。例如：NN16空集(emptyset)定义4.1.4不含任何元素的集合叫做空集，记作。空集的符号化表示为：＝{x|x≠x}。例如:{x|x∈R∧x2+1=0}是方程x2+1=0的实数解集，因为该方程无实数解，所以是空集。17空集的性质推论空集是唯一的。证明：假设存在空集1和2，由定理6.1有12，21。根据集合相等的定义，有1＝2。定理4.1.1空集是一切集合的子集。证明：任给集合A，由子集定义有Ax(x∈→x∈A)右边的蕴涵式因前件假而为真命题，所以A也为真。18n元集•含有n个元素的集合简称n元集，它的含有m(m≤n)个元素的子集叫做它的m元子集。例4.1.2A＝{1,2,3}，将A的子集分类：0元子集（空集）1元子集（单元集）{1}，{2}，{3}2元子集{1,2}，{1,3}，{2,3}3元子集{1,2,3}19幂集(powerset)•一般地说，对于n元集A，它的0元子集有个，1元子集有个，…，m元子集有个，…，n元子集有个。子集总数为nnn2n1n0n2CCCC0nC1nCmnCnnC定义4.1.5设A为集合，把A的全部子集构成的集合叫做A的幂集，记作P(A)(或2A)。幂集的符号化表示为P(A)＝{x|xA}若A是n元集，则P(A)有2n个元素。20全集在一个具体问题中，如果所涉及的集合都是某个集合的子集，则称这个集合为全集，记作E。说明全集是有相对性的，不同的问题有不同的全集，即使是同一个问题也可以取不同的全集。例如，在研究平面上直线的相互关系时，可以把整个平面(平面上所有点的集合)取作全集，也可以把整个空间(空间上所有点的集合)取作全集。一般地说，全集取得小一些，问题的描述和处理会简单些。214.2集合的运算定义4.2.1设A，B为集合，A与B的并集A∪B，A与B的交集A∩B，B对A的相对补集A－B分别定义如下：A∪B＝{x|x∈A∨x∈B}(unionset)A∩B＝{x|x∈A∧x∈B}(intersectionset)A－B＝{x|x∈A∧xB}(differenceset)举例设A＝{a，b，c}，B＝{a}，C＝{b，d}则有A∪B＝{a，b，c}，A∩B＝{a}，A－B＝{b，c}，B－A＝，B∩C＝说明如果两个集合的交集为，则称这两个集合是不相交的。例如B和C是不相交的。22定理4.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=BAB。证明：性质⑴，⑵，⑷，⑸，⑹由定义4.2.1立即可以得到。23⑶的证明：(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)。⑺的证明：必要性证明:所以AB。充分性证明:由⑹知BA∪B，现证明A∪BB所以有A∪B=B。()()()ABBxxAxxABxxB()()ABxxABxxB24定理4.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=AAB。证明略。25n个集合的并和交•两个集合的并和交运算可以推广成n个集合的并和交：A1∪A2∪…∪An＝{x|x∈A1∨x∈A2∨…∨x∈An}A1∩A2∩…∩An＝{x|x∈A1∧x∈A2∧…∧x∈An}上述的并和交可以简记为：n1iiA＝A1∩A2∩…∩Ann1iiA＝A1∪A2∪…∪An两个集合的并和交运算可以推广到无穷多个集合的情况：1iiA＝A1∩A2∩…1iiA＝A1∪A2∪…26交运算与并运算之间的关系定理4.2.3（分配律）设A,B,C为任意三个集合，满足（1）交运算对并运算的分配律（2）并运算对交运算的分配律()()()ABCABAC()()()ABCABAC27证明：（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)（2）略28定理4.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∪Φ=A29绝对补集定义4.2.3＝E－A＝{x|x∈E∧xA}•因为E是全集，x∈E是真命题，所以可以定义为：＝{x|xA}•例如:E＝{a，b，c，d}，A＝{a，b，c}＝{d}AAAA例4.2.4设E={1，2，3，4，5，6}，A={1，2，6}，B={1，4，5}则A-B={2，6}，={3，4，5}。A30定理4.2.5设A,B,C为任意三集合，则（1）对合律；（2）（3）（4）排中律；（5）矛盾律；（6）(De.MorgAn定理)①②（7）①②（8）（9）若，当且仅当①②AAEEAAEAAABABABABABAB()ABAAB()()()ABCABACABBA()BAAB31证明：由补运算的定义立即可得性质（1）～（5）。（6）的证明：①{}{}{()()}{()()}{}ABxxABxxABxxAxBxxAxBxxABAB②的证法与①类似，请读者自行证明。（7）的证明：①{()()}{()()}{}ABxxAxBxxAxBxxABAB；②()()()()AABAABAABAAABABAB。32（8）的证明：()()()()()()ABACABACABAC()()()ABAABCABCABC。（9）的证明：证明①必要性()()()()ABxxBxxBxxAxxA即BA；充分性()()()()BAxxAxxAxxBxxB即AB。证明②必要性()()()()ABBAABAABAAABAB；充分性()()AABA