1、第四章 二元关系离散数学及应用第四章 二元关系l4.1 关系及其表示l4.1.1 有序对与笛卡儿积l4.1.2 二元关系的定义l4.1.3 二元关系的表示l4.2 关系的运算l4.2.1 关系的基本运算l4.2.2 关系的幂和道路l4.3 关系的性质l4.3.1 关系性质的定义和判断l4.3.2 关系运算对性质的保持有序对l四名学生张,白,宋,方l三门课程离散数学,数据结构,计算机网络l可以使用什么样的数学结构来表示学生选课的情况？l一个选择l集合l例如张,离散数学有序对l再考虑另一个问题：l他们四人进行单循环羽毛球赛，l希望使用一种数学结构来表示各场比赛的胜负关系。l使用集合l白,方和方,白
2、l谁是胜者？l需要在数学结构中体现出序(order)有序对l由两个对象 a,b 按照一定次序组成的二元组称为一个有序对有序对或序偶序偶（ordered pair），记作(a,b)，其中 a 是它的第一元素第一元素或第一座标第一座标，b 是它的第二元素第二元素或第二座标第二座标。l(a,b)=(c,d)当且仅当 a=c 且 b=dl例：l平面直角坐标系上，每一个点的坐标都是一个有序对。笛卡尔积l设 A、B 为两个集合，定义它们的笛笛卡尔积（卡尔积（Cartesian product）AB 为AB=(a,b)|a A 且 b B ，l它也称作直积（直积（direct product）。lA=B=l
3、一般来讲 A B B Al例：l平面直角坐标系就是笛卡尔积 笛卡尔积l所有可能的选课情况：l张,白,宋,方 离散数学,数据结构,计算机网络=(张,离散数学),(张,数据结构),(张,计算机网络)(白,离散数学),(白,数据结构),(白,计算机网络),(宋,离散数学),(宋,数据结构),(宋,计算机网络),(方,离散数学),(方,数据结构),(方,计算机网络)笛卡尔积l定理若 A、B 都是有限集，则 A B 也是有限集，且|A B|=|A|B|l证明：考虑AB中的每一个元素(a,b)的产生方式，由乘法原理即得。笛卡尔积l定理笛卡儿积对于并或交运算满足分配律，即若A、B、C都是集合，则l A(BC
4、)=(AB)(AC)；l A(BC)=(AB)(AC)；l(BC)A=(BA)(CA)；l(BC)A=(BA)(CA)。笛卡尔积l笛卡尔积的推广：A1 A2 Am=(a1,a2,am)|ai Ai,i=1,2,m 第四章 二元关系l4.1 关系及其表示l4.1.1 有序对与笛卡儿积l4.1.2 二元关系的定义l4.1.3 二元关系的表示l4.2 关系的运算l4.2.1 关系的基本运算l4.2.2 关系的幂和道路l4.3 关系的性质l4.3.1 关系性质的定义和判断l4.3.2 关系运算对性质的保持二元关系l实际的选课情况只是笛卡尔积 张,白,宋,方离散数学,数据结构,计算机网络的一部分。l在羽
5、毛球比赛中，l不可能出现(张,张)l也不可能同时出现(张,白)和(白,张)二元关系l“关系”是一个基本而且普遍的概念。l数学上讲l假设 A、B 是集合，AB 的子集 R 称为A到到B的一个二元关系的一个二元关系，简称为关系关系（relation）。二元关系l若 R A B，当(a,b)R 时，称 a与与b具有关系具有关系R（a is related to b by R），记为aRb；l若(a,b)R，则称 a,b 不具有关系 R，记为 aRb。l如果 A=B 则称 R 为 A上的一个二元关上的一个二元关系系。二元关系l例：lA=1,2,3,4 lR=(1,1),(1,2),(1,4),(2,1
6、),(3,2),(3,4)l“选课”的例子：lR=(张,数据结构),(张,离散数学),(白,数据结构),(方,计算机网络)张,白,宋,方离散数学,数据结构,计算机网络l“羽毛球赛”的例子：l(张,白),(宋,张),(张,方),(白,宋),(方,白),(宋,方)二元关系l对于任意集合 A，可以在其幂集 P(A)上定义包含关系为：l假设A是非零整数集的任一子集，则可以定义A上的整除关系为：DA=(x,y)|x,y A 且 x|y l假设B是实数集的任一子集，则可以定义B上的小于等于关系为：LB=(x,y)|x,y A 且 x y(,)()()Rx yxAyAxy PP恒等关系l假设 A 是任一个集
7、合，则可定义 A 上的恒等恒等关系关系（equality relation）为：IA=(a,a)|a A 。l即(a,b)IA 当且仅当 a=b。二元关系l思考l如果|A|=n,那么可以在 A 上定义多少个不同的关系?lR A Al|P(A A)|=2|A A|l|A A|=|A|A|=n2二元关系l假设 A、B 是集合，R AB 是 A 到 B 的一个二元关系，C A，则定义关系关系 R 在集合在集合 C 上上的限制的限制（restriction of R to C）为集合(a,b)|(a,b)R 且 a C ，记之为 R|C。定义域与值域l假设 A、B 是集合，R AB 是 A 到 B 的
8、一个二元关系，lR 的定义域（定义域（domain）为集合 Dom(R)=a|a A,存在 b B 使得(a,b)R，即R中所有有序对的第一元素构成的集合；lR 的值域（值域（range）为集合 Ran(R)=b|b B,存在 a A 使得(a,b)R，即R中所有有序对的第二元素构成的集合。定义域与值域lDom(R)=a|aA,bB such that(a,b)R lRan(R)=b|bB,aA such that(a,b)R 定义域与值域lA=1,2,3,4lR=(1,1),(1,2),(1,4),(2,1),(3,2),(3,4)lDom(R)=1,2,3 lRan(R)=1,2,4 像集
9、l假设 A、B 是集合，R AB 是 A 到 B 的一个二元关系，l对于 A 中任一元素 x，可定义 x 的的像集像集(image)为R(x)=y B|xRy；l对于A的任一子集A1，可定义A1的的像集像集为R(A1)=y B|xRy 对某 x A1 成立，且定义 R()=。像集lR(x)=y B|xRy lR(A1)=y B|xRy 且存在 x A1 R(A1)=R(x)，对所有 x A1R()=像集lA=1,2,3,4lR=(1,1),(1,2),(1,4),(2,1),(3,2),(3,4)lR(2)=?lR(3)=?lR(2,3)=?lR(2)=1lR(3)=2,4lR(2,3)=1,
10、2,4像集l定理：假设 A、B 是集合，R、S 是 A 到 B 的二元关系，若对于所有 a A 都有R(a)=S(a)成立，则 R=S。l证明：l R Sl S R像集l证明：R S 若(a,b)R 则 b R(a)=S(a)于是(a,b)S.因此 R S.S R第四章 二元关系l4.1 关系及其表示l4.1.1 有序对与笛卡儿积l4.1.2 二元关系的定义l4.1.3 二元关系的表示l4.2 关系的运算l4.2.1 关系的基本运算l4.2.2 关系的幂和道路l4.3 关系的性质l4.3.1 关系性质的定义和判断l4.3.2 关系运算对性质的保持二元关系的表示形式l二元关系主要具有以下三种表示
11、方法l笛卡尔积的子集l有序对的集合l关系矩阵l有向图表示关系矩阵l设 A=a1,a2,am，B=b1,b2,bn，R 是从 A 到 B 的关系，l定义 R 的关系矩阵为一个 m n 的布尔矩阵 MR=rijm n，其中1if(,)0if(,)ijijijabRrabR关系矩阵lA=1,2,3,4 lR=(1,1),(1,2),(1,4),(2,1),(3,2),(3,4)123 412340000101000011011MR=关系矩阵离散 数据结构 网络张 白宋方 l“选课”的例子lR=(张,离散数学),(张,数据结构),(白,数据结构),(方,计算机网络)100000010011MR=关系图
12、l设 A=a1,a2,am，R 是 A 上的关系l例：lA=1,2,3,4lR=(1,1),(1,2),(1,4),(2,1),(3,2),(3,4)关系图l对 A 中每个元素，画一个圆形，并在圆形之中标明该元素。l此称之为关系图的顶点（顶点（vertice）lA=1,2,3,4 lR=(1,1),(1,2),(1,4),(2,1),(3,2),(3,4)1234关系图l若(ai,aj)R，则从顶点 ai 向顶点 aj 画一个箭头，称为有向边有向边或简称边（边（edge），若 ai=aj 则称这条边为自环（自环（cycle）。1234lA=1,2,3,4lR=(1,1),(1,2),(1,4)
13、,(2,1),(3,2),(3,4)关系图l得到的图表示称作关系 R 的关系图关系图（directed graph，或digraph）。1234lA=1,2,3,4lR=(1,1),(1,2),(1,4),(2,1),(3,2),(3,4)关系的示意图（和关系图不同）lR=(张,离散数学),(张,数据结构),(白,数据结构),(方,计算机网络)张白宋方离散数据结构网络第四章 二元关系l4.1 关系及其表示l4.1.1 有序对与笛卡儿积l4.1.2 二元关系的定义l4.1.3 二元关系的表示l4.2 关系的运算l4.2.1 关系的基本运算l4.2.2 关系的幂和道路l4.3 关系的性质l4.3.
14、1 关系性质的定义和判断l4.3.2 关系运算对性质的保持关系的基本运算l假设 A、B 是两个集合，a A，b B，R、S 为 A 到 B 的两个关系，l于是 R 和 S 都是 A B 的子集。l于是集合的运算也可以应用于 R 和 S。关系的基本运算lR 与 S 的交（交（intersection）关系 RS 定义为：(a,b)RS 当且仅当(a,b)R 且(a,b)S；lR 与 S 的并（并（union）关系 RS 定义为：(a,b)RS 当且仅当(a,b)R 或(a,b)S；lR 的补（补（complement）关系 R 定义为；aRb 当且仅当 aRb 关系的基本运算l张,白,宋,方 离
15、散数学,数据结构,计算机网络=lR=(张,数据结构),(张,离散数学),(白,数据结构),(方,计算机网络)lR=(张,计算机网络),(白,离散数学),(白,计算机网络),(宋,离散数学),(宋,数据结构),(宋,计算机网络),(方,离散数学),(方,数据结构),(张,离散数学),(张,数据结构),(张,计算机网络)(白,离散数学),(白,数据结构),(白,计算机网络),(宋,离散数学),(宋,数据结构),(宋,计算机网络),(方,离散数学),(方,数据结构),(方,计算机网络)关系的基本运算l例：lA=1,2,3,4 lR=(1,1),(1,2),(1,4),(2,1),(3,2),(3,4
16、)lS=(1,2),(1,3),(2,1),(2,2),(2,4),(4,4)lRS=(1,2),(2,1)lRS=(1,1),(1,2),(1,3),(1,4),(2,1),(2,2),(2,4),(3,2),(3,4),(4,4)关系的基本运算l假设 A、B 是两个集合，R 为 A 到 B 的关系，则 R 的逆（逆（inverse）关系）关系 定义为R 1=(b,a)|b B,a A,(a,b)R B A。l简言之，R 的逆关系是由将 R 中每个有序对的元素顺序交换构成的。l例：lA=1,2,3,4lR=(1,1),(1,2),(1,4),(2,1),(3,2),(3,4)lR 1=(1,
17、1),(2,1),(4,1),(1,2),(2,3),(4,3)关系的基本运算l例lR=(张,数据结构),(张,离散数学),(白,数据结构),(方,计算机网络)lR 1=(数据结构,张),(离散数学,张),(数据结构,白),(计算机网络,方)关系的基本运算lA=1,2,3,4lR=(1,1),(1,2),(1,4),(2,1),(3,2),(3,4)lR 1=(1,1),(2,1),(4,1),(1,2),(2,3),(4,3)关系的基本运算l假设 A、B、C 是集合，R 为 A 到 B 的关系，S 为 B 到 C 的关系，则 S R 表示 A 到 C 的一个关系S R=(a,c)|a A,c
18、 C,存在 b B 使得(a,b)R 且(b,c)S，称为 R 和 S 的复合（复合（composition）关系）关系或合成关系合成关系。关系的基本运算R=(张,数据结构),(张,离散数学),(白,数据结构),(方,计算机网络)，S=(数据结构,逸夫楼),(数据结构,一教),(离散数学,一教),(计算机网络,四教)张白宋方离散数据结构网络一教逸夫楼四教RS关系的基本运算S R=?张白宋方离散数据结构网络一教逸夫楼四教(方,四教)(白,一教),(白,逸夫楼),(张,逸夫楼),(张,一教),=RS关系的基本运算lR=(1,1),(1,2),(1,4),(2,1),(3,2),(3,4)lS=(1
19、,2),(1,3),(2,1),(2,2),(2,4),(4,4)lR S=?lR S=(1,1),(1,2),(1,4),(2,1),(2,2),(2,4)lS R=?lS R=(1,1),(1,2),(1,3),(1,4),(2,2),(2,3),(3,1),(3,2),(3,4)关系的基本运算l假设 A、B、C 为有限集合，R 为 A 到 B 的关系，S 为 B 到 C 的关系，则有MS R=MR MS0000101000011011MR=1000000010110110MS=0000101101101111MR MS=0000101101101111MS R=r11r12 r1mr21
20、r22 r2mri1ri2 rimrn1rn2 rnms11s12s1js1ps21s22s2js2psm1sm2smjsmp ri1ri2rims1js2jsmjcijrik=1skj=1kjikikj关系的基本运算关系矩阵形式关系图形式 RMR=MR =1-MR 图的“补”RSMRS=MRMS图的“交”RSMRS=MRMS图的“并”R 1MR 1=(MR)T每条边做“反向”S RMS R=MR MS关系运算的性质l定理假设 A、B 是集合，R、S 为 A 到 B 的关系，则：lDom(R 1)=Ran(R)，Dom(R)=Ran(R 1)；lR=R；l(R 1)1=R；l R 1=(R)1
21、；l(RS)1=R 1S 1 且(RS)1=R 1S 1。lR S=RS 且 RS=R S。关系运算的性质lR=S 当且仅当 MR=MSl证明：lM(RS)1=(MRS)T=(MRMS)TlMR 1S 1=(MR 1MS 1)=MRTMST(rjisji)(RS)1=R 1S 1关系运算的性质l定理 假设 A、B、C、D 均为非空集合，R 为 A 到 B 的关系，S 为 B 到 C 的关系，T 为 C 到 D 的关系，则T (S R)=(T S)R关系运算的性质l证明：MT (S R)=(MR MS)MTM(T S)R=MR (MS MT)关系运算的性质l定理假设 A、B、C 为非空集合，R
22、为 A 到 B 的关系，S 为 B 到 C 的关系，则(S R)1=R 1 S 1 关系运算的性质l定理 假设 A、B、C 是集合，R、S 为 A 到 B 的关系，l若 R S，则 R 1 S 1；l若 R S，则 S R。l定理假设 A、B、C 为集合，R1、R2 为 A 到 B 的关系，S1、S2 为 B 到 C 的关系，R1 R2，S1 S2，则 S1 R1 S2 R2 。关系的基本运算关系运算的性质l定理假设 A、B、C、D 为集合，R 为 A 到 B 的关系，S1、S2 为 B 到 C 的关系，T 为 C 到 D 的关系，则：l(S1S2)R=(S1 R)(S2 R)l(S1S2)R
23、 (S1 R)(S2 R)lT (S1S2)=(T S1)(T S2)lT (S1S2)(T S1)(T S2)l定理假设 A、B、C 为集合，R 为 A 到 B 的关系，S 为 B 到 C 的关系，则对于 A 的任意子集 A1 有：(S R)(A1)=S(R(A1)。关系运算的性质关系运算的性质(S R)(A1)=S(R(A1)RSBCAA1R(A1)S(R(A1)S R(S R)(A1)关系运算的性质(S R)(白白)=逸夫楼,一教一教 S(R(白白)=S(数据结构 )=逸夫楼,一教 张白宋方离散数据结构网络一教逸夫楼四教RSl证明（主体思路）(a)(S R)(A1)S(R(A1)令 c(
24、S R)(A1)。则存在 a A1，使得(a,c)S R。存在 b B，使得(a,b)R 且(b,c)S。于是 b R(A1)，并且有 c S(R(A1)。故而 c S(R(A1)。(b)S(R(A1)(S R)(A1)关系运算的性质(S R)(A1)=S(R(A1)关系运算的性质 1RSRS=RS(RS)1=R 1S 1RSRS=RS(RS)1=R 1S 1S R/(S R)1=R 1 S 1R SS RR 1 S 1R=R(R 1)1=RR 1=(R)1第四章 二元关系l4.1 关系及其表示l4.1.1 有序对与笛卡儿积l4.1.2 二元关系的定义l4.1.3 二元关系的表示l4.2 关系
25、的运算l4.2.1 关系的基本运算l4.2.2 关系的幂和道路l4.3 关系的性质l4.3.1 关系性质的定义和判断l4.3.2 关系运算对性质的保持关系的幂和道路1234关系的幂和道路l假设 A 为集合，a,b A，集合 A 上关系 R 中从 a 到 b 长为长为 n 的的道路（道路（path）是指 A 上有限序列:a,x1,x2,xn 1,b，满足：la R x1lxi R xi+1，1 i n 2lxn 1 R bl注：长度为n的道路包含n+1个顶点（允许重复）。abx1x2xn-1关系的幂和道路l从 a 到 e 长为 8 的一条道路abcdfegh关系的幂和道路l假设 A 为集合，a,
26、b A，集合 A 上关系 R 中从 a 到 b 的一条道路道路（path）是指 A 上有限序列:a,x1,x2,xn 1,b，l其中 n0 称为该道路的长度（长度（length），la 称作道路的起点起点，b 称作道路的终点终点。关系的幂和道路l从 a 到 d 的 一条道路abcdfegh关系的幂和道路l起点和终点相同的道路称之为回路回路（circuit）。abcdfegh关系的幂和道路l假设 1:a,x1,x2,xn-1,b 和 2:b,y1,y2,ym-1,c 是关系 R 中的两条道路l则定义 1 和 2 的复合（复合（composition）为道路 a,x1,xn-1,b,y1,ym-1
27、,c关系的幂和道路l1:a,e,b,c,dl2:d,f,g,el2 1:a,e,b,c,d,f,g,eabcdfegh关系的幂和道路l设 R 为集合 A 上的关系l定义 A 上的关系 Rn 为：la,b A，则 a Rn b 当且仅当存在 R 中从 a 到 b 长为 n 的道路l定义 A 上的关系 R 为：la,b A，则 a R b 当且仅当存在 R 中从 a 到 b 的道路关系的幂和道路1234R2R1234关系的幂和道路1234RR1234关系的幂和道路1234RR212341234RRRn关系的幂和道路l当集合 A 中元素较多时，如何计算 Rn 和 R？l手工绘制？l繁琐 l困难l变更
28、技术路线l代数方法关系的幂和道路l设 R 为集合 A 上的关系，n 为自然数l则 R 的 n 次次幂（幂（power）Rn 可递归地定义为lR0=IAlRn=Rn 1 R，n=1,2,3,.l与之前的定义等价等价关系的幂和道路l设 R 为有限集合 A 上的关系，n 为自然数，则lMR2=MR MR lMRn=MR MR MR (n个R的复合)也记作(MR)n 关系的幂和道路l定理：设 R 为集合 A 上的关系，则R =RR2R3，即 MR =MRMR2MR3 =MR(MR)2(MR)3 关系的幂和道路l证明：l(1)R RR2R3l假设 a,b A 且 aR b，则存在 R 中从 a 到 b
29、的道路 。设 的长度为 n，则 aRnb，于是(a,b)RR2R3。l(2)RR2R3 R l对于任意(a,b)RR2R3，必存在整数 n 使得 aRnb，即存在 R 中从 a 到 b 长为 n 的道路，于是存在 R 中从 a 到 b 的道路，继而因此 aR b。关系的幂和道路l定理：设 R 为集合 A 上的关系，则R =RR2R3，即 MR =MRMR2MR3 =MR(MR)2(MR)3 计算可行性？关系的幂和道路l定理假设 R 是有限集合 A 上的关系，|A|=n，则：R =RR2R3Rn。关系的幂和道路l证明：分两部分证明：(a)显然有RR2Rn R =RR2。(b)下面证明 R RR2
30、R3Rn。关系的幂和道路l证明：若 aR b，则存在 R 中从 a 到 b 的道路:a,x1,x2,xm 1,b 其中 m 1。若m 1 n 则由鸽巢原理，必定存在顶点 xi 和 xj，i j 使得 xi=xj。l证明：关系的幂和道路axi.xi+1bxj+1.xj-1xj更短的道路！关系的幂和道路l证明：因此总可以假定道路中间经过的顶点各异，且 m 1 n。（道路长度为m）若 m 1 n，则定理成立。若 m 1=n，则存在 k，使得1 k m 1,a=xk 或 b=xk；不失一般性地假定 a=xk。则l证明：关系的幂和道路ax1bxk+1.xk-1xk更短的道路！l证明：因此，存在从 a 到
31、 b 的道路，其长度不超过 n，即(a,b)RR2R3Rn。关系的幂和道路关系的幂和道路l思考：l是否存在集合 A 和 A 上的关系 R，使得对于任意 n 1，都有RR2R3Rn R？第四章 二元关系l4.1 关系及其表示l4.1.1 有序对与笛卡儿积l4.1.2 二元关系的定义l4.1.3 二元关系的表示l4.2 关系的运算l4.2.1 关系的基本运算l4.2.2 关系的幂和道路l4.3 关系的性质l4.3.1 关系性质的定义和判断l4.3.2 关系运算对性质的保持关系的性质l自反关系、非自反关系l涉及“1个”元素l对称关系、非对称关系、反对称关系l涉及“2个”元素l传递关系l涉及“3个”元
32、素自反性l 假设 R 为集合 A 上的关系，l如果(a,a)R 对于所有 a A 成立，则称 R 是自反的（自反的（reflexive），或称 R 满足自反性；l如果(a,a)R 对于所有 a A 成立，则称 R 是非自反非自反的（的（irreflexive），或称 R 满足非自反性。自反性关系矩阵的特点关系图的特点自反关系 a(a,a)R主对角线元素全是1，即对于所有 i，MR(i,i)=1每个顶点都有自环非自反关系 a(a,a)R主对角线元素全是0，即对于所有 i，MR(i,i)=0每个顶点都无自环自反？非自反？1234R自反？非自反？1234R自反？非自反？1234R自反关系与非自反关系
33、A 上所有关系自反关系非自反关系对称性l 假设 R 为集合 A 上的关系，l如果对于任意 a,b A，若(a,b)R 必然有(b,a)R，则称 R 是对称的（对称的（symmetric），或称 R 满足对称性；l如果对于任意 a,b A，若(a,b)R 必然有(b,a)R，则称 R 是非对称的非对称的（asymmetric），或称 R 满足非对称性；l如果对于任意 a,b A，若(a,b)R 且 (b,a)R 必然有 a=b，则称 R 是反对称的反对称的（antisymmetric），或称 R 满足反对称性。反对称性l另一等价定义 a b(a,b)R(b,a)R a=b)a b(a,b)R(b
34、,a)R)a=b)a b(a,b)R (b,a)R a=b)a b(a,b)Ra b)(b,a)R)a b(a,b)Ra b (b,a)R)对称？非对称？反对称？lA=1,2,3,R=(1,2),(3,1),(3,3)abaRbbRa aRb bRa11FFT12TFF13FTT21FTT22FFT23FFT31TFF32FFT33TTT1230 1 00 0 01 0 1不具有对称性对称？非对称？反对称？lA=1,2,3,R=(1,2),(3,1),(3,3)abaRbbRa aRb bRa11FFT12TFT13FTT21FTT22FFT23FFT31TFT32FFT33TTF1230 1
35、 00 0 01 0 1不具有非对称性对称？非对称？反对称？lA=1,2,3,R=(1,2),(3,1),(3,3)abaRbbRaaRb bRa b=a11FFT12TFT13FTT21FTT22FFT23FFT31TFT32FFT33TTT1230 1 00 0 01 0 1具有反对称性对称性关系矩阵的特点关系图的特点对称关系矩阵是对称矩阵，即对于所有i,j，MR(i,j)=MR(j,i)如果两个顶点之间有边，一定是一对方向相反的边非对称关系对于所有i,j，若MR(i,j)=1则 MR(j,i)=0两顶点之间至多存在一条有向边，每个顶点都无自环反对称关系对于所有i,j，若ij且MR(i,j
36、)=1则MR(j,i)=0 两互异顶点之间至多存在一条有向边，允许存在自环对称性l保留对称关系的有向图中的顶点，且将所有有向边改作无向边，其结果称作该关系的图（图（graph）。对称性1234R1234R对称性1234R1234R传递性l 假设 R 为集合 A 上的关系，l如果对于任意 a,b,c A，若(a,b)R 且(b,c)R 必然有(a,c)R，则称 R 是传递传递的（的（transitive），或称 R 满足传递性。具有传递性？lA=1,2,R=(1,1),(1,2)abc aRb bRa aRc aRb bRc aRc111TTTT112TTTT121TFTT122TFTT211F
37、TFT212FTFT221FFFT222FFFT12具有传递性？lA=1,2,R=(1,2),(2,1)abc aRb bRa aRc aRb bRc aRc111FFFT112FTTT121TTFF122TFTT211TFFT212TTFF221FTFT222FFFT12具有传递性？lA=1,2,R=(1,2)abc aRb bRa aRc aRb bRc aRc111FFFT112FTTT121TFFT122TFTT211FFFT212FTFT221FFFT222FFFT12不具有传递性 a b c(a,b)R(b,c)R (a,c)R)a b c(a,b)R (b,c)R (a,c)R)
38、a=cba a aabc传递性关系矩阵的特点关系图的特点传递关系abc(a,b)R(b,c)R(a,c)R)?关系性质的判断l定理 设 R 为集合 A 上的关系，则lR 具有对称性当且仅当 R=R 1 lR 具有非对称性当且仅当 RR 1=lR 具有反对称性当且仅当 RR 1 IA 关系性质的判断l证明：R 具有对称性当且仅当 R=R 1 若 R 具有对称性则 R=R 1(i)R R 1.假设(x,y)R，由于 R 具有对称性，因此(y,x)R即(x,y)R 1于是(x,y)R 1，于是 R R 1(ii)R 1 R.关系性质的判断l证明：R 具有对称性当且仅当 R=R 1 若则 R=R 1
39、则 R 具有对称性假设(x,y)R即(y,x)R 1由于 R=R 1，有(y,x)R，因此 R 具有对称性关系性质的判断l定理 设 R 为集合 A 上的关系，则lR 具有自反性当且仅当 IA R lR 具有非自反性当且仅当 RIA=关系性质的判断l定理 设 R 为集合 A 上的关系，则lR 具有传递性当且仅当 R2 R lR 具有传递性当且仅当对于所有 n 1，Rn R 成立。l（充分性令 n=2）l（必要性对 n 进行归纳即可证明）关系性质的判断自反关系IA R 非自反关系RIA=对称关系R=R 1非对称关系RR 1=反对称关系RR 1 IA 传递关系R2 R；或者Rn R 对所有 n 1成
40、立传递性关系矩阵的特点关系图的特点传递关系对于所有 i,j，若(MR MR)(i,j)=1则 MR(i,j)=0如果存在有向边(i,j)和(j,k)，则存在有向边(i,k)第四章 二元关系l4.1 关系及其表示l4.1.1 有序对与笛卡儿积l4.1.2 二元关系的定义l4.1.3 二元关系的表示l4.2 关系的运算l4.2.1 关系的基本运算l4.2.2 关系的幂和道路l4.3 关系的性质l4.3.1 关系性质的定义和判断l4.3.2 关系运算对性质的保持关系运算对性质的保持l要解决的问题：l哪些运算可以保持关系的哪些性质l哪些性质有可能因哪种运算而失去关系运算对性质的保持l定理1 设 R 和
41、 S 为集合 A 上的关系，则(a)若 R 是自反的，那么 R 1 也是自反的；(b)若 R 和 S 都是自反的，那么 RS，RS 及 S R 都是自反的；(c)R 是自反的当且仅当 R 是非自反的。关系运算对性质的保持l证明：若 R 是自反的，那么 R 1 也是自反的假设 x A。由于R 具有自反性，因此(x,x)R，于是(x,x)R 1，故而 R 1 具有自反性关系运算对性质的保持l定理2 设 R 和 S 为集合 A 上的关系，则(a)若 R 是对称的，那么 R 1 和 R 也是对称的(b)若 R 是对称的，那么 Rn 也是对称的(c)若 R 和 S 都是对称的，那么 RS 和 RS 也是
42、对称的。关系运算对性质的保持l定理3 设 R 和 S 为集合 A 上的关系，则(a)(RS)2 R2S2(b)若 R 是传递的，那么 R 1 也是传递的(c)若 R 和 S 都是传递的，那么 RS 也是传递的关系运算对性质的保持l证明：(a)(RS)2 R2S2（主要思路）baRSbaRbaS&(a,b)(RS)2(a,b)R2 (a,b)S2(RS)2 R2S2(a,b)R2S2 Operations on Relationsl证明：(c)由(a)，有(RS)2 R2S2。由于 R 具有传递性，有 R2 R。由于 S 具有传递性，有 S2 S。于是(RS)2 R2S2 RS。因此 RS 具有传递性。若 R 和 S 都是传递的，那么 RS 也是关系运算对性质的保持如果 R 和 S 具有如下性质 那么RR-1RS RS S R自反性具有非自反性非自反性具有自反性对称性反对称性传递性End
