集合和二元关系复习.ppt_三一办公31ppt.com

资源描述

《集合和二元关系复习.ppt》由会员分享，可在线阅读，更多相关《集合和二元关系复习.ppt（67页珍藏版）》请在三一办公上搜索。

1、温故而知新!,67-1,温故而知新!,2023/9/29,温故而知新!,67-2,集合的表示法,集合是由它包含的元素完全确定的，为了表示一个集合，通常有：列举法、隐式法（描述法）、归纳法、文氏图等表示方法。,温故而知新!,67-3,2.2集合的运算,定义设A、B是两个集合，则ABx|xAxB仍是一个集合，称为集合A与B的并集，称“”为并运算（Union Operation）。用文氏图表示如下：,温故而知新!,67-4,交集,定义设A，B是两个集合，则ABx|xAxB仍是一个集合，称为集合A与B的交集，称“”为交运算（Intersection Operatio

2、n）。用文氏图可表示如下：,温故而知新!,67-5,差集,定义设A，B是两个集合，则A-Bx|xAxB仍是一个集合，称为集合A与B的差集，称“-”为差运算（Subtraction Operation)，-又叫相对补集。用文氏图可表示如下：,温故而知新!,67-6,定义设U是全集，A是U的子集，则 U-Ax|xU并且xA仍是一个集合，称它为集合A的补集(也可记为，AC等），“”称为补运算（Complement Operation）。用文氏图可表示如下：,补集,温故而知新!,67-7,关于运算“差”和“补”的几个性质,1.；2.（）；3.（）（）；4（）；5。,温故

3、而知新!,67-8,对称差(环和),定义：设A，B是两个集合，则AB=x|(xA)(xB)(xB)(xA)=(A-B)(B-A)仍是一个集合，称它为与的对称差集，称“”为对称差运算。用文氏图可表示如下：,A,B,U,图中的阴影部分为AB。,温故而知新!,67-9,1.等幂律：；2交换律：；3结合律：（）（）；（）（）；4恒等律：；5零律：；6分配律：（）（）（）；（）（）（）。7吸收律：A（AB）A；A（AB）=A；8否定律：,9DeMorgan律：,10矛盾律：A=；,11排中律：A=U；,温故而知新!,67-10,幂集,定义由集合A的所有子集组成的集合称为A的幂集，记

4、为(A)或2A。(A)x|一切xA,这种以集合为元素构成的集合，常称为集合的集合或集族（Family of Set）。对集族的研究在数学方面、知识库和表处理语言以及人工智能等方面都有十分重要的意义。,结论:显然，若集合有个元素，则集合共有2n个子集，即：|(A)|2n。,温故而知新!,67-11,容斥原理,定义所谓容斥，是指我们计算某类物的数目时，要排斥那些不应包含在这个计数中的数目，但同时要包容那些被错误地排斥了的数目，以此补偿，这种原理称为容斥原理，又称为包含排斥原理。,定理设A和B是任意有限集合，有|AB|A|B|AB|。,例某软件公司的程序员都熟悉C+或VB，其中熟悉C+的共

5、47人，熟悉VB的共35人，C+和VB都熟悉的共23人，问该公司共有多少程序员？,温故而知新!,67-12,推论设U为全集，A和B是任意有限集合，则|U|(|A|B|)|AB|证明：=|U-(AB)|U|AB|U|(|A|B|)|AB|。,设A1,A2,An是任意有限集合，有:,温故而知新!,67-13,2.5 序偶与笛卡尔乘积,定义由两个元素x,y按照一定的次序组成的二元组称为有序偶对，简称序偶,记作,其中，称x为的第一元素，y为的第二元素。,例1平面上点的坐标，x,yR；中国地处亚洲，,等都是序偶。这条单地址指令也是序偶。,性质（1）（当xy时)（2）当且仅当xu,yv。,

6、温故而知新!,67-14,n重有序组,定义由n个元素a1,a2,a3,an按照一定的次序组成的n元组称为n重有序组，记作即：,an。,例2a年b月c日d时e分f秒可用下述六重有序组来描述：。,性质当且仅当aibi（i1,2,3,n）。,温故而知新!,67-15,定义设A,B是两个集合，称集合AB|(xA)(yB)为集合A与B的笛卡儿积。特别，记AA为A2。,笛卡儿积,AB|(xA)(yB),CD|(xC)(yD),温故而知新!,67-16,定义设A1,A2,An为n个非空集合，称,关系的定义,A1A2An的任意子集R为以A1A2An为基的n元关系。,特别：当R时，则称R

8、关系R”。如R，则记为xRy，读作“x对y没有关系R”。,温故而知新!,67-18,关系的表示法,1.集合表示法,由于关系也是一种特殊的集合，所以集合的几种基本的表示法也可以用到关系的表示中。可用枚举法和叙述法来表示关系。,例设A2,B3,关系R如定义集合N上的“小于等于”关系：R|(x,yN)(xy)。,温故而知新!,67-19,2.关系图法,设a1,a2,a3,.,an和b1,b2,b3,.,bm分别为图中的节点，用“。”表示；如R,则从ai到bj可用一有向边aibj相连。为对应图中的有向边。,设Aa1,a2,a3,.,an,Bb1,b2,b3,.,bm，R是从A到B的一个

9、二元关系，则对应于关系R之关系图有如下规定：,如R,则从ai到ai用一带箭头的小圆环表示ai,温故而知新!,67-20,设Aa1,a2,a3,.,an，Bb1,b2,b3,.,bm，R是从A到B的一个二元关系，称矩阵MR(rij)nm为关系R的关系矩阵或邻接矩阵，其中：,3.关系矩阵,显然，关系矩阵是布尔矩阵。注意在写关系矩阵时，首先应对集合A和B中的元素进行排序，不同的排序会得到不同的关系矩阵。当集合以枚举法表示时，如果没有对集合的元素排序，则默认枚举的次序为元素的排序。,温故而知新!,67-21,3.1.4 关系的性质（91-93）,自反性与反自反性,定义设R是集合A上的

10、二元关系，对任意的xA,都满足R，则称R是自反的，或称R具有自反性，即R在A上是自反的(x)(xA)(R)=1,2)对任意的xA,都满足R，则称R是反自反的，或称R具有反自反性，即R在A上是反自反的(x)(xA)(R)=1,温故而知新!,67-22,设A=a,b,c,d，,例,R=,。,因为A中每个元素x，都有R，所以R是自反的。,R的关系图,R的关系矩阵,温故而知新!,67-23,S=,。,例(续1),S的关系图,S的关系矩阵,因为A中每个元素x，都有 S，所以S是反自反的。,温故而知新!,67-24,T=,。,例(续2),因为A中有元素b，使 T，所以T不是自反的；

11、因为A中有元素a，使T，所以T不是反自反的。,T的关系图,T的关系矩阵,温故而知新!,67-25,任何不是自反的关系未必一定是反自反的关系，反之亦然。即存在既不是自反的也不是反自反的关系。表现在关系图上：关系R是自反的，当且仅当其关系图中每个结点都有环；关系R是反自反的，当且仅当其关系图中每个结点都无环。表现在关系矩阵上：关系R是自反的，当且仅当其关系矩阵的主对角线上全为1；关系R是反自反的当且仅当其关系矩阵的主对角线上全为0。,结论,温故而知新!,67-26,对称性与反对称性,设R是集合A上的二元关系，对任意的x,yA，如果R，那么R，则称关系R是对称的，或称R具有对称性，即

12、R在A上是对称的(x)(y)(xA)(yA)(R)(R)=1,2)对任意的x,yA，如果R且R，那么x=y，则称关系R是反对称的，或称R具有反对称性，即R在A上是反对称的(x)(y)(xA)(yA)(R)(R)(x=y)=1,温故而知新!,67-27,设A=a,b,c,d，,例,R1=,R2=,R1的关系图,R1的关系矩阵,是对称的,是反对称的,R2的关系图,R2的关系矩阵,温故而知新!,67-28,R3=,例(续1),R4=,既不是对称的，也不是反对称的,R3的关系图,R3的关系矩阵,既是对称的，也是反对称的,R3的关系图,R3的关系矩阵,温故而知新!,67-29,任

13、何不是对称的关系未必一定是反对称的关系，反之亦然。即存在既不是对称的也不是反对称的关系，也存在既是对称的也是反对称的关系。表现在关系图上：关系R是对称的当且仅当其关系图中，任何一对结点之间，要么有方向相反的两条边，要么无任何边；关系R是反对称的当且仅当其关系图中，任何一对结点之间，至多有一条边。表现在关系矩阵上：关系R是对称的当且仅当其关系矩阵为对称矩阵，即rij=rji，i,j=1,2,n；关系R是反对称的当且仅当其关系矩阵为反对称矩阵，即rijrji=0，i,j=1,2,n，ij。,结论,温故而知新!,67-30,传递性,定义设R是集合A上的二元关系，对任意的x,y,zA，如果R

14、且R，那么R，则称关系R是传递的，或称R具有传递性，即,R在A上是传递的(x)(y)(z)(xA)(yA)(zA)(R)(R)(R)=1,温故而知新!,67-31,设A=a,b,c,d，,例,R1=,R2=,是传递的,R1的关系图,R1的关系矩阵,是传递的,R2的关系图,R2的关系矩阵,温故而知新!,67-32,R3=,例(续1),R4=,不是传递的,R3的关系图,R3的关系矩阵,不是传递的,R3的关系图,R3的关系矩阵,温故而知新!,67-33,表现在关系图上：关系R是传递的当且仅当其关系图中，任何三个结点x,y,z（可以相同）之间，若从x到y有一条边存在，从y到z有

15、一条边存在，则从x到z一定有一条边存在。表现在关系矩阵上：关系R是传递的当且仅当其关系矩阵中，对任意i,j,k1,2,3,n，若rij=1且rjk=1，必有rik=1。,结论,温故而知新!,67-34,设A是任意的集合，A上的全关系AA是自反的、对称的、传递的关系；A上的空关系是反自反的、反对称的、对称的、传递的关系；A上的恒等关系IA是自反的、对称的、反对称的、传递的关系。,例,例朋友关系是自反的、对称的、而非传递的关系；父子关系是反自反的、反对称的、而非传递的关系.,温故而知新!,67-35,在整数集I上定义的“小于等于”关系是自反的、反对称的、传递的关系；“小于”关系是反

16、自反的、反对称的、传递的关系；“等于”关系是自反的、反对称的、对称的、传递的关系。,例,例8.21设A1,2,3,4，R,，是A上的关系。,幂集上的“包含”关系是自反的、反对称的、传递的关系；“真包含”关系是反自反的、反对称的、传递的关系；“相等”关系是自反的、反对称的、对称的、传递的关系。,则R既不是自反的，又非反自反的；即不是对称的，也非反对称的；也不是传递的。即不具备关系的任何性质。,温故而知新!,67-36,关系性质的逻辑表示,设R是集合A上的二元关系，R是自反的,是永真的,R不是自反的,是永真的,R是反自反的,是永真的,R不是反自反的,是永真的,R是对称的,是永真的,R不是对

17、称的,是永真的,温故而知新!,67-37,关系性质的逻辑表示(续),R是反对称的,R是传递的,是永真的,R不是传递的,是永真的,是永真的,R不是反对称的,是永真的,温故而知新!,67-38,设R，S都是集合A到B的两个关系，则：RS|(xRy)(xSy)RS|(xRy)(xSy)R-S|(xRy)(xSy)|(xy),3.2关系的运算,关系的交、并、补、差运算（补充）,根据定义，由于AB是相对于R的全集，所以AB-R,且RAB,R。,温故而知新!,67-39,定义设R是一个从集合A到集合B的二元关系，则从B到A的关系R-1|R称为R的逆关系,运算“-1”称为逆运算。,关

18、系的逆运算 P101,注意：关系是一种集合，逆关系也是一种集合，因此，如果R是一个关系，则R-1和都是关系，但R-1和是完全不同的两种关系，千万不要混淆。,温故而知新!,67-40,关系的合成运算 P96,设R是一个从集合A到集合B的二元关系，S是从集合B到集合C的二元关系(也可简单地描述为R：AB，S：BC)，则R与S的合成关系（合成关系）RS是从A到C的关系，并且：RS|(xA)(zC)(y)(yB)(xRy)(ySz)运算“”称为合成运算。,注意，在合成关系中，R的后域B一定是S的前域B，否则R和S是不可合成的。合成的结果RS的前域就是R的前域A，后域就是S的后域C。如果对任意的

19、xA和zC，不存在yB，使得xRy和ySz同时成立，则RS为空，否则为非空。并且，R=R=。,温故而知新!,67-41,RSR。SABCAC1。1。11。12。2。22。23。3。33。34。4。44。4,2).用关系图求RS。,例 R,，S,，,3).用关系矩阵求RS。P99,MRS MR.MS,温故而知新!,67-42,设I是整数集合，R，S是I到I的两个关系：R|xI；S|xI。则：RSSRRRSS(RR)R(RS)R,例,|xI|xI|xI|xI|xI|xI,温故而知新!,67-43,设R是从集合A到集合B的关系，S1,S2是从集合B到集合C的关系，T是从集合C

20、到集合D的关系，则：R(S1S2)(RS1)(RS2)R(S1S2)(RS1)(RS2)(S1S2)T(S1T)(S2T)(S1S2)T(S1T)(S2T),定理3.2.1 P97,证明4)对任意(S1S2)T，则由合成运算知，,至少存在cC,使得：(S1S2)，T。即：S1,且S2。因此，由S1,且T，则有：(S1T),由S2,且T，则有：(S2T)。所以，(S1T)(S2T)。即，(S1S2)T(S1T)(S2T)。,温故而知新!,67-44,设R,S,T分别是从集合A到集合B，集合B到集合C，集合C到集合D的二元关系，则1)(RS)TR(ST)2)(RS)-1S-1R-1(补充)

21、,定理,证明1)设(RS)T，,cC,使得：RS，T。,则由合成运算知,至少存在,R(ST),又对于RS，则至少存一个bB，使得R，S。因此,由S,T,有ST，又由R和ST，知：所以(RS)TR(ST)。同理可证：R(ST)(RS)T。由集合性质知：(RS)TR(ST)。,温故而知新!,67-45,2).任取(RS)-1，则RS由“”的定义知：则至少存一个bB,使得：R，S，即：R-1,S-1。由S-1和R-1,有：S-1R-1，所以，(RS)-1S-1R-1。反之，任取S-1R-1，由“”的定义知：则至少存一个bB,使得：S-1和R-1，所以：R，S。由“”知：RS。即有：(RS)-

22、1。所以，S-1R-1(RS)-1。由集合的定义知：(RS)-1S-1R-1。,定理(续)2)(RS)-1S-1R-1,温故而知新!,67-46,定义设R是集合A上的二元关系，则可定义R的n次幂Rn,该Rn也是A上的二元关系，定义如下：1.R0IA|aA；2.R1；3.Rn+1RnRRRn。,关系的幂 P98,显然，RmRnRm+n,(Rm)nRmn。,温故而知新!,67-47,定义设R是定义在A上的二元关系，若存在R的一个扩充ExtR满足：ExtR是自反的(或对称的、或传递的)。对任何的扩充Ext*R，若Ext*R是自反的(对称的、或传递的)，则：ExtRExt*R。此时称E

23、xtR为R的自反闭包关系(或对称闭包关系、或传递闭包关系)，分别记为r(R)(s(R)或t(R)。,关系的闭包,温故而知新!,67-48,求一个关系的自反闭包，即将图中的所有无环的节点加上环；关系矩阵中对角线上的值rij全变为“1”。求一个关系的对称闭包，则在图中，任何一对节点之间，若仅存在一条边，则加一条方向相反的另一条边；关系矩阵中则为：若有rij1(ij)，则令rji1(若rji1),即Ms(R)MRMR-1。求一个关系的传递闭包，则在图中，对任意节点a,b,c,若a到b有一条边，同时b到c也有一条边，则从a到c必增加一条边(当a到c无边时)；在关系矩阵中，若rij1，rjk1,

24、则令rik1(若rik1)。,利用关系图和关系矩阵求闭包,温故而知新!,67-49,设R是集合A上的二元关系，则：r(R)RIA。s(R)RR-1。t(R)，若|A|n，则t(R)。,定理,温故而知新!,67-50,设PP1,P2,P3,P4是四个程序，R,S是定义在P上的调用关系如下：R,S,求r(R),s(R),t(R)，r(S),s(S),t(S)。,例,解：r(R)RIA,。,。,温故而知新!,67-51,例(续1),s(R)RR-1,。t(R)RR2R3R4,。r(S)SIA,。,温故而知新!,67-52,s(S)SS-1,例(续2),t(S)SS2S

25、3S4,),。,温故而知新!,67-53,定义1）集合A上的关系的自反对称闭包定义为rs(R)r(s(R)2）集合A上的关系的自反传递闭包定义为rt(R)r(t(R)3）集合A上的关系的对称传递闭包定义为st(R)s(t(R)同上，我们还可定义sr(R),tr(R),ts(R),多重闭包,定理设R是集合A上的关系，则：1)rs(R)sr(R)2)rt(R)tr(R)3)st(R)ts(R),温故而知新!,67-54,设A1,2,R,则：,例,传递闭包和自反传递闭包，常用于形式语言与程序设计中，在计算机文献中，常把关系R的传递闭包t(R)记作R+，而自反传递闭包rt(R)记作R*

26、。显然有(R+)+=R+。,st(R)s(t(R)s(),ts(R)t(s(R)t(,),即：st(R)ts(R),温故而知新!,67-55,3.4次序关系,次序关系的定义定义设R是集合A上的自反的、反对称的、传递的关系，则称R是A上的偏序关系(记为“”)。序偶称为偏序集。,设R是集合A上的反自反的、反对称的、传递的关系，则称R是A上的拟序关系(记为“”)。序偶称为拟序集。,为使叙述简洁，我们常将ab并且ab记为ab。容易证明：偏序的逆关系-1也是一个偏序，我们用“”表示，读作“大于等于”；拟序的逆关系-1也是一个拟序，我们用“”表示，读作“大于”。,温故而知新!,67-56

27、,集合A的幂集(A)上定义的“”和“”分别是偏序关系和拟序关系。是偏序集，是拟序集。,例,实数集合R上定义的“”和“”分别是偏序关系和拟序关系。是偏序集，是拟序集。大于零的自然数集合N上定义的“整除”关系“”也是一个偏序关系,是偏序集。ALGOL或PL/I等都是块结构语言，设：Bb1,b2,b3,bn是这种语言的一个程序中的块的集合。对所有i和j，定义关系“”如下：bibj当且仅当bi被bj所包含。则“”也是一个偏序关系,是偏序集。,温故而知新!,67-57,定义设是一个偏序集，对任意x,yA，如果xy或yx，则称x与y是可比的。若x与y是可比的，xy，并且不存在zA，使得xzy，则

28、称y覆盖x。,可比与覆盖,例 1）集合A=a,b,c，偏序集中，a与a,b是可比的，a与b,c不是可比的；a,b覆盖a，但a,b,c不覆盖a。偏序集中，对任意x,yA，x与y都是可比的，但是，x不覆盖y，y也不覆盖x。偏序集中，对任意x,yA，x与y都是可比的，但是，x覆盖x-1。Z:所有的整数偏序集中，2与3不是可比的；2与6是可比的，并且6覆盖2；2与8是可比的，但8不覆盖2；对任意nN+，0与n是可比的，但0不覆盖n。N:自然数的全体,温故而知新!,67-58,偏序集的哈斯图,用小圆圈或点表示A中的元素，省掉关系图中所有的环。(因自反性)对任意x,yA，若xy，则将x画在y的下

29、方，可省掉关系图中所有边的箭头。(因反对称性)对任意x,yA，若y覆盖x，则x与y之间用一条线相连之，否则无线相连。(因传递性)按1),2),3)所作成的图称为哈斯图(Hasse图)。,温故而知新!,67-59,例,设A2,3,6,12,24,36,“”是A上的整除关系，画出其一般的关系图和哈斯图。,温故而知新!,67-60,例,设集合Aa，Ba,b，Ca,b,c，Da,b,c,d。分别画出集合A、B、C、D之幂集P(A)、P(B)、P(C)、P(D)上定义的“”的哈斯图。,a,a,b,a,b,a,b,c,a,b,a,c,b,c,a,b,c,a,b,c,d,a,b,a,c,b,

30、c,a,d,b,d,c,d,a,b,c,a,b,d,a,c,d,b,c,d,a,b,c,d,温故而知新!,67-61,偏序集中的特殊元素,定义设是偏序集，B是A的任何一个子集。,若存在元素bB,使得对任意xB,都有xb,则称b为B的最大元素，简称最大元。若存在元素bB,使得对任意xB,都有bx,则称b为B的最小元素，简称最小元。若存在元素bB,使得对任意xB,满足bxxb,则称b为B的极大元素，简称极大元。若存在元素bB,使得对任意xB,满足xbxb,则称b为B的极小元素，简称极小元。若存在元素aA,使得对任意xB,都有xa,则称a为B的上界。若存在元素aA,使得对任意xB,都有ax,

31、则称a为B的下界。若元素aA是B的上界,元素aA是B的任何一个上界,若均有aa,则称a为B的最小上界或上确界,记aSupB。或lub若元素aA是B的下界,元素aA是B的任何一个下界,若均有aa,则称a为B的最大下界或下确界,记aInfB。或glb,温故而知新!,67-62,设是一偏序集，B是A的子集。则：若bB是B的最大元b是B的极大元、上界、最小上界；若bB是B的最小元b是B的极小元、下界、最大下界；若aA是B的最小上界，且aBa是B的最大元；若aA是B的最大下界，且aBa是B的最小元；若B存在最大元，则B的最大元是惟一的；若B存在最小元，则B的最小元是惟一的；若bB是B的极大元，且

32、b是唯一的b是B的最大元；若bB是B的极小元，且b是唯一的b是B的最小元；若B存在最小上界，则B的最小上界是惟一的；若B存在最大下界，则B的最大下界是惟一的。,定理,温故而知新!,67-63,集合的划分 P120,定义设A是一个集合，A1,A2,A3.Am是A的任何m个子集，如果A1,A2,A3.Am满足：对一切的ij(i,j1,2,3,.,m)，都有AiAj。,则称集合(A)A1,A2,A3,.,Am为集合A的一个划分,而A1,A2,A3,.Am叫做这个划分的块。,温故而知新!,67-64,例,上述划分用文氏图可表示如下：,对任何一个集合，我们要对集合中的元素进行划分，那么，

33、按照“怎样”的方式才能得到“正确”的划分呢？通常，不严格的“分类”是要闹出笑话的。下面，我们将会看到集合中的元素如果按照“等价关系”进行“分类”时，就可得到正确的划分。,温故而知新!,67-65,等价关系,定义设R是定义在集合A上的关系，如果R是自反的、对称的、传递的，则称此关系R为A上的等价关系。,例1）在全体中国人所组成的集合上定义的“同姓”关系，就是具备自反的、对称的、传递的性质，因此，就是一个等价关系；对任何集合A,考虑RAA,则R是A上的等价关系；三角形的“相似关系”、“全等关系”等都是等价关系；直线的“平行关系”不是等价关系，因为它们不是自反的。幂集上定义的“”，整数集上定

34、义的“”都不是等价关系，因为它们不是对称的。“朋友”关系，则不是等价关系，因它不是传递的。,温故而知新!,67-66,以m为模的同余关系,R称为Z上以m为模的同余关系，一般记xRy为xy(mod m)称为同余式。如用resm(x)表示x除以m的余数，则xy(mod m)resm(x)resm(y)。,此时，R将Z分成了如下m个子集：,-3m,-2m,-m,0,m,2m,3m,-3m+1,-2m+1,-m+1,1,m+1,2m+1,3m+1,-3m+2,-2m+2,-m+2,2,m+2,2m+2,3m+2,-2m-1,-m-1,-1,m-1,2m-1,3m-1,4m-1,温故而知新!,67-67,以m为模的同余关系,这m个Z的子集具有的特点：在同一个子集中的元素之间都有关系R，而不同子集的元素之间无关系R。也就是说，通过等价关系，将集合分成若干子集，使这些子集构成的集合就是Z的一个划分。,例如我们常见的时钟上的时针重复关系即为m=12，A=0,1,2,3,23，此等价关系R的关系图如下图所示，A被分成了12个子集0,12、1,13、2,14、11,23。,

展开阅读全文