数理逻辑与二元关系3

《数理逻辑与二元关系3》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数理逻辑与二元关系任课教师：杨春Email:yc517922@126.com数学科学学院一些计数问题可归结为计算一个或一些集合中的元素个数。而有时在计算集合并的元素个数较困难而计算交较容易时，我们可利用集合的性质将计算的问题转化为计算交。这就是容斥原理思想。容斥原理1.集合的几个性质有(a)︱︱=︱U︱-︱A︱设U为全集,集合A的补集为(b)DeMorgan]律A∩B=A∪BA∪B=A∩BDeMogan定理可推广为多个集合的并与交(1)(c)

2、A∪B

3、=

4、A

5、+

6、B

7、-

8、A∩B

9、UBAA∩B定理1设A1,A2,…,Am均为有限集，m≥2，则证明对m用归

10、纳法。m=2即为(1)式。(1)设（2）于是(3)代（2）和(4)入（3）,得而

11、(A1∪…∪Am-1)∩Am

12、=

13、(A1∩Am)∪…∪(Am-1∩Am)

14、（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中具有至少一个性质的元素组成的集合；Ai“∩”是S中既不具有性质p1，又不具有性质p2,…，更不具有性质pm的元素的集合。

15、例1求a,b,c,d,e,f六个字母的全排列中不允许出现ace和df图象的排列数。3.容斥原理举例解取全集S为六个字母的全排列的集合，设A为S中ace作为一个元素出现的排列的集合，B为S中df作为一个元素出现的排列的集合.则有根据容斥原理，不出现ace和df的排列数为：

16、S

17、=6!因

18、A

19、=4！，

20、B

21、=5！，

22、A∩B

23、=3！

24、A∩B

25、=6!-(5!+4!)+3!=582例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

26、∈S,且8整除i}于是有其中符号lcm{6，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位符号串，故其个数

27、A

28、=3n。易知

29、S

30、=4n同理

31、B

32、=

33、C

34、=3n所以a,b,c,

35、d四个字母构成的n位符号串中，a,b,c至少出现一次的符号串数目为

36、A∩B

37、=

38、A∩C

39、=

40、B∩C

41、=2n

42、A∩B∩C

43、=1

44、A∩B∩C

45、=4n-3×3n+3×2n-1例4求欧拉函数之值。注欧拉函数是指小于n又和n互素的正整数的个数解考虑大于1的正整数n的唯一分解式其中p1

46、S

47、=n，（i=1,

48、2,…,m）

49、Ai∩Aj

50、=（i,j=1,2,…,m；i≠j）将以上数值代入的表达式即得如n=30=2×3×5,则=30(1-1/2)(1-1/3)(1-1/5)=8例5把n本不同的书放入m个有编号的箱子中去（n≥m），使得没有一个箱子为空，问共有多少种放法？解令S表示把n本不同的书任意放入m个有编号箱子的所有放法所组成的集合。显然有令pi(i=1,2,…,m)表示箱子i为空这一性质，Ai(i=1,2,…,m)表示S中具有性质pi的元素所组成的集合，则没有一个箱子为空的元素所组成的集合为

51、S

52、=mn对Ai,因第i个箱子为空时，n本不同的书只能放入(m-

53、1)个箱子中去，而每本书有m-1种选择，因此n本书就有(m-1)n种方式。即类似地：

54、Ai∩Aj

55、=(m-2)n(i≠j；i=1,2,…,m)｜Ai｜=(m-1)n(i=1,2,…,m)一般地，对于下标为i1,i2,…,ik的k个Ai有而对于i=1,2,…,m，在m个集合中取k个集合一共有C(m,i)种方式。由乘法规则和容斥原理即可得符合题意的放法数为：