《包含排斥原理》PPT课件

《《包含排斥原理》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、3-3包含排斥原理(容斥原理)要求：掌握n个集合的包含排斥原理，并应用它求解实际问题。复习：集合的运算（交、并、补、对称差）1、交集定义3-2.1：设任意两个集合A和B，由A和B的所有共同元素组成的集合，称为A和B的交集，记为AB。AB={x

2、xAxB}文氏图2、并集定义3-2.2：设任意两个集合A和B，所有属于A或属于B的元素组成的集合，称为A和B的并集，记作AB。AB={x

3、xAxB}文氏图3、差集、补集定义3-2.3：设A、B是任意两个集合，所有属于A而不属于B的元素组成的集合称为B对A的补集，或相对补，(

4、或A和B差集)记作A-B。A-B={x

5、xA∧xB}文氏图4、对称差定义3-2.5：设A、B是任意两个集合，集合A和B的对称差，其元素或属于A，或属于B，但不能既属于A又属于B，记作AB。AB=(A-B)(B-A)文氏图(1)max(

6、A

7、，

8、B

9、)≤

10、AB

11、≤

12、A

13、+

14、B

15、(2)

16、AB

17、≤min(

18、A

19、，

20、B

21、)(3)

22、A

23、-

24、B

25、≤

26、A-B

27、≤

28、A

29、(4)

30、AB

31、=

32、A

33、+

34、B

35、-2

36、AB

37、一、有限集合的计数设A，B为有限集合，其元素个数分别为

38、A

39、，

40、B

41、，根据集合运算的定义，显然以下各式成立。二、包含排斥原

42、理1、定理3-3.1：设A1，A2为有限集合，其元素个数分别为

43、A1

44、，

45、A2

46、，则

47、A1A2

48、=

49、A1

50、+

51、A2

52、-

53、A1A2

54、，此定理被称作包含排斥原理。证明：a)当A1A2=，则

55、A1A2

56、=

57、A1

58、+

59、A2

60、b)若A1A2，则

61、A1

62、=

63、A1～A2

64、+

65、A1A2

66、，

67、A2

68、=

69、～A1A2

70、+

71、A1A2

72、所以

73、A1

74、+

75、A2

76、=

77、A1～A2

78、+

79、A1A2

80、+

81、～A1A2

82、+

83、A1A2

84、=

85、A1～A2

86、+

87、～A1A2

88、+2

89、A1A2

90、而

91、A1～A2

92、+

93、～A1A2

94、+

95、A1A2

96、=

97、A

98、1A2

99、故

100、A1A2

101、=

102、A1

103、+

104、A2

105、-

106、A1A2

107、解：设A为从1到500的整数中，能被3除尽的数的集合。B为从1到500的整数中，能被5除尽的数的集合。则A=[500/3]=166（[x]表示不超过x的最大整数）B=[500/5]=100AB=[500/（3*5）]=33由包含排斥原理：AB=A+B-AB=166+100-33=233即从1到500的整数中，能被3或5除尽的数有233个。例1：求从1到500的整数中，能被3或5除尽的数的个数。解：设职员和学生的集合分别是A和B。由已知条件

108、A=10，B=12，AB=5，有AB=A+B-AB=10+12-5=17，则(AB)=E-AB=20-17=3。有3名青年既不是职员又不是学生。例2：在20名青年中有10名是公司职员，12名是学生，其中5名既是职员又是学生，问有几名既不是职员，又不是学生。例题3假设在10名青年中有5名是工人，7名是学生，其中兼具工人和学生双重身份的青年有3名，问有几名既不是工人又不是学生。解：设工人的集合为W，学生的集合为S。则根据题设有

109、E

110、=10，W=5，S=7，WS=3，则W

111、S=W+S-WS=5+7-3=9，则(AB)=E-AB=10-9=1。有1名既不是工人又不是学生。2、三个集合的包含排斥原理：对于三个集合A1，A2和A3，其元素个数分别为

112、A1

113、，

114、A2

115、，

116、A3

117、，则

118、A1A2A3

119、=

120、A1

121、+

122、A2

123、+

124、A3

125、-

126、A1A2

127、-

128、A1A3

129、-

130、A2A3

131、+

132、A1A2A3

133、例题4在某工厂装配30辆汽车，可供选择的设备是收音机、空气调节器和对讲机。已知其中有15辆汽车有收音机，8辆有空气调节器，6辆有对讲机，而且其中有3辆汽车这三样设备都有。我们希望

134、至少有多少辆汽车没有任何设备。解：设A1，A2和A3分别表示配有收音机、空气调节器和对讲机的汽车集合。因此

135、A1

136、=15，

137、A2

138、=8，

139、A3

140、=6，

141、A1A2A3

142、=3，故

143、A1A2A3

144、=

145、A1

146、+

147、A2

148、+

149、A3

150、-

151、A1A2

152、-

153、A1A3

154、-

155、A2A3

156、+

157、A1A2A3

158、=15+8+6-

159、A1A2

160、-

161、A1A3

162、-

163、A2A3

164、+3=32-

165、A1A2

166、-

167、A1A3

168、-

169、A2A3

170、因为

171、A1A2

172、

173、A1A2A3

174、，

175、A1A3

176、

177、A1A2A3

178、，

179、A2A3

180、

181、A1A2A3

182、所以

183、

184、A1A2A3

185、32-3-3-3=23即至多有23辆汽车有一个或几个选择的设备，因此至少有7辆汽车不提供任何可选择的设备。练习：某年级有59名学生，期末考高等数学、线性代数和英语三门课。已知高等数学、线性代数和英语各门课的及格人