离散数学 集合.ppt

离散数学 集合现在学习的是第1页，共23页内容回顾内容回顾oo集合、元素、属于集合、元素、属于集合、元素、属于集合、元素、属于()oo集合的表示集合的表示集合的表示集合的表示n n枚举法枚举法枚举法枚举法n n描述法描述法描述法描述法 A=x|P(x)A=x|P(x)n n文氏图文氏图文氏图文氏图法法法法oo集合的基数集合的基数集合的基数集合的基数|A|A|oo集合包含集合包含集合包含集合包含 B B A iff A iff 对对对对于任一元素于任一元素于任一元素于任一元素x x：如果：如果：如果：如果x x B B则则则则必然有必然有必然有必然有x x A Aoo集合相等集合相等集合相等集合相等 B=A iff BB=A iff B A A并且并且并且并且A A B Boo集合真包含集合真包含集合真包含集合真包含 B B A iff BA iff B A A并且并且并且并且B B A Aoo空集空集空集空集 vs.vs.oo幂集幂集幂集幂集 P P(A A)=2)=2A A=x|x =x|x A A 问：问：问：问：如果如果如果如果|AA|=n|=n，则，则，则，则|P P(AA)|=?)|=?现在学习的是第2页，共23页练习练习ooP P()=?)=?ooP P(P P()=?)=?ooP P(P P(P P()=?)=?oo现在学习的是第3页，共23页1.3 集合的运算集合的运算设设设设UU为全集，为全集，为全集，为全集，AA、BB是是是是UU的子集。的子集。的子集。的子集。oo并并并并：n nA AB B=x|x=x|x A A 或者或者或者或者 x x BBoo交交交交：n n A ABB=x|x=x|x A A 并且并且并且并且 x x BBn n若若若若 A AB=B=，则称，则称，则称，则称A A与与与与B B不相交不相交不相交不相交现在学习的是第4页，共23页集合运算集合运算oo差差差差：n nA A B B=x|x=x|x A A 并且并且并且并且 x x BBoo补补补补：n n A A=U=U A=x|xA=x|x U U 并且并且并且并且 x x AAn n性质：性质：性质：性质：n nA A B B =A=A B B 现在学习的是第5页，共23页集合运算集合运算oo对称差对称差对称差对称差：n nA A B B =(A(A B)B)(B(B A)A)=x|xx|x A A且且且且x x B B，或者，或者，或者，或者x x B B且且且且x x AAn n性质：性质：性质：性质：n nA A B B =(A=(A B)B)(B(B A)A)现在学习的是第6页，共23页集合运算集合运算例例例例1.71.7：已知全集：已知全集：已知全集：已知全集UU和集合和集合和集合和集合AA、BB为为为为U:U:全体英文小写字母全体英文小写字母全体英文小写字母全体英文小写字母A=a,b,c,dA=a,b,c,dB=a,d,e,fB=a,d,e,f求集合求集合求集合求集合AA和和和和BB的并集、交集、差集、补集和对称差集的并集、交集、差集、补集和对称差集的并集、交集、差集、补集和对称差集的并集、交集、差集、补集和对称差集 解：解：解：解：A A B=B B=B A=a A=a，b b，c c，d d，e e，ffA A B=B B=B A=a A=a，ddA B=bA B=b，c c，B A=eB A=e，f f A=eA=e，f f，g g，h h，i i，j j，k k，l l，mm，n n，o o，p p，q q，r r，s s，t t，v v，ww，x x，z z B=bB=b，c c，g g，h h，i i，j j，k k，l l，mm，n n，o o，p p，q q，r r，s s，t t，v v，ww，x x，y y A A B=B B=B A=b A=b，c c，e e，f f 现在学习的是第7页，共23页习题习题求下列集合求下列集合求下列集合求下列集合AA和和和和BB的并集、交集、差集、补集和对称差集的并集、交集、差集、补集和对称差集的并集、交集、差集、补集和对称差集的并集、交集、差集、补集和对称差集 。A=NA=N，B=ZB=Z，全集，全集，全集，全集U=ZU=ZA=1A=1，3 3，5 5，88，B=2B=2，3 3，4 4，55，全集，全集，全集，全集U=x|xU=x|x为自然数，且为自然数，且为自然数，且为自然数，且x x 10 10现在学习的是第8页，共23页集合运算的性质集合运算的性质幂等律：幂等律：幂等律：幂等律：AAA=A=AA A A A=A=AA交换律：交换律：交换律：交换律：AAB=B=BBAA AA B=B=BB AA AA B=B=BB AA结合律：结合律：结合律：结合律：(A(AB)B)C C=AA(B(B C)C)(A (A B)B)C C=AA(B(B C)C)(A(A B)B)C=AC=A (B(B C)C)现在学习的是第9页，共23页集合运算的性质集合运算的性质分配律：分配律：分配律：分配律：AA(B(B C)=C)=(A(AB)B)(A(AC)C)A A(B(BC)C)=(A(A B)B)(A(A C)C)吸收律：吸收律：吸收律：吸收律：AA(A(A B)B)=AA AA(A(AB)=B)=AA零律：零律：零律：零律：AAU=U=UU A A =同一律：同一律：同一律：同一律：AA=AA A A U=U=AA现在学习的是第10页，共23页集合运算的性质集合运算的性质排中律：排中律：排中律：排中律：AA A=A=UU矛盾律：矛盾律：矛盾律：矛盾律：AA A=A=双重否定律：双重否定律：双重否定律：双重否定律：（AA）=AA现在学习的是第11页，共23页集合运算的性质集合运算的性质补交转换律补交转换律补交转换律补交转换律 AA BB=AA BB 德德德德 摩根律：摩根律：摩根律：摩根律：(A(AB)B)=AA BB (A(A B)B)=AA B B AA (B(BC)C)=(A(A B)B)(A(A C)C)A A (B(B C)C)=(A(A B)B)(A(A C)C)(余补集余补集余补集余补集)=UU U U=上述性质都可用文氏图得到方便分析和直观理解。上述性质都可用文氏图得到方便分析和直观理解。上述性质都可用文氏图得到方便分析和直观理解。上述性质都可用文氏图得到方便分析和直观理解。现在学习的是第12页，共23页证明集合运算的性质证明集合运算的性质如何证明这些基本性质的正确性？如何证明这些基本性质的正确性？n以对集合运算的定义为基础。以对集合运算的定义为基础。n以已经得到证明的性质为基础，以已经得到证明的性质为基础，利用利用集合演算集合演算。要求：熟练掌握集合运算的基本定律，能够用来证明集要求：熟练掌握集合运算的基本定律，能够用来证明集合之间的相等关系。合之间的相等关系。现在学习的是第13页，共23页证明集合运算的性质证明集合运算的性质例例例例1.8.1.8.对于集合对于集合对于集合对于集合AA和和和和BB，证明，证明，证明，证明AA B=(AB)B=(AB)(BA)(BA)证明证明证明证明 对于任意对于任意对于任意对于任意x x AA BB，根据对称差的定义知：，根据对称差的定义知：，根据对称差的定义知：，根据对称差的定义知：x x A A且且且且x x B B，或，或，或，或者者者者x x B B且且且且x x AA；又根据差集的定义知：；又根据差集的定义知：；又根据差集的定义知：；又根据差集的定义知：x x AB AB，或者，或者，或者，或者x x B B AA；再根据并集的定义知：；再根据并集的定义知：；再根据并集的定义知：；再根据并集的定义知：x x (AB)(AB)(BA)(BA)。由此，。由此，。由此，。由此，AA B B (AB)(AB)(BA)(BA)。对于任意对于任意对于任意对于任意x x (AA BB)(BB AA)，根据并集的定义知：，根据并集的定义知：，根据并集的定义知：，根据并集的定义知：x x A A BB，或者，或者，或者，或者x x B A B A；又根据差集的定义知：；又根据差集的定义知：；又根据差集的定义知：；又根据差集的定义知：x x A A且且且且x x B B，或者，或者，或者，或者x x B B且且且且x x AA；再根据对称差的定义知：；再根据对称差的定义知：；再根据对称差的定义知：；再根据对称差的定义知：x x (AA BB)(BB AA)。由此，。由此，。由此，。由此，(AA BB)(BB AA)AA BB。综上述，综上述，综上述，综上述，AA B B=(=(AA BB)(BB AA)。证毕。证毕。证毕。证毕。现在学习的是第14页，共23页证明集合运算的性质证明集合运算的性质例例例例1.9:1.9:对于集合对于集合对于集合对于集合AA、BB和和和和C C，证明：如果，证明：如果，证明：如果，证明：如果A A B=A B=A C C，则则则则B=CB=C 证明证明证明证明 对于任意对于任意对于任意对于任意x x BB，分两种情形讨论。，分两种情形讨论。，分两种情形讨论。，分两种情形讨论。情形一：情形一：情形一：情形一：x x AA。由。由。由。由x x AA及交集的定义，及交集的定义，及交集的定义，及交集的定义，x x AA BB。从而，由对称差的定义。从而，由对称差的定义。从而，由对称差的定义。从而，由对称差的定义知知知知x x AA BB，那么由已知条件得到，那么由已知条件得到，那么由已知条件得到，那么由已知条件得到x x AA C C。假定。假定。假定。假定x x C C，那么由差集，那么由差集，那么由差集，那么由差集的定义知：的定义知：的定义知：的定义知：x x AA C C；进而，由；进而，由；进而，由；进而，由AA C C=(=(AA C C)(C C AA)知：知：知：知：x x AA C C。矛盾。所以有。矛盾。所以有。矛盾。所以有。矛盾。所以有x x C C。故。故。故。故BB C C情形二：情形二：情形二：情形二：x x AA。由。由。由。由x x BB及差集的定义，及差集的定义，及差集的定义，及差集的定义，x x BB AA。由。由。由。由AA B B=(=(AA BB)(BB AA)知：知：知：知：x x AA BB，那么由已知条件得到，那么由已知条件得到，那么由已知条件得到，那么由已知条件得到x x AA C C。再由。再由。再由。再由AA C C=(=(AA C C)(C C AA)知：知：知：知：x x AA C C或或或或x x C C AA。由于。由于。由于。由于x x AA，于是，于是，于是，于是x x AA C C。由此，。由此，。由此，。由此，x x C C AA。进而。进而。进而。进而x x C C。故。故。故。故BB C C同理，可证得同理，可证得同理，可证得同理，可证得C C BB。综上知，如果综上知，如果综上知，如果综上知，如果AA B B=AA C C，则，则，则，则BB=C C。证毕。证毕。证毕。证毕。现在学习的是第15页，共23页证明集合运算的性质证明集合运算的性质例例例例1.10:1.10:已知已知已知已知AA B=AB=A C C，AA B=AB=A C C，求证，求证，求证，求证B=CB=C证明证明证明证明BB=BB (AA BB)（吸收律）（吸收律）（吸收律）（吸收律）=BB (AA C C)（已知条件）（已知条件）（已知条件）（已知条件）=(=(BB AA)(B B C C)（分配律）（分配律）（分配律）（分配律）=(=(AA BB)(B B C C)（交换律）（交换律）（交换律）（交换律）=(=(AA C C)(B B C C)（已知条件）（已知条件）（已知条件）（已知条件）=(=(AA BB)C C （分配律）（分配律）（分配律）（分配律）=(=(AA C C)C C=C C （已知条件、吸收律）（已知条件、吸收律）（已知条件、吸收律）（已知条件、吸收律）证毕。证毕。证毕。证毕。现在学习的是第16页，共23页集合运算的基本定律集合运算的基本定律例例例例1.11:1.11:试证明试证明试证明试证明P(AB)P(AB)(P(A)P(B)(P(A)P(B)证明证明证明证明 对于任意对于任意对于任意对于任意x x P P(AA BB)，如果，如果，如果，如果x x=，显然，显然，显然，显然x x (P P(AA)P P(BB)；如果；如果；如果；如果x x ，根据幂集定义，根据幂集定义，根据幂集定义，根据幂集定义，x x AA BB。从。从。从。从而，而，而，而，x x AA且且且且x x中的任何元素不是中的任何元素不是中的任何元素不是中的任何元素不是BB的元素。那么，的元素。那么，的元素。那么，的元素。那么，x x不是不是不是不是BB的的的的子集合。因此，子集合。因此，子集合。因此，子集合。因此，x x P P(AA)且且且且x x P P(BB)。所以，。所以，。所以，。所以，x x (P P(AA)P P(BB)。故。故。故。故P P(AA BB)(P P(AA)P P(BB)。证毕。证毕。证毕。证毕。现在学习的是第17页，共23页用举反例的方法判断不成立的情况用举反例的方法判断不成立的情况ooAA B=AB=A C C B=B=C C?ooAA B=AB=A C C B=B=C C?现在学习的是第18页，共23页1.4 计数问题计数问题1.4.1 1.4.1 基本计数原理基本计数原理基本计数原理基本计数原理(不作要求不作要求不作要求不作要求)1.4.2 1.4.2 排列与组合排列与组合排列与组合排列与组合(不作要求不作要求不作要求不作要求)1.4.3 1.4.3 容斥原理容斥原理容斥原理容斥原理现在学习的是第19页，共23页容斥原理（包含排斥原理）容斥原理（包含排斥原理）（计数问题）（计数问题）（计数问题）（计数问题）设设设设AA，BB是有限集合，当是有限集合，当是有限集合，当是有限集合，当AA和和和和BB不相交时，显然有不相交时，显然有不相交时，显然有不相交时，显然有|A|A BB|=|A|+|=|A|+|BB|定理定理定理定理1.4(1.4(容斥原理容斥原理容斥原理容斥原理)：设设设设AA，BB是有限集合，则：是有限集合，则：是有限集合，则：是有限集合，则：|A|AB B|=|=|A|+|A|+|B B|-|A|-|ABB|由集合运算的文氏图（图由集合运算的文氏图（图由集合运算的文氏图（图由集合运算的文氏图（图1.21.2）可以看出）可以看出）可以看出）可以看出（证明省略）（证明省略）（证明省略）（证明省略）现在学习的是第20页，共23页容斥原理（包含排斥原理）容斥原理（包含排斥原理）定理定理定理定理1.51.5：对于有限集合对于有限集合对于有限集合对于有限集合AA、BB和和和和C C，AA BB C C的基数为的基数为的基数为的基数为|A|AB BC C|=|A|+|=|A|+|B B|+|+|C C|-|A-|ABB|-|A|-|ACC|-|-|BBC|+|C|+|A A B C B C|现在学习的是第21页，共23页例例1.20例例例例1.20 1.20 求求求求15001500之间能被之间能被之间能被之间能被3 3、5 5、7 7中任一数整除的整数个数。中任一数整除的整数个数。中任一数整除的整数个数。中任一数整除的整数个数。解：设解：设解：设解：设1 1到到到到500500间分别能被间分别能被间分别能被间分别能被3 3，5 5，7 7整除的整数集合为整除的整数集合为整除的整数集合为整除的整数集合为AA，BB和和和和C C|A|=500/3=166|A|=500/3=166，|B|=500/5=100|B|=500/5=100|C|=500/7=71|C|=500/7=71|A|A B|=500/(3B|=500/(3 5)=335)=33，|A|A C|=500/(3C|=500/(3 7)=237)=23|B|B C|=500/(5C|=500/(5 7)=147)=14|A|A BB C|=500/(3C|=500/(3 5 5 7)=47)=4根据定理根据定理根据定理根据定理1.51.5得到得到得到得到|A|A B B C|=(|A|+|B|+|C|)C|=(|A|+|B|+|C|)(|A(|A B|+|AB|+|A C|+|BC|+|B C|)+|AC|)+|A B B C|C|=166+100+71=166+100+71 (33+23+14)+4=271(33+23+14)+4=271 现在学习的是第22页，共23页例例1.21例例例例1.21 1.21 对对对对100100名技术人员的调查结果表明，有名技术人员的调查结果表明，有名技术人员的调查结果表明，有名技术人员的调查结果表明，有3232人学过日语，人学过日语，人学过日语，人学过日语，2020人学过法语，人学过法语，人学过法语，人学过法语，4545人学过英语。并且，其中有人学过英语。并且，其中有人学过英语。并且，其中有人学过英语。并且，其中有1515人既学过日语人既学过日语人既学过日语人既学过日语又学过英语，又学过英语，又学过英语，又学过英语，7 7人既学过日语又学过法语，人既学过日语又学过法语，人既学过日语又学过法语，人既学过日语又学过法语，1010人既学过法语又人既学过法语又人既学过法语又人既学过法语又学过英语。学过英语。学过英语。学过英语。3030人没学过这三门语言的任何一种。根据以上提人没学过这三门语言的任何一种。根据以上提人没学过这三门语言的任何一种。根据以上提人没学过这三门语言的任何一种。根据以上提供的数据回答以下问题：供的数据回答以下问题：供的数据回答以下问题：供的数据回答以下问题：(1)(1)三种语言都学过的人数为多少？三种语言都学过的人数为多少？三种语言都学过的人数为多少？三种语言都学过的人数为多少？(2)(2)只学过日语、只学过法语、只学过英语的人数各为多少？只学过日语、只学过法语、只学过英语的人数各为多少？只学过日语、只学过法语、只学过英语的人数各为多少？只学过日语、只学过法语、只学过英语的人数各为多少？(3)(3)至少学过以上三种语言中的两种语言的人数为多少？至少学过以上三种语言中的两种语言的人数为多少？至少学过以上三种语言中的两种语言的人数为多少？至少学过以上三种语言中的两种语言的人数为多少？(4)(4)只学过日语和法语、只学过日语和英语、只学过法语和英语只学过日语和法语、只学过日语和英语、只学过法语和英语只学过日语和法语、只学过日语和英语、只学过法语和英语只学过日语和法语、只学过日语和英语、只学过法语和英语的人数各为多少？的人数各为多少？的人数各为多少？的人数各为多少？解：解：解：解：(P15)(P15)略略略略.现在学习的是第23页，共23页