关系与序关系

关系与序关系第1页，共76页，2023年，2月20日，星期三2.1关系的概念[例]设A={Alice,Bob,Tom},B={Algebra,Graphs,Sets}Alice选修了Graphs,Bob选修了Algebra,Graph和Sets;Tom选修了Algebra,Graphs;R={<Alice,Graphs>,<Bob,Algebra>,<Bob,Graphs>,<Bob,Sets>,<Tom,Algrbra>,<Tom,Graphs>}AB,表示了学生集合A与课程集合B之间的选修关系。第2页，共76页，2023年，2月20日，星期三2.1关系的概念[二元关系的一般性描述]

一对对象之间的关系称为二元关系。[例]

teachers={a,b,c}，students={x,y,z}

建立教学关系T:aTxiffaTEACHINGx用序偶集合表示为：

T={<a,x>,<a,z>,<b,y>,<c,y>,<c,z>}Tteachersstudents图示为：第3页，共76页，2023年，2月20日，星期三2.1关系的概念[例]

Subroutines={a,b,c,d,e}子程序间调用关系图示为：Calling={<a,a>,<a,b>,<a,d>,<b,a>,<b,c>,<c,c>,<c,e>,<d,d>}CallingSubroutinesSubroutines第4页，共76页，2023年，2月20日，星期三2.1关系的概念[二元关系的集合定义]

设X,Y是两个集合，XY的任何一个子集

R都确定了一种二元关系，称为从X到Y的二元关系。

<x,y>R可记为xRy，显然RXY

<x,y>R可记为xRy当X=Y即X与Y同一时，称R为X上的一个二元关系。第5页，共76页，2023年，2月20日，星期三2.1关系的概念[例]

F={<x,y>|x是y的父亲}

S={<x,y>|x,y为正整数且x可整除y}T={<y2,y>|y为实数}对上述的：x，y，R，有<x,y>R或

<x,y>R，二者必居其一。第6页，共76页，2023年，2月20日，星期三2.1关系的概念[定义域]设二元关系S。由<x,y>S的所有对象x组成的集合称为S的定义域，记为Dom(S)。[值域]由<x,y>S的所有对象y组成的集合称为S的值域，记为Ran(S)(Range(S))。记

F(S)=D(S)R(S)，称为S的域。描述：Dom(S)={x|(y)(<x,y>S)}Ran(S)={y|(x)(<x,y>S)}第7页，共76页，2023年，2月20日，星期三2.1关系的概念若干特殊关系：①

X到Y的全域关系：Ex,y=XY

特别地：

Ex,x=XX②空关系：

③恒等关系：Ix={<xi,xi>|xiX}[例]设X={1,2,3,4}，求X上的关系“>”(大于)及其定义域、值域。第8页，共76页，2023年，2月20日，星期三2.2关系的表示方法(1)集合表示法借用集合的各种描述方法对表示关系的序偶集合进行描述(2)关系矩阵设X={x1,x2,…,xm}，Y={y1,y2,…,yn}，m,n<+R是X到Y的二元关系。构造矩阵MR=[mij]mn，mij

=<xi,yj>R0其它第9页，共76页，2023年，2月20日，星期三2.2关系的表示方法[例]非0行对应元素构成D(S)非0列对应元素构成R(S)第10页，共76页，2023年，2月20日，星期三2.2关系的表示方法(3)关系图表示法用结点表示X、Y上的元素；若<x,y>R则从结点x到结点y画一条弧。[例]上述Teaching关系的关系图：第11页，共76页，2023年，2月20日，星期三2.2关系的表示方法[例]设X={1,2,3,4}，X上的关系“>”：第12页，共76页，2023年，2月20日，星期三2.3关系的性质[定义]设R是X上的二元关系，则：①R是自反的(x)(xXxRx)②R是对称的(x)(y)(x,yXxRyyRx)③R是传递的(x)(y)(z)(x,y,zXxRyyRz

xRz)④R是反自反的(x)(xX¬(xRx))⑤R是反对称的(x)(y)(x,yXxRyyRx

x=y)第13页，共76页，2023年，2月20日，星期三2.2关系的性质[习题]

设X={1,2,3,4}，画出X上的关系“>”，“”和整除“|”的关系图和关系矩阵，并判断其性质。[习题]集合上的”isanelement”以及”isasubset”具有什么性质？第14页，共76页，2023年，2月20日，星期三2.3关系的性质[例]正整数集合上的若干关系及其性质整除=≤＜自反性对称性传递性反自反性反对称性判定关系“＜”的反对称性的前提条件总为F,反对称性成立。第15页，共76页，2023年，2月20日，星期三2.3关系的性质从关系矩阵和关系图看关系的性质：R是自反的：MR的对角元均为1；关系图为自环图。R是对称的：MR为对称矩阵；关系图中弧成对出现。R是反自反的：MR的对角元均为0；关系图为无自环图。R是反对称的：MR为反对称矩阵；关系图中只出现单向弧。第16页，共76页，2023年，2月20日，星期三2.3关系的性质存在着既非自反也非反自反的关系，如：存在着既对称又反对称的关系，如：第17页，共76页，2023年，2月20日，星期三2.3关系的性质存在着既非对称又非反对称的关系，如：第18页，共76页，2023年，2月20日，星期三2.4集合的划分与覆盖[定义]给定集合S，A={A1,A2,…,An}，AiS，i=1..n。②若①成立且AiAj=(若ij)，则说A是S的一个划分，并称A1,A2,…,An为此划分的块。第19页，共76页，2023年，2月20日，星期三2.4集合的划分与覆盖[例]

N={0,1,2,3,4,……}自然数集合。取A0={0,6,12,18,……}A1={1,7,13,19,……}A2={2,8,14,20,……}……A5={5,11,17,23,……}则A={A0，A1，A2，A3，A4，A5}是N的一个划分。第20页，共76页，2023年，2月20日，星期三2.4集合的划分与覆盖[例]

S={a,b,c}取A={{a},{b},{c}}B={{a,b},{c}}C={{a,b,c}}均构成对S的划分。显然有|A|>|B|>|C|

可以将A称为最大划分；将C称为最小划分。第21页，共76页，2023年，2月20日，星期三关系IX

具有自反、对称和传递性；设X={1,2,3,4}，写出X上的模２同余关系，并判断其是否具有自反、对称和传递等性质。具有自反、对称和传递性的关系称为等价关系。第22页，共76页，2023年，2月20日，星期三2.5等价关系[等价关系]

集合X上的关系R若具有自反性、对称性和传递性，则称R为X上的一个等价关系。[例]

N上的模6同余关系

R={<x,y>|x,yN(xy)=6L，L为整数}自反性：对称性：传递性：第23页，共76页，2023年，2月20日，星期三2.5等价关系[定理]N上的模m同余关系是等价关系。[证明]自反性：xx=0，故xx=mL，这里L=0。对称性：设xRy

即xy=mL，L为整数则yx=mL，故yRx。传递性：设xRy

且yRz，即

xy=mL1，yz=mL2

，L1、L2

为整数则xz=mL1+mL2=m(L1+L2)

故xRz第24页，共76页，2023年，2月20日，星期三2.5等价关系[等价类]

设R为X上的一个等价关系，对任何xX，所有与x有关系R的元素的集合，称为X上由x生成的R–等价类。记为[x]R。

[x]R={y|yXxRy}[例]

X={1,2,3,4,5,6,7}，R为X上的模3同余关系。则[1]R={1,4,7}，[2]R={2,5}，[3]R={3,6}第25页，共76页，2023年，2月20日，星期三2.5等价关系[性质]设R为X上的一个等价关系，则①

X中的任何一个元素，至少属于一个等价类。②若x,yX，则x,y或属同一等价类，或属两个不同等价类但此两个不同等价类的交集为（不相交）。[证明]第26页，共76页，2023年，2月20日，星期三2.5等价关系[结论]对X上的等价关系R，①任意xX属于且只属于一个等价类；②若xRy，则[x]R=[y]R，否则

[x]R[y]R=。第27页，共76页，2023年，2月20日，星期三2.5等价关系[定理]

集合X上的一个等价关系R产生对此集合的一个划分，该划分的块对应于R的等价类。[证明]由上述结论得到。将该划分记作：X/R={[x]R|xX}第28页，共76页，2023年，2月20日，星期三2.5等价关系[定理]X上的任意划分均可确定一个等价关系。[证明]设X上的一个划分为A={A1,A2,…,An}，定义

R={<x,y>|x,yX(Ai)(AiAxAiyAi)}

可以证明R具有自反性：对称性：传递性：第29页，共76页，2023年，2月20日，星期三2.5等价关系[问题]X上由不同方法定义的等价关系R1、R2，若产生的等价类相同，则R1=R2。不等价关系也能产生划分。第30页，共76页，2023年，2月20日，星期三2.6相容关系[相容关系]

X上的二元关系R，若R是自反的、对称的，则称R为X上的一个相容关系，记作。[例]

X={2661,243,315,648,455}R={<x,y>|x,yX，x与y至少含有一个相同数字}容易看出，R具有自反性、对称性。

R不具有传递性：如<2661,243>,<243,455>R但<2661,455>R因此R不是等价关系，R是一个相容关系。第31页，共76页，2023年，2月20日，星期三2.6相容关系[相容类]

设AX，是X上的一个相容关系。称A是X上的一个相容类当且仅当A中任二元素相容。即(x)(y)(x,yA

x

y)。[最大相容类]

设A是X上的一个相容类，若X-A中不存在与A中所有元素相容的元素，则称A为X的一个最大相容类。在相容关系的关系图中，最大相容类对应于一个最大完全子图。第32页，共76页，2023年，2月20日，星期三2.6相容关系例如，在上图表示的相容关系中，最大相容类为:{a,b,d,f},{d,c,f},{d,e},{g}[问题]相容类与覆盖的关系。第33页，共76页，2023年，2月20日，星期三2.7关系的运算(1)关系的一般运算[定义]

设R、S是X到Y的二元关系，定义运算如下：

RS={<x,y>|xRyxSy}RS={<x,y>|xRyxSy}RS={<x,y>|xRyxSy}~R=XYR第34页，共76页，2023年，2月20日，星期三2.7关系的运算(2)

关系的复合运算[复合关系]

设二元关系R:XY，S:YZ，则称

S

R={<x,z>|xXzZ(y)(yYxRyySz)}

为R和S的复合关系。注意,关系的复合运算定义和函数复合保持了一致。在某些课本上，以上关系的复合记作RS。第35页，共76页，2023年，2月20日，星期三2.7关系的运算[例]

X={x1,x2,x3}，Y={y1,y2,y3,y4}，Z={z1,z2,z3}R={<x1,y1>,<x2,y3>,<x2,y4>}S={<y1,z3>,<y2,z1>,<y4,z2>}显然有：Dom(SR)Dom(R)Ran(SR)Ran(S)SR={<x1,z3>,<x2,z2>}第36页，共76页，2023年，2月20日，星期三2.7关系的运算关系的复合运算没有交换律。[定理]

关系复合运算的结合律：设二元关系

R：XY，S：YZ，P：ZW，则有(PS)R=P(SR)[证明]第37页，共76页，2023年，2月20日，星期三2.7关系的运算[定理]

关系复合运算与一般运算的结合律：设二元关系R1,R2

：XY，S1,S2：YZ，则有(S1S2)R1=(S1

R1)(S2

R1)(S1S2)R1

(S1R1)(S2R1)S1

(R1R1)=(S1R1)(S1R2)S1(R1R2)

(S1R1)(S1R2)[证明]第38页，共76页，2023年，2月20日，星期三2.7关系的运算[关系的幂运算]设R为X上的二元关系，RR…R记为Rn，规定Rn=Rn1R，R0=IX第39页，共76页，2023年，2月20日，星期三2.7关系的运算(3)关系的逆运算[逆关系]

设二元关系R：XY，定义

R-1={<y,x>|xXyY<x,y>R}为R的逆关系。[性质](R-1)-1=R，-1= (RS)-1=R-1S-1

，(RS)-1=R-1S-1

(~R)-1=~(R-1)(SR)-1=R-1S-1

R=SR-1=S-1 RSR-1S-1 第40页，共76页，2023年，2月20日，星期三2.7关系的运算[问题]设Ａ上关系R，S的关系矩阵分别为ＭR,MS,试求SR的关系矩阵。第41页，共76页，2023年，2月20日，星期三2.7关系的运算(4)关系的闭包运算[闭包]

设R为X上的二元关系，若另有一关系R，满足：①

R是自反的（对称/传递）；②

RR；③对于任何自反（对称/传递）的关系R，若

RR，则RR。则称R为R的自反（对称/传递）闭包，记为r(R)(s(R)/t(R))。第42页，共76页，2023年，2月20日，星期三2.7关系的运算[例]整数集上的“＜”关系的自反闭包是“≤”，对称闭包是“≠”，传递闭包仍然是“＜”。[例]整数“=”的自反、对称、传递闭包都是它本身。[例]有关系矩阵求Mr(R)、Ms(R)、Mt(R)第43页，共76页，2023年，2月20日，星期三2.7关系的运算第44页，共76页，2023年，2月20日，星期三2.7关系的运算[定理]设R为X上的二元关系，则①

r(R)=RIx②s(R)=RR-1[证明]③

1)Rt(R)

(t(R)表示右式无穷并）

2)

t(R)是传递的；

3)如果R’是包含R的传递关系，则对于任意n,RnR’,所以，t(R)是包含R的最小传递关系。第45页，共76页，2023年，2月20日，星期三2.7关系的运算问题：如何求传递闭包呢？设R是A上的关系，|A|=n,则

t(R)=RR1…Rn这是因为如果从x到y有道路相连，则存在长度不超过n的道路。求传递闭包的Washall算法。参阅课本。第46页，共76页，2023年，2月20日，星期三2.7关系的运算容易证明：R是自反的当且仅当r(R)=R；R是对称的当且仅当s(R)=R;R是传递的当且仅当t(R)=R.问题：设R是A上的关系r(RS)=r(R)r(S)?s(RS)=s(R)s(S)?t(RS)=t(R)t(S)?如果将并换成交呢？第47页，共76页，2023年，2月20日，星期三2.8偏序关系[偏序关系(partialorder)]

集合A上的一个关系R满足自反性、反对称性和传递性时，称R是A上的一个偏序关系，记为“”，用二元组〈A,〉表示该偏序结构，或称之为偏序集。[例]

A={2,3,6,8},“”={<x,y>|x,yA(x整除y)}

“”={……..}

容易验证，上述关系为偏序关系。第48页，共76页，2023年，2月20日，星期三2.8偏序关系x、y之间存在偏序关系时，说x、y（在该关系下）可比较，否则说x、y

不可比较。上例中，2和3不可比较（在上述定义的“”下）。[盖住]

盖住（紧邻遮盖）。设〈A,〉，x，yA，

y盖住xxyxy(z)((xzzy)(x=zy=z))

记covA={<x,y>|x,yA(y盖住x)}第49页，共76页，2023年，2月20日，星期三2.8偏序关系表达偏序关系的Hasse图设有偏序关系<A,>①用结点表示集合元素②若<x,y>covA，则用线段连接结点x,y，且令x(小者)在y的下方。第50页，共76页，2023年，2月20日，星期三2.8偏序关系Hasse图如右图①默认aa,bb,cc自反性②

ac,cb③

ab传递性acbHasseDiagram[例]集合A={a,b,c}上的偏序关系为：

{<a,a>,<b,b>,<c,c>,<a,c>,<c,b>,<a,b>}

covA＝{<a,c>,<c,b>}第51页，共76页，2023年，2月20日，星期三2.8偏序关系上述Hasse图表示的对应关系集合为：

{<a,a>,<b,b>,<c,c>,<a,c>,<c,b>,<a,b>}对应关系图如下：acbHasseDiagramacb关系图第52页，共76页，2023年，2月20日，星期三2.8偏序关系[例]由偏序关系的关系图构造相应的Hasse图cab关系图dabcHasseDiagramd第53页，共76页，2023年，2月20日，星期三2.8偏序关系[例]{2,3,6,12,24,36,17}上的整除关系的Hasse图。HasseDiagram26243612317第54页，共76页，2023年，2月20日，星期三2.8偏序关系[例]

A的幂集上的关系的Hasse图。A={a}{a}{a,b}A={a,b}{b}{a}第55页，共76页，2023年，2月20日，星期三2.8偏序关系[例]

A的幂集上的关系的Hasse图。{a,b,c}A={a,b,c}{b}{a}{c}{a,b}{a,c}{b,c}第56页，共76页，2023年，2月20日，星期三2.8偏序关系[最大最小元]

对偏序集<A,>y0A为最小元(x)(xAy0x)y0A为最大元(x)(xAxy0)[定理]

<

A,>中最大(最小)元若存在则唯一。[证明][极大极小元]

对<

A,>y0A为极小元(x)(xAxy0¬(x

y0))y0A为极大元(x)(xAxy0¬(y0x))第57页，共76页，2023年，2月20日，星期三2.8偏序关系[例]{2,3,6,12,24,36}上的整除关系的Hasse图。2624361232,3为极小元24,36为极大元没有最小元和最大元第58页，共76页，2023年，2月20日，星期三2.8偏序关系[例]

A的幂集上的关系的Hasse图。{a,b,c}A={a,b,c}{b}{a}{c}{a,b}{a,c}{b,c}

为最小元{a,b,c}为最大元第59页，共76页，2023年，2月20日，星期三2.8偏序关系[上下界]

对<

A,>,BA,aA

a是B的一个上界(x)(xBx

a)

a是B的一个下界(x)(xBax)说明：a不一定是B的元素，即可能aA-BB的上(下)界不一定存在，存在也不一定唯一。第60页，共76页，2023年，2月20日，星期三2.8偏序关系[例]{2,3,6,12,24,36}上的整除关系的Hasse图。262436123令B1={2,3,6}B1的上界是6,12,24,366B1，而12,24,36B1

B1没有下界令B2={2,6,12,24}

B2的上界是24，下界是2第61页，共76页，2023年，2月20日，星期三2.8偏序关系[上确界]

对<A,>,BA,aA是B的一个上界。

a是B的上确界(y)(y是B的上界a

y)上确界若存在则唯一。[下确界]

对<A,>,BA,bA是B的一个下界。

b是B的下确界(x)(x是B的下界xb)下确界若存在则唯一。第62页，共76页，2023年，2月20日，星期三2.8偏序关系[例]{2,3,6,12,24,36}上的整除关系的Hasse图。262436123令B1={2,3,6}B1的上界是6,12,24,36

B1的上确界是6

B1没有下界也没有下确界令B2={2,6,12,24}

B2的上界和上确界是24

B2的下界和下确界是2第63页，共76页，2023年，2月20日，星期三2.8偏序关系[链与反链]

对<A,>,BA,若B中任两个元素之间都是可比较的，则称B是A中的一条链。若B中任两个元素之间都是不可比较的，则称B是A中的一条反链。262436123[例]右边所示Hasse图中，

{2,6,12,24}是一条链{2,3}和{24,36}是反链注意：{2,3,24,36}并非反链第64页，共76页，2023年，2月20日，星期三2.9其他序关系(1)全序关系[全序关系]

设偏序集<A,>，若A是一条链，则称“”为A上的一个全序关系，此时称<A,>是一个全序集合。(2)偏序关系的逆关系[定义]设偏序集<A,>，定义A上的关系“”

xyx,yAyx

集合A和关系“”仍然构成一个偏序集<A,>。第65页，共76页，2023年，2月20日，星期三2.9其他序关系[拓扑排序]

一个偏序集可以表示一个工程中各个任务之间的依赖关系。如果一个时刻只能进行一个任务，那么整个工程的流程是一个与原偏序协调的全序。找出这个全序的过程称为拓扑排序。[定义]设有偏序集<A,>,如果存在一个全序*使得xy蕴含x*y,则称*是A上的一个拓扑排序。[拓扑排序算法][问题]是否每个偏序集都存在拓扑排序？第66页，共76页，2023年，2月20日，星期三2.9其他序关系(3)拟序关系（strictpartialorder）[拟序关系]

集合A上的关系R满足反自反性和传递性时，称为A上的一个拟序关系，用二元组<A,<>表示该结构。[定理]若R为A上的偏序关系，则R-IA为A上的拟序关系。若R为A上的拟序关系，则RIA为A上的偏序关系。第67页，共76页，2023年，2月20日，星期三2.9其他序关系[定理]设有拟序集<A,<>，对任何x,y,zA,①

x<y,x=y,y<x

中至多有一种情况成立(三分律)；②

xyx

则x=y，这里xy

表示x<y

或x=y。[证明]利用拟序集的反自反性和传递性。第68页，共76页，2023年，2月20日，星期三2.9其他序关系(4)词典次序设字母表为X，“”为X上的自然次序。显然

<X,>为全序集合。①长度为2的词库A=XX在A上定义全序关系S：

<x1,y1>S<x2,y2>(x1<x2)(x1=x2y1y2)

第69页，共76页，2023年，2月20日，星期三2.9其他序关系②长度不大于n的词库A=XX2…..X