离散数学 集合

离散数学集合第1页，共23页，2023年，2月20日，星期一内容回顾集合、元素、属于()集合的表示枚举法描述法A={x|P(x)}文氏图法集合的基数|A|集合包含BAiff对于任一元素x：如果xB则必然有xA集合相等B=AiffBA并且AB集合真包含BAiffBA并且BA空集vs.{}幂集P(A)=2A={x|xA}问：如果|A|=n，则|P(A)|=?第2页，共23页，2023年，2月20日，星期一练习P()=?P(P())=?P(P(P()))=?……第3页，共23页，2023年，2月20日，星期一1.3集合的运算设U为全集，A、B是U的子集。并：

A∪B={x|xA

或者

xB}交：

A∩B={x|xA

并且

xB}若A∩B=，则称A与B不相交第4页，共23页，2023年，2月20日，星期一集合运算差：

AB={x|xA

并且

xB}补：A=UA={x|xU

并且

xA}性质：

AB

=A∩B第5页，共23页，2023年，2月20日，星期一集合运算对称差：AB=(AB)∪(BA)={x|xA且xB，或者xB且xA}性质：

AB

=(AB)∪(BA)第6页，共23页，2023年，2月20日，星期一集合运算例1.7：已知全集U和集合A、B为 U:全体英文小写字母 A={a,b,c,d} B={a,d,e,f}求集合A和B的并集、交集、差集、补集和对称差集解：AB=BA={a，b，c，d，e，f}AB=BA={a，d}A–B={b，c}，B–A={e，f}A={e，f，g，h，i，j，k，l，m，n，o，p，q，r，s，t，v，w，x，z}B={b，c，g，h，i，j，k，l，m，n，o，p，q，r，s，t，v，w，x，y}AB=BA={b，c，e，f}第7页，共23页，2023年，2月20日，星期一习题求下列集合A和B的并集、交集、差集、补集和对称差集。①

A=N，B=Z，全集U=Z②A={1，3，5，8}，B={2，3，4，5}，全集U={x|x为自然数，且x10}第8页，共23页，2023年，2月20日，星期一集合运算的性质①幂等律：A∪A=

AA∩A=

A②交换律：A∪B=

B∪A

A∩B=

B∩A

AB=

BA③结合律：(A∪B)∪C=A∪(B∪C)(A∩B)∩C=A∩(B∩C)

(AB)C=A(BC)第9页，共23页，2023年，2月20日，星期一集合运算的性质④分配律：A∪(B∩C)=

(A∪B)∩(A∪C)A∩(B∪C)=(A∩B)∪(A∩C)⑤吸收律：A∪(A∩B)=A

A∩(A∪B)=

A⑥零律：A∪U=

UA∩=

⑦同一律：A∪=

AA∩U=

A第10页，共23页，2023年，2月20日，星期一集合运算的性质⑧排中律：A∪A=

U⑨矛盾律：A∩A=

⑩双重否定律：（A）=

A第11页，共23页，2023年，2月20日，星期一集合运算的性质⑪补交转换律A–B=AB

⑫德摩根律：(A∪B)=A∩B

(A∩B)=A∪B

A(B∪C)=(AB)∩(AC) A(B∩C)=(AB)∪(AC)⑬(余补集)=U

U=上述性质都可用文氏图得到方便分析和直观理解。第12页，共23页，2023年，2月20日，星期一证明集合运算的性质如何证明这些基本性质的正确性？以对集合运算的定义为基础。以已经得到证明的性质为基础，

利用集合演算。要求：熟练掌握集合运算的基本定律，能够用来证明集合之间的相等关系。第13页，共23页，2023年，2月20日，星期一证明集合运算的性质例1.8.对于集合A和B，证明AB=(A–B)(B–A)

证明对于任意xAB，根据对称差的定义知：xA且xB，或者xB且xA；又根据差集的定义知：xA–B，或者xB–A；再根据并集的定义知：x(A–B)(B–A)。由此，AB(A–B)(B–A)。对于任意x(A–B)(B–A)，根据并集的定义知：xA–B，或者xB–A；又根据差集的定义知：xA且xB，或者xB且xA；再根据对称差的定义知：x(A–B)(B–A)。由此，

(A–B)(B–A)

AB。综上述，AB=(A–B)(B–A)。证毕。第14页，共23页，2023年，2月20日，星期一证明集合运算的性质例1.9:对于集合A、B和C，证明：如果AB=AC，则B=C

证明对于任意xB，分两种情形讨论。情形一：xA。由xA及交集的定义，xAB。从而，由对称差的定义知xAB，那么由已知条件得到xAC。假定xC，那么由差集的定义知：xA–C；进而，由AC=(A–C)(C–A)知：xAC。矛盾。所以有xC。故B

C情形二：xA。由xB及差集的定义，xB–A。由AB=(A–B)(B–A)知：xAB，那么由已知条件得到xAC。再由AC=(A–C)(C–A)知：xA–C或xC–A。由于xA，于是xA–C。由此，xC–A。进而xC。故B

C同理，可证得C

B。综上知，如果A

B=A

C，则B=C。证毕。

第15页，共23页，2023年，2月20日，星期一证明集合运算的性质例1.10:已知AB=AC，AB=AC，求证B=C证明B=B(AB)（吸收律）=B(AC)（已知条件）=(BA)(BC)（分配律）=(AB)(BC)（交换律）=(AC)(BC)（已知条件）=(AB)

C

（分配律）=(AC)

C=C

（已知条件、吸收律）证毕。

第16页，共23页，2023年，2月20日，星期一集合运算的基本定律例1.11:试证明P(A–B)(P(A)–P(B)){}

证明对于任意xP(A–B)，如果x=，显然x(P(A)–P(B)){}；如果x

，根据幂集定义，x

A–B。从而，x

A且x中的任何元素不是B的元素。那么，x不是B的子集合。因此，xP(A)且xP(B)。所以，x(P(A)–P(B))。故P(A–B)(P(A)–P(B)){}。证毕。

第17页，共23页，2023年，2月20日，星期一用举反例的方法判断不成立的情况A∪B=A∪CB=C?A∩B=A∩CB=C?第18页，共23页，2023年，2月20日，星期一1.4计数问题1.4.1基本计数原理(不作要求)1.4.2排列与组合(不作要求)1.4.3容斥原理第19页，共23页，2023年，2月20日，星期一容斥原理（包含排斥原理）（计数问题）设A，B是有限集合，当A和B不相交时，显然有|A∪B|=|A|+|B|定理1.4(容斥原理)：设A，B是有限集合，则：

|A∪B|=|A|+|B|-|A∩B|由集合运算的文氏图（图1.2）可以看出（证明省略）

第20页，共23页，2023年，2月20日，星期一容斥原理（包含排斥原理）定理1.5：对于有限集合A、B和C，ABC的基数为

|A∪B∪C|=|A|+|B|+|C|

-|A∩B|-|A∩C|-|B∩C|+|

A∩

B∩C|第21页，共23页，2023年，2月20日，星期一例1.20例1.20求1~500之间能被3、5、7中任一数整除的整数个数。解：设1到500间分别能被3，5，7整除的整数集合为A，B和C|A|=[500/3]=166，|B|=[500/5]=100|C|=[500/7]=71|AB|=[500/(35)]=33，|AC|=[500/(37)]=23|BC|=[500/(57)]=14|ABC|=[500/(357)]=4根据定理1.5得到|ABC|=(|A|+|B|+|C|)–(|AB|+|AC|+|BC|)+|ABC| =166+100+71(33+23+14)+4=271第22页，共23页，2023年，2月20日，星期一例1.21例1.21对100名技