离散数学课件：关系的运算

05:3711离散数学

(DiscreteMathematics)05:372关系的集合运算关系的复合小结4.4关系的复合05:373一、关系的集合运算解4.4关系的复合例1

设A={1,2,3}，求R∪S，R∩S，R-S，，定理4.4.1

若R与S都是集合A到集合B的关系，则R∪S，R∩S，R-S，，均为A到B的关系。05:374二、关系的复合4.4关系的复合1.复合关系的定义定义4.4.1

设R是由A到B的关系，S是由B到C的关系，则称为R和S的复合关系，是一个由A到C的关系，表示为：这种由R和S求复合关系的运算称为关系的复合运算。05:375于是复合关系例2

设R是由A={1,2,3,4}到B={2,3,4}的关系，S是由B到C={3,5,6}的关系，分别定义为：4.4关系的复合123653234R4SBAC05:376例3

设A是所有人的集合，于是复合关系4.4关系的复合05:377定理4.4.2

设集合A={a1,a2,am}，B={b1,b2,bp}，C={c1,c2,cn}，R是由A到B的关系，S是由B到C的关系，MR=(uij)mp，MS=(vij)pn

，则MR◦S=MR◦MS=(wij)mn，这里2.复合关系的关系矩阵4.4关系的复合其中的加法和乘法分别为布尔加和布尔乘。05:3784.4关系的复合例4

设A={1,2,3,4}，B={a,b,c}，C={e,f,g}.A到B的关系B到C的关系则abcfegfeg05:3794.4关系的复合例5

设A={1,2,3,4}，B={2,3,4}，C={1,2,3}.A到B的关系B到C的关系则23421321305:3710定理4.4.3

设R是由集合A到B的关系，则例如

设R是由A={1,2,3,4}到B={2,3,4}的关系，从关系图，可知：3.复合关系的性质4.4关系的复合123432234R4IABAB1234AIB05:3711

定理4.4.4

设R是由A到B的关系，S是由B到C的关系，则有(1)(2)(3)4.4关系的复合05:3712

复合关系的性质：4.4关系的复合(1)结合律：若，，，则05:3713

复合关系的性质：4.4关系的复合(1)结合律：若，，，则(2)若，，05:3714

复合关系的性质：4.4关系的复合(1)结合律：若，，，则(2)若，，05:3715则A到C的关系因此因此所以例6

设A={1,2,3,4}，B={2,3,4}，C={1,2,3}，D={4,5,6}.A到B的关系B到C的关系C到D的关系4.4关系的复合05:3716一般地，若R1是一由A1到A2的关系，R2是由A2到A3的关系，…，Rn是一由An到An+1的关系，则不加括号的表达式，唯一地表示一由A1到An+1的关系，在计算这一关系时，可以运用结合律将其中任意两个相邻的关系先结合。4.4关系的复合特别地，当A1=A2=

=An+1，R1=R2=

=Rn=R时，复合关系R◦R◦

◦R简记作Rn，它也是集A上的一个关系。05:3717三、小结4.4关系的复合本节主要介绍了复合关系的运算与性质。重点掌握复合关系的运算及其性质。05:371818离散数学

(DiscreteMathematics)05:3719逆关系的定义逆关系的性质小结4.5逆关系05:37204.5逆关系一.逆关系的定义定义4.5.1

设A、B是任意集合，R是由A到B的关系，由B到A的关系称为关系R的逆关系。

RC是由B到A的关系。RC的关系矩阵：RC的关系图：R的关系图中所有有向弧线全部反向。05:3721于是解例1

设A={2,3,5}，B={4,6,10}，定义由A到B的关系D如下：当且仅当a整除b时，有aDb，试求D的逆关系DC。4.5逆关系由D的定义知05:3722定理4.4.6

设A、B是任意集合，R1、R2和R都是由A到B的关系，则有二.逆关系的性质4.5逆关系(1)(2)(3)(4)(5)(6)(7)05:3723(8)令R是由A到B的关系，S是B到C的关系，则4.5逆关系证因为所以05:37244.5逆关系(9)设R是集合A上的二元关系，则(1)R是对称的，当且仅当R=RC。(2)R是反对称的，当且仅当RRCIA.证(1)已知R对称，则对任意的a,bA，同理反之，已知所以对任意的a,bA，设设，因为R对称则所以，因此R=RCR=RC因为R=RC所以，因此R对称。05:37254.5逆关系(9)设R是集合A上的二元关系，则(1)R是对称的，当且仅当R=RC。(2)R是反对称的，当且仅当RRCIA.证(2)设R反对称，则对任意的a,bA，所以反之，当RRCIA。所以，R是反对称的。对任意的a,bA，设05:3726三、小结4.5逆关系本节主要介绍了逆运算的定义与性质。重点掌握逆关系的应用、性质及其性质的证明方法。05:372727离散数学

(DiscreteMathematics)05:3728关系的闭包的概念关系的闭包的性质关系的闭包的求法小结4.6关系的闭包运算05:3729例1

设R是由A上的关系，A={1,2,3}，(1)求一个A上的关系R’，使得R

R’，且R’是自反的。(2)这样的关系共有多少个?4.6关系的闭包运算解(1)举例：(2)一、

关系的闭包的概念05:37304.6关系的闭包运算定义4.6.1

设R、是集合A上的关系，如果满足：(1)是自反的(对称的/可传递的)(2)(3)对任何自反的(对称的/可传递的)的关系，若，则。称

为R的自反(对称/传递)闭包。R的自反闭包、对称闭包、传递闭包分别记作05:3731说明:求集合A上的关系的自反、对称、传递闭包的运算，称为关系的闭包运算。R的自反(对称、传递)闭包是包含R的具有自反(对称/可传递)性质的最小关系。4.6关系的闭包运算05:37324.6关系的闭包运算二、

关系的闭包的性质定理4.6.1

设R是集合A上的二元关系，则(1)R是自反的

r(R)=R(2)R是对称的

s(R)=RR是可传递的

t(R)=R证明略05:37334.6关系的闭包运算三、

关系的闭包的求法定理4.6.2

设R是集合A上的二元关系，则(1)1.利用定义求闭包(2)(3)(通常，将记作R+，所以t(R)=R+)05:37344.6关系的闭包运算三、

关系的闭包的求法定理4.6.2

设R是集合A上的二元关系，则(1)1.利用定义求闭包证明(3)分两部分证明。(2)(3)(a)先证，用数学归纳法。(通常，将记作R+，所以t(R)=R+)05:37354.6关系的闭包运算①由传递闭包的定义，立即有Rt(R).②假设Rnt(R)，n1。设，由①及②，有再由t(R)的传递性，有所以故所以05:37364.6关系的闭包运算首先证明(a)再证。设则必存在整数s和t，s1，t1，使得因此，所以因为包含R的传递关系都包含t(R)，故由(a)和(b)，得。而05:3737例2

设A={a,b,c}，R是集合A上的关系，解求r(R)、s(R)、t(R)。4.6关系的闭包运算05:3738定理4.6.3

设R是集合A上的二元关系，A为含有n个元素的集合，则存在某个正整数kn，使得因此，我们有4.6关系的闭包运算05:37394.6关系的闭包运算2.利用关系矩阵求闭包例3

设A={a,b,c}，R是集合A上的关系，求r(R)、s(R)、t(R)。解abcabc05:37404.6关系的闭包运算abc因为所以于是因为所以于是05:37414.6关系的闭包运算因为|A|=3，所以于是而所以故05:37424.6关系的闭包运算3.利用Warshall求传递闭包的关系矩阵算法如下：(1)置新矩阵N:=MR(2)置i:=1(3)对所有j，如果N[j,i]=1，则对k=1,2,,nN[j,k]:=N[j,k]+N[i,k](4)i加1

(5)如果i

n，则转(3)，否则停止。

05:37434.6关系的闭包运算例4

设A={1,2,3}，R是集合A上的关系，求t(R)。解i=105:37444.6关系的闭包运算i=2i=3求t(R)。例4

设A={1,2,3}，R是集合A上的关系，解i=4时，N的第4列全为0，所以矩阵不变。故05:3745整数集合上的以下关系的自反，对称，传递闭包是什么？小于小于等于