3-2-集合的基本概念与运算-离散数学-教学课件.ppt

第3章 集合的基本概念和运算3.1 集合的基本概念3.2 集合的基本运算3.3 集合中元素的计数例题n分别对条件(1)到(5)，确定 X 集合与下述那些集合相等。S1=1,2,3,4,5,6,7 8,9,S2=2,4,6,8,S3=1,3,5,7,9,S4=3,4,5,S5=3,5 若若 X S1，X S3=,则则 X 若若 X S4,X S2=,则则 X 若若 X S1，X S3,则则 X 若若 X S3=,则则 X 若若 X S3，X S1,则则 X=S2=S5=S1,S2,S4=S3,S5不存在不存在集合包含或相等的证明方法n证明证明 X Yn命题演算法命题演算法n包含传递法包含传递法n等价条件法等价条件法n反证法反证法n并交运算法并交运算法n证明证明 X=Yn命题演算法命题演算法n等式代入法等式代入法n反证法反证法n运算法运算法以上的以上的 X,Y 代表集合公式代表集合公式任取任取 x，x X x Y命题演算法证 X Yn证证:(1)A B P(A)P(B)任取任取x,x P(A)x A x B x P(B)(2)P(A)P(B)A B 任取任取x x A x A x P(A)x P(B)x B x B 例例1 证明证明 A B P(A)P(B)X Yx(x Xx Y)利用包含的等价条件证 X Y(1)证证 (A B)C=C A C A C=C B C B C=C (A B)C =A (B C)=A C=C(A B)C=C A B C(2)证证 (A B)C=A B A C A C=A B C B C=B (A B)C =(A C)(B C)=A B(A B)C=A BA B C例例3 A C B C A B C 反证法证 X Y欲证欲证X Y,假设命题不成立，必存在假设命题不成立，必存在 x 使得使得 x X 且且 x Y.然后推出矛盾然后推出矛盾.例例4 证明证明 A C B C A B C证证 假设假设 A B C 不成立，则不成立，则 A B C x(x A B x C)x(x A x B)x C)x(x A x C)(x B x C)x(x A x C)x(x B x C)A C B C （与前提矛盾）（与前提矛盾）Q P P Q A B x(x A x B)利用已知包含式并交运算证 X Y例例5 证明证明 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)(A C)(B C)(B C)A(C C)B(C C)A E B E A B由已知包含式通过运算产生新的包含式由已知包含式通过运算产生新的包含式 X Y X Z Y Z,X Z Y Z A B,C D (A C)(B D)等式替换证明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(x A x B)A B 所以，所以，A BA 从而与从而与 A B=A 矛盾矛盾.假设假设 X=Y 不成立，则存在不成立，则存在 x 使得使得 x X且且x Y，或者，或者存在存在 x 使得使得 x Y且且x X，然后推出矛，然后推出矛盾盾.A B x(x A x B)n集合的基数与有穷集合n集合集合 A 的的基数基数集合集合A中的元素数，记作中的元素数，记作 cardAn有穷集有穷集 A cardA=|A|=n，n为自然数.n集合基本运算的基数n|A B|A|+|B|n|A B|min(|A|,|B|)n|A B|A|B|n|A B|=|A|+|B|2|A B|3.3 集合中元素的计数对于任意三个集合A，B和C，有|A B C|=|A|+|B|+|C|A B|A C|B C|+|A B C|三个集合的并集的元素个数n个集合的包含排斥原理定理：设A1，A2，An为有限集合，其元素个数分别为|A1|，|A2|，|An|，则解：解：S=x|x Z,1 x 1000,如下定义如下定义 S 的的 3 个子集个子集 A,B,C：A=x|x S,5|x，B=x|x S,6|x，C=x|x S,8|x 利用下面公式求利用下面公式求|A B C|A B C|=|A|+|B|+|C|-|A B|-|A C|-|B C|+|A B C|例3.10 求1到1000之间（包含1和1000在内）既不能被 5 和6 整除，也不能被 8 整除的数有多少个？应用 对上述子集计数：对上述子集计数：|S|=1000,|A B C|=1000/120 =8,|A B|=1000/30 =33,|A C|=1000/40 =25,|B C|=1000/24 =41,|A|=1000/5 =200,|B|=1000/6=166，|C|=1000/8 =125,|A B C|=(200+166+125)(33+25+41)+8=400 N=1000|A B C|=1000-400=600例3.10 求1到1000之间（包含1和1000在内）既不能被 5 和6 整除，也不能被 8 整除的数有多少个？P68例3.15文氏图法对对24名科技人员掌握外语情况调查结果如下名科技人员掌握外语情况调查结果如下每人至少会每人至少会1门外语门外语.英语：英语：13；日语：日语：5；德语：德语：10；法语：法语：9英日：英日：2;英德：英德：4；英法：英法：4；法德：法德：4会日语的不会法语、德语会日语的不会法语、德语求：只会求：只会 1 种语言人数，会种语言人数，会 3 种语言人数种语言人数 解：解：设同时会设同时会3种语言的有种语言的有x人人 只会英、法或德语只会英、法或德语1种语言种语言 分别有分别有y1、y2、y3人人会英语的人数会英语的人数:x+2(4-x)+y1+2=13会法语的人数会法语的人数:x+2(4-x)+y2=9 会德语的人数会德语的人数:x+2(4-x)+y3=10总人数为总人数为:x+3(4-x)+y1+y2+y3+5=24xy132y2y34-x4-x4-x英语英语日语日语法语法语德语德语P68例3.15文氏图法对对24名科技人员掌握外语情况调查结果如下名科技人员掌握外语情况调查结果如下每人至少会每人至少会1门外语门外语.英语：英语：13；日语：日语：5；德语：德语：10；法语：法语：9英日：英日：2;英德：英德：4；英法：英法：4；法德：法德：4会日语的不会法语、德语会日语的不会法语、德语求：只会求：只会 1 种语言人数，会种语言人数，会 3 种语言人数种语言人数x+2(4-x)+y1+2=13x+2(4-x)+y2=9x+2(4-x)+y3=10 x+3(4-x)+y1+y2+y3+5=24x=1,y1=4,y2=2,y3=3 3x+6(4-x)+y1+y2+y3+2=32P68例3.15包含排斥原理法(1)由题意得只会日语的有：由题意得只会日语的有：5-2=3（人）（人）(2)设设A、B、C分别表示会英、法、德语的人的集合分别表示会英、法、德语的人的集合 则：则：|A B C|=24 3=21(3)因为：因为：|A|=13,|B|=9,|C|=10,|A B|=|A C|=|B C|=4 则：则：|A B C|=|A B C|-(|A|+|B|+|C|)+|A B|+|A C|+|B C|=21-(13+9+10)+4+4+4=1(4)只会英语的人只会英语的人：|A-B C|=|A|-(|A B|+|A C|)+|A B C|=13-4-4+1=6(1)这这 6人中有人中有2人还会日语，所以人还会日语，所以，只会英语的人，只会英语的人=6-2=4(2)(5)只会法语的人只会法语的人：(3)|B-A C|=|B|-(|B A|+|B C|)+|A B C|=9-4-4+1=2(4)(4)只会德语的人只会德语的人：(5)|C-A B|=|C|-(|C A|+|C B|)+|A B C|=10-4-4+1=3