资源描述：
《离散数学第二讲》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、一、集合的概念与运算（§仁2。）4、、集合的运算对称差：(A-5)U(B-A)=(AUB)-(AA5)3）、有关推论：⑴、AB<==>A—A（^B（充分必要条件）(2)、AUA=（/Ap
2、A=O（集合之最简单划分）•集合的VENN图表示……5、集合之运算规律:(1)專等律AUA=A,AQA=A(2)交换律AAB=BAA，A㊉B—B㊉A(3)结合律(AUB)UC=AU(BUC)(AAB)nc=An(Bnc)(4㊉B)㊉C=A㊉(B㊉C)(4)分配律AA(BUC)=(AnB)U(AnC)AU(BAC)=(AUB)n(AUC)(5)摩根律AUB=AQ
3、B,AQB=AU5(1)双否定律A=A(2)补余律AJA=U,=O(3)同一律AUO=A,A^U=A,A㊉(D=A(4)零一律AJU=U,的①二①(5)A—B=APlB=A—AB(11)A㊉B=(A-B)U(B-A)=(AUB)-(AAB)(12)(⑶A㊉A=O（14）吸收律AU(AAB)=AAA(AUB)=A6、证明集合相等之方法:方法一：利用定义若F匚Q且QmP则P=Qe.g1证明：A=A方法二：利用已知运算公式，演算逻辑等式e.g2设A㊉B=A㊉C证明方法越简单越好方法三：反证法（同一法）e.g3证明若A㊉B=AjBf则anb=①证明
4、一、（同一法）右Bx€小5则xeAUB=A㊉B,但xeA㊉乩有AU5冃ARB；矛盾。证明二、an=（Ann（au=（AnB）n（A㊉b）=…二①其它方法：e.g4证明4㊉B=A㊉B二、容斥原理与鸽巢原理1、容斥原理（§1。3o）（计数原理、包含排斥原理）e.g1在1,2……,100这100个自然数中,有多少个不能被2、3、5整除的数？B：考虑集合S={1,2,3,…,100}xeS，2整除兀}XGS,3整除X}xeS，5整除x}a2na3na51002-3-5
5、4n人彳曇卜10,刖制将=6,肉
6、=豊=50写在VENN图上，得A2UA3uA5
7、=7
8、4,A?n17nA?=100-74=26除了文氏图的方法外，对于集合还有一条重要的定理:容斥原理（包含排斥原理）:设A,B是有限集，贝IJa[^b=a+b-a^b证明：证法一：（利用VENN图看）证法二：（由集合的运算规律）证法三：（贡献法）容斥原理的相关推论：(i)
9、AUBUC
10、+
11、b
12、+
13、c
14、—
15、aAb
16、—
17、bpc
18、—
19、aAc
20、+
21、aAbAc
22、证明：(ii)利用归纳法
23、AUA2UA3U-U4
24、n=£人卜工
25、4门人」+工人门人川入z=l1
26、+Ia
27、=uf
28、a
29、=
30、
31、c/1-
32、a(iv)e.g「在1,2……,100这100个自然数中,有多少个不能被2、3、5整除的数？e.g2设出=3,=64,
33、P(AU列=256.求A—BA㊉Bo解：0=6,#Ub
34、
35、=8（注意基的具体含义）设S是有限集，尸1，尸2,•…，P『是r条性质,A/是s中具有性质匚的子集，即4=｛兀xeS.x具有性质用｝（i二1,2,…，r）则（1）S中至少具有性质P1'卩2，••・、P丫_条的元素数是:I4U4UAU--U4=1LIA
36、-AA+AAAAki=\37、性质尸1，尸2，…，Pr的元素数是：AnA2n---nAr=u-e.g3求在1到1000000之间（包括1和1000000在内，10°）有多少个整数既不是平方数也不是立方数?e.g4一个班里有50个学生，第一次考试中有26人及格，在第二次考试中有21人及格，如果两次考试都没有及格的有17人，那么两次考试都及格的有多少人？解仁设A,B分别表示在第一次和第二次考试中及格的学生的集合，则有
38、5
39、=509A=26,
40、B
41、=21AflB=17由包含排斥原理，有
42、/4AS=S—(
43、/114-B—APljB
44、)
45、aab=AQB-
46、5
47、+
48、a
49、+
50、b
51、=1
52、7-50+26+21=14解2：画出WENN图首先填入中的人数x,然后填入其它区域的数字,列出相应的方程，解出X.e・g5（课堂练习）求在1和1000之间不能被5,6,也不能被8整除的数的个数。解：设S={1,2,3,・・・，1000}A={x
53、xeS,5整除x}B={xxeS，6整除兀}C={x
54、xgS,8整除x}则A卜］晋2j=200,同==166小［忡25（符号［d,b］最小公倍数）1000100030=33
55、Anc1000丽100040=251000~2AAABAC1000_［5A8］BDC
56、=1000丽1000"120-=41所以
57、AU
58、BUC
59、=
60、y4
61、+
62、b
63、+
64、cj—
65、AflB
66、——AflCj+
67、AriBric
68、=200+166+125—33—25—41+8=400
