离散数学关系的性质省名师优质课赛课获奖课件市赛课一等奖课件.ppt

14.3 关系性质l关系性质及特点关系性质及特点l关系性质充要条件关系性质充要条件l关系性质证实关系性质证实l运算和性质关系运算和性质关系第1页21.自反二元关系自反二元关系(1).定定义义：R是是上上二二元元关关系系，若若 x(xA R),则称则称R在在A上是上是自反自反二元关系。二元关系。比如比如 a,b,c,R=(a,a),(b,b),(c,c),(a,b)，则是自反。则是自反。又如又如1,2,3,R是上整除关系，是上整除关系，显然，是自反，因为（显然，是自反，因为（1,1）,（2,2）,（3,3）都属于都属于R。即即假假如如对对于于中中每每一一个个元元素素a,都都有有(a,a)R，则则称称为为自反二元关系。自反二元关系。一、关系性质及特点一、关系性质及特点第2页3注意，在关系自反性定义中，要求对于注意，在关系自反性定义中，要求对于A中中每一个元素每一个元素a都有都有(a,a)R。所以当。所以当A=a,b,c，而，而R=(a,a),(b,b)时，时，R并不是自反，因为并不是自反，因为(c,c)R。又如又如A=1,2,3，R是是A上二元关系，当上二元关系，当a,bA，且且a和和b都是素数时，都是素数时，(a,b)R。可见可见(2,2),(3,3),(2,3),(3,2)，也不是自反关，也不是自反关系，因为系，因为(1,1)R。第3页4(2).关系矩阵特点：关系矩阵特点：关系矩阵中主对角线上元素全为关系矩阵中主对角线上元素全为1。(3).关系图特点：关系图特点：关系图中每个顶点都有环。关系图中每个顶点都有环。实例：实例：A上全域关系上全域关系EA,恒等关系恒等关系IA，小于等于关系，小于等于关系LA,整除关系整除关系DA都是自都是自反关系：反关系：第4页52反自反二元关系反自反二元关系(1).定义：定义：R是上二元关系，若是上二元关系，若 x(xA R),则称则称R在在A上是上是反自反反自反二元关系二元关系.比如比如a,b,c,R=(a,b),(b,c),(b,a)，则是反自反。，则是反自反。又如又如1,2,3,R是上小于关系，即当是上小于关系，即当ab时，时，(a,b)R。显然，是反自反。显然，是反自反。注意，非自反二元关系不一定是反自反二元关系，注意，非自反二元关系不一定是反自反二元关系，因为存在着这么二元关系，它既不是自反又不是反自因为存在着这么二元关系，它既不是自反又不是反自反，如反，如=a,b,c,R=(a,a),(a,b)，那么不是自反，那么不是自反(因因为为(b,b),(c,c)都不属于都不属于)，也不是反自反，也不是反自反(因为因为(a,a)R)。即对于中每一个元素即对于中每一个元素a,都有都有(a,a)R，则称为，则称为反自反二元关系。反自反二元关系。第5页6实例：实例：实数集上小于关系，空关系实数集上小于关系，空关系，幂集上，幂集上真包含关系都是反自反关系。真包含关系都是反自反关系。(2).关系矩阵特点：关系矩阵特点：关系矩阵中主对角线上元素全为关系矩阵中主对角线上元素全为0。(3).关系图特点：关系图特点：关系图中每个顶点都没有环。关系图中每个顶点都没有环。第6页7例例1 A=1,2,3,R1,R2,R3是是A上关系上关系,其中其中R1,R2,R3R1既不是自反也不是反自反既不是自反也不是反自反R2为自反关系为自反关系,R3为反自反关系。为反自反关系。第7页83.对称二元关系对称二元关系(1).定义定义:R是上二元关系，是上二元关系，若若 x，y(x,yARR),则称则称R为为A上上对称对称二元关系二元关系.比如比如=a,b,c,d,R=(a,a),(a,b),(b,a),(b,d),(d,b)则是对称二元关系。则是对称二元关系。又如又如=1,2,3,4,5,对于中元素对于中元素a和和b,假如假如a,b是模是模3同余关系，则同余关系，则(a,b),易见是对称关系。易见是对称关系。即假如即假如(a,b)R,就一定有就一定有(b,a)R,则称为对称二元关系。则称为对称二元关系。第8页9实例：实例：A上全域关系上全域关系EA,恒等关系恒等关系IA和空关系和空关系都是都是对称关系。对称关系。(2).关系矩阵特点：关系矩阵特点：关系矩阵为对称矩阵。关系矩阵为对称矩阵。(3).关系图特点：关系图特点：关系图中假如两个顶点之间有边一定是一对关系图中假如两个顶点之间有边一定是一对方向相反边。方向相反边。第9页104反对称二元关系反对称二元关系即即R是上二元关系，每当有是上二元关系，每当有(a,b)和有和有(b,a)时，必有时，必有a=b,则称是反对称二元关系。则称是反对称二元关系。反对称定义也可写为：是上二元关系，反对称定义也可写为：是上二元关系，当当ab时，假如时，假如(a,b),则必有则必有(b,a)R,称为反对称二元关系。称为反对称二元关系。比如比如=1,2,3,R是上小于关系，即是上小于关系，即ab，（，（a,b）。易见易见=(1,2),(1,3),(2,3),所以是反对称。所以是反对称。又如是一些整数组成集合，假如又如是一些整数组成集合，假如a整除整除b，则，则(a,b),R也是反对称。也是反对称。(1).定义：若定义：若 x，y(x,yARRx=y),则称则称R为为A上上反对称反对称关系关系.第10页11注意，注意，“对称对称”和和“反对称反对称”这两个概念并非相互对立，这两个概念并非相互对立，相互排斥。存在着既不是对称又不是反对称二元相互排斥。存在着既不是对称又不是反对称二元关系，也存在着既是对称又是反对称二元关系。关系，也存在着既是对称又是反对称二元关系。又如又如A=a,b,c,R=(a,a),可知是对称，又是反对称。可知是对称，又是反对称。因为虽有因为虽有(a,b)R,(b,a)R，但，但(c,d)R时时(d,c)R,所以所以R不是对称，不是对称，比如比如A=a,b,c,d R=(a,b),(b,a),(c,d)这里这里R既不是对称，也不是反对称。既不是对称，也不是反对称。因为有因为有(a,b)R和和(b,a)R，所以，所以R不是反对称。不是反对称。第11页12实例：实例：恒等关系恒等关系IA，空关系空关系都是都是A上反对称关系。上反对称关系。(2).关系矩阵特点：关系矩阵特点：关系矩阵中以主对角线对称元素不能同时为关系矩阵中以主对角线对称元素不能同时为1。(3).关系图特点：关系图特点：关系图中假如两个顶点之间有边一定是一条有向边。关系图中假如两个顶点之间有边一定是一条有向边。第12页13例例2 设设A1,2,3,R1,R2,R3和和R4都是都是A上关系上关系,其中其中 R1,，R2,R3,，R4,R1 对称、反对称对称、反对称.R2 对称，不反对称对称，不反对称.R3 反对称，不对称反对称，不对称.R4 不对称、也不反对称不对称、也不反对称.第13页14 5.可传递二元关系可传递二元关系(1).定义：定义：R是是A上二元关系，上二元关系，x y z(x,y,zARRR),则称则称R是是A上上传递传递关系关系.比如整除关系是可传递，因为每当（比如整除关系是可传递，因为每当（a，b）R时，时，即即 a 能整除能整除 b，b能整除能整除c时，显然时，显然 a 能整除能整除 c，所以必有（所以必有（a，c）R。又如又如A=a，b，c，d，e，其中，其中a、b、c、d、e分别是表示分别是表示5个人，且个人，且a、b、c同住一个房间；同住一个房间；d和和e同住另一个房间。同住另一个房间。假如同住一房间人认为是相关，显然这种同房间关系假如同住一房间人认为是相关，显然这种同房间关系是可传递。是可传递。每当有每当有(a,b)R和和(b,c)R时，必有时，必有(a,c)R，则称为可传递二元关系。，则称为可传递二元关系。第14页15实例：实例：A上全域关系上全域关系EA,恒等关系恒等关系IA和空关系和空关系 小于等于关系小于等于关系,小于关系，整除关系，包含关系，小于关系，整除关系，包含关系，真包含关系都是传递二元关系。真包含关系都是传递二元关系。(2).关系矩阵特点：关系矩阵特点：(3).关系图特点：关系图特点：关系图中假如两个顶点关系图中假如两个顶点xi到到xj之间有边之间有边,xj到到xk之间有边之间有边,则从则从xi到到xk之间有边。之间有边。第15页16关系性质判别汇总l表示式自反性自反性反自反性反自反性对称性对称性 反对称性反对称性传递性传递性关系关系矩阵矩阵主对角主对角线元素线元素全是全是1主对角线主对角线元素全是元素全是0矩阵是矩阵是对称矩对称矩阵阵若若rij1,且且ij,则则rji0关系图关系图每个顶每个顶点都有点都有环环每个顶点每个顶点都没有环都没有环l假如两个顶点之间有边,是一对方向相反边(无单边)l假如两点之间有边,是一条有向边(无双向边)l假如顶点 xi 连通到xk,则从 xi到 xk 有边 第16页例例3 设设A1,2,3,R1,R2是是A上关系上关系,其中其中 R1,R2,R1 是是A上传递关系上传递关系 R2不是不是A上传递关系上传递关系第17页18例例4 判断下列图中关系性质判断下列图中关系性质,并说明理由并说明理由.(2)反自反，不是自反；反对称，不是对称；反自反，不是自反；反对称，不是对称；(1)不自反也不反自反；对称不自反也不反自反；对称,不反对称；不传递不反对称；不传递.(3)自反，不反自反；反对称，不是对称；不传递自反，不反自反；反对称，不是对称；不传递.第18页19二、关系性质充要条件设设R为为A上关系上关系,则则 (1)R在在A上上自反自反当且仅当当且仅当 IA R (2)R在在A上上反自反反自反当且仅当当且仅当 RIA=(3)R在在A上上对称对称当且仅当当且仅当 R=R 1 (4)R在在A上上反对称反对称当且仅当当且仅当 RR 1 IA (5)R在在A上上传递传递当且仅当当且仅当 R R R 第19页201.自反性证实自反性证实证实模式证实模式 证实证实R在在A上自反上自反 任取任取x,x A .R 前提前提 推理过程推理过程 结论结论例例5 证实若证实若 IA R，则则 R在在A上自反上自反.三、关系类型证实三、关系类型证实证证 任取任取x,x A IA R 所以所以 R 在在 A 上是自反上是自反.第20页212.对称性证实对称性证实证实模式证实模式 证实证实R在在A上对称上对称 任取任取 R .R 前提前提 推理过程推理过程 结论结论例例6 证实若证实若 R=R 1,则则R在在A上对称上对称.证证 任取任取 R R 1 R 所以所以 R 在在 A 上是对称上是对称.第21页223.反对称性证实反对称性证实证实模式证实模式 证实证实R在在A上反对称上反对称 任取任取 R R .x=y 前提前提 推理过程推理过程 结论结论例例7 证实若证实若 RR 1 IA,则则R在在A上反对称上反对称.证证 任取任取 R R R R 1 RR 1 IA x=y 所以所以 R 在在 A 上是反对称上是反对称.第22页234.传递性证实传递性证实证实模式证实模式 证实证实R在在A上传递上传递 任取任取，R R.R 前提前提 推理过程推理过程 结论结论例例8 证实若证实若 R R R,则则R在在A上传递上传递.证证 任取任取，R R R R R 所以所以 R 在在 A 上是传递上是传递.第23页思索思索1.设设A=a,b,c,R是是A上二元关系上二元关系 且且 R=(a,a),(b,b),(a,c),(c,a),问问R是自反吗？是自反吗？是反自反吗？是对称吗？是反对称吗？是反自反吗？是对称吗？是反对称吗？是可传递吗？是可传递吗？解：因为解：因为c R,但但(c,c)R,所以所以R不是自反关系；不是自反关系；又因为又因为(c,a)R,(a,c)R,但但(c,c)R,所以所以R不是传递关系。不是传递关系。显然显然R是对称关系，是对称关系，R不是反对称关系；不是反对称关系；因为因为(a,a)R,(b,b)R,所以所以R也不是反自反关系；也不是反自反关系；第24页思索思索2.设设A=a,b，写出，写出（1）A上全部自反关系；（上全部自反关系；（2）A上全部反自反关系；上全部反自反关系；（3）A上全部对称关系；（上全部对称关系；（4）A上全部反对称关系。上全部反对称关系。解解（1）因为因为AA=(a,a),(b,b),(a,b),(b,a)，而而A上自反关系必须含有上自反关系必须含有(a,a),(b,b)。所以所以A上自反关系共有上自反关系共有4种。种。它们是它们是 (a,a),(b,b)，(a,a),(b,b),(a,b)，(a,a),(b,b),(b,a)，(a,a),(b,b),(a,b),(b,a)。第25页(2)因为因为A上反自反关系必须不含有上反自反关系必须不含有(a,a),(b,b)。所以所以A上反自反关系也有上反自反关系也有4种。种。它们是它们是(空关系空关系)，(a,b)，(b,a)，(a,b),(b,a)。(3)因为因为A上对称关系上对称关系R,当当(a,b)R时时,必有必有(b,a)R,所以只需考虑在所以只需考虑在(a,a),(b,b),(a,b)中选取中选取0个，个，1个，个，2个，个，3个有序对组成集合。个有序对组成集合。它们是空关系它们是空关系,(a,a),(b,b),(a,b),(b,a),(a,a),(b,b),(a,a),(a,b),(b,a)，(b,b),(a,b),(b,a),(a,a),(b,b),(a,b),(b,a)。所以所以A上对称关系有上对称关系有8种。种。第26页27所以在所以在AA子集中删去同时含有子集中删去同时含有(a,b)和和(b,a)子集子集后，其它子集都是反对称关系，共有后，其它子集都是反对称关系，共有12种。种。即即(空关系空关系)，(a,a),(a,b),(b,a),(b,b),(a,a),(a,b),(a,a),(b,a),(a,a),(b,b),(a,b),(b,b),(b,a),(b,b),(a,a),(a,b),(b,b)，(a,a),(b,a),(b,b)。（4）因为）因为A上反对称关系，当上反对称关系，当(a,b)R必有必有(b,a)R。第27页28思索思索3.设设A=1，2，3，问在，问在A上有多少种不一样自反关系？上有多少种不一样自反关系？解：当解：当R R是是A A上自反关系时，上自反关系时，R R必须含有表格中对角线上必须含有表格中对角线上 3 3个小方格所表示有序对，对于表格中余下个小方格所表示有序对，对于表格中余下6 6个小个小 方格，能够依次选取方格，能够依次选取1 1个，个，2 2个，个，6 6个小方格，个小方格，也能够不取，它们所表示二元关系都是也能够不取，它们所表示二元关系都是A A上自反关系，上自反关系，所以，所以，A A上共有上共有6464个自反关系。个自反关系。第28页5.传递性判定方法传递性判定方法判定判定定理定理1 1：设集合：设集合A=aA=a1 1,a,a2 2,a,an n，R R是是A A上二上二元关系，元关系，R R 关系矩阵为关系矩阵为M MR R，令令M MR R2 2=M MR R M MR R，则，则R R是是A A上传递关系充要条件是对上传递关系充要条件是对M MR R2 2中中1 1所在位置所在位置,M MR R中对中对应位置都是应位置都是1 1。例例9：设：设A=a，b，c，d，e，R=,试判断试判断R传递性。传递性。判定判定定理定理2 2：设集合：设集合A=aA=a1 1,a a2 2,a,an n，R R是是A A上二上二元关系，元关系，R R 关系矩阵为关系矩阵为M MR R，R R是是A A上传递关系充要上传递关系充要条件是若条件是若M MR R中零元素中零元素a aijij=0=0所对应所对应M MR R2 2元素元素bij=0时，时，则则R R是是A A上传递关系。上传递关系。第29页思索：设思索：设A=a1，a2，a3，a4，a5，R=,试判断试判断R传递性。传递性。第30页31四、运算与性质关系自反性自反性反自反性反自反性对对称性称性反反对对称性称性传递传递性性R1 1 R1R2 R1R2 R1 R2 R1 R2 第31页32思索：思索：1.当当|A|=n时，时，(1)(1)在在A A上有多少种不一样自反关系？上有多少种不一样自反关系？(2)(2)有多少种不一样反自反关系？有多少种不一样反自反关系？(3)(3)有多少种不一样对称关系？有多少种不一样对称关系？(4)(4)有多少种不一样自反且对称关系？有多少种不一样自反且对称关系？2.设设A=1，2，3，4，R是是A上二元关系，上二元关系，R=(1,1),(1,2),(1,3),(3,1),(3,2),(3,3),),(4,1),),(4,2),),(4,3),(1)画出画出R关系图；关系图；(2)写出写出R关系矩阵；关系矩阵；(3)判断判断R性质。性质。第32页