交大数理逻辑课件9-3集合

《交大数理逻辑课件9-3集合》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、调课通知因下周五(11月26日)为广州亚运会闭幕式官方放假时间，<数理逻辑>课程调到下周三(11月24日)5,6节在310305课室上课，特告之。第9章集合9.1集合的概念和表示方法9.2集合间的关系和特殊集合9.3集合的运算9.4集合的图形表示法9.5集合运算的性质和证明9.6有限集合的基数证明集合XY的方法命题演算法x，xX…xY包含传递法找到集合T满足XT且TY，从而有XY利用包含的等价条件XYX∪Y=YX∩Y=XX－Y=反证法利用已知包含式并交运算XYXZYZ,XZYZ例6证明A(AB)=A（吸收律）证

2、任取x,xA(AB)xAxABxA(xAxB)xA命题演算法证明X=Y任取x，xX…xYxY…xX或者xX…xYX(XY)X等式替换证明X=Y例7证明A(AB)=A（吸收律）证(假设分配律、同一律、零律成立)A(AB)=(AE)(AB)同一律=A(EB)分配律=AE零律=A同一律不断进行代入化简，最终得到两边相等反证法证明X=Y例8证明AB=AAB=证:假设AB,即xAB，那么xA且xB.而xBxAB.从而与AB=A矛盾.假设X=Y不成立，则存

3、在x使得xX且xY，或者存在x使得xY且xX，然后推出矛盾.集合运算法证明X=Y例9证明AC=BCAC=BCA=B证:由AC=BC和AC=BC得到(AC)-(AC)=(BC)-(BC)从而有AC=BC因此AC=BC(AC)C=(BC)CA(CC)=B(CC)A=BA=B由已知等式通过运算产生新的等式X=YXZ=YZ,XZ=YZ，X-Z=Y-ZA=B,C=D(A-C)=(B-D)有限集合的基数若n∈N，使集合A与集合{x

4、x∈N∧x

5、记作:#(A)=n或

6、A

7、=n,或card(A)=n,空集的基数为0，即

8、Æ

9、=0有限集的实例：A={a,b,c},cardA=

10、A

11、=3；B={x

12、x2+1=0,xR},cardB=

13、B

14、=09.6有限集合的基数9.6.2幂集和笛卡尔积的基数[定理9.6.1]对有限集合A，

15、P(A)

16、=2

17、A

18、证明:设

19、A

20、=n∈N，由A的k个元素组成的子集的数目(k=0,1,…,n)∴=2n=2

21、A

22、[定理9.6.2]对有限集合A和B，

23、A×B

24、=

25、A

26、·

27、B

28、9.6.3基本运算的基数[定理9.6.3]对有限集合A和B，有

29、A∪B

30、≤

31、A

32、+

33、B

34、

35、A∩B

36、≤min(

37、

38、A

39、,

40、B

41、)

42、A－B

43、≥

44、A

45、－

46、B

47、

48、AB

49、=

50、A

51、+

52、B

53、－2

54、A∩B

55、包含排斥原理（有限集合的元素个数的计数问题）[定理9.6.4]:设A1、A2为有限集合,有

56、A1A2

57、=

58、A1

59、+

60、A2

61、-

62、A1A2

63、证明：(1)当A1A2=，则

64、A1A2

65、=

66、A1

67、+

68、A2

69、(2)当A1A2，则

70、A1

71、=

72、A1-A2

73、+

74、A1A2

75、

76、A2

77、=

78、-A1A2

79、+

80、A1A2

81、所以

82、A1

83、+

84、A2

85、=

86、A1-A2

87、+

88、-A1A2

89、+2

90、A1A2

91、=

92、A1A2

93、+

94、A1A2

95、所以

96、A1A2

97、=

98、A1

99、+

100、A2

101、-

102、A1A2

103、包含

104、排斥原理举例某班有50名学生，第一次考试中26人成绩为优，第二次考试中21人成绩为优，已知两次考试中都不为优的共17人。问两次考试都为优的有几人？解：设A，B分别表示第一次和第二次考试中成绩为优的学生集合，画出文氏图。(1)首先填A∩B中的人数，这正是要求的，设为x。(2)A-B中的人数是26-x，B-A中的人数是21-x，分别填入对应的区域。(3)并列出如下方程：(26-x)＋x＋(21-x)＋17=50解得：x=14x21-x26-x对于任意三个集合A1，A2和A3，有

105、A1A2A3

106、=

107、A1

108、+

109、A2

110、+

111、A2

112、-

113、A1A2

114、-

115、A1A3

116、-

117、

118、A2A3

119、+

120、A1A2A3

121、三个集合的并集的元素个数n个集合的包含排斥原理定理：设A1，A2，…An为有限集合，其元素个数分别为

122、A1

123、，

124、A2

125、，…

126、An

127、，则包含排斥原理举例解：S={x

128、xZ,1x1000},如下定义S的3个子集A,B,C：A={x

129、xS,5

130、x}，B={x

131、xS,6

132、x}，C={x

133、xS,8

134、x}利用下面公式求

135、ABC

136、

137、ABC

138、=

139、A

140、+

141、B

142、+

143、C

144、-

145、AB

146、-

147、AC-

148、BC

149、+

150、ABC

151、例:求1到1000之间（包含1和1000在内）既不能被5和6整除，也不能被8整除的数有多少个？对上述子集计数

152、：

153、S

154、=1000,

155、A

156、=1000/5=200