《数理逻辑与二元关系3》由会员分享，可在线阅读，更多相关《数理逻辑与二元关系3（23页珍藏版）》请在金锄头文库上搜索。
1、数理逻辑与二元关系数理逻辑与二元关系任课教师：杨春任课教师：杨春Email: 1 一些计数问题可归结为计算一个或一些计数问题可归结为计算一个或一些集合中的元素个数。而有时在计一些集合中的元素个数。而有时在计算集合并的元素个数较困难而计算交算集合并的元素个数较困难而计算交较容易时，我们可利用集合的性质将较容易时，我们可利用集合的性质将计算的问题转化为计算交。这就是容计算的问题转化为计算交。这就是容斥原理思想斥原理思想。容斥原理容斥原理21. 集合的几个性质集合的几个性质有有(a) = U - A 设设 U 为全集为全集, 集合集合A的的补集补集 为为(b) DeMorgan律律AB = AB A
2、 B = A B3DeMogan定理定理可可推广为推广为多多个集合的并与交个集合的并与交(1)(c)|A B | = |A| + |B| - |A B|UBAAB4定理定理1设设A1 , A2 , , Am均为有限集，均为有限集，m2，则则 证明证明 对对m 用归纳法。用归纳法。 m =2 即为即为(1)式。式。(1)5 设设（2）于是于是(3)6代（代（2）和）和 (4) 入（入（3）, 得得而而 |(A1Am-1) Am | = |(A1 Am) (Am-1 Am ) | （4）7推论推论 设全集设全集 S 为有限集，对集合为有限集，对集合 A1 , , Am 有有 （5） 证明证明再将再
3、将 (1) 式代入上式便得式代入上式便得(5) 式。其中（式。其中（2.6)(2.5)2.6)(2.5)是集是集合的两个性质合的两个性质8设有性质设有性质 p1, p2, pm ，令令 Ai 是是 S 中具有性质中具有性质 pi 的元的元素所组成的子集合，素所组成的子集合，Ai (i =1,2,m) S。则。则定理和推论的组合意义定理和推论的组合意义: “ Ai ” 是是 S 中具有至少一个性质的元素组成中具有至少一个性质的元素组成的集合；的集合； Ai“ ” 是是S 中既不具有性质中既不具有性质 p1，又不具有又不具有性质性质 p2, ，更不具有性质更不具有性质 pm 的元素的集合。的元素的
4、集合。9 例例1 求求 a,b,c,d,e,f 六个字母的全排列中不允六个字母的全排列中不允许出现许出现 ace 和和 df 图象的排列数。图象的排列数。3. 容斥原理举例容斥原理举例解解 取全集取全集S 为六个字母的全排列的集合，为六个字母的全排列的集合，设设A为为S 中中 ace 作为一个元素出现的排列的作为一个元素出现的排列的集合，集合，B 为为 S 中中 df 作为一个元素出现的作为一个元素出现的排列的集合排列的集合. 则有则有10 根据容斥原理，不出现根据容斥原理，不出现 ace 和和 df 的排列数的排列数为：为：|S| = 6!因因 |A | = 4！，！，|B | = 5！，！
5、，|A B |= 3！ | A B | =6!- (5!+4!)+3!=582 11 例例2 求求1到到1000的整数中，不能被的整数中，不能被5，6和和8任一任一个整除的整数个数。个整除的整数个数。解解 取全集取全集 S = 1,2,1000，令令A1 = i i S , 且且5 整除整除 i A2 = i i S , 且且6 整除整除 i A3 = i i S , 且且8 整除整除 i 于是有于是有12 其中符号其中符号 lcm6，8 表示表示 6 和和 8 的最的最小公倍数。小公倍数。 表示非负实数表示非负实数 x 的整数部分。又的整数部分。又13于是于是 = 1000- -(200+1
6、66+125)+(33+25+41)- -8 = 600 即即 1 到到 1000 的整数中，不能被的整数中，不能被5，6 和和 8 任一个整除的整数有任一个整除的整数有600个。个。14 解解 取全集取全集S 为为4 个字母的全排列的集合，个字母的全排列的集合，令令A、B、C 分别为分别为 n 位符号串中不出现位符号串中不出现a，b，c 符号的集合。符号的集合。例例3 求由求由 a,b,c,d 四个字母构成的四个字母构成的 n 位符号位符号串中，串中，a,b,c 至少出现一次的符号串数目。至少出现一次的符号串数目。 不允许出现不允许出现 a 的的 n 位符号串位符号串应应由由b，c，d 构成
7、的构成的 n 位符号串，故位符号串，故其个数其个数 |A| = 3n。易知易知 |S| = 4n同理同理 |B| = |C| = 3n15 所以所以 a,b,c,d 四个字母构成的四个字母构成的 n 位符位符号串中，号串中，a,b,c 至少出现一次的符号串数至少出现一次的符号串数目为目为|AB| = |AC | = |BC |=2n |AB C |=1|AB C | = 4n - 3 3n + 3 2n - 116例例4 求欧拉函数求欧拉函数 之值。之值。 注注 欧拉函数是指小于欧拉函数是指小于n 又和又和 n 互素的正整数的个数互素的正整数的个数解解 考虑大于考虑大于1的正整数的正整数n的唯
8、一分解式的唯一分解式其中其中p1 p2 pm都是不超过都是不超过n的素数，而的素数，而a1, a2,am都是正整数。都是正整数。 设设S =1,2,n，令令 Ai表示表示S 中能被中能被 pi 整除的那些整数所组成的集合，整除的那些整数所组成的集合，i =1,2,m 17 这样这样 为为S中不能被中不能被 pi 整除的数所组成整除的数所组成的集合。于是的集合。于是S 中不能被中不能被 p1,p2, pm 整除的整除的整数个数，即整数个数，即 为为而而 |S|=n， （i =1,2,m） | AiAj|= （i,j =1,2,m；ij） 18将以上数值代入将以上数值代入 的表达式即得的表达式即得
9、 19如如 n = 30 = 235, 则则=30(1-1/2)(1-1/3)(1-1/5)= 8例例5 把把 n 本不同的书放入本不同的书放入 m 个有编号的箱个有编号的箱子中去（子中去（nm），），使得没有一个箱子为空，使得没有一个箱子为空，问共有多少种放法？问共有多少种放法？20解解 令令S 表表示示把把n本本不不同同的的书书任任意意放放入入m个个有有编编号号箱箱子子的的所所有有放放法法所所组组成成的的集集合合。显显然有然有令令 pi (i =1,2,m) 表示箱子表示箱子 i 为空这一性质，为空这一性质，Ai (i =1,2,m)表示表示S中具有性质中具有性质 pi 的元素所的元素所组
10、成的集合，则没有一个箱子为空的元素所组成的集合，则没有一个箱子为空的元素所组成的集合为组成的集合为 |S| = mn21 对对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) 一般地，对于下标为一般地，对于下标为 i1 ,i2 ,ik 的的 k 个个Ai 有有22 而对于而对于 i =1,2,m，在在 m 个集合中取个集合中取k个集合一共有个集合一共有 C(m,i) 种方式。由乘法规则种方式。由乘法规则和容斥原理即可得符合题意的放法数为和容斥原理即可得符合题意的放法数为： 23
