数理逻辑与二元关系3

数理逻辑与二元关系,任课教师：杨春,Email:yc517922,数学科学学院,一些计数问题可归结为计算一个或一些集合中的元素个数。而有时在计算集合并的元素个数较困难而计算交较容易时，我们可利用集合的性质将计算的问题转化为计算交。这就是容斥原理思想。,容斥原理,1.集合的几个性质,设U为全集,集合A的补集为,DeMogan定理可推广为多个集合的并与交,定理1设A1,A2,Am均为有限集，m2，则,证明对m用归纳法。m=2即为(1)式。,(1),设,（2）,于是,(3),代（2）和(4)入（3）,得,而|(A1Am-1)Am|=|(A1Am)(Am-1Am)|,（4）,推论设全集S为有限集，对集合A1,Am有,（5）,证明,再将(1)式代入上式便得(5)式。其中（2.6)(2.5)是集合的两个性质,设有性质p1,p2,pm，令Ai是S中具有性质pi的元素所组成的子集合，Ai(i=1,2,m)S。则,定理和推论的组合意义:,“Ai”是S中具有至少一个性质的元素组成的集合；,例1求a,b,c,d,e,f六个字母的全排列中不允许出现ace和df图象的排列数。,3.容斥原理举例,解取全集S为六个字母的全排列的集合，设A为S中ace作为一个元素出现的排列的集合，B为S中df作为一个元素出现的排列的集合.则有,根据容斥原理，不出现ace和df的排列数为：,|S|=6!,因|A|=4！，|B|=5！，|AB|=3！,例2求1到1000的整数中，不能被5，6和8任一个整除的整数个数。,解取全集S=1,2,1000，令,A1=iiS,且5整除iA2=iiS,且6整除iA3=iiS,且8整除i,于是有,其中符号lcm6，8表示6和8的最小公倍数。表示非负实数x的整数部分。又,于是,=1000-(200+166+125)+(33+25+41)-8=600,即1到1000的整数中，不能被5，6和8任一个整除的整数有600个。,解取全集S为4个字母的全排列的集合，令A、B、C分别为n位符号串中不出现a，b，c符号的集合。,例3求由a,b,c,d四个字母构成的n位符号串中，a,b,c至少出现一次的符号串数目。,不允许出现a的n位符号串应由b，c，d构成的n位符号串，故其个数|A|=3n。,易知|S|=4n,同理|B|=|C|=3n,所以a,b,c,d四个字母构成的n位符号串中，a,b,c至少出现一次的符号串数目为,|AB|=|AC|=|BC|=2n|ABC|=1,例4求欧拉函数之值。,注欧拉函数是指小于n又和n互素的正整数的个数,解考虑大于1的正整数n的唯一分解式,其中p1p2pm都是不超过n的素数，而a1,a2,am都是正整数。,设S=1,2,n，令Ai表示S中能被pi整除的那些整数所组成的集合，i=1,2,m,这样为S中不能被pi整除的数所组成的集合。于是S中不能被p1,p2,pm整除的整数个数，即为,将以上数值代入的表达式即得,如n=30=235,则,=30(1-1/2)(1-1/3)(1-1/5)=8,例5把n本不同的书放入m个有编号的箱子中去（nm），使得没有一个箱子为空，问共有多少种放法？,解令S表示把n本不同的书任意放入m个有编号箱子的所有放法所组成的集合。显然有,令pi(i=1,2,m)表示箱子i为空这一性质，Ai(i=1,2,m)表示S中具有性质pi的元素所组成的集合，则没有一个箱子为空的元素所组成的集合为,|S|=mn,对Ai,因第i个箱子为空时，n本不同的书只能放入(m-1)个箱子中去，而每本书有m-1种选择，因此n本书就有(m-1)n种方式。即,类似地：|AiAj|=(m-2)n(ij；i=1,2,m),Ai=(m-1)n(i=1,2,m),一般