第六章集合代数简PPT讲稿.ppt

《第六章集合代数简PPT讲稿.ppt》由会员分享，可在线阅读，更多相关《第六章集合代数简PPT讲稿.ppt（40页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第六章集合代数简1第1页，共40页，编辑于2022年，星期三（一）集合间的关系及其符号化（一）集合间的关系及其符号化第2页，共40页，编辑于2022年，星期三思考题思考题 采用一阶逻辑构造证明法证明如下推理：采用一阶逻辑构造证明法证明如下推理：如果如果A A B B并且并且B B C C，则，则A A C C。集合的关系及其符号化集合的关系及其符号化第3页，共40页，编辑于2022年，星期三 定定义义6.16.1（包包含含关关系系）设A，B为集合，如果B中的每个元素都是A中的元素，则称B为A的子集。这时也称B B被A A包含，或A A包含B B。记作B B A A。B B A A的符号化为：x

2、(xx(x BxBx A)A)定定义义6.26.2（相相等等关关系系）设A，B为集合，如果BA且AB，则称A A与B B相等，记作A A B B。显然A A B BA A BBBB A A AB的符号化为：x(xx(x BxBx A)A)x(xx(x AxAx B)B)第4页，共40页，编辑于2022年，星期三 定定义义6.36.3（真真包包含含关关系系）设A A，B B为集合，如果B B A A且B B A A，则称B B是A A的真子集，记作B B A A。显然B B A AB B ABAB A A B B A A的符号化为：x(xx(x BxBx A)A)(x(xx(x BxBx A)A

3、)x(xx(x AxAx B)B)第5页，共40页，编辑于2022年，星期三 定定义义6.36.3（真真包包含含关关系系）设A A，B B为集合，如果B B A A且B B A A，则称B B是A A的真子集，记作B B A A。显然B B A AB B ABAB A A B B A A的符号化为：x(xx(x BxBx A)A)x(xx(x AxAx B)B)第6页，共40页，编辑于2022年，星期三 采用一阶逻辑构造证明法证明如下推理：如果AB并且BC，则AC。证：设F(x)F(x)：x x A A，G(x)G(x)：x x B B，H(x)H(x)：x x C C 前提：x(F(x)G(

4、x)x(F(x)G(x)，x(G(x)H(x)x(G(x)H(x)结论：x(F(x)H(x)x(F(x)H(x)证明：x(F(x)G(x)x(F(x)G(x)前提引入 F(y)G(y)F(y)G(y)UI规则 x(G(x)H(x)x(G(x)H(x)前提引入 G(y)H(y)G(y)H(y)UI规则 F(y)H(y)F(y)H(y)假言推理 x(F(x)H(x)x(F(x)H(x)UG规则 第7页，共40页，编辑于2022年，星期三思考题思考题采用一阶逻辑构造证明法证明如下推理：(1)如果A=B并且B=C，则A=C (2)如果AB并且BC，则AC第8页，共40页，编辑于2022年，星期三（二）

5、三类特殊的集合（二）三类特殊的集合 第9页，共40页，编辑于2022年，星期三 定义定义6.46.4（空集）（空集）不含任何元素的集合叫做空集，记作。空集的性质：定理6.16.1 空集是一切集合的子集。推论 空集是唯一的。例：例：判断下列命题的真值。（1 1）（2 2）（3 3）（4 4）解：（1 1）（）（3 3）（）（4 4）为真，（2 2）为假 注意注意和和 的区别的区别：不含任何元素；含有唯一一个元素。第10页，共40页，编辑于2022年，星期三 定定义义6.5(6.5(幂幂集集)集合的全体子集构成的集合叫作的幂集，记作P P（A A）或2 2A A，即P P（A A）=x|x=x|x

6、 AA。含有n个元素的集合简称n元集。一个集合的含有m m个元素的子集称作它的m元子集。问题：问题：A=n，则 P(A)=?说明：说明：对于n元集A，不同的子集总数为 Cn0+Cn1+Cnn=2n 即若 A=n，则 P(A)=2n 第11页，共40页，编辑于2022年，星期三例例 A A 11，2 2，33，求A A的全部子集及P P（A A）。解：解：将A的子集从小到大分类：0元子集，即空集，只有一个：1元子集，有C C3 31 1个：11，22，33 2元子集，有C C3 32 2个：11，22，11，33，22，33 3元子集，有C C3 33 3个：11，2 2，33 P P（A A）

7、=，11，22，33，1 1，22，11，33，22，33，11，2 2，33 第12页，共40页，编辑于2022年，星期三例：已知（1）A=A=；（；（2 2）B=B=，。分别求P P（A A）和）和P P（B B）。）。解：（1）P P（A A）为2 20 0=1=1元集，P P（）=.（2）P P（B B）为2 22 2=4=4元集，P P（B B）=，第13页，共40页，编辑于2022年，星期三 定定义义6.66.6（全全集集）：在一个具体问题中，如果涉及到的集合均是某一个集合的子集，则称该集合是全全集集，记作E E。全集的概念是相对，所研究的问题不同，所取的全集也不同。第14页，共4

8、0页，编辑于2022年，星期三（三）集合的五种基本运算（三）集合的五种基本运算 第15页，共40页，编辑于2022年，星期三设集合A A，B B为集合，E为全集，则 并并：A B=x x Ax B 交交：A B=x x Ax B（绝对）补（绝对）补：A=E A=x x Ex A=x x A 相对补相对补：A B=x x A x B=AB 对称差：对称差：A B=（A B）（B A）=（A B）（A B）第16页，共40页，编辑于2022年，星期三 例：A=a，b，c，B=a，C=b，d，分别求A B、B A、A-C、C A、A C。则有 A B=b，c B A=A-C=a,c C A=d A

9、C=a，c d=a，c，d 或或A C=a，b，c，d b=a，c，d第17页，共40页，编辑于2022年，星期三集合运算性质(P101)A A B B A A，A A B B B BA A A A B B，B B A A B BA A B B A AA A B=AB=AB BA A B=BB=BA A B BA A B=AB=AA-B=A-B=A A B=BB=B A A（A A B B）C=AC=A（B B C C）A A=A=AA A A=A=A A B=AB=A C CB=CB=C第18页，共40页，编辑于2022年，星期三例例 化简下列集合表达式（A A B B C C）（A A B

10、 B）-（A A（B-CB-C）A A）解：解：因为A A B B A A B B C C，A A A A（B-CB-C）所以（A A B B C C）（A A B B）=A=A B B （A A （B-CB-C）A=AA=A 原式=（A A B B）-A-A =（A A B B）A A =（A AA A）（B BA A）=B =BA A =B-A =B-A第19页，共40页，编辑于2022年，星期三（四）集合恒等式的证明及化简（四）集合恒等式的证明及化简第20页，共40页，编辑于2022年，星期三 恒等式的证明 方法一：等值演算法 证明的基本思想：欲证P=QP=Q，即证明对任意的x,x,有x

11、 x P Px x Q Q。这一方法还可以用于集合公式包包含含关关系系的的证证明明,欲证P P Q Q，也就是要证明对任意的x x有x x P Px x Q Q成立。第21页，共40页，编辑于2022年，星期三并：x A B x Ax B交：x A B x Ax B绝对补：xA x A(x A)相对补：x A B x Ax B对称差：x A B x(A B)-(A B)或 x(A-B)(B-A)第22页，共40页，编辑于2022年，星期三例例 证明A-A-（B B C C）=（A-BA-B）（A-CA-C）证明证明 对任意的x x，x x A-A-（B B C C）x x AxAx B B C

12、 C x x A(xA(x B B C)C)x x A(xA(x BxBx C)C)x x A(xA(x BxBx C)C)x x AxAx BxBx C C （x x AxAx B B）（x x AxAx C C）x x A-BxA-Bx A-CA-C x x（A-BA-B）（A-CA-C）第23页，共40页，编辑于2022年，星期三 恒等式的证明 方法二：恒等变换 即利用已知的恒等式来证明集合恒等式。第24页，共40页，编辑于2022年，星期三 集合运算的主要恒等式（P99-100）其中的A A，B B，C C表示任意的集合，E E是全集 幂等律 A A A=A AA=A A A=AA=A

13、 结合律 （A A B B）C=AC=A（B B C C）（A A B B）C=AC=A（B B C C）交换律 A A B=BB=B A AA A B=BB=B A A 分配律 A A（B B C C）=（A A B B）（A A C C）A A （B B C C）=（A A B B）（A A C C）第25页，共40页，编辑于2022年，星期三同一律 A A=A A=A A E=AE=A零律 A A E=E AE=E A=排中律 A AA=EA=E矛盾律 A AA=A=吸收律 A A（A A B B）=A A=A A（A A B B）=A=A德摩根律 A-A-（B B C C）=（A-BA

14、-B）（A-CA-C）A-A-（B B C C）=（A-BA-B）（A-CA-C）（B B C C）=B BC C （B B C C）=B BC C =E =E E=E=双重否定律 （A A）=A=A第26页，共40页，编辑于2022年，星期三例例 证明A-A-（B B C C）=（A-BA-B）（A-CA-C）证明证明 A-A-（B B C C）=A =A （B B C C）=A =A（B B C C）=（A A B)B)(A A C C）=（A A-B)B)(A A-C C）第27页，共40页，编辑于2022年，星期三（五）集合计数（文氏图）（五）集合计数（文氏图）第28页，共40页，编辑

15、于2022年，星期三 文氏图文氏图 以图形的形式来描述集合之间的相互关系和集合之间的运算第29页，共40页，编辑于2022年，星期三下面列举一些文氏图的实例 A A B=B=A A B B A-BA-B A A B B A A B B A A B B 第30页，共40页，编辑于2022年，星期三 A A（A A B B）C C 第31页，共40页，编辑于2022年，星期三 文氏图的构造方法：1 1、首先画一个大矩形表示全集E E 2 2、其次在矩形内画一些圆（或任何其它适当的闭曲线），用圆的内部表示集合。在一般情况下，如果不作特殊说明，这些表示集合的圆应该是彼此相交的。如果两个集合是不交的，则

16、表示它们的圆彼此相离 通常在图中用画有阴影的区域表示新组成的集合 第32页，共40页，编辑于2022年，星期三 例例6.26.2 有2424人，其中会英、日、德和法语的人分别为1313，5 5，1010和9 9人，同时会英语和日语的有2 2人，会英、德和法语中任两种的都是4 4人。已知会日语的人不会法语和德语，分别求只会一种语言（英、法、德、日）的人数和会三种语言的人数。解解:令A A，B B，C C，D D分别表示会英、法、德、日语的人的集合。根据题意画出文氏图。第33页，共40页，编辑于2022年，星期三4-x4-x4-x4-x4-x4-xx xy2y2y1y12 25-25-2y3y3

17、设同时会三种语言的有x x人，只会英、法、德语一种语言的分别为y y1 1，y y2 2和y y3 3人。将x x和y y1 1，y y2 2，y y3 3填入图中相应的区域，然后依次填入其它区域的人数，根据已知条件列出方程组如下：第34页，共40页，编辑于2022年，星期三 因为会英、法、德和日语的人分别为1313，9 9，10 10，5 5人，所以可得方程组 y y1 1+2+2（4-x4-x）+x+2=13+x+2=13 y y2 2+2+2（4-x4-x）+x=9+x=9 y y3 3+2+2（4-x4-x）+x=10+x=10 y y1 1+y+y2 2+y+y3 3+3+3（4-x

18、4-x）+x=24-5+x=24-5 解得x=1x=1，y y1 1=4=4，y y2 2=2=2，y y3 3=3=3。第35页，共40页，编辑于2022年，星期三 例例6.36.3 求1到1000之间（包含1和1000在内）既不能被5和6，也不能被8整除的数有多少个？解解：设1到1000之间的整数构成全集E，而A，B，C分别代表其中可被5，6，8整除的数的集合。按题意画出文氏图第36页，共40页，编辑于2022年，星期三 说说明明：用 x x 表示小于等于x的最大整数，lcmlcm（x x1 1，x x2 2，xxn n）表示x x1 1，x x2 2，xxn n的最小公倍数。首先计算A

19、A B B C C A A B B C C=1000/lcm1000/lcm（5 5，6 6，8 8）=1000/1201000/120=8=8 将结果填入A A B B C C的区域第37页，共40页，编辑于2022年，星期三 其次A A B B、A A C C、B B C C A A B B=1000/lcm1000/lcm（5 5，6 6）=33=33 A A C C=1000/lcm1000/lcm（5 5，8 8）=25=25 B B C C=1000/lcm1000/lcm（6 6，8 8）=41=41 将结果分别填入A A B B、A A C C、B B C C的区域中去 第38页，共40页，编辑于2022年，星期三 最后计算A A、B B、C C A A=1000/51000/5=200=200 B B=1000/61000/6=166=166 C C=1000/81000/8=125=125 将这些数据依次填入文氏图15010067第39页，共40页，编辑于2022年，星期三由图可知，不能被5 5，6 6和8 8整除的数有1000-1000-（150+100+67+25+33+17+8150+100+67+25+33+17+8）=600=600个。1000第40页，共40页，编辑于2022年，星期三