离散数学：第4讲 关系的表示

2026/9/71复习序偶(有序二元组)笛卡尔积二元关系一些特殊关系2026/9/72序偶(orderedpair)序偶:两个具有固定次序的客体组成一个序偶

<a,b>={{a},{a,b}}

其中,a是第一元素,b是第二元素.<a,b>也记作(a,b)2026/9/73笛卡尔积(Cartesianproduct)笛卡尔积:令A和B是任意两个集合,若序偶的第一个成员是A中的元素,第二个成员是B中的元素,所有这些序偶组成的集合称为集合A和B的笛卡尔积或卡氏积,记作A

B。

A

B={<x,y>|x

A

y

B}.2026/9/74本节内容二元关系关系的表示关系的集合运算复合关系和逆关系2026/9/75二元关系(binaryrelation)二元关系(简称关系)：序偶的任一集合确定了一个二元关系R，R中任一序偶<x,y>可记作<x,y>∈R或xRy;不在R中的任一序偶<x,y>可记作<x,y>

R或xRy/2026/9/76二元关系的记号设R是二元关系,则<x,y>Rx与y具有R关系xRy对比:xRy(中缀(infix)记号)R(x,y)(前缀(prefix)记号)

<x,y>R(后缀(suffix)记号)例如:2<15<(2,15)<2,15><.2026/9/77定义域,值域,域对任意关系R,可以定义:定义域(domain)(前域):domR={x|

y(xRy)}值域(range):ranR={y|x(xRy)}域(field):fldR=domR

ranR2026/9/78定义域,值域,域(举例)例4:R1={},R2={<c,d>,<e,f>},R3={<1,2>,<3,4>,<5,6>}.domR1=

,ranR1=

,fldR1=

domR2={c,e},ranR2={d,f},fldR2={c,d,e,f}domR3={1,3,5},ranR3={2,4,6},fldR3={1,2,3,4,5,6}.#2026/9/79讨论由上我们可看出:设domR=A，ranR=B，则R

A

B

关系由序偶定义的，因此与笛卡尔积有关.结论:关系是两集合笛卡尔积的子集.2026/9/710A到B的二元关系A到B的二元关系:是A

B的任意子集.R是A到B的二元关系

R

A

B

R

P(A

B)当A=B时,则叫做A上的二元关系。

2026/9/711A到B的二元关系的个数Problem:若|A|=m,|B|=n,则A到B的二元关系有多少个?|AB|=mn,故|P(AB)|=2mn即A到B不同的二元关系共有2mn个!2026/9/712A到B的二元关系(举例)例5:设A={a1,a2},B={b},

则A到B的二元关系共有4个:R1=,R2={<a1,b>},R3={<a2,b>},R4={<a1,b>,<a2,b>}.B到A的二元关系也有4个:R5=,R6={<b,a1>},R7={<b,a2>},R8={<b,a1>,<b,a2>}.#2026/9/713A上的二元关系例6:设B={b},

则B上的二元关系共有2个:R1=,R2={<b,b>}.#例7:设A={a1,a2},

则A上的二元关系共有16个.#例8:设C={a,b,c},

则C上的2元关系共有29=512个!#2026/9/714一些特殊关系空关系恒等关系全域关系整除关系小于等于关系,…包含关系,真包含关系2026/9/715特殊关系设A是任意集合,则可以定义A上的:空关系:

恒等关系:IA={<x,x>|xA}全域关系:EA=AA={<x,y>|xAyA}2026/9/716特殊关系(续)设AZ,则可以定义A上的:整除关系:DA={<x,y>|xAyAx|y}例:A={1,2,3,4,5},则DA={<1,1>,<1,2>,<1,3>,<1,4>,<1,5>,<2,2>,<2,4>,<3,3>,<4,4>,<5,5>}.#2026/9/717特殊关系(续)设AR,则可以定义A上的:小于等于(lessthanorequalto)关系:LEA={<x,y>|xAyAxy}小于(lessthan)关系,LA={<x,y>|xAyAx<y}大于等于(greaterthanorequalto)关系大于(greatthan)关系,…2026/9/718特殊关系(续)设A为任意集合,则可以定义P(A)上的:包含关系:

A={<x,y>|xAyAxy}真包含关系:

A={<x,y>|xAyAxy}2026/9/719100米跳高铅球足球跨栏张三√√李四√√王五√赵六√关系的表示——表格用字母数字来代替这些元素

Ａ＝｛ａ,ｂ,ｃ,ｄ｝

Ｂ＝｛１,２,３,４,５｝2026/9/720关系矩阵(matrix)设A={a1,a2,…,an},RAA,则R的关系矩阵M(R)=(rij)nn,其中例如,A={a,b,c},R1={<a,a>,<a,b>,<b,a>,<b,c>},R2={<a,b>,<a,c>,<b,c>},2026/9/721整除关系矩阵表示例:A={1,2,3,4,5},则DA={<1,1>,<1,2>,<1,3>,<1,4>,<1,5>,<2,2>,<2,4>,<3,3>,<4,4>,<5,5>}.#2026/9/722全域关系2026/9/723恒等关系2026/9/724abcd12345关系的表示——图示法R={<a,3>,<a,4>,<b,1>,<b,2>,<c,5>,<d,1>,}2026/9/725关系的表示——图示法设A＝{1,2,3,4},A上的关系H＝{<1,1>,<1,2>,<1,4>,<2,4>,<3,4>}12342026/9/726关系图(graph)设A={a1,a2,…,an},R

A

A,则A中元素以"◦”表示(称为顶点),R中元素以"

”表示(称为有向边);若xiRxj,则从顶点xi向顶点xj引有向边<xi,xj>,这样得到的图称为R的关系图G(R).例如,A={a,b,c},R1={<a,a>,<a,b>,<b,a>,<b,c>},R2={<a,b>,<a,c>,<b,c>},则abcabcG(R1)G(R2)2026/9/727二元关系的集合运算

CombiningRelations二元关系是集合,集合存在并,交,差和对称差的运算。故二元关系也存在这样的运算。

2026/9/728定理若R和S是从集合X到Y的两个关系,则R、S的并、交、补、差仍是X到Y的关系.2026/9/729关系的集合运算设R1和R2是Ａ到Ｂ的二元关系,则R1∪R2＝｛<ａ,ｂ>｜<ａ,ｂ>∈R1或<ａ,ｂ>∈R2｝R1∩R2＝｛<ａ,ｂ>｜<ａ,ｂ>∈R1且<ａ,ｂ>∈R2｝R1-R2＝｛<ａ,ｂ>｜<ａ,ｂ>∈R1但<ａ,ｂ>

R2｝~R1＝｛<ａ,ｂ>｜<ａ,ｂ>∈A

B,但<ａ,ｂ>

R1｝

通常记为R1

R2＝｛<ａ,ｂ>｜<ａ,ｂ>∈R1∪R2但<ａ,ｂ>

R1∩R2｝2026/9/730举例设A＝｛1,2,3,4｝，Z为整数集R＝｛<a,b>｜a，b∈A，(a-b)/2∈Z｝S＝｛<a,b>｜a，b∈A，(a-b)/3∈Z，a－b＞０｝求:R∪S，R∩S，

，R－S，S－R，S

R2026/9/731举例（续)解:R与S都是Ａ上的二元关系R＝｛<１，１>，<２，２>，<３，３>，<４，４>，<１，３>，<３，１>，<２，４>，<４，２>｝S＝｛<４，１>｝R∪S＝｛<１，１>，<２，２>，<３，３>，<４，４>，<１，３>，<３，１>，<２，４>，<４，２>，<４，１>｝2026/9/732举例（续)R∩S＝Φ

＝｛<１,２>,<２,１>,<１,４>,<４,１>,<２,３>,<３,２>,<３,４>,<４,３>｝R-S=R,S-R=S,S

R=R∪S2026/9/733设:Ａ＝｛ａ1，ａ2，…，ａn｝

Ｂ＝｛ｂ1，ｂ2，…，ｂm｝

Ｒ1＝（ｃij)

Ｒ2＝（ｄij)利用矩阵表示进行运算二元关系的矩阵运算:相关矩阵可表示二元关系，可用矩阵的逻辑运算来研究二元关系的运算。

2026/9/734其中:

逻辑加(∨):０∨０＝０，０∨１＝１，

１∨０＝１，１∨１＝１

逻辑乘(∧):０∧０＝０，

０∧１＝０，

１∧０＝０，

１∧１＝１2026/9/735则用矩阵的逻辑运算:2026/9/7362026/9/737逆,复合(合成)对任意集合F,G,可以定义:逆(inverse):F-1={<x,y>|yFx}右复合(composite):F◦G={<x,y>|z(xFzzGy)}xzyFG2026/9/738逆关系的性质Rc

的关系矩阵是R的转置矩阵Rc

的关系图是R的关系图中弧方向取反2026/9/739定理1定理1:设F是任意关系,则(1)domF-1=ranF;(2)ranF-1=domF;(3)(F-1)-1=F.2026/9/740定理1(证明(1))(1)domF-1=ranF;证明:(1)x,xdomF-1y(xF-1y)y(yFx)xranF

domF-1=ranF.(2)可类似证明.2026/9/741定理1(证明(3))(3)(F-1)-1

=F.证明:(1)<x,y>,<x,y>(F-1)-1x(F-1)-1yyF-1xxFy.这时

(F-1)-1=F.#2026/9/742逆关系满足性质定理:设

R、R1和R2都是从A到B的二元关系，则下列各式成立.

a)(R1∪R2)-1＝R1-1∪R2-1

b)(R1∩R2)-1＝R1-1∩R2-1

c)(A×B)-1＝B×A

d)(R)-1＝R-1这里R＝A×B-R

e)(R1-R2)-1＝R1-1-R2-1____2026/9/743关于复合顺序复合(右复合):F◦G={<x,y>|z(xFzzGy)}逆序复合(左复合):F◦G={<x,y>|z(xGzzFy)}2026/9/744则:Ｒ1＝｛<ａ1，ｂ1>，<ａ1，ｂ3>，<ａ2，ｂ2>，<ａ2，ｂ4>，<ａ3，ｂ3>，<ａ3，ｂ4>,<ａ4，ｂ1>，<ａ4，ｂ4>｝

是选双学位专业的二元关系。

举例Ａ＝｛a1,a2,a3,a4｝是学生集合Ｂ＝｛b1,b2,b3,b4

｝是专业集合C＝{c1,c2,c3,c4

｝

是课程集合

2026/9/745Ｒ2＝｛<b1,ｃ3>,<b1,ｃ4>,<b2,ｃ2>,<b2,ｃ3>,<b2,ｃ4>,<b3,ｃ1>,<b3,ｃ2>,<b4,ｃ2>,<b4,ｃ4>｝

是各专业本学期必修课的二元关系。

Ｒ3＝Ｒ1·Ｒ2＝｛<ａ1,ｃ1>,<ａ1,ｃ2>,<ａ1,ｃ3>,<ａ1,ｃ4>,<ａ2,ｃ2>,<ａ2,ｃ3>,<ａ2,ｃ4>,<ａ3,ｃ1>,<ａ3,ｃ2>,<ａ3,ｃ4>,<ａ4,ｃ2>,<ａ4,ｃ3>,<ａ4,ｃ4>｝

是选双学位学生本学期必修课的二元关系举例（续)2026/9/746复合关系的其他求法用矩阵相乘求复合关系用关系图求复合关系2026/9/747用矩阵相乘求复合关系R为集合X＝{x1,……,xm}到Y={y1,……,yn}上的关系,MR=[uij]m×n表示R的关系矩阵S为集合Y＝{y1,……,yn}到Z={z1,……,zl}上的关系,MS=[vjk]n×lMR◦S=

MRMS=[Wik]

其中Wik=∨j=1n(uij∧vjk)

2026/9/748

在行处标上姓名,列处标上课程,就知谁该必修哪些课了。

矩阵乘积举例2026/9/749用关系图求复合关系R◦S={<x,y>|z(xRzzSy)}xzyRS2026/9/750关系图求复合举例a1R1a2a3a4b1b2b3b4c1c2c3c4R2a1a2a3a4c1c2c3c4R1◦R22026/9/751复合关系的性质无交换律:R◦S≠S◦R有结合律:(R◦S)◦P=R◦(S◦P)2026/9/752定理2定理2(1):设R1,R2,R3为二元关系,则(R1◦R2)◦R3=R1◦(R2◦R3)证明:<x,y>,<x,y>(R1◦R2)◦R3

z(x(R1◦R2)zzR3y)

z(t(xR1t

tR2z)zR3y))

zt(xR1t

tR2zzR3y)

tz(xR1t

tR2zzR3y)2026/9/753定理2(续)证明(续):

tz(xR1t

tR2zzR3y)

t(xR1t

z(tR2zzR3y)

t(xR1t

t(R2◦R3)y)

xR1◦(R2◦R3)t

<x,y>R1◦(R2◦R3)

(R1◦R2)◦R3=R1◦(R2◦R3).#说明:定理2说明复合运算具有结合律.xtzyR1R2R32026/9/754定理2(续)定理2（2):设F,G为二元关系,则(F◦G)-1=G-1◦F-1.FF-1GG-12026/9/755定理2(2)(证明)(F◦G)-1=G-1◦F-1证明:<x,y>,<x,y>(F◦G)-1<y,x>(F◦G)z(yFzzGx)z(zF-1yxG-1z)z(xG-1zzF-1y)<x,y>G-1◦F-1.#xyz2026/9/756复合关系的性质(续)定理4:设R1,R2,R3是集合,则(1)R1◦(R2

R3)=(R1◦R2)(R1◦R3)(2)(R1

R2)◦R3=(R1◦R3)(R2◦R3)(3)R1◦(R2

R3)

(R1◦R2)(R1◦R3)(4)(R1

R2)◦R3

(R1◦R3)(R2◦R3)2026/9/757定理4(证明(1))(1)R1◦(R2

R3)=(R1◦R2)

(R1◦R3)证明:

<x,y>,<x,y>

R1◦(R2

R3)

z(x(R1)z

z(R2

R3)y)

z(xR1z

(zR2y

zR3y))

z((xR1z

zR2y)

(xR1z

zR3y))

z(xR1z

zR2y)

z(xR1z

zR3y)（对可分配)

x(R1◦R2)y

x(R1