最新离散数学6教学讲义ppt.ppt

《最新离散数学6教学讲义ppt.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、离散数学6第六章集合代数6.1集合的基本概念6.2集合的运算6.3有穷集合的计数6.4集合恒等式8/18/20212DiscreteMath.1.集合：将一些事物汇集到一起组成的整体，其中每个事物称为这个集合的元素。注：如果x是集合A的元素，则记为xA。集合的表示方法：列元素法和谓词表示法列元素法：列出集合的所有元素或部分元素，可用于有限集和有一定规律的无限集。如：A={a，b，…，z}Z={0，-1，1，-2，2，…}D={a，{a}，{a，b}}集合中的元素还可以是集合。谓词表示法：用谓词来描述集合中元素的性质。如：B=

2、{x

3、x∈R∧(x-1=0)}描述法={x

4、F(x)∧G(x)}谓词描述法设F(x):x∈R,G(x):x-1=0.集合的性质：（1）集合的元素是彼此不同的，相同的元素应该认为是同一个元素。（2）集合的元素是无序的。如：{1，2，3}={2，3，1}§6.1集合的基本概念8/18/20213DiscreteMath.一.集合的基本运算设A,B是集合(def6.7~~6.9)1.A与B的并：A∪B={x

5、xA∨xB}2.A与B的交：A∩B={x

6、xA∧xB}3.A与B的差(B对A的相对补)：A–B={x

7、xA∧xB}

8、4.A与B的对称差：A⊕B=(A–B)∪(B–A)=(A∪B)–(A∩B)5.A的补集(或称绝对补)：～A=E–A={x

9、xE∧xA}注:(1)“并”和“交”运算可以推广到有（无）限个集合：§6.2集合的运算8/18/20217DiscreteMath.集合运算的进一步推广定义6.10设A为集合，A的元素的元素构成的集合称为A的广义并，记为∪A。符号化∪A={x

10、z(z∈A∧x∈z)}若A={A1，A2，…，An}则∪A=A1∪A2∪…∪An。定义6.11设A为非空集合，A的所有元素的公共元素构成的集合称为A的广义交，记

11、为∩A。符号化∩A={x

12、z（z∈A→x∈z）}若A={A1，A2，…，An}则∩A=A1∩A2∩…∩An。例6.2设A={{a,b,c},{a,c,d},{a,e,f}},B={{a}},C={a,{c,d}}.∩C=解：∪A={a,b,c,d,e,f}∪B={a}∪C=a∪{c,d}∪Ø=Ø∩A=∩B=∩Ø不是集合a∩{c,d}{a}{a}8/18/20218DiscreteMath.例6.3设A={{a},{a,b}},计算:∪∪A,∩∩A,∩∪A∪(∪∪A-∪∩A).解：∪A={a,b}∩A={a}∪∪A=a∪b∩∩A

13、=a∩∪A=a∩b∪∩A=a∩∪A∪(∪∪A-∪∩A)=(a∩b)∪((a∪b)-a)=(a∩b)∪(b-a)=b集合运算的进一步推广一类运算：广义并，广义交，幂集，绝对补二类运算：并，交，相对补，对称差集合运算的优先顺序:一类运算优于二类运算;一类运算由右向左顺序进行;二类运算由括号决定先后顺序。8/18/20219DiscreteMath.EEBEBEABA∩B=AA∩B=AEABA-BEABA∪BEABA∩BEA~AAABB(A∩B)-CAC§6.3有穷集的计数集合间的关系与运算的表示：文氏图(VennDiagram

14、s)8/18/202110DiscreteMath.例6.4对24名会外国语的科技人员进行掌握外语情况的调查，起统计结果如下：会英、日、德和法语的人分别为13，5，10和9人。其中同时会英语和日语的有2人，会英、德和法语中任两种语言的都是4人。已知会日语的人既不会法语也不会德语，分别求只会一种语言的人数和会三种语言的人数。解令A,B,C,D分别表示会英、法、德、日语的人的集合，根据题意得文氏图.ADBCy15-22y3x4-xy24-x4-x设同时会三种语言有x人，只会英、法或德语一种语言的分别是y1,y2,y3人。则有y1+

15、2(4-x)+x+2=13y2+2(4-x)+x=9y3+2(4-x)+x=10y1+y2+y2+3(4-x)+x=19解方程组得x=1,y1=4,y2=2,y3=3.§6.3有穷集的计数8/18/202111DiscreteMath.例6.5求1到1000之间(包含1和1000在内),既不能被5和6,也不能被8整除的数有多少个.解设S={x

16、xZ∧1x1000}A={x

17、xS∧x可被5整除}B={x

18、xS∧x可被6整除}C={x

19、xS∧x可被8整除}

20、A

21、=int(1000/5)=200

22、B

23、=int(1000/

24、6)=166

25、C

26、=int(1000/8)=125

27、A∩B

28、=int(1000/lcm(5,6))=33

29、A∩C

30、=int(1000/lcm(5,8))=25

31、B∩C

32、=int(1000/lcm(6,8))=41

33、A∩B∩C

34、=int(1000/lcm(5,6,8))=810