离散数学第三讲

二、容斥原理与鸽巢原理1、容斥原理(§1。3。)（计数原理、包含排斥原理）容斥原理（包含排斥原理）：设A，B是有限集，则BABABA容斥原理的相关推论：(i)CBACACBBACBACBA(ii)利用归纳法nnnkjikjinjijiniinAAAAAAAAAAAAA211111321)1((iii)UAA,AUA(iv)nnAAAUAAA2121（注意基的具体含义）设S是有限集，rPPP,,,21是r条性质，iA是S中具有性质iP的子集，即iiPxSxxA具有性质,（i=1,2,…，r）则（1）S中至少具有性质rPPP,,,21一条的元素数是：rrrkjikjirjijiriirAAAAAAAAAAAAA211111321)1(（2）S中不具有性质rPPP,,,21的元素数是：rrAAAUAAA2121e.g1设2n，)(n表示不超过n且与n互质的正整数的个数，求)(n该函数在计算机中称为EURTER函数。解：nS,,3,2,1不妨令：rrpppn1121rppp,,,21为互异的质数；设ripxSxxAii,,2,1,且则jijiiippnAApnA,rAAAn21)(……2、鸽巢原理（抽屉原理、鞋盒原理）（教材P63）n+1个鸽子飞进n个鸽巢，则可以找到一鸽巢里至少有2只鸽子。或者：如果k+1个或更多的物体放入k个盒子，那么至少有一个盒子包含了2个或更多的物体。e.g1把10个点放入边长为1的正三角形内，证明，可以找到两个点，它们之间的距离不超过三分之一。（具体问题，找鸽子，做笼子）推广1、n个鸽洞，（多于）1nr个鸽子，必有一个鸽洞住有至少r+1只鸽子。推论2、（平均数原理）设ix是自然数，且rnxxxn21)(Nr则kx，使得1rxk。证明：……e.g2一个园盘划分为36个扇形，把1~36这36个数放入扇形中，每格一个数，证明无论怎样放，总可以找到三个连续的扇形，使得这三个扇形中的数之和56。解：……练习No1有n个乒乓球运动员比赛，每人至少赛一场，同一对手至多比赛一场，证明这n个运动员可以找到二个运动员，他们比赛的场数一样。No2设nxxx,,,21是n个正整数，证明，其中至少存在若干个（下标）连续的数，使得它们的和是n的倍数。e.g3假定一组6个人，任意两个人或者是朋友或者是敌人，证明在这组人中或存在3个人彼此都是朋友，或存在3个人彼此都是敌人。(教材P65：例3.12)（任意一个人和其他5个人的关系）三、二元关系（第2章）利用“有序偶”给出关系的定义，先看两个基本概念1、序偶与笛卡儿积定义1设A，B是两个非空集合，对BbAa,，则称（a,b）为A到B上的一个序偶。注：序偶讨论的是有序对，不同的书描述的是不一样的；显然（i）(a,b)=(c,d)a=c且b=d(ii)(a,b)=(b,a)一般不成立定义2非空集合A到B的所有序偶的集合，称为A到B上的积或笛卡儿积，记为：BADescartes[1596-1650]法国哲学家、数学家e.g1设baBA,,3,2,1求（1）BA，（2）AB（3）BB……e.g2R(全体实数集)（x,y）平面坐标系中的一个坐标、RR的一个序偶e.g3NZ,NqZpqp,,),(将qpqp定义成),(；如53)5,3(定义成则NZ可看成全体有理数以前遇到的很多事物和现象都可以看成序偶处理e.g4设}2,1{A；写出AAP)(本书只讨论二元另A=B时，记2AAABAe.g5设nBmA,；则nmBA有了笛卡儿积，进一步讨论关系的概念2、二元关系（§2。1二元关系及其表示形式）e.g1姓名与成绩99,95,85,65,,,,SdcbaC联系：Rdcba,)85,(),85,(),99,(),65,(联系…关系即集合SC的一个子集。1）定义3若)(BAPR，则称R是A到B上的一个二元关系。即（i）R是集合BA上的一个子集；（ii）R是BA幂集)(BAP上的一个元素（iii）R中的元素（a,b）是集合A到B上的一个序偶组成.定义4记RbaBbAaadomR),,,使得（且(domain)称为R的前域。RbaAaBbbranR),,,似的（阿且（range）称为R的值域。上例dcbadomR,,,，99,85,65ran另（i）若,),(Rba称a与b有关系R，记为aRb(ii)若B=A则称R是A上的关系。e.g1设}2010{级信计班学生是xxAR1：xR1y表示x与y同姓R2：xR2y表示x与y同一寝室。e.g2设}6,5,4,3,2{S定义R：若yx（整除）；则xRy.R是S上的关系即)}6,6(),5,5(),4,4(),6,3(),3,3(),6,2(),4,2(),2,2{(R定义5设R是A上的一个关系，即AAR或)(AAPR则称)(AAP：空关系)(AAPAA：全域关系，记为EAAAAaaa}),{(：恒等关系IAe.g3若mBnA,有多少种不同的A到B上的二元关系？……e.g4设}9,8,7,6,5,4,3,2,1{A，R是A上的模4同余关系，即当Aba,，且a和b被4除后余数相同时，有aRb,用例举法写出关系R。2）关系的表示法：（P21）(I)表格表示法：……(II)矩阵表示法：……(III)图形表示法……问题：设21,RR是A到B上的两个关系，关系矩阵为21,RRMM如何求2121,RRRRMM21RR：关系矩阵2112RRRRMMM矩阵的对应元素相加，但为逻辑加；即000110011121RR：关系矩阵2112RRRRMMM矩阵的对应元素相乘ijijijbac，但为逻辑乘；即1110001001e.g1设}6,5,4,3,2{A，R是A上的整除关系，S是A上的小于等于关系，求.,SRSR解：关系矩阵1000001000001001001010101RM，1000011000111001111011111SM1000011000111001111011111SRM，1000001000001001001010101SRM又：T是A上的小于关系，求.,TRTR……3、具有某些特性的关系（§2。2二元关系的基本类型与判定方法）设R是非空集合A上的关系（集合R，R中的元素是序偶，由AA的元素组成，即},,),{(具有某些特性、且baAbAabaR；除此之外，AAR是一个子集；）（AAPR幂集的一个元素；另外Rba），（即aRb）1）自反的二元关系定义1设R是非空集合A上的关系，若对,Aa都有aRa即Raa),(则称R是自反的二元关系，也称R具有自反性。e.g1设}205{）班学生信计（表示xxA1R：yxR1则x与y同姓……1R是自反的二元关系e.g2设}6,5,4,3,2{A，R是A上的整除关系，S是A上的小于等于关系，T是A上的小于关系;则……e.g3设},,{cbaA；)},(),,(),,(),,{(cccbbaaaRR不是A上的自反的关系；Rbb),(从关系表示法是看自反关系的特点：设R是A上自反的二元关系，nA表格表示法上对角线上全打钩；关系矩阵上对角线上元素全为1；关系图示法上元素（每个顶点）自身画圈（环）2）反自反的二元关系定义2设R是非空集合A上的关系，若对,Aa都有Raa),(则称R是反自反的二元关系，也称R具有反自反性。e.g4设}6,5,4,3,2{A,R是A上的小于关系;则……e.g5设}4,3,2,1{A,对于A上的如下关系全域关系空关系,,)}4,4(),3,1(),3,2(),2,1(),1,1{()}1,2(),3,1{()}4,4(),3,3(),2,2(),1,2(),2,1(),1,1{(54321AARRRRR试确定何者为自反关系何者为反自反关系解：自反关系：51,RR反自反关系：42,RR另：关系矩阵中，自反关系的关系矩阵中，对角线上元素全为0。注：自反的反面是否为反自反？关系矩阵中对角线上元素有0也有1……3R3)对称的二元关系定义3设R是非空集合A上的关系，若有Rba),(，必有Rab),(，则称R是A上的对称关系，也称R具有对称性。e.g1`设}211{）班学生信计（表示xxA1R：yxR1则x与y同姓……1R是对称关系关系矩阵RM是对称矩阵又2R：yxR2则x认识y，……2R不是对称的二元关系e.g6设}8,7,6,5,4,3,2{A关系R：aRb则a,b都是素数。……4）反对称的二元关系定义4设R是非空集合A上的关系，当ba时，若aRb，必有Rab),(；则称R为A上的反对称关系，或称R具有反对称性。e.g4`设}6,5,4,3,2{A,R是A上的小于关系;反对称关系R中，对ba，aRb与bRa至多有一个出现。反对称关系R中，对ba，aRb与bRa至多有一个出现。5）可传递的二元关系定义5设R是非空集合A上的关系，若aRb且bRc，则必有aRc；则称R是可传递的二元关系，或称R具有可传递性。e.g1``设}111{班学生信计表示xxA1R：yxR1则x与y同姓…………e.g2设A是非空集合，对幂集P（A）上的关系R，对),(,APba若ba，则;aRb讨论关系R特性。R具有自反性，反对称性，可传递性。1、可传递性的判定方法（P27）1）逐个检查法2）关系矩阵检查法……P30……2、相关结论（i）设A是元素个数为n的集合，则(1)A上可定义多少种自反的二元关系?(2)A上可定义多少种反自反的二元关系?(3)A上可定义多少种对称的二元关系？(4)A上可定义多少种反对称的二元关系？(5)A上可定义多少既不是自反的也不是反自反的二元关系解：（1）)2()1(nn；（2）)2()1(nn；（3）)2(2)1(nn;(4))2(2)1(nn;(5))1(2222nnn（ii）（1）21,RR是A上的自反关系，则2121,RRRR仍具有自反性；（2）21,RR是A上的反自反关系，则212121,,RRRRRR仍具有反自反性；（3）21,RR是A上的对称关系，则212121,,RRRRRR仍具有对称性；（4）21,RR是A上的反对称关系，则2121,RRRR仍具有反对称性；（5）21,RR是A上的传递关系，则21RR仍具有对称性证明（3）4、等价关系与集合的划分（§2。3P33）1）等价关系的定义定义1、设R是集合A上的二元关系，若R具有自反性、对称性和可传递性；则称R是集合A上的等价关系。即、R是集合A上的等价关系，则有（i）RaaaRaAa),(,或则(ii)若aRb则bRa（iii）若aRb且bRc则aRce.g1}007{班学生信计是xxAA上的关系R:aRb则a与b在同一寝室；……又A上的关系S：aSb则a与b是好朋友……e.g2以物种来给动物分类，即“属于同一种属”的关系R，是所有动物集合A上的一个等价关系；e.g3非空集合A上的恒等关系IA和全域关系EA都是等价关系。e.g4集合的包含关系不是等价关系。它是自反的和传递的，但不是对称的*等价关系的表述特征e.g5设}7,6,5,4,3,2,1{A,A上的关系R若aRb,a与b关于模3同余，证明R是A上的等价关系。并用表格表示法、矩阵表