集合论与图论第一章

1集合论与图论课时：30学时平时成绩30分，期末考试成绩70分。平时成绩考核方法：安排5次课堂作业，每次6分，共30分。课件邮箱:[e-mail]密码:201302252集合论和图论的应用范畴计算机科学领域的大多数基本概念和理论，几乎均采用集合论和图论的有关术语来描述。特别是在构建数学模型，算法描述时用的更广泛。集合论和图论都属于离散数学离散数学分为：数论、集合论、图论、近世代数、数理逻辑、组合数学3集合论和图论的应用范畴集合论与图论是：数据结构、算法设计与分析、计算机图形学、图像处理、密码学、编码理论、数据压缩、人工智能、生物信息工程等计算机课程的基础课程。****可以说《集合论和图论》是计算机方向所有软件课程的基础。4选用教材离散数学引论王义和著哈尔滨工业大学出版社5参考教材离散数学及其应用DiscreteMathematicsandItsApplicatioms(美)KennethH.Rosen著(英文版)机械工业出版社6参考教材集合论与图论耿素云编著北京大学出版社**7课程内容第一章:集合及其应用第二章:映射第三章:关系*第四章:无穷集合及其基数*第五章:模糊集合论第六章:图的基本概念第七章:树和割集第八章:连图度和匹配第九章:平面图和图的着色*第十章:有向图8第一章：集合及其应用1.1集合的概念1.2子集、集合的相等1.3集合的基本运算1.4余集、DeMorgan公式1.5笛卡尔乘积1.6有穷集合的基数91.1集合的概念1、集合的概念，通常把具有某种特定性质的具体的或抽象的对象的全体称做集合，其中的每个对象称为该集合中的元素。在朴素集合论体系中,“集合”是集合论中的一个原始概念，在朴素集合论中“集合”不能严格定义。常用大写英文字母A,B,C,...表示集合，用小写英文字母a,b,c,...,表示集合中的元素。10对于一个集合A来说，某一对象x或者是集合A的元素，或者不是，两者必居其一；如果x是集合A的元素，我们说x属于A，记为xA；如果x不是集合A的元素，我们说x不属于A，记为xA。集合的表示方法：列举法：列出集合中的全体元素，元素之间用逗号分开，然后用花括号括起来。例如：设A是由26个英文字母为元素的集合，则:A={a,b,c,d,...x,y,z}。1.1集合的概念11描述法：当集合A是具有某种性质P的元素全体时,我们往往用下面的形式表示A。A={x|x具有性质P}第三次数学危机!例如:A={x|x是中国人}1.1集合的概念12罗素悖论一天，某村理发师挂出一块招牌：“村里所有不自己理发的男人都由我给他们理发，我也只给这些人理发。”1.1集合的概念13属于理发师理发范围的集合可以表示成：A={x|x是村里不给自己理发的男人｝下面我们来看一下理发师自己是否属于集合A。把理发师设为x，如果xA，那么理发师就是不给自己理发的人，既然xA,那就属于理发师可以理发的范围，他自己给自己理发,又推出来xA；因此xAxA；产生予盾!1.1集合的概念14反过来如果xA；也就是说理发师是自己给自己理发的那些人，按定义，理发师不给这些人理发，这又推出理发师不给自己理发,xA,也产生矛盾。这就是第三次数学危机的来源，对集合论加以适当的修正，避免悖论。代表性成果是公理集合论。1.1集合的概念15对于集合的表示法应该注意以下几点：(2)集合中的元素不规定顺序；(1)集合中的元素是各不相同的；(3)集合的两种表示法有时是可以互相转化的。例如：正偶数集合用列举法可表示为：B={2,4,6,8,...}。用描述法可表示为：B={x|x0且x为偶数}或{x|x=2(k+1),k为非负整数}。1.1集合的概念**161.2子集、集合的相等定义1.1设A,B为二集合,若A中的每个元素都是B中的元素，则称A是B的子集合,简称子集。这时我们说A包含在B里(A包含于B),或B包含着A(B包含A),记作AB。其符号化形式为：ABx(xAxB)或者：ABx(xBxA)ABxA,xB(1)、子集的概念17如果A不是B的子集,则记作AB,读作A不包含于B,或B不包含A。AB若A，B，C是集合。x(xA并且xB)(1)AA(2)如果AB,且BC则:AC要注意“”与“”在概念上的区别。1.2子集、集合的相等对照上面这两个概念，比较集合{a}与{a,{a}}。{a}{a,{a}}。并且{a}{a,{a}}18定义1.2.2设A，B为二集合，若AB且x(xB并且xA),则称A是B的真子集,记作AB,读作A是B的真子集。设A,B,C为3个集合，下面3个命题为真：ABAB并且x(xB并且xA),(1)AA。(2)AB，则BA。(3)AB，且BC，则AC。(2)、真子集的概念例如：{a,b}是{a,b,c}的真子集。1.2子集、集合的相等19定义1.2.3设A,B是集合，如果AB且BA,则称A与B相等，记作A=B。其符号化形式为：A=Bx(xAxB)由子集与集合相等的概念，可知：(1)ABAB或者BA(2)ABAB且A≠B。(3)、集合相等的概念1.2子集、集合的相等20定义1.2.4不拥有任何元素的集合称为空集合，简称为空集，记作Ø。例如：A={x|x2+1=0xR}B={(x,y)|x2+y20x,yR}都是空集。{Ø}不是空集！{Ø}它是包含一个空集的集合。(4)、空集的概念1.2子集、集合的相等21定理1.2.1空集是一切集合的子集。1.2子集、集合的相等推论：空集是唯一的。由推论可知，空集无论以什么形式出现，它们都是相等的。{x|x2+1=0xR}={(x,y)|x2+y20x,yR}=Ø22定义1.2.4以集合为元素的集合称为集族。例如：在学校中，每个班级的学生形成一个集合，而全校的各个班级就形成一个集族。1.2子集、集合的相等(5)、集族的概念23设A1,A2,A3为集合,若令I={1,2,3}，则iI,i确定了一个唯一的集合Ai。于是集族{A1,A2,A3}又常写成{Ah}hI。若J为任一集合，对J中每个元素i有唯一的一个集合与之对应，这个集合记为Ai,那么所有这些Ai,形成的集族就用{Ai}iJ表示，其J称为标号集。那么{A1,A2,A3}为一个集族。1.2子集、集合的相等集族的表示方法：24例如：设p为一素数,Ak={x|x=k(modp)},k=0,1,...,p-1则A={A0,A1,...,Ap-1}是以{0,1,2,...p-1}为标号集的集族,也可以记为A={Ak}k{0,1,2,...p-1}1.2子集、集合的相等25定义1.2.5集合S的所有子集(包括空集Ø和S本身)形成的集族称为S的幂集,并记为2S,或记为P(S)。2S={A|AS}例1.2.3设S={1,2,3},求2S的步骤如下：A的幂集2S={Ø,{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}}。1.2子集、集合的相等(6)、幂集的概念26定理1.2.2设集合A的元素个数|A|=n(n为自然数),则|P(A)|=2n。证明:A的0个元素的子集个数为:C(n,0)|P(A)|=C(n,0)+C(n,1)+C(n,2)+...+C(n,n)A的1个元素的子集个数为:C(n,1)A的2个元素的子集个数为:C(n,2).........A的S个元素的子集个数为:C(n,n)=2n1.2子集、集合的相等27注意,2Ø={Ø}。在这里要区分Ø和{Ø}Ø{Ø}Ø为空集,而{Ø}是一个集族。Ø{Ø}Ø{Ø}。1.2子集、集合的相等**281.3集合的基本运算定义1.8设A,B为二集合，称由A和B所有元素组成的集合为A与B的并集,记作A∪B,称∪为并运算符，A∪B的描述法表示如下：A∪B={x|xA或者xB}。例1.3.1设A={x|xN并且5x10}，B={x|x10并且x为素数}，A∪B={2,3,5,6,7,8,9,10}。={5,6,7,8,9,10}∪{2,3,5,7}(1)、并集的概念29定理1.3.1设A,B,C为任意的三个集合1.交换律成立,2.幂等律成立,即A∪A=A;即A∪B=B∪A;3.∪A=A;4.A∪B=BAB。1.3集合的基本运算5.结合律成立,即(A∪B)∪C=A∪(B∪C);30将集合的并运算推广到多个集合的并集。A1∪A2∪...∪An定义为至少属于A1,A2,...,An中之一的那些元素构成的集合。若A1,A2,...,An,...是一个集合的无穷序列,则它们的并集记为:A1∪A2∪...∪An∪...,niiA1A1∪A2∪...∪An简记为:1iiA简记为:定义:A1∪A2∪...∪An∪...={x|nN使得xAn}1.3集合的基本运算31一般地,若{Al}lI是任一集族,则集族中那些集合的并集记为简记为}{lIllAxIlxA使得集族中元素的并集1.3集合的基本运算**32定义1.9设A,B为二集合，称由A和B的公共元素(既属于A又属于B)组成的集合为A与B的交集，记作A∩B，称∩为交运算符。A∩B的描述法表示为：A∩B={x|xA且xB}1.3集合的基本运算(2)、交集的概念33定理1.3.2设A,B,C为任意的三个集合，则:7.幂等律成立,即A∩A=A;6.交换律成立,即A∩B=B∩A;8.∩A=;9.A∩B=AAB。1.3集合的基本运算10.结合律成立,即(A∩B)∩C=A∩(B∩C);34与并运算类似，可以将集合的交推广到有限个或可数个集合：)}},,...,2,1{{...121iniinAxnixAAAA},{......121nnnnAxNnxAAAA类似定义1.3集合的基本运算对于集族{Al}lI中各集的交记成,其定义为IllA},{AxIxAIll35定理1.3.3设A为一集合,{Bl}lI为任一集族,则:)()(IllIllBABAIllIllBABA)()(1.3集合的基本运算36定理1.3.4设A,B,C为任意三个集合，则:11.交运算对并运算满足分配律,即A∩(B∪C)=(A∩B)∪(A∩C);12.并运算对交运算满足分配律,即A∪(B∩C)=(A∪B)∩(A∪C);1.3集合的基本运算37定理1.3.5对任何集合A,B,吸收律成立。13.A∩(A∪B)=A;14.A∪(A∩B)=A;1.3集合的基本运算38定义1.3.3设A,B为任意集合，若A∩B=Ø，则称A,B不相交。若集序列A1,A2,...,An,...对于任意的Ai与Aj(i≠j)不相交,则称A1,A2,...,An,...是两两不相交的集序列。1.3集合的基本运算39定义1.11设A,B为两个任意集合，由属于A而不属于B的全体元素组成的集合称为A与B的差集，记作A\B。}.{\BxAxxBA且1.3集合的基本运算(3)、差集的概念40定理1.3.6设A,B,C为任意三个集合,则13.A∩(B\C)=(A∩B)\(A∩C)。1.3集合的基本运算41差运算不满足交换律。即一般情况下：A\BB\A。(A\B)\C差运算不满足结合律。=A\(B\C)1.3集合的基本运算42定理1.3.7设A,B为任意二个集合,则(A\B)∪B=ABA。1.3集合的基本运算43定义1.3.5设A,B为任意两个集合，称A\B与B\A的并集称为A与B的对称差，记作AB(也记作AB)。AB=(A\B)∪(B\A)={x(xA且xB)或(xA且xB)={xxA∪B且xA∩B}=(A∪B)\(A∩B)1.3集合的基本运算(3)、对称差的概念44定理1.3.8设A,B,C为任意三个集合,则16.AB=BA;17.AA=;18.A=