《离散数学]》PPT课件.ppt
《《离散数学]》PPT课件.ppt》由会员分享,可在线阅读,更多相关《《离散数学]》PPT课件.ppt(133页珍藏版)》请在三一办公上搜索。
1、集 合 论,由于集合论的语言适合于描述和研究离散对象及其关系,所以也是计算机科学与工程的理论基础,在程序设计、关系数据库、排队论、开关理论,形式语言和自动机理论等学科领域中都有重要的应用。本篇主要介绍:集合、二元关系和函数,以及集合的基数问题。,集 合 论,第三章集合与关系,1集合的概念和表示法2集合的运算4序偶与笛卡尔积5关系及其表示6关系的性质7复合关系和逆关系8关系的闭包运算,9集合的划分和覆盖10等价关系与等价类11相容关系12序关系,1集合的概念和表示法,1、集合与元素(1)集合:就是把人们直观的或想象中的某些确定的能够区分的对象汇合在一起组成的一个整体。讨论:一些不同的确定的对象之
2、全体。例:1000以内的素数的集合;这个班里高个子学生的集合;(不是集合)元素(成员):组成集合的各个对象。符号:用大写英文字母表示集合,用小写英文字母或其它符号表示元素。集合:A,B.元素:a,b.,1集合的概念和表示法,元素与集合间的关系:若a是集合S中的元素,则可写成a S;若b不是集S合中的元素,则可写成b S。集合S的基数(势):S中的元素个数。用|S|表示。有限集合:集合的基数(元素)是有限的。无限集合:集合的基数(元素)是无限的。,1集合的概念和表示法,本书中常用集合符:Im(m1)有限个正整数的集合1,2,3m Nm(m0)有限个自然数的集合0,1,2m 以上是有限集合,下面是
3、无限集合:N 自然数集合 0,1,2 I+正整数集合 1,2,3 I 整数集合-1,0,1,2 P 素数集合 大于1的正整数,只能被1和自己整除 Q 有理数集合 i/j.i、j均为整数且j0 R 实数集合 有理数、无理数 C 复数集合 a+bi,a、b可为实数,1集合的概念和表示法,(2)集合的表示方法:(a)枚举法(列举法)把集合的元素列于花括号内。例:命题的真假值组成的集合:S=T,F自然数0,1,2,3,4五个元素的集合:P=0,1,2,3,4(b)谓词公式描述法所有集合均可用谓词公式来表示:S=x|p(x),1集合的概念和表示法,例:大于10的整数的集合:S1=x|x I x10 偶整
4、数集合:S2=x|y(y I x=2y)有限个元素集合:S3=1,2,3,4,5=x|x I(1 x 5)S4=F,T=x|x=T x=F S5=1,4=x|(x-5x+4=0)(c)同一集合可以用多种不同的形式表示。(d)集合也可作为某一集合的元素。例:S=a,1,2,p,q,1集合的概念和表示法,(3)三个特殊集合:空集、全集合、集合族定义如果一个集合包含了所要讨论的每一个集合,则称该集合为全集合,简称全集,用E表示。E=x|p(x)p(x)p(x)为任何谓词公式定义不拥有任何元素的集合称为空集(或称零集),用表示=x|p(x)p(x)=注意:前者是空集,是没有元素的集合;后者是以作为元素
5、的集合。,1集合的概念和表示法,定义集合中的元素均为集合,称这样的集合为集合族。例A=a,b,c、d2、集合之间的关系公理给定二个集合A和B,当且仅当A和B具有同样的元素(成员),则A和B才是相等的,记作A=B并规定:(A=B)x(x A x B)例:a,b,c=b,a,a,c,c,1集合的概念和表示法,例:a,b,c=b,c,a例:设P=1,2,4,Q=1,2,4,则PQ定义设A、B是任意二个集合,如果集合A的每一个元素都是B的一个元素,则称A 是B的子集,或者说A包含于B,或者说B包含A,记作AB,或者BA。并规定:ABBAx(x A x B),1集合的概念和表示法,例:A1=1,2,3
6、A2=0 A3=1,2,3,0 B=1,2,3,0 则A1、A2、A3均为B的子集合,并记为 A1B,A2B,A3B定义设A、B是任意二个集合,若AB且AB,则称A是B的真子集,记作AB(A真包含于B)并规定:AB(AB AB),1集合的概念和表示法,注意:区分“”和“”的关系:“”关系是指集合和该集合中元素之间的关系。例:S=a,b,c 则a S,bS,c S而“”关系是指二个集合之间的关系。例:S1=a,b S2=a,b,1,2 则S1 S2若A不包含于B,则也可表示成AB定理设E是全集,A是一个集合,则一定有AE。,1集合的概念和表示法,定理设A、B是任意二个集合,当且仅当A B和B A
7、才有A=B。证明:()充分性:(A=B)(A B B A)(A=B)x(x A xBxB xA)x(xA xB)x(xB xA)(AB)(BA)()必要性:ABBAA=B(AB)(BA)x(xA xB)x(xB xA)(A=B),1集合的概念和表示法,推论对于任一集合A,则有A A。定理设A、B、C是任意集合,如果AB和BC,则AC。推论若AB和BC,则AC。定理设有空集和任一集合A,则A证明:设xA,要证明A,只要证:x(x xA)为“T”中没有元素,x为假,x(x xA)为“T”定理 是唯一的。,1集合的概念和表示法,证明:设有二个空集合1和2 是任何集合的子集(1 22 1)(1=2)3
8、、幂集和索引集合(1)幂集:例:给定S1=a 则子集为,a S2=1,2 则子集为,1,2,1,2 S3=则子集有(而不是),1集合的概念和表示法,定义 设A是集合,A的所有子集(作为元素)的集合称为A的幂集。记作(A)或2A 且有:(A)(=2A)=x|x A例:若A1=,则(A1)=若A2=a,则(A2)=,a 若A3=1,2,则(A3)=,1,2,1,2注:|(S)|=2|s|为幂集(S)的基数,1集合的概念和表示法,(2)索引集合 为了在计算机上表示集合,必须给每一个集合的元素加上标记,以用来表示元素在集合中的位置。例:S1=a,b 假设集合S1中,a,b的位置已经固定。则用二进制下标
9、法来表示S的所有子集:=B00,a=B10,b=B01,a,b=B11这样(S1)=B00,B01,B10,B11=Bi|iJ 而其中J=00,01,10,11(索引集合或指标集合),1集合的概念和表示法,例:已知集合S=a1,a2,a3,a4,S的子集有24 个 可以分别表示成B0,B1B(24-1)则B7=B0111=a2,a3,a4 B15=B1111=a1,a2,a3,a4,2 集合的运算,1.交集(交运算)定义任何二个集合A和B的交集AB是由A和B所共有的全部元素构成的集合,即:AB=x|x A x B例:A=a,b B=a,c AB=a定理 集合的相交运算是可交换的和可结合的,即对
10、于任何集合A,B,C有 AB=BA,(AB)C=A(BC)证明:设x是AB中任一元素 则x ABx x|x A x B x x|x B x Ax BA AB=BA,2 集合的运算,定理设A是E的任一子集,则有(1)AA=A(2)A=(3)AE=A定义 A、B是二个集合,若AB=,则称A和B是不相交的,或者说A和B没有相同的元素。若C是一个集合族(集合族:元素均为集合的集合)且C的任何二个元素都不相交,则称C为不相交的集合族。例:A=a,b,c A为不相交的集合族,2 集合的运算,2.并集(并运算)定义 A、B是任意二个集合,A和B的并集AB是由A和B的所有元素构成的集合。即:AB=x xAxB
11、。例:A=a,b,c B=1,2,3 则AB=a,b,c,1,2,3 定理集合的并运算是可交换的和可结合的,即对任何A,B,C有 AB=BA和(AB)C=A(BC),2 集合的运算,定理集合的并和交运算,每一个对另一个都是可分配的。即:(1)A(BC)=(AB)(AC)(2)A(BC)=(AB)(AC)定理设A、B、C是全集E的任意子集,则有:(1)AA=A(2)A=A(3)AE=E,2 集合的运算,3.相对补集:定义设A和B是二个任意集合,B对A的相对补集(A-B)是由属于A且不属于B的所有元素组成的集合。即:A-B=xxAxB=xxAxB。例:设A=0,1,2 B=2,3,4 则A-B=0
12、,1 B-A=3,4A-BB-A相对补集不满足交换律。,2 集合的运算,定理设A,B,C,D是E的子集,则有:(1)A-BA,(2)若AB和CD,则ACBD,(3)若AB和CD,则AC BD,(4)若AAB,则 BAB(5)若ABA,则ABB(6)若AB,则AB=B(7)若AB,则AB=A(8)A-=A(9)A(B-A)=(10)A(B-A)=AB,2 集合的运算,4、绝对补集(补运算)定义设E是全集,任一集合A对E的相对补集称为A的绝对补集(或称补集)记作A(或A)。即:A=E-A=x|xExA=x|xA例:设E=a,b,c,d A=a,b 则A=c,d 定理)A是E的任一子集,则有(1)A
13、A=E(2)AA=,2 集合的运算,补集的性质:(1)(A)=A(2)(AB)=AB(3)(AB)=AB(4)=E(5)A-B=AB 例:设A=2,5,6,B=2,3,4,C=1,3,4,E=1,2,3,4,5,6 则A-B=5,6=AB=2,5,61,5,6=5,6,2 集合的运算,5、环和(对称差)定义设A、B是任意二集合,A和B的环和记作AB。即:AB=(A-B)(B-A)=(AB)(BA)或者x(AB)xx|xAxB 例:设A=2,5,6,B=2,3,4 则AB=3,4,5,6,2 集合的运算,对称差的性质:(1)AB=BA 可交换的(2)(AB)C=A(BC)可结合的(3)AA=(4
14、)A=A(5)A(BC)=(AB)(AC)(对是可以分配的),2 集合的运算,6、文氏图(1)文氏图的画法规则:规定矩形表示E。子集用圆画在E中。(2)文氏图应用:(a)表示集合和运算的关系 可用文氏图画出各种运算:(b)证明集合恒等式例:A(BC)=(AB)(AC),下图中的阴影部分表示了每个图下边所指出的集合。,AB,AB,A-B,AB,A,A,A,A,A,A,A,B,B,B,B,B,AB=,2 集合的运算,3 序偶与笛卡尔乘积,1.序偶:定义由二个具有给定次序的客体所组成的序列称为序偶。记作x,y 例:XY二维平面上的一个点的坐标x,y就是一个序偶。说明:在序偶中二个元素要有确定的排列次
15、序。即:若ab时,则a,bb,a 若x,y=a,b(x=ay=b)下面定义多重序元:三元组:x,y,z=x,y,zn元组:x1,x2,x3,xn=x1,xn,3 序偶与笛卡尔乘积,2.笛卡尔乘积定义设A,B为二个任意集合,若序偶的第一个成员(左元素)是A的一个元素,序偶的第二个成员(右元素)是B的一个元素,则所有这样的序偶的集合称为A和B的笛卡尔乘积。记作:AB=x,y|(xA)(yB)例:设A=1,2 B=a,b则AB=1,a,1,b,2,a,2,b BA=a,1,a,2,b,1,b,2ABBA 即“”是不满足交换律。,3 序偶与笛卡尔乘积,例:设A=a,b,B=1,2,C=z 则(AB)C
16、=a,1,a,2,b,1,b,2z=a,1,z,a,2,z,b,1,z,b,2,z A(BC)=a,b1,z,2,z=a,1,z,a,2,z,b,1,z,b,2,z(AB)CA(BC)“”不满足结合律。定理若A,B,C是三个集合,则有:A(BC)=(AB)(AC)A(BC)=(AB)(AC)(AB)C=(AC)(BC)(AB)C=(AC)(BC),3 序偶与笛卡尔乘积,证明:(2)设x,y是A(BC)中的任一元素,则:x,yA(BC)x,y x,y|xAyBC|xAyByC|(xAyB)(xAyC)(AB)(AC)即 A(BC)=(AB)(AC)例:设A=1,B=1,2,C=2,3 则A(BC
17、)=11,2,3=1,1,1,2,1,3,3 序偶与笛卡尔乘积,(AB)(AC)=11,212,3=1,1,1,2,1,3 A(BC)=12=1,2(AB)(AC)=1,1,1,21,2,1,3=1,2 n个集合的笛卡儿乘积的定义:A2=AAA3=AAAAn=AAA,N个A,4关系及其表示,序偶a,b实际上反映了二个元素之间的关系。1.关系:指事物之间(客体之间)的相互联系。在数学上关系可表达集合中元素间的联系。日常生活中:父子关系,母子关系,兄弟关系等均为二个客体之间的关系。n元笛卡尔积A1A2An是n元关系。,4关系及其表示,定义若则是一个二元关系。即:以序偶作为元素的任何集合是一个二元关
18、系。关系表示方法(1)枚举法(直观法、列举法)设R表示二元关系,若 用 表示,若,则也可写成:x R y。,4关系及其表示,例:二元关系定义如图:可写成:由定义可见:关系是一个集合,定义集合的方法都可以来定义关系。(2)谓词公式表示法 前面讲述,一个集合可用谓词公式来表达,所以关系也可用谓词公式来表达。,4关系及其表示,例:实数集合R上的“”关系可表达为:大于关系:“”=父子关系:“F”=(3)关系矩阵表示法 规定:(a)二元关系中的左元素表示行,右元素表示列;(b)若,则在对应位置记上“1”,否则为“0”。,4关系及其表示,例1:设并定义为列出关系矩阵:,4关系及其表示例2:设X=a,b,c
19、,Y=1,2,R2是的关系,,是的全域关系,,4关系及其表示,(4)关系图表示法规定:(a)把、集合中的元素以点的形式全部画在平面上;(b)若,则xi和yi之间画一箭头弧线,其箭头指向yi。反之不画任何联线。,4关系及其表示,用关系图表示:,例:,是X中的二元关系,,4关系及其表示,关系的前域和值域:定义:设R是一个二元关系,由 的所有x组成的集合dom R称R的前域,即,R的前域和值域一起称做R的域,记做FLD R,即FLD R=dom R ran R,设R是一个二元关系,由 的所有y组成的集合ran R称R的值域,即,4关系及其表示,4关系及其表示,均为二元关系。,4关系及其表示,三个特殊
20、关系:空白关系,全域关系,恒等关系,定义:集合X2定义了X集合中的一种关系,通称为X中的全域关系,用Ex表示:,4关系及其表示,5关系的性质,自反性:,例:设,是自反的关系。,R的关系矩阵,5关系的性质,定义:设R是X中的二元关系,对于每一个,有x x,则称R是反自反的关系,表示成:R是X中的反自反的关系 x x。,例:设X=1,2,3,5关系的性质,S4既不是自反的,又不是反自反的,5关系的性质,例:设X=1,2,3,R=则R是对称的关系,5关系的性质,即当且仅当,X中的R才是反对称的。,5关系的性质,反对称的另一定义如下:,下面举例说明:,定义:设R是X集合中的二元关系,对于每一个,来讲,
21、如果xy且xRy,则yRx,称R是反对称的关系。,5关系的性质,例:设X=a,b,c,均是反对称的,5关系的性质,例:X=a,b,c,下列关系不是对称的,也不是反对称的,5关系的性质,5关系的性质,X上的全域关系:,是自反的,对称的,X上的空关系是反自反、对称、反对称的。,5关系的性质,传递性:,5关系的性质,例:设X=a,b,c,则下列关系均是可传递的,5关系的性质,下列关系是不可传递的:,5关系的性质,确定二元关系性质举例,(1)设X=1,2,3,,反自反,反对称,可传递的;,反对称的;,5关系的性质,自反,对称,反对称,可传递的;,自反,对称,可传递的;,反自反的,对称的,反对称的,可传
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 离散数学 PPT 课件
![提示](https://www.31ppt.com/images/bang_tan.gif)
链接地址:https://www.31ppt.com/p-5563726.html