离散数学及其应用-04 二元关系

第四章二元关系4.1序偶与笛卡儿积4.2关系及表示4.3关系的运算4.4关系的性质4.5关系的闭包4.6等价关系和划分4.7序关系定义4.1.1(有序对(或序偶)，orderedpairs)由两个元素x和y(允许x=y)按一定次序排列组成的二元组<x，y>称为一个有序对或序偶，其中x是它的第一元素，y是它的第二元素。注意，第一、二元素未必不同。如平面直角坐标系中的任意一点坐标(x，y)均是序偶，而全体这种实数对的集合{(x，y)|x∈R∧y∈R}就表示整个平面。

4.1.1序偶有序对<x，y>具有以下性质：(1)当x≠y

时，<x，y>≠<y，x>。(2)<x，y>=<u，v>的充要条件是x=u

且y=v。(3)<x，x>也是序偶。

4.1.1序偶定义4.1.2

(n元有序组)若n∈N且n＞1，x1，x2，…，xn

是n

个元素，则n元组<x1，x2，…，xn>定义为：

当n=2时，二元组是有序对<x1，x2>；

当n≠2时，<x1，x2，…，xn>=<<x1，x2，…，xn-1>，xn>。本质上，n元有序组依然是序偶。n元有序组有如下性质：

<x1，x2，…，xi,

…，xn>=<y1，y2，…，yi，…，yn>的充要条件是x1=y1，x2=y2，…，xi=yi，…，xn=yn。4.1.1序偶定义4.1.3

设A，B为集合，用A中元素为第一元素，B中元素为第二元素构成有序对。所有这样的有序对组成的集合称为集合A和B的笛卡儿积(cartesianproduct)，又称作直积，记作A×B。A和B

的笛卡儿积的符号化表示为A×B={<x，y>|x∈A∧y∈B}

4.1.2笛卡儿积定义4.1.4

(n阶笛卡儿积(cartesianproduct))若n∈N，且n＞1，A1，A2，…，An是n个集合，它们的n阶笛卡儿积记作A1×A2×…×An

，并定义为:

A1×A2×…×An={<x1，x2，…，xn>|x1∈A1∧x2∈A2∧…∧xn∈An}

当A1=A2=…=An=A时，A1×A2×…×An简记为An。4.1.2笛卡儿积【例4.1.1】设A={a,b,c},B={1,2},求A×B、B×A、A2、B2

的笛卡儿积。解A×B={<a,1>,<b,1>,<c,1>,<a,2>,<b,2>,<c,2>}B×A={<1,a>,<1,b>,<1,c>,<2,a>,<2,b>,<2,c>}A2={<a,a>,<a,b>,<a,c>,<b,a>,<b,b>,<b,c>,<c,a>,<c,b>,<c,c>}B2={<1,1>,<1,2>,<2,1>,<2,2>}显然A×B与B×A所含元素的个数相同(A,B是有限集合),但A×B≠B×A。4.1.2笛卡儿积注意：A×B与B×A所含元素的个数相同(A，B是有限集合)，但A×B≠B×A。

4.1.2笛卡儿积【例4.1.2】

设A={1，2}，求P(A)×A解:P(A)×A

={φ,{1},{2},{1,2}}×{1,2}

={<φ,1>,<φ,2>,<{1},1>,<{1},2>,<{2},1>,

<{2},2>,<{1,2},1>,<{1,2},2>}4.1.2笛卡儿积定理4.1.1

若A，B是有穷集合，则有

|A×B|=|A|·|B|(·为数乘运算)

4.1.2笛卡儿积定理4.1.2

对任意有限集合A1，A2，…，An，有

|A1×A2×…×An|＝|A1|·|A2|·…·|An|(·为数乘运算)

4.1.2笛卡儿积定理4.1.3

(笛卡儿积与∪，∩，～运算的性质)对任意的集合A，B

和C，有(1)A×(B∪C)=(A×B)∪(A×C)

(2)A×(B∩C)=(A×B)∩(A×C)

(3)(B∪C)×A=(B×A)∪(C×A)

(4)(B∩C)×A=(B×A)∩(C×A)

(5)A×(B-C)＝(A×B)-(A×C)

(6)(B-C)×A＝(B×A)-(C×A)

4.1.2笛卡儿积定理4.1.4

(笛卡儿积与运算的性质1)对任意的集合A、B和C，若C≠φ，则(A⊆B)<=>(A×C⊆B×C)<=>(C×A⊆C×B)

4.1.2笛卡儿积定理5(笛卡儿积与⊆运算的性质2)对任意的集合A、B、C和D，有(A×B⊆C×D)<=>(A⊆C∧B⊆D)

4.1.2笛卡儿积定理4.16

对任意非空集合A、B，有(A×B)⊆P(P(A∪B))

4.1.2笛卡儿积【例4.1.3】设A，B，C，D为任意集合，判断以下命题是否为真，并说明理由。

（1）A×B=

A×C=>B=C

（2）A-（B×C）=

（A-B）×（A-C）

（3）A=B∧C=D=>A×C=B×D

（4）存在集合A，使得A⊆

A×A4.1.2笛卡儿积解：（1）不一定为真，当A＝φ，B＝{1}，C＝{2}时有A×B=C×D，但B≠C（2）不一定为真、当A＝B＝{1}，C＝{2}时有A-(B×C)={1}-{<1,2>}={1},(A-B)×(A-C)=φ×{1}=φ（3）为真、由等量代入的原理可证（4）为真．当A＝φ时有A⊆

A×A成立

4.1.2笛卡儿积定义4.2.1

任何序偶的集合，确定了一个二元关系，并称该集合为一个二元关系，记作R

。二元关系也简称关系。对于二元关系R，如果<x，y>∈R，也可记作xRy。注意：定义并不要求R中的元素<x，y>中的x，y取自哪个个体域。因此，R={<2，a>，<u，狗>，<钱币，思想>}也是一个二元关系。4.2.1关系的基本概念定义4.2.2

R称为集合A1，A2，…，An-1到An上的n元关系(n-arrayrelations)，如果R是A1×A2×…×An-1×An的一个子集。当A1＝A2＝…＝An-1＝An时，也称R为A上的n元关系。当n=2时，称R为A1到A2的二元关系。n元关系也可视为A1×A2×…×An-1到An的二元关系。当A，B均是有限集合时，因为|A×B|=|A|·|B|，而其子集的个数恰是幂集P(A×B)的元素个数，P(A×B)|=2|A|·|B|，所以由A到B共有2|A|·|B|个不同的二元关系。

4.2.1关系的基本概念特殊的二元关系设R是A到B的二元关系：φ⊆

A×B，称φ为A到B的空关系。A×B⊆A×B

，称A×B

为A到B的全域关系。IA={<x，x>|x∈A}，称为A上的恒等关系。

4.2.2几种特殊的关系几种常见的二元关系：若A是实数集合或其子集，R是A上的二元关系，可定义下面：

若R={<x，y>|x∈A∧y∈B∧x≤y}，则称R为小于等于关系，常记为≤。若R={<x，y>|x∈A∧y∈B∧x|y}，则称R为整除关系，常记为|，其中x|y表示x整除y。若A是任意集合，R是A上的二元关系，下面的关系也常见：若R={<x，y>|x∈P(A)∧y∈P(A)∧x⊆y}，则称R为包含关系，常记为⊆。若R={<x，y>|x∈P(A)∧y∈P(A)∧x⊂y}，则称R为真包含关系，常记为⊂。

4.2.2几种特殊的关系定义4.2.3

设R是A到B的二元关系。(1)用xRy表示<x，y>∈R，意为x，y有R关系(为使可读性好，我们将分场合使用这两种表达方式中的某一种)。xRy表示<x，y>∈R。(2)由<x,y>∈R的所有x组成的集合称为关系R的定义域(domain),记作DomR，即

DomR={x|x∈A∧∃y(y∈B∧<x，y>∈R)}

4.2.2几种特殊的关系(3)由<x，y>∈R的所有y组成的集合称为关系R的值域(range)，记作RanR，即

RanR＝{y|y∈B∧∃x(x∈A∧<x，y>∈R)}(4)R的定义域和值域的并集称为R的域，记作FldR。形式化表示为：

FldR=DomR∪RanR一般地，若R是A到B的二元关系，则有DomR⊆A，RanR⊆B。

4.2.2几种特殊的关系【例4.2.1】

A={a1,a2,a3,a4,a5,a6},B={b1,b2,b3,b4,b5},则R={<a3,b1>,<a3,b2>,<a4,b4>,<a6,b4>,<a6,b5>},求DomR,RanR,FldR。

那么如图4-2-1所示:DomR={a3,a4,a6},RanR={b1,b2,b4,b5}FldR={a3,a4,a6,b1,b2,b4,b5}各箭头分别表示a3Rb1,a3Rb2,a4Rb4,a6Rb4,a6Rb5。

4.2.2几种特殊的关系4.2.2几种特殊的关系定义4.2.4

设集合A={x1，x2，…，xm}到B={y1，y2，…，ym}上的一个二元关系为R，以集合A、B中的元素为顶点，在图中用“。”表示顶点。若xiRyj，则可自顶点xi向顶点yj引有向边<xi，yj>，其箭头指向yj。用这种方法画出的图称为关系图(graphofrelation)。如图4.2.1就表示了例4.2.1中的关系R。如关系R是定义在一个集合A上，即R⊆A×A，只需要画出集合A中的每个元素即可。起点和终点重合的有向边称为环(loop)。

4.2.3关系图法【例4.2.2】

求集合A={a,b,c,d}上的恒等关系、空关系、全关系的关系图。

4.2.3关系图法定义4.2.5

设R⊆A×B，A={a1，a2，…，am}，B=

{b1，b2，…，bn}，那么R的关系矩阵MR为一m×n矩阵，它的第i，j分量rij只取值0或1，而4.2.4关系矩阵1rij=当且仅当aiRbj

当且仅当aiRbj

0-例如，图4.2.1所示关系R的关系矩阵为4.2.4关系矩阵例4.2.2中的图4.2.2、图4.2.3、图4.2.4、图4.2.5所示关系的关系矩阵分别是

4.2.4关系矩阵关系R的集合表达式与R的关系矩阵也可以唯一相互确定，因此R的集合表达式、关系图、关系矩阵三者均可以唯一相互确定，并且它们各有各的特点，可以根据不同的需要选用不同的表达方式。4.2.4关系矩阵定义4.3.1

设R和S为A到B的二元关系，其并、交、差、补运算定义如下：

R∪S＝{<x，y>|xRy∨xSy}

R∩S＝{<x，y>|xRy∧xSy}

R-S＝{<x，y>|xRy∧┐xSy}

～R＝A×B-R＝{<x，y>|┐xRy}4.3.1关系的基本运算【例4.3.1】

设A={a,b,c,d},A上的关系R和S定义如下:R={<a,b>,<b,d>,<c,c>},S={<a,c>,<b,d>,<d,b>},求R∪S,R∩S,R-S,~R,R⊕S。解：R∪S={<a,b>,<a,c>,<b,d>,<c,c>,<d,b>}R∩S={<b,d>}R-S={<a,b>,<c,c>}~R=A×A-R={<a,a>,<a,b>,<a,c>,<a,d>,<b,a>,<b,b>,<b,c>,<c,a>,<c,b>,<c,d>,<d,a>,<d,b>,<d,c>,<d,d>}R⊕S=(R∪S)-(R∩S)=={<a,b>,<a,c>,<c,c>,<d,b>}

4.3.1关系的基本运算一个n元集合上，可有多少个不同的二元关系？因为|A|=n，|A×A|=n2，|P(A×A)|=2n2，所以共有2n2个不同的二元关系。推广：若|A|=n，|B|=m，则A到B有2mn个不同的二元关系。

4.3.1关系的基本运算关系并、交、差、补的矩阵可用如下方法求取：MR∪S=MR∨MS(矩阵对应分量作逻辑析取运算)MR∩S=MR∧MS(矩阵对应分量作逻辑合取运算)MR-S=MR∩～S=MR∧M～S

M～S=～(MS)(矩阵各分量作逻辑非运算)由于关系是序偶的集合，所以它不同于一般的集合。除了可以进行集合的一般运算，还有自身所特有的一些运算，它们更为重要。4.3.1关系的基本运算定义4.3.2

设R是A到B的关系，R的逆关系或逆(converse)是B到A的关系，记为R-1，规定为R-1={<y，x>|x∈A，y∈B，xRy}由定义很显然，对任意x∈A，y∈B，有xRy<=>yR-1x若MR为R的关系矩阵，那么MR-1＝MR′(M′表示矩阵M的转置矩阵)4.3.2关系的逆运算【例4.3.2】

设A={1,2,3,4},B={a,b,c,d},R是从A到B的一个关系,且R={<1,a>,<1,b>,<1,c>,<2,a>,<4,a>},计算R-1。解R-1={<a,1>,<b,1>,<c,1>,<a,2>,<a,4>}4.3.2关系的逆运算定理4.3.1

设R和S都是A到B上的二元关系，那么

(1)(R-1)-1=R

(2)(～R)-1=～(R-1)(A×B为全关系)

(3)(R∩S)-1=R-1∩S-1，(R∪S)-1=R-1∪S-1，(R-S)-1=R-1-S-1(4)R⊆S

当且仅当R-1⊆

S-1

(5)Dom(R-1)=Ran(R)

(6)Ran(R-1)=Dom(R)

(7)φ-1=φ

(8)(A×B)-1=B×A4.3.2关系的逆运算定义4.3.3

设R为A到B的二元关系，S为B到C的二元关系，那么R○S为A到C的二元关系，称为关系R与S的复合(compositions)，定义为

R○

S={<x，z>|x∈A∧z∈C∧∃y(y∈B∧xRy∧ySz)}

这里“○”称为复合运算。R○R也记为R2。4.3.3关系的复合运算【例4.3.3】

设R表示父子关系，即<x，y>∈R说明x是y的父亲，R○

R就表示祖孙关系。

4.3.3关系的复合运算【例4.3.4】设R表示朋友关系，S表示直接后门关系，R○

S就表示间接后门关系。

4.3.3关系的复合运算【例4.3.5】设A={a,b,c,d},A上的关系R和S分别为R={<b,b>,<b,c>,<c,a>},S={<b,a>,<c,a>,<c,d>,<d,c>},计算R○S,S○R,R○R,S○S,(R○S)○R,S○(R○R)解：R○S={<b,a>,<b,d>}S○R={<d,a>}R○R={<b,b>,<b,c>,<b,a>}S○S={<c,c>,<d,a>,<d,d>}(R○S)○R=⌀S○(R○R)=⌀

4.3.3关系的复合运算【例4.3.6】

设集合A＝{0，1，2，3，4}，R，S均为A上的二元关系，且R＝{<x，y>|x+y＝4}＝{<0，4>，<4，0>，<1，3>，<3，1>，<2，2>}，S＝{<x，y>|y-x＝1}＝{<0，1>，<1，2>，<2，3>，<3，4>}求R○

S，S○

R，R○

R，S○

S，(R○

S)○

R，R○(S○

R)。解：R

○

S＝{<4，1>，<1，4>，<3，2>，<2，3>}＝{<x，z>|x+z＝5}S

○

R＝{<0，3>，<1，2>，<2，1>，<3，0>}＝{<x，z>|x+z＝3}R

○

R＝{<0，0>，<4，4>，<1，1>，<3，3>，<2，2>}

＝{<x，z>|x-z＝0}S

○

S＝{<0，2>，<1，3>，<2，4>}＝{<x，z>|z-x＝2}(R

○

S)

○

R

＝{<4，3>，<1，0>，<3，2>，<2，1>}R

○(S

○

R)＝{<4，3>，<3，2>，<2，1>，<1，0>}从上例已可看出，一般地R

○

S≠S

○

R。

4.3.3关系的复合运算定理4.3.2设IA，IB为集合A，B上的恒等关系，R⊆A×B，那么

(1)IA○

R=R○IB=R

(2)φ○R=R○φ=φ

4.3.3关系的复合运算定理4.3.3

设R，S，T均为A上二元关系，那么

(1)R○(S∪T)=(R○

S)∪(R○

T)

(2)(S∪T)○

R=(S○

R)∪(T○

R)

(3)R○(S∩T)⊆(R○

S)∩(R○

T)

(4)(S∩T)○

R⊆(S○

R)∩(T○

R)

(5)R○(S○

T)=(R○

S)○

T

(6)(R○

S)-1=S-1○

R-14.3.3关系的复合运算复合运算的关系矩阵设A是有限集合，|A|=n。关系R和S都是A上的关系，R和S的关系矩阵MR=［rij］和MS=［sij］都是n×n

的方阵。R与S的复合R

○

S的关系矩阵可以用下述的矩阵逻辑乘计算(类似于矩阵乘法)得到，记作MR

○

S=MR·MS＝［tij］n×n，其各分量tij可采用下式求取：

ntij=

∨rikskj(i=1,2,…，n;j=1,2,…,n)

K=1n这里，∨f(k)=f(1)∨f(2)∨…∨f(n)。∨为真值析取运算。 K=1nn·乘与普通矩阵乘的不同在于，各分量计算中用∨代替Σ。

K=1K=1

4.3.3关系的复合运算【例4.3.6】

设集合A＝{0，1，2，3，4}，R，S均为A上的二元关系，且R＝{<x，y>|x+y＝4}＝{<0，4>，<4，0>，<1，3>，<3，1>，<2，2>}，S＝{<x，y>|y-x＝1}＝{<0，1>，<1，2>，<2，3>，<3，4>}求R○

S解：4.3.3关系的复合运算定义4.3.4

设R是A上的关系，n个R的复合称为R的n次幂。

由于关系复合运算有结合律，因此用“幂”表示集合上关系对自身的复合是适当的，Rn=R○

…○R，规定R0＝IA(R为A上二元关系)。Rn满足下列性质。4.3.4关系的幂运算定理4.3.4

设R为A上二元关系，m，n为自然数，那么

(1)Rn+1=Rn○R=R○

Rn=Rm○

Rn-m+1

(2)Rm○

Rn＝Rm+n

(3)(Rm)n＝Rmn

(4)(R-1)n=(Rn)-1

4.3.4关系的幂运算【例4.3.7】设A={0，1，2，3，4}，R={<0，0>，

<0，1>，<1，3>，<2，4>，<3，1>，<4，4>}，求R2，R3，R4。解：R2={<0，0>，<0，1>，<0，3>，<1，1>，<2，4>，<3，3>，<4，4>}R3={<0，0>，<0，1>，<0，3>，<1，3>，<2，4>，<3，1>，<4，4>}R4={<0，0>，<0，1>，<0，3>，<1，1>，<2，4>，<3，3>，<4，4>}=R24.3.4关系的幂运算R、R2、R3、R4的关系图如图4.3.2所示。R、R2、R3、R4所对应的关系矩阵为：4.3.4关系的幂运算4.3.4关系的幂运算定理4.3.5

设集合A的基数为n，R是A上二元关系，那么存在自然数i、

j使得Ri＝Rj

(0≤i＜j≤2n2)证明：当|A|=n时，A上不同二元关系共计2n2个，令K=2n2，因此，在R0，R1，R2，…，RK。这K+1个关系中，至少有两个是相同的(鸽巢原理)，即有i，j(0≤i＜j≤2n2)，使Ri＝Rj

。

4.3.4关系的幂运算定义4.3.5

设R为X到Y的二元关系，A⊆X，则A在R下的像R［A］为集合R［A］={y|(∃x)(x∈A∧<x，y>∈R)}

4.3.4关系的幂运算定理4.3.6R是X到Y的关系和集合A、B，A⊆X，B⊆X，则

(1)R［A∪B］=R［A］∪R［B］

(2)R［∪A］=∪{R［B］|B∈A}

(3)R［A∩B］⊆

R［A］∩R［B］

(4)R［∩A］⊆∩{R［B］|B∈A}(A≠φ)

(5)R［A］-R［B］⊆

R［A-B］

4.3.4关系的幂运算定义4.4.1

设R是A上的二元关系，即R⊆A×A。(1)称R是自反的(reflexive)，如果对任意x∈A，均有xRx。即R在A上是自反的当且仅当∀x(x∈A→xRx)。(2)称R是反自反的(irreflexive)，如果对任意x∈A，xRx均不成立。即R在A

上是反自反的当且仅当∀x(x∈A→┐xRx)。(3)称R是对称的(symmetric)，如果对任意x∈A，y∈A，xRy蕴含yRx。即R在A

上是对称的当且仅当

∀x∀y(x∈A∧y∈A∧xRy→yRx)。

4.4.1关系性质的定义(4)称R是反对称的(antisymmetric)，如果对任意x∈A，y∈A，xRy且yRx蕴含x＝y。即R在A上是反对称的当且仅当∀x∀y(x∈A∧y∈A∧xRy∧yRx→x=y)。

反对称性的另一种等价的定义为：

R在A上是反对称的当且仅当∀x∀y(x∈A∧y∈A∧xRy

∧x≠y→<y

，x>∈R)。(5)称R是传递的(transitive)，如果对任意x∈A，y∈A，z∈A，xRy且yRz蕴含xRz

。即R在A上是传递的当且仅当∀x∀

y∀

z(x∈A∧y∈A∧z∈A∧xRy∧yRz→xRz)。

4.4.1关系性质的定义【例4.4.1】

设A={a，b，c}，以下各关系Ri(i＝1，2，…，8)均为A上的二元关系。(1)R1＝{<a，a>，<a，c>，<b，b>，<c，c>}是自反的，而R2＝{<a，c>，<c，a>}不是自反的，是反自反的。存在既不自反也不反自反的二元关系，例如R3＝{<a，a>}。显然A上的φ关系是反自反的，不是自反的。可是值得注意的是，当A＝φ时(这时A上只有一个关系φ)，A上空关系既是自反的，又是反自反的，因为A＝φ使两者定义的前提总为假。

4.4.1关系性质的定义(2)R4＝{<a，b>，<b，a>}是对称的；R5＝{<a，c>，<c，a>，<a，b>，<a，a>}不是对称的；R6＝{<a，b>，<a，c>}是反对称的。其实R5既不是对称的，也不是反对

称的。特别有意思的是，存在既对称又反对称的二元关系，例如A上的恒等关系IA。(3)R7＝{<a，b>，<b，c>，<a，c>，<c，c>}是传递的，但R7-{<a，c>}便不是传递的了。应当注意，A上的空关系，R8＝{<a，b>}等是传递的，因为传递性定义的前提对它们而言均为假。

4.4.1关系性质的定义(4)任何非空集合上的空关系都是反自反、对称、反对称、传递的；其上的相等关系是自反、对称、反对称、传递的；其上的全关系是自反、对称、传递的。(5)三角形的相似关系、全等关系是自反、对称、传递的。(6)正整数集合上的整除关系是自反、反对称、传递的；但整数集合上的整除关系只有传递性。

4.4.1关系性质的定义定理4.4.1

设R为集合A上的二元关系，即R⊆A×A，则

(1)R是自反的当且仅当IA⊆R。

(2)R是反自反的当且仅当IA∩R=φ。

(3)R是对称的当且仅当R=R-1。

(4)R是反对称的当且仅当R∩R-1⊆IA。

(5)R是传递的当且仅当R○R⊆R。4.4.2关系性质的判定定理关系的基本性质与关系图、关系矩阵有怎样的联系呢？表4.4.1详解之。表

4.4.14.4.2关系性质的判定定理【例4.4.2】设Ri是A={1，2，3}上的二元关系(如图4.4.1所示)，判断它们各具有什么性质？并说明理由。解：根据关系图的特征，我们可判断下列各关系具有的性质。

R1具有反自反性、对称性、反对称性、传递性。因为每一结点处均无环，既无双边又无单边，既无双边又无三角形。

R2具有自反性、对称性、反对称性、传递性。因为每一结点处有一环，既无双边又无单边，既无双边又无三角形。4.4.2关系性质的判定定理R3具有自反性、对称性、传递性。因为每一结点处有一环，有边就有双边，有双边又有双环，有三角形就是向量三角形。R4具有反对称性、传递性。因为无双边，无三角形。R5具有对称性。因为无单边。R6具有反自反性、反对称性。因为每一结点处均无环。R7具有自反性、传递性。因为每一结点处有一环，有三角形，且是向量三角形。R8具有反自反性、反对称性、传递性。因为每一结点处均无环，有三角形，且是向量三角形。R9均不具备。

4.4.2关系性质的判定定理4.4.2关系性质的判定定理定理4.4.2

设R1、R2是A上的自反关系，则R1-1、R1∩R2、R1∪R2、R1○

R2也是A上的自反关系。4.4.3关系性质的封闭性定理4.4.3设R1、R2是A上的对称关系，则R1-1、R1∩R2、R1∪R2、R1-R2也是A上的对称关系。4.4.3关系性质的封闭性定理4.4.4

设R1、R2是A上的传递关系，则R1-1、R1∩R2是A上的传递关系。但R1∪R2不一定是传递的。4.4.3关系性质的封闭性定理4.4.5

设R1、R2是A上的反对称关系，则R1-1、R1∩R2、R1-R2是A上的反对称关系。但R1∪R2不一定是反对称的。

4.4.3关系性质的封闭性定理4.4.6

设R1、R2是A上的反自反关系，则R1-1、R1∩R2、R1∪R2、R1-R2是A上的反自反关系。

4.4.3关系性质的封闭性总结：设R1、R2是A上的关系，他们具有某些共同的性质。在经过并、交、相对补、求逆或右复合运算，所得新关系是否还能保持原来关系的性质呢？原有

性质运算自反性反自反性对称性反对称性传递性R1-1

√√√√√R1∩R2√√√√√R1∪R2√√√××R1-R2×√√√×R1○R2√××××4.4.3关系性质的封闭性【例4.4.3】

A={a，b，c}，讨论在下列各种情况下R

○

S具有的性质。(1)R={<a，b>}，S={<b，a>}，R、S是反自反的。(2)R={<a，b>，<b，a>}，S={<b，c>，<c，b>}，R、S是对称的。(3)R={<a，b>，<b，c>}，S={<b，b>，<c，a>}，R、S是反对称的。(4)R={<a，b>，<b，c>，<a，c>}，S={<b，a>，<b，c>，<c，a>}，R、S是传递的。4.4.3关系性质的封闭性解：R

○

S={<a，a>}，所以R

○

S不是反自反的。(2)R

○

S={<a，c>}，所以R

○

S不是对称的。(3)R

○

S={<a，b>，<b，a>}，所以R

○

S是对称的。(4)R

○

S={<a,a>，<a,c>，<b,a>}，因为<b,a>∈R

○

S，<a,c>∈R

○

S，但<b，c>∉R

○

S，所以R

○

S不是传递的。4.4.3关系性质的封闭性4.5.1闭包的概念4.5.2闭包的构建4.5.3闭包的性质4.5.1关系的闭包【定义4.5.1】设R是非空集合A上的关系，如果A上有另一个关系R′满足：

①R′是自反的；a

②R⊆R′；

③对A上任何自反的关系R″，若R⊆

R″，均有R′⊆R″，则称R′为R的自反闭包。4.5.1关系的闭包例：设A＝{a，b，c，d}，R={<a，a>，<a，b>，<b，b>，<b,a>，<b，c>,<c，d>，<d，d>}。判断R是否具有自反性？如不具有，构建关系使R具有自反性。RR′R″4.5.1关系的闭包【定义4.5.2】设R是非空集合A上的关系，如果A上有另一个关系R′满足：

①R′是对称的；

②R⊆R′；

③对A上任何对称的关系R″，若R⊆

R″，均有R′⊆R″，则称R′为R的对称闭包。4.5.1关系的闭包例：设A＝{a，b，c，d}，R={<a，b>，<b，a>，<b，c>，<c，d>，<d，c>}。判断R是否具有对称性？如不具有，构建关系使R具有对称性。RR′R″4.5.1关系的闭包【定义4.5.3】设R是非空集合A上的关系，如果A上有另一个关系R′满足：

①R′是传递的；

②R⊆R′；

③对A上任何传递的关系R″，若R⊆

R″，均有R′⊆R″，则称R′为R的传递闭包。4.5.1关系的闭包例：设A＝{a，b，c，d}，R={<a，a>，<a，b>，<a，c>，<b,

b>，<b，a>,<b，c>，<b，d>，<c，d>}。判断R是否具有传递性？如不具有，构建关系使R具有传递性。RR′R″4.5.1关系的闭包一般将R的自反闭包记作r(R)，对称闭包记作s(R)，传递闭包记作t(R)。称r、s、t为闭包运算，它们作用于关系R后，分别产生包含R的、最小的具有自反性、对称性、传递性的二元关系。4.5.1关系的闭包定理4.5.1设R是集合A上的二元关系，那么

(1)r(R)=IA∪R

(2)s(R)=R∪R-1

(3)t(R)=

4.5.2闭包的判定定理推论

A为非空有限集合，|A|=n。R是A上的关系，则存在正整数k≤n，使得t(R)=R

+=R∪R

2∪…∪R

k

4.5.2闭包的判定定理【例4.5.1】

设A＝{1，2，3}，R={<1，2>，<2，1>，<1，3>，<1，1>}，求它的闭包，并画出对应的关系图。4.5.2闭包的判定定理【例4.5.2】设A＝{1，2，3}，R={<1，2>，<2，1>}，求它的闭包，并画出对应的关系图。4.5.2闭包的判定定理【例4.5.3】设A＝{1，2，3}，R={<1，2>，<1，3>，<2，1>}，求它的闭包，并画出对应的关系图。4.5.2闭包的判定定理【例4.5.4】设集合A={a，b，c，d}，A上的关系R={<a，b>，<b，a>，<b，c>，<c，d>，<d，b>},求R的自反闭包r(R)、对称闭包s(R)和传递闭包t(R)。解：r(R)=R∪IA={<a,b>,<b,a>,<b,c>,<c,d>,<d,b>,<a,a>,<b,b>,<c,c>,<d,d>}s(R)=R∪R-1={<a,b>,<b,a>,<b,c>,<c,b>,<c,d>,<d,c>,<d,b>,<b,d>}t(R)=R+=R∪R2∪R3∪R4={<a,a>,<a,b>,<a,c>,<a,d>,<b,a>,<b,b>,<b,c>,<b,d>,<c,a>,<c,b>,<c,c>,<c,d>,<d,a>,<d,b>,<d,c>,<d,d>}4.5.2闭包的判定定理【例4.5.5】设集合A={a，b，c，d}，A上的关系R={<a，b>，<b，a>，<b，c>，<c，d>，<d，b>},求R的自反闭包r(R)、对称闭包s(R)和传递闭包t(R)解：r(R)=R∪IA={<a,b>,<b,a>,<b,c>,<c,d>,<d,b>,<a,a>,<b,b>,<c,c>,<d,d>}

s(R)=R∪R-1={<a,b>,<b,a>,<b,c>,<c,b>,<c,d>,<d,c>,<d,b>,<b,d>}

t(R)=R+=R∪R2∪R3∪R4={<a,a>,<a,b>,<a,c>,<a,d>,<b,a>,<b,b>,<b,c>,<b,d>,<c,a>,<c,b>,<c,c>,<c,d>,<d,a>,<d,b>,<d,c>,<d,d>}4.5.2闭包的判定定理Warshall(沃夏尔)算法：设R为有限集A上的二元关系，|A|=n，M为R的关系矩阵，可如下求取R+的关系矩阵W。

(1)置W为M。

(2)置i=1。

(3)对所有j，1≤j≤n，做

①如果W［j，i］=1，则对每一k=1，2，…，n，置W［j，k］为W［j，k］∨W［i，k］，即当第j行、第i列为1时，对第j行每个分量重新置值，取其当前值与第i行的同列分量之析取。

②否则对下一j值进行①。

(4)置i为i+1。

(5)若i≤n，回到步骤(3)，否则停止。4.5.2闭包的判定定理

Warshall(沃夏尔)算法伪代码：M（R的关系矩阵）

W（t(R)的关系矩阵）

W=M

fori=1ton

forj=1ton

fork=1ton

if(W［j，i］=1)

W［j，k]=W［j，k］+W［i，k］(逻辑加

)

4.5.2闭包的判定定理【例4.5.6】

设R是集合A={a，b，c，d}上的二元关系，R={<a，b>，<b,a>，<b，c>，<c，d>}。求R的t(R)(Warshall(沃夏尔)算法)。4.5.2闭包的判定定理定理4.5.2

设R是集合A上任一关系，那么

(1)R自反当且仅当R=r(R)。

(2)R对称当且仅当R=s(R)。

(3)R传递当且仅当R=t(R)。

4.5.3闭包的性质定理4.5.3

对非空集合A上的关系R1、R2，若R1

R2，则

(1)r(R1)⊆r(R2)

(2)s(R1)⊆s(R2)

(3)t(R1)⊆t(R2)

4.5.3闭包的性质定理4.5.4

对非空集合A上的关系R1、R2，则

(1)r(R1)∪r(R2)=r(R1∪R2)

(2)s(R1)∪s(R2)=s(R1∪R2)

(3)t(R1)∪t(R2)⊆t(R1∪R2)

4.5.3闭包的性质定理4.5.5

设R是集合A上任意二元关系，则

(1)如果R是自反的，那么s(R)和t(R)都是自反的。

(2)如果R是对称的，那么r(R)和t(R)都是对称的。

(3)如果R是传递的，那么r(R)是传递的。

4.5.3闭包的性质定理4.5.6

设R为集合A上的任一二元关系，那么

(1)rs(R)＝sr(R)

(2)rt(R)＝tr(R)

(3)st(R)⊆ts(R)

4.5.3闭包的性质【例4.5.7】

设R是集合X上的二元关系，X={a，b，c}，R={<a，b>，<b，c>}。求st(R)和ts(R)，并画出关系图。

4.5.3闭包的性质【例4.5.5】设A＝{1，2，3}，R={<1，2>，<2，1>}，求st(R)和ts(R)，并画出关系图。4.5.3闭包的性质【例4.5.8】设集合A={a，b，c}，A上的关系R={<a，b>，<b，c>，<c，a>},求R的自反闭包r(R)、对称闭包s(R)和传递闭包t(R)。解：r(R)=R∪IA={<a,b>,<b,c>,<c,a>,<a,a>,<b,b>,<c,c>}s(R)=R∪R-1={<a,b>,<b,a>,<b,c>,<c,b>,<c,a>,<a,c>}t(R)=R+=R∪R2∪R3={<a,a>,<a,b>,<a,c>,<b,a>,<b,b>,<b,c>,<c,a>,<c,b>,<c,c>}4.5.3闭包的性质定义4.6.1

设R是非空集合A上的二元关系，如果R是自反的、对称的和传递的，则称R为A上的等价关系(equivalentrelation)。

4.6.1等价关系【例4.6.1】(1)人类集合中的“同龄”、“同乡”关系都是等价关系。(2)住校学生的“同寝室关系”是等价关系。4.6.1等价关系【例4.6.2】设A={1，2，3，4}且R={<1，1>，<1，2>，<2，1>，<2，2>，<3，4>，<4，3>，<3，3>，<4，4>}。

4.6.1等价关系【例4.6.3.1】整数集合I中的二元关系R={<x，y>|m|(x-y)，m∈I+}，其中“|”表示整除关系，证明R是等价关系。

4.6.1等价关系解：(1)∀

x∈I，因为x-x=0，所以m|(x-x)，因此<x，x>∈R，R是自反的。(2)∀x，y∈I，设<x，y>∈R，则m|(x-y)，即(x-y)/m=k∈I

由于(y-x)/m=-(x-y)/m=-k∈I

故<y，x>∈R，所以R是对称的。(3)∀x，y，z∈I，设<x，y>∈R且<y，z>∈R，则

(x-y)/m=k∈I(y-z)/m=l∈I因而

(x-z)/m=(x-y+y-z)/m=k+l∈I

故<x，z>∈R，所以R是传递的。

因此，R是一个等价关系。4.6.1等价关系注意：(x-y)/m=k∈I，即x=km+y，说明x与y除以m的余数是一样的。所以这个关系又称为x与y的模m同余关系，x与y的模m相等关系。模m相等关系用符号“≡m”表示。

4.6.1等价关系【例4.6.3.2】设A={1,2,…,8}，A上的关系R定义如下：R={<x,y>|x,y∈A∧x≡y(mod3)}其中x≡y(mod3)叫做x与y模3相等，即x除以3的余数与y除以3的余数相等或x−y可被3整除。证明R是等价关系。

4.6.1等价关系解：（1）自反：∀x∈A，x≡x(mod3)，即<x,x>∈R。（2）对称：∀x,y∈A，若x≡y(mod3)即<x,y>∈R，则y≡x(mod3)即<y,x>∈R。（3）传递：∀x,y,z∈A，若x≡y(mod3)且y≡z(mod3)，则x≡z(mod3)。因此，R是一个等价关系。该关系的关系图如下：

4.6.1等价关系定义4.6.2

设R为集合A上的等价关系。对每一a∈A，令A中所有与a

等价的元素构成的集合记为[a]R

，即形式化为

[a]R

={x|x∈A∧xRa}

称[a]R为a的关于R所生成的等价类(equivalentclass)，简称a的等价类，简单地记为[a]R，a称为[a]R的代表元素。4.6.2集合的划分【例4.6.4】

设R是X={0，1，2，3，4}上的二元等价关系，R={<x,y>|x，y∈X且(x-y)/2是整数}。

(1)给出关系矩阵；

(2)画出关系图；

(3)求出等价类。解：

(1)R的关系矩阵为

4.6.2集合的划分4.6.2集合的划分(2)R的关系图如图4.6.1所示。(3)[0]R=[2]R=[4]R={0，2，4}

[1]R=[3]R={1，3}从上述关系图可看出，等价类是关系图中互不相连的各个部分的顶点组成。4.6.2集合的划分【例4.6.5】若在例4.6.3中取m=4，即设R为整数集上的≡4关系，它有四个不同的等价类:

[0]={…，-12，-8，-4，0，4，8，12，…}={x|4整除x}

[1]={…，-11，-7，-3，1，5，9，13，…}={x|4除x余1}

[2]={…，-10，-6，-2，2，6，10，14，…}={x|4除x余2}

[3]={…，-9，-5，-1，3，7，11，15，…}={x|4除x余3}

4.6等价关系和划分定理4.6.1

设R是非空集合A上的等价关系。

(1)对任意的a∈A，[a]R≠φ，且[a]R⊆A，[a]R是A的非空子集。

(2)∪{[a]|a∈A}=A(∪S表示集合S中的元素做并运算所构成的集合)。

4.6.2集合的划分定理4.6.2

设R是集合A上的等价关系，那么，对任意a，b∈A，有aRb

当且仅当[a]R=[b]R

4.6.2集合的划分定理4.6.3

设R是集合A上的等价关系，那么，对任意a，b∈A，或者[a]R=[b]R，或者[a]R∩[b]R=φ

。

4.6.2集合的划分由定理4.6.2、定理4.6.3知，对任何集合A上的等价关系R，有对任何a，b∈A，aRb<=>[a]R=[b]R<=>[a]R∩[b]R≠φ

等价类有下面的性质：(1)对任何集合A，IA有|A|个不同的等价类，每个等价类都是单元素集。(2)对任何集合A，A×A只有一个等价类为A(即每个元素的等价类全为A)。(3)同一等价类可以有不同的表示元素，或者说，不同的元素可能有相同的等价类。

4.6.2集合的划分定义4.6.3

当非空集合A的子集族π(π⊆P(A))满足下列条件时称为A的一个划分(partitions)：

(1)对任意B∈π，B≠φ,

(2)对任意B∈π，B⊆A,

(3)∪π＝A(其中∪π表示π中元素的并)

(4)对任意B，B′∈π，B≠B′时，B∩B′=φ,则称π中元素为划分的划分块。4.6.2集合的划分【例4.6.6】设A＝{0，1，2，3，4}，则π1={{1，3}，{0，2，4}}π2={{0，1，3}，{2，4}}π3={{3}，{0，1，2，4}}π4={{0，1，2，3，4}}

均为A的划分。4.6.2集合的划分【例4.6.7】当A={a，b，c，d}时，给定的π1，

π2，

π3，

π4，

π5，

π6如下：

π1={{a，b，c}，{d}}

π2={{a，b}，{c}，{d}}，

π3={{a}，{a，

b，c

，d}}

π4={{a，b}，{c}}

π5={{a，b}，{c，d}}

π6={{a，{a}}，{b，c，d}}哪些是A的划分？哪些不是？4.6.2集合的划分定理4.6.4

设R为集合A上的等价关系，那么R对应的A的划分是{[x]R|x∈A}。定理4.6.5

设π是集合A的一个划分，则如下定义的关系R为A上的等价关系：R={<x，y>|∃B(B∈π∧x∈B∧y∈B)}称R为π对应的等价关系。

4.6.2集合的划分定理4.6.6

设π是集合A的划分，R是A上的等价关系，那么，对应π的等价关系为R，当且仅当R对应的划分为π。

4.6.2集合的划分【例4.6.8】

设A={1,2,3}，则A

上共有多少种不同的等价关系？

4.6.2集合的划分【例4.6.9】

设A

是一个集合且|A|=4，则A

上共有多少种不同的等价关系？解：本题利用划分与等价关系的一一对应，用划分求等价关系，具体求解见表4.6.1。

4.6.2集合的划分表4.6.1

4.6.2集合的划分定义4.6.4

设R为集合A上的等价关系，那么称A的划分{[a]R|a∈A}为A关于R的商集(quotientsets)，记为A/R。

4.6.2集合的划分定义4.6.4

设R为集合A上的等价关系，那么称A的划分{[a]R|a∈A}为A关于R的商集(quotientsets)，记为A/R。

4.6.2集合的划分【例4.6.11】

在例4.6.3中的等价关系中，取m=2。求A/R。解：[0]={…，-6，-4，-2，0，2，4，6，8，…}，即由偶整数组成，因为它们整除2的余数是0。[1]={…，-5，-3，-1，1，3，5，7，…}，即由奇整数组成，因为它们整除2的余数是1。因此A/R是由偶整数集合和奇整数集合组成的集合。

4.6.2集合的划分对有穷集合A如何求A/R的步骤：

(1)从集合A中任意选一个元素a，并计算a所在的等价类[a]。(2)如果[a]≠A，选另一个元素b，b∈A且b∉[a]，计算[b]。(3)如果A不与上面计算的所有等价类的并相等，则在A中选不在这些等价类中的元素x且计算[x]。(4)重复(3)直到集合A与所有等价类的并相等，则结束。

4.6.2集合的划分定义4.6.5设π1，π2为集合的两个划分。称π1细分π2，如果π1的每一划分块都包含于π2的某个划分块。π1细分π2表示为π1≤π2。π1≤π2且π1≠π2，则表示为π1＜π2，读作π1真细分于π2。

4.6.2集合的划分【例4.6.12】当A={a，b，c，d}时，π1={{a，b}，

{c}，{d}}细分π2={{a，b，c}，{d}}，π3={{a}，{b}，{c}，{d}}细分所有划分。而所有划分均细分π4={{a，b，c，d}}。并且，π1真细分π2，π3真细分π1。4.6.2集合的划分定理4.6.7

设R1，R2为集合A上的等价关系，π1，π2分别是R1，R2所对应的划分，那么R1⊆R2

当且仅当π1≤π2本定理表明，越“小”(含有较少序偶)的等价关系对应越细的划分，反之亦然。很明白，最小的等价关系是相等关系，它对应于最细的划分(每一划分块恰含一个元素)，最大的等价关系是全关系，它对应于最粗的划分(只有一个划分块)。

4.6.2集合的划分定义4.7.1

设R是非空集合A上的二元关系，如果R是自反、反对称、传递的，称R为A上的偏序关系(partialorderedrelations)，记作≼。如果集合A上有偏序关系R，则称A为偏序集(orderedsets)，用序偶<A，R>表示之。若<x，y>∈≼

，常记作x≼

y，读作“x小于或等于y”，说明x在偏序上排在y的前面或者相同。

为简明起见，我们用记号“≼”表示一般的偏序关系，从而<A，≼>表示一般的偏序集。4.7.1偏序关系注意：这里的“小于或等于”不是指数的大小，而是指在偏序关系中的顺序性。x小于或等于y的含义是：按照这个序，x排在y的前边或者x就是y。根据不同偏序的定义，对偏序有着不同的解释。例如，正整数集合上的整除关系“|”为一偏序关系，<I+，|>为一偏序集，2|4(通常写为2≼4)的含义是2整除4，2在整除关系上排在4的前面，也就是说2比4小。4.7.1偏序关系【例4.7.1】

(1)设A是集合S的子集为元素所构成的集合，包含关系“⊆”是A

上的一个偏序关系，因此<A，⊆

>是一个偏序集。(2)实数集R上的“≤”即小于等于关系为一偏序关系，<R,≤>表示偏序集。实数集R上的“≥”即大于等于关系也是偏序关系，<R，≥>也表示一个偏序集。7≥6，可以写作7≼6，理解为在大于等于偏序关系中，7排在6的前面，或说7比6大。

4.7.1偏序关系定义4.7