华科离散数学第一章电子教案.ppt

华科离散数学第一章,二、离散数学课程的特点,离散数学课程是应计算机科学和技术发展的需要，综合了高等数学的多个分支而形成的。其特点是以离散量为研究对象，内容丰富，涉及面较宽。因此概念多、定理多、推理多并且内容较为抽象。但由于它是为学生后继专业知识的学习做必要的数学准备，因此它研究的内容均比较基础，难度不大。,三、如何学好离散数学,要学好这门课程，首先必须充分认识到这门课程的上述特点，需要做到以下几点：,1,熟读教材。,准确理解各个概念和定理的含义（结合多个例子来理解），必要的推理过程要看懂、理解（它可以帮助你熟悉和深刻理解定理的含义）。,2,独立思考，大量练习。,仅靠熟读教材并不能将书本上的知识 变成你自己的知识，在熟读教材的基础上，必须通过大量练 习，独立思考来真正获取知识。,3,注重抽象思维能力的培养。,数学与其他学科相比较具有较高的抽象性，而离散数学的抽象性特点更为显著，它有着大量抽象的概念和抽象的推理，要学好这门课程必须具有较好的抽象思维能力，才能深入地掌握课程内容。,第四部分,数理逻辑。,包括命题逻辑和谓词逻辑。（教材的第九、十章,四、离散数学课程的主要内容,离散数学课程的主要内容可以分为四个部分：,第一部分 集合论。,包括集合、关系和函数。（教材的第一、二、三章）,第二部分 代数系统。,包括代数系统的一般概念，几类典型的代数系统。（教材的第四、五、六、七章）,第三部分 图论。,包括图的基本概念，几种特殊的图。（教材的第八章）,五、教材及参考书,2,参考书：,离散数学习题题解,洪帆、付小青编，华中理工大学出版社。,1,、,教材：,离散数学基础,第二版，洪帆主编，华中理工大学出版社,。,第一章 集 合,本章采用朴素集合论的方法，介绍有关集合的一些基本知识，内容显得较为直观，学起来易于接受。但集合及其相关的概念是本门课程后面各章内容的基础，读者务必熟练的掌握。,主要内容如下：,1.1,集合及其表示方法,1.2,集合间的关系,1.3,集合的运算和运算定律,1.4,集合成员表,1.5,集合的分划与覆盖,又例如,所有的正整数组成一个集合，每一个正整数均是这个集 合的元素。,例如,全体中国人可组成一个集合，每一个中国人均是这个集合的 元素,第一章 集 合,1.1,集合及其表示方法,一、集合和元素,把一些确定的、彼此不同的事物作为一个整体来 看待时，这个整体便称为是一个,集合,。,组成集合的那些个体称为集合的,元素,。,通常用大写英文字母来标记集合，用小写英文字母标记组成集合的个体,若个体,a,是集合,A,的元素，则记作,“,aA,”,若,a,不是集合,A,的元素，则记作,“,a A,”,几个常见的集合的表示符号：,N,：所有正整数的集合。,Q,：所有有理数的集合。,Z,：所有非负整数的集合。,R,：所有实数的集合。,I,：所有整数的集合。,N,m,：从,1,到,m,，这,m,个正整数的集合。,P,：所有素数的集合。,Z,m,：从,0,到,m-1,，这,m,个非负整数的集合。,于是,2N,，,2.5 N,，,-3 N,，但,2.5Q,，,-3I,。,二、集合的表示方法,(1),列举法,：按任意顺序逐一列举集合中的元素于花括号内，元素之间用逗号隔开。,例如：,A=2,a,b,9,B=4,5,6,7,8,(2),描述法,：给定一个条件,P(x),，当且仅当个体,a,使,P(a),成立时，,aA,。其一般形式为,A=aP(a),例如,上述集合,B=aaN,且,4a8,又如,C=2,i,iZ,即,C=2,0,2,1,2,2,2,3,D=2xxZ,且,x50即,D=0,2,4,6,98,100,三、集合的基数,集合,A,中不同元素的个数称为集合,A,的,基数,，记作,#A,。,例如,上页中的集合，,#A=4,，,#B=5,，,#D=51,，集合,C,有无穷多个元素，因此,C,的基数是无穷大。,若,#A,是有限数，则称,A,为有限集，否则称,A,为无限集。,例如,N,Z ,I ,R,等均为无限集,。,四、空集,定义,1-1,不含有任何元素的集合，称为,空集,，记作,。,例如,A=x|x,R,且,x,2,+8=0=,练习,1-1,用列举法表示下列集合,（,1,）,A=a|a,P,且,a20,（,2,）,B=a|a|4,且,a,为奇数,2.,用描述法表示下列集合,(1)A=0,2,4,200,(2)B=2,4,8,1024,2,3,5,7,11,13,17,19,-,3,-,1,1,3,2x|x,Z,且,x100,2,n,|n,N,且,n10,1.2,集合间的关系,集合的包含和相等是集合间的两个基本关系。,例如,设,A=a,b,c,d,B=a,e,x,y,z,C=a,x,B A,，,A B,。,则 ，,C A,，,一、集合的包含,定义,1-2,设有集合,A,、,B,，如果,A,的每一个元素都是,B,的元素，则称,A,是,B,的子集或,B,是,A,的包含集，记 。如果,A,不是,B,的子集，则记作,A B,。,集合的包含关系具有如下几条性质证明性质（,1,）,（反证法）,假设 ，,（,1,）对任意集合,A,，；,（,2,）对任意集合,A,，；,（,3,）对任意集合,A,、,B,、,C,，若,，则 。,则至少有一个元素,但 ，这与空集的定义相矛盾，因此成立。,二、集合的相等,例如,设,A=x|xN,且,x,能整除,24,，,B=1,2,3,4,6,8,12,24,则,A=B,=,又例如,（,1,）,a,b,c,b,c,a,（,2,）,a,b,c,c,a,b,c,（,3,）,a,b,c,a,b,c,（,4,）,=,定义,1-3,设有集合,A,、,B,，若 且,，则称集合,A,与,B,相等，记作,A=B,。,例如,设,A=0,，,1,，,B=0,，,1,，,2,，,C=0,则,但,四、空集的唯一性,定理,1-1,空集是唯一的,因为空集被包含于每一个集合中,，,三、集合的真包含,定义,1-4,设有集合,A,、,B,，若,且,A,B,，则称,A,是,B,的真子集，记作 ，若,A,不是,B,的真子集，则记作,。,证明,假设有两个空集 和 ，,所以有,，,由定义,1-3,，,故空集是唯一的。,五、幂集,定义,1-5,设有集合,A,，由,A,的所有子集组成的集合，称为集合,A,的幂集，记作,2,A,即,例,1,设,A=a,则,0,个元素的子集：,1,个元素的子集：,a,因此,设,B=a,b,则,0,个元素的子集,：,1,个元素的子集：,a,b,2,个元素的子集,：,a,b,因此,设,C=a,b,c,则,0,个元素的子集：,；,1,个元素的子集：,a,b,c,2,个元素的子集：,a,b,a,c,b,c,3,个元素的子集：,a,b,c,因此,定理,1-2,设,A,是有限集，则,#(2,A,)=2,#A,在二项式定理,中，令,x=y=1,便有,因此,#(,2,A,)=,2,n,即,#(,2,A,)=,2,#A,:,:,a,1,:,a,2,a,n,:,a,1,a,2,a,1,a,3,:,a,1,a,2,a,n,证明,设,A=,a,1,a,2,a,n,从,n,个元素中选取,m,个元素的方法有 种，所以,A,的子集个数为,例,2设,求,2,A,和,2,B,解,对于集合,A,，它只有一个子集 ，,即,对于集合,B,，有,1,个元素的子集：，,a,，,a,2,个元素的子集：,3,个元素的子集：,0,个元素的子集：,因此,答案：,A,B,D,2,设,试判断下列各式是否正确，并将正确的题号填入括号内。,A.B.C.D.,答案：,A,B,C,A.B.C.,D.,练习,1-2,1,试判断下列各式是否正确，并将正确的题号填入括号内。,3,设,，判断下列论断是否正确，并将,“,Y”,或,“,N”,填入相应论断后面的括号中。,(1),(2),(3),(4),(),(),(),(),(),(),(),(),Y,Y,Y,Y,Y,Y,N,N,令,则,1.3,集合的运算和运算定律,二、文氏图,定义,1-6,如果在某个问题中，所讨论的一切集合均是某个集合的子集，则称这个集合是该问题的全集合。记作,U,（或,E,）。,一、全集合,例如,U,A,A,B,三、集合的运算,1.,并运算,定义,1-7,设有集合,A,、,B,，属于,A,或属于,B,的所有元素组成的集合称为,A,与,B,的并集，记作 。即,例如,设,A=a,b,c,B=c,d,f,C=b,e,则,由定义,1-7,知,，,A,B,2.,交运算,定义,1-8,设有集合,A,、,B,，属于,A,同时又属于,B,的所有元素组成的集合称为,A,与,B,的交集，记作 。即,例如,设,A=a,b,c,d,B=d,f,a,C=e,f,g,则,由定义,1-8,可知,，,A,B,3.,相对补运算,定义,1-9,设有集合,A,、,B,，所有属于,B,而不属于,A,的元素组成的集合，称为,A,相对于,B,的补集，记作,B-A,。即,例如,设,A=a,b,c,d,B=d,f,a,C=e,f,g,则,B-A=f,C-A=e,f,g=C,B,A,32,页,2.,绝对补运算,定义,1-10,集合,A,相对于全集合,U,的补集称为,A,的绝对补集，简称为,A,的补集，记作 。即,例如,设,U=1,，,2,，,3,，,4,，,，,10,，,A=2,，,4,，,6,，,8,，,10,则,又例如,设,UI,（,I,是整数集），,则,四、集合运算的定律,1.,集合运算的十条定律,对于全集合,U,的任意子集,A,、,B,、,C,，有：,交换律,结合律,分配律,同一律,互补律,对合律,等幂律,零一律,吸收律,德,摩根律,1.,集合恒等式的几种证明方法,（,1,）根据定义进行证明,若要证明集合,S=H,，根据集合相等关系的定义，我们需证明,且,例,1,证明,证明,若,则 ，,因此 或者,于是 或者,从而 ，则,反之 若 ，故 或者 。,因此，或者,于是 ，,从而 ，故有 。,由上证得，。,例,2,证明,证明,若 则 且 ，,即 且 ，,因 此，,故 。,反之 若 ，,则 且 ，,即 且 ，,因此 故 。,由上证得，,（,2,）利用已有的集合恒等式证明新的恒等式,例如,假设交换律、分配律、同一律和零一律都成立，则可以证明吸收律 也成立。,证明,（由同一律）,（,由分配律）,（由交换律）,（由零一律）,（由同一律）,又例如,证明等幂律,证明,=A,(3),利用下一节介绍的集合成员表证明集合恒等式,D,若 ，则,A=B,练习,1-3,1,设,A,、,B,、,C,是任意集合，判断下述论断是否正确，并将正确的题号填入括号内。,A,若 ，则,B=C,B,若 ，则,B=C,C,若,A-B=A-C,，则,B=C,(),D,反例,设,A=a,b,c,B=b,d,C=c,d,则,但,23,页,2,设,U=1,，,2,，,3,，,4,，,5,，,A=2,，,4,，,B=4,，,3,，,5,，,C=2,，,5,，,3,，确定下列集合的元素，将其填入相应的花括号内。,(1),(2),(3),(4),(5,2,1,4,2,3,4,5,4,3,设,U,表示刘平拥有的所有书的集合，其中,A,是离散数学参考书的集合，,B,是操作系统参考书的集合，,C,是今年出版的新书的集合，,D,是从图书馆借来的书的集合。现知道如下情形：,（,1,）所有离散数学参考书都是今年出版的新书。（）,（,2,）所有操作系统参考书都是从图书馆借来的。（）,（,3,）今年出版的新书不是从图书馆借来的。（）,（,4,）没有一本操作系统的参考书是今年出版的。（,）,3,1,5,7,试用集合的方法分别表示上述四种情形，可供选择的答案如下，请从下述答案中挑选出相应表达式的编号填入每一种情形后面的括号中。,2.3.4.,5.6.7.,4,判断下列论断是否正确，对正确的论断在相应题后的括号中标入“,Y”,，对错误的论断在相应题后的括号中标入“,N”,。,1,）若 ，则 （）,2,）若 ，则 （）,3,）若 ，则 （）,4,）若 ，则 （）,5,）若 ，则,(),6,）若 ，则,(),7,）若 ，则,(),8,）若 ，则,(),Y,Y,Y,Y,N,N,N,N,1.4,集合成员表,一、并、交和补集的成员表,根据集合的并和交运算的定义，全集合,U,中的元素,u,可分为如下四种情形：,（,1,），,（,2,），,（,3,），,（,4,），,A B,0 00 11 01 1,0 0 1 0 1 0 1 1,设,A,是全集合,U,的子集，根据补集的定义，全集合,U,中的元素可分为两种情形，,（,1,）若 ，则,（,2,）若 ，则,的成员表,A,0,1,1,0,二、由集合,A,1,、,A,2,、,、,A,r,所产生的集合的成员表。,设,A,1,、,A,2,、,、,A,r,是全集合,U,的子集，对这些集合以及,和,U,有限次地施加补、并、交运算，可以产生出一些新的集合，这样产生的集合称为是由,A,1,、,A,2,、,、,A,r,所产生的集合。,例 如,S,例,1,构造,T=,的成员表,A B,0 0,0 1,0,1 1,0,1,1,1,1,0,1,0,0,0,1,0,例,2,构造,S,的成员表,A B C,0 0 0,0 0 1,0 1 0,0 1 1,0 0,1 0 1,1 1 0,1 1 1,S,1,1,0,0,1,1,0,0,0,1,0,0,0,1,0,0,1,0,1,0,1,0,1,0,0,0,1,0,0,0,1,0,0,1,1,0,0,1,1,0,0,0,0,0,0,1,1,0,三、利用集合成员表证明集合恒等式,例,设,A,、,B,、,C,是任意集合，试问等式,S=T,是否成立？,解,令,S=T=,分别构造,S,和,T,的成员表如下：,A B C,0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1,S,T,11110000,00111111,11110101,00110101,00110000,00000101,00110101,1.5,集合的分划与覆盖,一、集合的分划,定义,1-11,设有非空集合,A,，,H=A,1,、,A,2,、,、,A,m,，其中 ，且 （,i=1,，,2,，,，,m,），若,（,1,），当,i,j,时,(2),例,1,设,A=1,，,2,，,3,，,4,则,H,1,=1,，,2,，,3,，,4,H,2,=2,，,3,，,1,，,4,H,3,=1,2,，,3,，,4,。,都是,A,的分划,则称,H,是集合,A,的一个分划，每一个 称为这个分划的一个分块。,例,2,设,A=2,，,3,，,4,，,8,，,9,，,10,，,15,定义,A,的如下子集：,试问 是否,A,的一个分划。,解,根据题意,2,，,4,，,8,，,10,3,，,9,，,15,10,，,15,不是,A,的分划，,可成为,A,的一个分划。,二、集合的覆盖,定义,1-12,设有非空集合,A,，,其中 且 （,i=1,，,2,，,，,m,），若 ，则称,S,是集合,A,的一个覆盖。,例如,例,2,中 是,A,的分划，也是,A,的覆盖。,是,A,的覆盖，但不是,A,的分划。练习,1-5,1,设,A=a,，,b,，,c,，,d,，,e,，,f,，指出下列哪些是,A,的分划（在相应括号内填入“,1”,），哪些是,A,的覆盖（在相应括号内填入“,2”,），哪些既不是分划，也不是覆盖（在相应括号内填入“,0”,）,H,1,=a,，,b,，,c,，,d,，,a,，,e,，,f ,（）,H,2,=c,，,e,，,c,，,d,，,f,，,b ,（）,H,3,=a,，,b,，,c,，,d,，,e,，,f ,（）,H,4,=a,，,c,，,e,，,b,，,c ,（,）,2,0,1,2,0,例题一,1,给定正整数集,N,的下列子集,求集合,解,B=1,2,3,4,5,6,7,=12,3,4,5,6,8,16,32,64,C=3,6,9,12,15,18,21,24,27,30,D=1,2,4,8,16,32,64,2,设,A,、,B,、,C,和,D,是集合，下述论断哪些正确？哪些错误？对正确的论断给出证明，对错误的论断举出反例。,（,1,）若 ，则,解,（,1,）,正确。证明如下：,设,因为,所以,因此,（,2,）若 ，则,设 ，则,正确。证明如下：,解,因为,所以,因此,（,3,）若 ，则,解,错误,但,则,例如，设,A=1,，,2,，,C=3,，,4,，,B=D=1,，,2,，,3,，,4,（,4,）若 ，则,解,错误,例如，设,A=2,，,3,，,B=1,，,2,，,3,，,C=2,，,3,，,D=2,，,3,，,4,则,但,3 n,个元素的集合,A,，有多少种不同的方法分划成为两块？,解,A,有 个不同的子集，且这 个不同的子集中，两两互补，除 和,U,互补，但不能构成,A,的分划外，其余的每对集合均构成将,A,分成两块的一个分划，因此,A,有 种方法分成两块。,4,设某校有运动员总数为,70,人，其中足球队员,38,人，篮球队员,35,人，排球队员,32,人，其中有,8,人同时参加三个队，试求仅同时参加两个队的队员人数是几人？,A,C,B,X,Y,Z,8,则,#,又,在文氏图中用,A,、,B,、,C,分别,表示足球队员、篮球队员和,排球队员的集合,解,答案：,仅同时参加两个队的队员人数是,19,人,此课件下载可自行编辑修改，仅供参考！感谢您的支持，我们努力做得更好！谢谢,