下载文档原格式
离散数学结构第6章集合代数第六章集合代数1. 集合，相等，（真）包含，⼦集，空集，全集，幂集2. 交，并，（相对和绝对）补，对称差，⼴义交，⼴义并3. ⽂⽒图，有穷集计数问题4. 集合恒等式（等幂律，交换律，结合律，分配律，德·摩根律，吸收律，零律，同⼀律，排中律，⽭盾律，余补律，双重否定律，补交转换律等）学习要求1. 熟练掌握集合的⼦集、相等、空集、全集、幂集等概念及其符号化表⽰2. 熟练掌握集合的交、并、（相对和绝对）补、对称差、⼴义交、⼴义并的定义及其性质3. 掌握集合的⽂⽒图的画法及利⽤⽂⽒图解决有限集的计数问题的⽅法4. 牢记基本的集合恒等式（等幂律、交换律、结合律、分配律、德·摩根律、收律、零律、同⼀律、排中律、⽭盾律、余补律、双重否定律、补交转换律）5. 准确地⽤逻辑演算或利⽤已知的集合恒等式或包含式证明新的等式或包含式6.1 集合的基本概念⼀．集合的表⽰集合是不能精确定义的基本概念。
直观地说，把⼀些事物汇集到⼀起组成⼀个整体就叫集合，⽽这些事物就是这个集合的元素或成员。
例如：⽅程x2－1＝0的实数解集合；26个英⽂字母的集合；坐标平⾯上所有点的集合；……集合通常⽤⼤写的英⽂字母来标记，例如⾃然数集合N(在离散数学中认为0也是⾃然数)，整数集合Z，有理数集合Q，实数集合R，复数集合C等。
表⽰⼀个集合的⽅法有两种：列元素法和谓词表⽰法，前⼀种⽅法是列出集合的所有元素，元素之间⽤逗号隔开，并把它们⽤花括号括起来。
例如A={a，b，c，…，z}Z={0，±1，±2，…}都是合法的表⽰。
谓词表⽰法是⽤谓词来概括集合中元素的属性，例如集合B＝{x|x∈R∧x2－1＝0}表⽰⽅程x2－1＝0的实数解集。
许多集合可以⽤两种⽅法来表⽰，如B也可以写成{-1，1}。
但是有些集合不可以⽤列元素法表⽰，如实数集合。
集合的元素是彼此不同的，如果同⼀个元素在集合中多次出现应该认为是⼀个元素，如{1，1，2，2，3}＝{1，2，3}集合的元素是⽆序的，如{1，2，3}＝{3，1，2}在本书所采⽤的体系中规定集合的元素都是集合。
第六章集合代数§1 集合的基本概念集合用大写英文字母标记，A，B，C，…特别地，分别用N、Z、Q、R、C标记全体自然数的集合、全体整数的集合、全体有理数的集合、全体实数的集合、全体复数的集合。
元素用小写英文字母标记，a，b，c，…x∈A：x是A的元素，称x属于A。
x∉A：x不是A的元素，称x不属于A。
列元素法：{a1, a2, …, a n, …}谓词表示法：{x| F(x)}注①集合中的元素每个只写一次②集合中的元素不计排列次序A⊆B：A是B的子集，称A被B包含A B：A不是B的子集，称A不被B包含A=B ⇔A⊆B∧B⊆A：A与B相等A⊂B ⇔A⊆B∧A≠B：A是B的真子集N⊆Z⊆Q⊆R⊆C空集：是任意集合的子集，记为∅。
有限集，无限集n元集，k元子集n元集有2n个子集集合A的幂集P(A)（或2A）全集：E§2 集合的运算并：A∪B ={x| x∈A∨x∈B}交：A∩B ={x| x∈A∧x∈B}差（B对A的相对补集）：A-B ={x| x∈A∧x∉B} 对称差：A⊕B=(A-B)(∪B-A)=(A∪B)-(A∩B)绝对补集（简称A的补集）：∼A=A=E-A，文氏图：大矩形表示全集E，内部的圆表示不同集合。
例已知24人中，会英语的有13人，会日语的有5人，会德语的有10人，会法语的有9人。
其中，同时会英语和日语的有2人，同时会英语和德语、同时会英语和法语、同时会德语和法语的各有4人；此外，会日语的人不会德语和法语。
求只会英语、日语、德语、法语中一种语言的人数和同时会三种语言的人数。
解：设同时会三种 语言有x 人，只会只会 英语、法语、德语中一 种语言的人数分别为y 1、y 2、y 3人，则根据文氏图可得1231232(4)2132(4)92(4)103(4)24519y x x y x x y x x y y y x x +−++=⎧⎪+−+=⎪⎨+−+=⎪⎪+++−+=−=⎩解出x =1，y 1=4，y 2=2，y 3=3。
《离散数学》教学大纲（Discrete Mathematics）适用专业：电子信息类课程类别：学科基础课课程学时：48课程学分：3.0先修课程：高等数学、线性代数等一、课程简介离散数学是研究离散量的结构及其相互关系的数学学科，是现代数学的一个重要分支，是计算机科学中基础理论的核心课程，是计算机科学与技术的支撑学科。
它在计算机科学与技术领域有着广泛的应用，同时离散数学也是计算机专业的许多专业课程，如程序设计语言、数据结构、操作系统、编译技术、人工智能与机器人、数据库、网络、计算机图形学、算法设计与分析、理论计算机科学基础等必不可少的先行课程。
通过离散数学的学习，不但可以掌握离散结构的描述工具和处理方法，为后续课程的学习创造条件，而且可以提高抽象思维和严格的逻辑推理能力，为将来参与创新性的研究和开发工作打下坚实的基础。
二、教学目的与任务离散数学是一门培养学生缜密思维、严格推理，具有综合归纳分析能力的课程。
通过本课程的学习，使学生有一定的严格逻辑推理与抽象思维能力，掌握离散量的处理及运算技能，能够将离散数学应用到解决计算机技术中的实际问题中。
不仅能为学生奠定计算机科学的专业基础，并且能为将后续课程的学习及将来开发软、硬件技术及研究、应用提供有力的工具。
三、课程内容第1章命题逻辑的基本概念1.1命题与联结词1.2命题公式及其赋值第2章命题逻辑等值演算2.1等值式2.2析取范式与合取范式* 2.3联结词的完备集* 2.4可满足性问题与消解法第3章命题逻辑的推理理论3.1推理的形式结构3.2自然推理系统P3.3消解证明法第4章一阶逻辑基本概念4.1一阶逻辑命题符号化4.2一阶逻辑公式及其解释第5章一阶逻辑等值演算与推理5.1一阶逻辑等值式与置换规则5.2一阶逻辑前束范式* 5.3一阶逻辑的推理理论第6章集合代数6.1集合的基本概念6.2集合的运算6.3有穷集的计数6.4集合恒等式第7章二元关系7.1有序对与笛卡儿积7.2二元关系7.3关系的运算7.4关系的性质7.5关系的闭包7.6等价关系与划分7.7偏序关系第8章函数8.1函数的定义与性质8.2函数的复合与反函数* 8.3双射函数与集合的基数* 8.4一个电话系统的描述实例第14章图的基本概念14.1图14.2通路与回路14.3图的连通性14.4图的矩阵表示* 14.5图的运算第15章欧拉图与哈密顿图15.1欧拉图15.2哈密顿图15.3最短路问题、中国邮递员问题与货郎担问题第16章树16.1无向树及其性质16.2生成树16.3根树及其应用三、课程学时分配、教学内容与教学基本要求四、教学方法与教学手段说明该课程教学方式主要有：课堂教学、交互学习、课后作业。
第六章集合代数1. 集合，相等，（真）包含，子集，空集，全集，幂集2. 交，并，（相对和绝对）补，对称差，广义交，广义并3. 文氏图，有穷集计数问题4. 集合恒等式（等幂律，交换律，结合律，分配律，德·摩根律，吸收律，零律，同一律，排中律，矛盾律，余补律，双重否定律，补交转换律等）学习要求1. 熟练掌握集合的子集、相等、空集、全集、幂集等概念及其符号化表示2. 熟练掌握集合的交、并、（相对和绝对）补、对称差、广义交、广义并的定义及其性质3. 掌握集合的文氏图的画法及利用文氏图解决有限集的计数问题的方法4. 牢记基本的集合恒等式（等幂律、交换律、结合律、分配律、德·摩根律、收律、零律、同一律、排中律、矛盾律、余补律、双重否定律、补交转换律）5. 准确地用逻辑演算或利用已知的集合恒等式或包含式证明新的等式或包含式6.1 集合的基本概念一．集合的表示集合是不能精确定义的基本概念。
直观地说，把一些事物汇集到一起组成一个整体就叫集合，而这些事物就是这个集合的元素或成员。
例如：方程x2－1＝0的实数解集合；26个英文字母的集合；坐标平面上所有点的集合；……集合通常用大写的英文字母来标记，例如自然数集合N(在离散数学中认为0也是自然数)，整数集合Z，有理数集合Q，实数集合R，复数集合C等。
表示一个集合的方法有两种：列元素法和谓词表示法，前一种方法是列出集合的所有元素，元素之间用逗号隔开，并把它们用花括号括起来。
例如A={a，b，c，…，z}Z={0，±1，±2，…}都是合法的表示。
谓词表示法是用谓词来概括集合中元素的属性，例如集合B＝{x|x∈R∧x2－1＝0}表示方程x2－1＝0的实数解集。
许多集合可以用两种方法来表示，如B也可以写成{-1，1}。
但是有些集合不可以用列元素法表示，如实数集合。
集合的元素是彼此不同的，如果同一个元素在集合中多次出现应该认为是一个元素，如{1，1，2，2，3}＝{1，2，3}集合的元素是无序的，如{1，2，3}＝{3，1，2}在本书所采用的体系中规定集合的元素都是集合。
元素和集合之间的关系是隶属关系，即属于或不属于，属于记作∈，不属于记作，例如A＝{a，{b，c}，d，{{d}}}这里a∈A，{b，c}∈A，d∈A，{{d}}∈A，但b A，{d} A. b和{d}是A的元素的元素。
可以用一种树形图来表示这种隶属关系，该图分层构成，每个层上的结点都表示一个集合，它的儿子就是它的元素。
上述集合A的树形图如图6.1所示。
图中的a，b，c，d也是集合，由于所讨论的问题与a，b，c，d的元素无关，所以没有列出它们的元素。
鉴于集合的元素都是集合这一规定，隶属关系可以看作是处在不同层次上的集合之间的关系。
为了体系上的严谨性，我们规定：对任何集合A都有A A。
二．集合之间的关系下面考虑在同一层次上的两个集合之间的关系。
定义6.1设A，B为集合，如果B中的每个元素都是A中的元素，则称B是A的子集合，简称子集。
这时也称B被A包含，或A包含B，记作B A。
如果B不被A包含，则记作B A。
包含的符号化表示为B A x(x∈B→x∈A)例如N Z Q R C，但Z N。
显然对任何集合A都有A A。
隶属关系和包含关系都是两个集合之间的关系，对于某些集合可以同时成立这两种关系。
例如A＝{a，{a}}和{a}既有{a}∈A，又有{a}A。
前者把它们看成是不同层次上的两个集合，后者把它们看成是同一层次上的两个集合，都是正确的。
定义6.2设A，B为集合，如果A B且B A，则称A与B相等，记作A＝B。
如果A与B不相等，则记作A≠B。
相等的符号化表示为A＝B A B∧B A定义6.3设A，B为集合，如果B A且B≠A，则称B是A的真子集，记作B A。
如果B不是A的真子集，则记作B A。
真子集的符号化表示为B A B A∧B≠A例如N Z Q R C，但N N。
定义6.4不含任何元素的集合叫做空集，记作。
空集可以符号化表示为＝{x|x≠x}。
例如{x|x∈R∧x2+1=0}是方程x2+1=0的实数解集，因为该方程无实数解，所以是空集。
定理6.1空集是一切集合的子集。
证：任何集合A，由子集定义有A x(x∈→x∈A)右边的蕴涵式因前件假而为真命题，所以A也为真。
推论空集是唯一的。
证：假设存在空集1和2，由定理6.1有1 2 ，21。
根据集合相等的定义，有1＝2。
含有n个元素的集合简称n元集，它的含有m(m≤n)个元素的子集叫做它的m元子集。
任给一个n元集，怎样求出它的全部子集呢？举例说明如下。
例6.1 A＝{1,2,3}，将A的子集分类：0元子集，也就是空集，只有一个：；1元子集，即单元集：{1}，{2}，{3}；2元子集：{1,2}，{1,3}，{2,3}；3元子集：{1,2,3}。
一般地说，对于n元集A，它的0元子集有个，1元子集有个，…，m元子集有个，…，n元子集有个。
子集总数为+++…+＝2n个。
定义6.5设A为集合，把A的全部子集构成的集合叫做A的幂集，记作P(A)(或PA，2A)。
幂集的符号化表示为P(A)＝{x|x A}对于例6.1中的集合A有P(A)＝{，{1}，{2}，{3}，{1，2}，{1，3}，{2，3}，{1，2，3}}不难看出，若A是n元集，则P(A)有2n个元素。
定义 6.6在一个具体问题中，如果所涉及的集合都是某个集合的子集，则称这个集合为全集，记作E。
全集是有相对性的，不同的问题有不同的全集，即使是同一个问题也可以取不同的全集。
例如在研究平面上直线的相互关系时，可以把整个平面(平面上所有点的集合)取作全集，也可以把整个空间(空间上所有点的集合)取作全集。
一般地说，全集取得小一些，问题的描述和处理会简单些。
6.2 集合的运算一．集合的基本运算集合的基本运算有并，交，相对补和对称差。
定义6.7设A，B为集合，A与B的并集A∪B，交集A∩B，B对A的相对补集A－B分别定义如下：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中的元素构成，A∩B由A和B中的公共元素构成，A－B由属于A但不属于B的元素构成。
例如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是不相交的。
两个集合的并和交运算可以推广成n个集合的并和交：A1∪A2∪…∪A n＝{x|x∈A1∨x∈A2∨…∨x∈A n}A1∩A2∩…∩A n＝{x|x∈A1∧x∈A2∧…∧x∈A n}上述的并和交可以推广成n个集合的并和交：＝A1∪A2∪…∪A n＝A1∩A2∩…∩A n并和交运算还可以推广到无穷多个集合的情况：＝A1∪A2∪…＝A1∩A2∩…定义6.8设A，B为集合，A与B的对称差集A B定义为：A B＝(A－B)∪(B－A)例如A＝{a，b，c}，B＝{b，d}，则A B＝{a，c，d}。
对称差运算的另一种定义是A B＝(A∪B)－(A∩B)可以证明这两种定义是等价的，证明可留作练习。
在给定全集E以后，A E，A的绝对补集～A定义如下：定义6.9～A＝E－A＝{x|x∈E∧x A}二．有穷计数集使用文氏图可以很方便地解决有穷集的计数问题。
首先根据已知条件把对应的文氏图画出来。
一般地说，每一条性质决定一个集合。
有多少条性质，就有多少个集合。
如果没有特殊说明，任何两个集合都画成相交的，然后将已知集合的元素数填入表示该集合的区域内。
通常从n个集合的交集填起，根据计算的结果将数字逐步填入所有的空白区域。
如果交集的数字是未知的，可以设为x。
根据题目中的条件，列出一次方程或方程组，就可以求得所需要的结果。
例6.2对24名会外语的科技人员进行掌握外语情况的调查。
其统计结果如下：会英、日、德和法语的人分别为13，5，10和9人，其中同时会英语和日语的有2人，会英、德和法语中任两种语言的都是4人。
已知会日语的人既不懂法语也不懂德语，分别求只会一种语言(英、德、法、日)的人数和会三种语言的人数。
解令A，B，C，D分别表示会英、法、德、日语的人的集合。
根据题意画出文氏图如图6.3所示。
设同时会三种语言的有x人，只会英、法或德语一种语言的分别为y1，y2和y3人。
将x和y1，y2，y3填入图中相应的区域，然后依次填入其它区域的人数。
根据已知条件列出方程组如下：解得x＝1，y1＝4，y2＝2，y3＝3。
例6.3求1到1000之间(包含1和1000在内)既不能被5和6，也不能被8整除得数有多少个。
解设S＝{x|x∈Z∧1≤x≤1000}A＝{ x|x∈S∧x可被5整除}B＝{ x|x∈S∧x可被6整除}C＝{ x|x∈S∧x可被8整除}用|T|表示有穷集T中得元素数，表示小于等于x的最大整数，lcm(x1,x2,…,x n)表示x1,x2,…,x n的最小公倍数，则有|A|=＝200|B|=＝166|C|=＝125|A∩B|＝＝33|A∩C|＝＝25|B∩C|＝＝41|A∩B∩C|＝＝8将这些数字依次填入文氏图，得到图6.4.由图可知，不能被5，6和8整除的数有1000－(200+100＋33＋67)＝600个。
三．广义交和广义并以上定义的并和交运算称为初级并和初级交。
下面考虑推广的并和交运算，即广义并和广义交。
定义6.10设A为集合，A的元素的元素构成的集合称为A的广义并，记为∪A。
符号化表示为∪A＝{x|z(z∈A∧x∈z)}。
例6.4设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,…,A n}，则∪A＝A1∪A2∪…∪A n。
类似地可以定义集合的广义交。
定义6.11设A为非空集合，A的所有元素的公共元素构成的集合称为A的广义交，记为∩A。
符号化表示为∩A＝{x|z(z∈A→x∈z)}考虑例6.4中的集合，有∩A＝{a}，∩B＝{a}，∩C＝a∩{c，d}细心的读者一定会注意到在定义6.11中特别强调了A是非空集合。
对于空集可以进行广义并，即∪＝。
但空集不可以进行广义交，因为∩不是集合，在集合论中是没有意义的。
和广义并类似，若A＝{A1,A2,…,A n}，则∩A＝A1∩A2∩…∩A n。
在后面的叙述中，若只说并或交，则这都是指集合的初级并或初级交；如果在并或交前边冠以“广义”两个字，则指集合的广义并或广义交。
为了使得集合表达式更为简洁，我们对集合运算的优先顺序做如下规定：称广义并，广义交，幂集，绝对补运算为一类运算，并，交，相对补，对称差运算为二类运算。
