第一章集合new

离散数学侯爱民东莞理工学院计算机科学与技术系前言离散数学是计算机学科的基础理论的核心课程。是学好数据结构、数据库、操作系统、形式语言、并行处理、人工智能等知识的理论基础。离散数学的特点——内容广泛，抽象理论多。离散数学的贡献——提高学生的抽象思维、逻辑思维和创新思维。离散数学的学习方法——类似高等数学：清楚概念，多做习题。第一章集合学习重点：1、集合、子集、空集、全集、补集、幂集等概念。2、集合的基本运算：并、交、差、对称差。3、集合代数的有关公式及证明。4、在组合计数中广泛使用的包含排斥原理。第1.1节集合的基本概念第1.1.1节集合概念及表示方法第1.1.2节子集和空集第1.1.3节全集和补集第1.1.4节幂集第1.1.1节集合概念及表示方法集合的概念：只能给出说明性的描述。集合就是具有某种特点的研究对象的聚合。其中每一个研究对象称为这个集合的元素。通常用大写字母表示集合，小写字母表示元素。若a是集合A中的元素，则记为aA。称元素a属于集合A。若a不是集合A中的元素，则记为aA。称元素a不属于集合A。第1.1.1节集合概念及表示方法列举法（也称枚举法）是把集合中的所有元素置于花括号内，元素之间用逗号隔开。即在集合中列举出所有的元素。很显然，这种方法只能表示有穷集合。例1：集合A含5个元素，它们分别是2,3,5,7,13。用列举法可把A表示成：A={2,3,5,7,13}显然，2A，而4A。第1.1.1节集合概念及表示方法特征法（也称谓词法）是以某个小写的英文字母来统一表示该集合的元素，并指出这类元素的共同特征。例2：B={x|x是素数，x15}花括号内的符号“|”读作“系指”，逗号读作“并且”。因此，集合B是由小于15的素数组成。集合B的元素就是2,3,5,7,13。可见集合B和列举法提到的集合A的元素完全相同。第1.1.2节子集和空集定义1.1.1：设A，B是集合，如果A中每一个元素又都是B中的元素，则称A是B的子集，也称B包含A或A包含于B中，记作BA或AB说明：1.如果A不是B的子集，即A中至少有一个元素不属于B，则称B不包含A或A不包含于B中，记作B⊉A或A⊈B第1.1.2节子集和空集2.如果A是B的子集，但A和B不相等，即在B中总有一些元素不属于A，则称A为B的真子集，记作BA或AB3.当两个集合X和Y的元素相同时，称这两个集合相等，记作X=Y。定理1.1.1：集合A和B相等的充分必要条件是：AB且AB。第1.1.2节子集和空集说明：1.不含有任何元素的集合称为空集，记作或{}。2.空集是任何集合的子集。3.集合中的元素也可以是另一个集合。4.一般，属于关系“∈”是元素和集合之间的关系；包含关系“”是集合和集合之间的关系。但集合也可以属于（∈）另一个集合。第1.1.2节子集和空集例3：设A={a，b}，B={a，b，{a，b}}。则：a∈A，b∈A。a∈B，b∈B，{a，b}∈B。AB，A∈B。第1.1.3节全集和补集研究对象的全体称为全集，记作∪。设A是集合，由属于全集∪但不属于集合A的元素构成的集合称为A的补集，记作A（或~A）。第1.1.3节全集和补集说明：例1：全集∪是全体正整数构成的集合。若集合A={x|x是正偶数}。则A的补集~A={x|x是正奇数}。例2：全集∪={1,2,3,4,5,6,7,8,9,10}。若集合A={1,2,3,4}。则A的补集~A={5,6,7,8,9,10}。第1.1.4节幂集定义1.1.2：设A是集合，由A的所有子集作为元素构成的集合称为A的幂集，记作(A)。例1：设A={a，b}，则A的子集:,{a},{b},{a,b}。A的幂集：(A)={,{a},{b},{a,b}}当一个集合的元素个数为有限时，称该集合为有限集，集合中的元素个数为无限时，称该集合为无限集。有限集A中元素的个数称为有限集A的基。记作|A|。第1.1.4节幂集定理1.1.2：设A是有限集，且|A|=n，则|(A)|=2n。证明：由排列组合的知识可知|(A)|=C0n+C1n+C2n+…+Cn-1n+Cnn又由二项式定理可知(a+b)n=C0n•an+C1n•an-1•b+C2n•an-2•b2+…+Cn-1n•a1•bn-1+Cnn•bn若取a=b=1,则有:(1+1)n=C0n+C1n+…+Cnn由此证得|(A)|=2n。第1.1.4节幂集例2：A={a，b，c}，其幂集(A)=？第1.2节集合的基本运算第1.2.1节并第1.2.2节交第1.2.3节差第1.2.4节对称差第1.2.1节并定义1.2.1：设A和B是集合，由属于集合A或者属于集合B的所有元素构成的集合，称为A和B的并，记作A∪B，也即A∪B={x|x∈A或x∈B}例1：A={1，3，5}，B={2，3，4}，则：A∪B={1，2，3，4，5}。例2：A={a，b，c}，B={b，c，d，e}，则：A∪B={a，b，c，d，e}。第1.2.1节并“并”运算的文氏图：A∪BUAB第1.2.1节并“并”运算的性质：1、A∪B=B∪A2、A∪(B∪C)=(A∪B)∪C3、A∪A=A4、A∪=A5、A∪U=U第1.2.2节交定义1.2.2：设A和B是集合，由属于A，B两集合的所有共同元素构成的集合，称为A和B的交，记作A∩B，也即A∩B={x|x∈A且x∈B}例1：A={1，3，5}，B={2，3，4}，则：A∩B={3}。例2：A={a，b，c}，B={b，c，d，e}，则：A∩B={b，c}。第1.2.2节交“交”运算的文氏图：A∩BUAB第1.2.2节交“交”运算的性质：1、A∩B=B∩A2、A∩(B∩C)=(A∩B)∩C3、A∩A=A4、A∩=5、A∩U=A第1.2.2节交集合的并、交运算规律：设A,B,C为任意集合,则:幂等律A∪A=A,A∩A=A交换律A∪B=B∪A,A∩B=B∩A结合律(A∪B)∪C=A∪(B∪C)(A∩B)∩C=A∩(B∩C)同一律A∪=A,A∩U=A零律A∪U=U,A∩=第1.2.2节交并和交运算有着密切联系——分配律：定理1.2.1：设A，B，C是集合，则下列分配律成立A∩(B∪C)=(A∩B)∪(A∩C)A∪(B∩C)=(A∪B)∩(A∪C)证明：只证第一等式，第二等式的证明方法相同。（在黑板上演算）第1.2.2节交并和交运算有着密切联系——吸收律：定理1.2.2：设A，B是集合，则下列吸收律成立A∩(A∪B)=AA∪(A∩B)=A证明：只证第一等式，第二等式的证明方法相同。（在黑板上演算）第1.2.2节交并和交运算有着密切联系——迪•摩根律：定理1.2.3：设A，B是集合，则下列迪•摩根律成立(A∩B)=A∪B(A∪B)=A∩B证明：只证第一等式，第二等式的证明方法相同。（在黑板上演算）第1.2.2节交迪•摩根律的推广应用：对于3个集合A，B，C，则有：(A∩B∩C)=A∪B∪C(A∪B∪C)=A∩B∩C对于n个集合A1，A2，…，An，则有：(A1∩A2∩…∩An)=A1∪A2∪…∪An(A1∪A2∪…∪An)=A1∩A2∩…∩An第1.2.2节交以上的运算规律在证明其它等式中可直接引用,使得集合等式的运算可用代数的方式进行。例3：设A，B是集合，证明下列等式。（1）A∪(A∩B)=A∪B（2）(A∩B)∪(B∩A)∪(A∩B)=(A∪B)（3）(A∩B)∪(A∩B)=(A∪B)∩(A∪B)(在黑板上演算第(2)等式的证明过程）第1.2.3节差定义1.2.3:设A和B是集合，由所有属于A但不属于B的元素构成的集合，称为A减B的差，记作A-B，即A–B={x|x∈A且xB}例1：对于下列集合A={1，2，3，4}，B={3，4，5}，则：差集A-B={1，2}，B-A={5}例2：A={1，2，3}，B={4，5，6}，则：差集A-B={1，2，3}第1.2.3节差“差”运算的文氏图：UABA-B第1.2.3节差定理1.2.4:设A，B是集合，则A-B=A∩B。证明：（在黑板上演算）例3：设A、B、C是集合，证明(1)A-(B∩C)=(A-B)∪(A-C)(2)(A-B)∪(B-C)∪(C-A)=(A∪B∪C)∩(A∪B∪C)（在黑板上演算）第1.2.4节对称差定义1.2.4:设A，B是集合，由所有属于A但不属于B或者属于B但不属于A的元素构成的集合，称为A和B的对称差，记作AB，也即AB=(A–B)∪(B–A)例1：A={1，2，3，4}，B={3，4，5，6}，则：AB={1，2，5，6}，BA={1，2，5，6}。第1.2.4节对称差“对称差”运算的文氏图：ABUAB第1.2.4节对称差“对称差”运算的性质：1）AB=BA2）(AB)C=A(BC)3）AA=4）A=A5）AU=A第1.2.4节对称差定理1.2.5:设A，B是集合，则:AB=(A∪B)–(A∩B)。证明：（在黑板上演算）例2：(1)证明A∩(BC)=(A∩B)(A∩C)(2)设A，B是集合，若AB=，证明A=B。（在黑板上演算）集合运算性质的一些重要结果：1）A∪A=A，A∩A=A。等幂律2）A∪B=B∪A，A∩B=B∩A，AB=BA。交换律3）(A∪B)∪C=A∪(B∪C)，(A∩B)∩C=A∩(B∩C)，(AB)C=A(BC)。结合律4）A∩(B∪C)=(A∩B)∪(A∩C)A∪(B∩C)=(A∪B)∩(A∪C)。分配律5）A∪B=A∩B，A∩B=A∪B。迪•摩根律6）A=A。集合运算性质的一些重要结果：7）A∪A=U，A∩A=。补余律8）A∪=A，A∩U=A。同一律9）A∪U=U，A∩=。零一律10）A-B=A∩B。11）AB=(A-B)∪(B-A)=(A∪B)-(A∩B)。12）AA=。13）=U。14）U=。第1.3节包含排斥原理定理1.3.1:(容斥原理)设A，B为有限集合，则|A∪B|=|A|+|B|-|A∩B|证明:（用文氏图理解）a)当A和B不相交，即A∩B=φ，则：|A∪B|=|A|+|B|第1.3节包含排斥原理证明:b)当A和B相交不空，即A∩B≠φ，则：由，A∪B=A∪(B-A)，且A和(B-A)不相交，所以：|A∪B|=|A|+|B-A|。由，B=(B-A)∪(A∩B)，且B-A和A∩B不相交，所以：|B|=|(B-A)∪(A∩B)|=|(B-A)|+|(A∩B)|。于是有：|(B-A)|=|B|-|(A∩B)|。所以：|A∪B|=|A|+|B|-|(A∩B)|。第1.3节包含排斥原理三个有限集合A、B、C的包含排斥原理：|A∪B∪C|=|A|+|B|+|C|-|A∩B|-|A∩C|-|B∩C|+|A∩B∩C|四个有限集合A、B、C、D的包含排斥原理：|A∪B∪C∪D|=|A|+|B|+|C|+|D|-|A∩B|-|A∩C|-|A∩D|-|B∩C|-|B∩D|-|C∩D|+|A∩B∩C|+|A∩B∩D|+|A∩C∩D|+|B∩C∩D|-|A∩B∩C∩D|第1.3节包含排斥原理例1：某班有学生38人，其中有20人参加合唱队，有16人参加话剧队，有8人既参加合唱队又参加话剧队。问有多少人既不参加合唱队也不参加话剧队？解：设A表示参加合唱队的学生的集合，B表示参加话剧队的学生的集合。则：|A|=20，|B|=16，|A∩B|=8所以，|A∪B|=|A|+|B|-|A∩B|=20+16-8=28所以，参加了活动（指合唱队或话剧队）的学生人数为28人，剩下者=38-28=10第1.3节包含排斥原理例2：某班有72人，其中选学PASCAL语言的有30人，选学C语言的有36人，选学FORTRAN语言的有29人；选学PASCAL和C语言的有12人；3门语言都选学的有5人；仅仅选学FORTRAN语言的有7人，试求：（1）仅选学两门语言的人数。（2）这3门语言都不选学的人数。解：(黑板上演算)第1.3节包含排斥原理例3：求1～250间能被2，3，5，7中任一个数