离散数学教学

1,集合论,2,集合论部分,第3章集合的基本概念和运算第4章二元关系和函数,3,第3章集合的基本概念和运算,3.1集合的基本概念3.2集合的基本运算3.3集合中元素的计数,4,3.1集合的基本概念,集合的定义与表示集合与元素集合之间的关系空集全集幂集,5,集合定义与表示,集合没有精确的数学定义理解：一些离散个体组成的全体组成集合的个体称为它的元素或成员集合的表示列元素法A=a,b,c,d谓词表示法B=x|P(x)B由使得P(x)为真的x构成常用数集N,Z,Q,R,C分别表示自然数、整数、有理数、实数和复数集合，注意0是自然数.,6,集合与元素,元素与集合的关系：隶属关系属于，不属于实例A=x|xRx2-1=0,A=-1,11A,2A注意：对于任何集合A和元素x(可以是集合)，xA和xA两者成立其一，且仅成立其一.,7,隶属关系的层次结构,例3.1A=a,b,c,d,db,cAbAdAdAdA,8,集合之间的关系,包含（子集）ABx(xAxB)不包含ABx(xAxB)相等A=BABBA不相等AB真包含ABABAB不真包含AB思考：和的定义注意和是不同层次的问题,9,空集与全集,空集不含任何元素的集合实例x|x2+1=0xR就是空集定理空集是任何集合的子集Ax(xxA)T推论空集是惟一的.证假设存在1和2，则12且12，因此1=2全集E相对性在给定问题中，全集包含任何集合，即A(AE),10,幂集,定义P(A)=x|xA实例P()=，P()=,P(1,2,3)=,1,2,3,1,2,3计数如果|A|=n，则|P(A)|=2n,11,3.2集合的基本运算,集合基本运算的定义文氏图（JohnVenn）例题集合运算的算律集合包含或恒等式的证明,12,集合基本运算的定义,并AB=x|xAxB交AB=x|xAxB相对补AB=x|xAxB对称差AB=(AB)(BA)=(AB)(AB)绝对补A=EA,13,文氏图表示,14,关于运算的说明,运算顺序：和幂集优先，其他由括号确定并和交运算可以推广到有穷个集合上，即A1A2An=x|xA1xA2xAnA1A2An=x|xA1xA2xAn某些重要结果ABAABAB=（后面证明）AB=AB=A,15,只有一、二年级的学生才爱好体育运动,F:一年级大学生的集合S：二年级大学生的集合R：计算机系学生的集合M：数学系学生的集合T：选修离散数学的学生的集合L：爱好文学学生的集合P：爱好体育运动学生的集合,T(MR)S,RST,(MF)T=,MLP,PFS,S(MR)P,除去数学和计算机系二年级学生外都不选修离散数学,例1,所有计算机系二年级学生都选修离散数学,数学系一年级的学生都没有选修离散数学,数学系学生或爱好文学或爱好体育运动,16,例2,=S2,=S5,=S1,S2,S4,=S3,S5,与S1,.,S5都不等,17,集合运算的算律,吸收律的前提：、可交换,18,集合运算的算律（续）,19,集合包含或相等的证明方法,证明XY命题演算法包含传递法等价条件法反证法并交运算法,证明X=Y命题演算法等式代入法反证法运算法,以上的X,Y代表集合公式,20,任取x，xXxY,命题演算法证XY,例3证明ABP(A)P(B)任取xxP(A)xAxBxP(B)任取xxAxAxP(A)xP(B)xBxB,21,包含传递法证XY,找到集合T满足XT且TY，从而有XY例4ABAB证ABAAAB所以ABAB,22,利用包含的等价条件证XY,例5ACBCABC证ACAC=CBCBC=C(AB)C=A(BC)=AC=C(AB)C=CABC命题得证,23,反证法证XY,欲证XY,假设命题不成立，必存在x使得xX且xY.然后推出矛盾.例6证明ACBCABC证假设ABC不成立，则x(xABxC)因此xA或xB，且xC若xA,则与AC矛盾；若xB,则与BC矛盾.,24,利用已知包含式并交运算,例7证明ACBCACBCAB证ACBC，ACBC上式两边求并，得(AC)(AC)(BC)(BC)(AC)(AC)(BC)(BC)A(CC)B(CC)AEBEAB,由已知包含式通过运算产生新的包含式XYXZYZ,XZYZ,25,例8证明A(AB)=A（吸收律）证任取x,xA(AB)xAxABxA(xAxB)xA,命题演算法证明X=Y,任取x，xXxYxYxX或者xXxY,26,等式替换证明X=Y,例9证明A(AB)=A（吸收律）证(假设交换律、分配律、同一律、零律成立)A(AB)=(AE)(AB)同一律=A(EB)分配律=A(BE)交换律=AE零律=A同一律,不断进行代入化简，最终得到两边相等,27,反证法证明X=Y,例10证明以下等价条件ABAB=BAB=AAB=(1)(2)(3)(4)证明顺序：(1)(2),(2)(3),(3)(4),(4)(1),假设X=Y不成立，则存在x使得xX且xY，或者存在x使得xY且xX，然后推出矛盾.,28,(1)(2)显然BAB，下面证明ABB.任取x，xABxAxBxBxBxB因此有ABB.综合上述（2）得证.,(2)(3)A=A(AB)A=AB（将AB用B代入),29,(3)(4)假设AB,即xAB，那么xA且xB.而xBxAB.从而与AB=A矛盾.,(4)(1)假设AB不成立，那么x(xAxB)xABAB与条件（4）矛盾.,30,集合运算法证明X=Y,例11证明AC=BCAC=BCA=B证由AC=BC和AC=BC得到(AC)-(AC)=(BC)-(BC)从而有AC=BC因此AC=BC(AC)C=(BC)CA(CC)=B(CC)A=BA=B,由已知等式通过运算产生新的等式X=YXZ=YZ,XZ=YZ，X-Z=Y-Z,31,集合的基数与有穷集合包含排斥原理有穷集的计数,3.3集合中元素的计数,32,集合A的基数：集合A中的元素数，记作cardA有穷集A：cardA=|A|=n，n为自然数.有穷集的实例：A=a,b,c,cardA=|A|=3；B=x|x2+1=0,xR,cardB=|B|=0无穷集的实例：N,Z,Q,R,C等,集合的基数与有穷集合,33,包含排斥原理,定理设S为有穷集，P1,P2,Pm是m种性质，Ai是S中具有性质Pi的元素构成的子集，i=1,2,m.则S中不具有性质P1,P2,Pm的元素数为,34,证明,证设x不具有性质P1,P2,Pm,xAi,i=1,2,mxAiAj,1ijmxA1A2Am,x对右边计数贡献为10+00+(1)m0=1,证明要点：任何元素x，如果不具有任何性质，则对等式右边计数贡献为，否则为,35,证明（续）,设x具有n条性质，1nmx对|S|贡献为1x对贡献为x对贡献为.x对|A1A2Am|贡献为x对右边计数贡献为,36,S中至少具有一条性质的元素数为,推论,37,解：S=x|xZ,1x1000,如下定义S的3个子集A,B,C：A=x|xS,5|x，B=x|xS,6|x，C=x|xS,8|x,例1求1到1000之间（包含1和1000在内）既不能被5和6整除，也不能被8整除的数有多少个？,应用,38,对上述子集计数：|S|=1000,|A|=1000/5=200,|B|=1000/6=133，|C|=1000/8=125,|AB|=1000/30=33,|BC|=1000/40=25,|BC|=1000/24=41,|ABC|=1000/120=8,代入公式N=1000(200+133+125)+(33+25+41)8=600,例1（续）,39,文氏图法,求1到1000之间（包含1和1000在内）既不能被5和6整除，也不能被8整除的数有多少个？,40,例224名科技人员，每人至少会1门外语.英语：13；日语：5；德语：10；法语：9英日：2;英德：4；英法：4；法德：4会日语的不会法语、德语求：只会1种语言人数，会3种语言人数,x+2(4-x)+y1+2=13x+2(4-x)+y2=10 x+2(4-x)+y3=9x+3(4-x)+y1+y2+y3=19x=1,y