《包含排斥原理》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輛汽車，可供選擇的設備是收音機、空氣調節(jié)器和對講機。已知其中有15輛汽車有收音機，8輛有空氣調節(jié)器，6輛有對講機，而且其中有3輛汽車這三樣設備都有。我們希望

134、至少有多少輛汽車沒有任何設備。解：設A1，A2和A3分別表示配有收音機、空氣調節(jié)器和對講機的汽車集合。因此

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名學生，期末考高等數學、線性代數和英語三門課。已知高等數學、線性代數和英語各門課的及格人