离散数学：4-2 二元关系与函数

复习思考题8用公式表示下列文氏图的彩色部分：由1,2,3,4,5五个数字构成的全排列中，不出现”135”和”24”子串的排列数是________。ABC第4章二元关系与函数4.1集合的笛卡儿积与二元关系4.2关系的运算4.3关系的性质4.4关系的闭包4.5等价关系和偏序关系4.6函数的定义和性质4.7函数的复合和反函数

AB={<x,y>|xA

yB}笛卡儿积()的性质约定：若A=或

B=，则

A

B=一般地，不满足交换律：

A

B≠BA一般地，不满足结合律：

(AB)C≠A(BC)

若|A|=n，|B|=m，则：|A

B|=nm=|A||B|对于并或交运算满足分配律

A(BC)=(AB)(AC)

(BC)A=(BA)(CA)

A(BC)=(AB)(AC)(BC)A=(BA)(CA)

AB={<x,y>|xA

yB}<<a,b>,c>

<a,<b,c>>

直积运算性质的证明证明:

A(BC)=(AB)(AC)证:

任取<x,y><x,y>A(BC)

xA

y(BC)

xA

(yByC)(xA

yB)(xA

yC)

<x,y>A

B

<x,y>A

C<x,y>(A

B)(AC)

<x,y>AB

xA

yB

AB={x|xAxB}[P77例4.2]判断等式是否成立

(1)(AB)(CD)=(AC)(BD)

证：<x,y>

(AB)(CD)

x(AB)

y(CD)

(xA

xB)(yC

yD)

<x,y>(AC)

<x,y>(BD)

<x,y>(AC)(BD)

<x,y>(AD)<x,y>(BC)

<x,y>(AD)(BC)设A、B、C和D为任意集合(AB)(CD)=(AC)(BD)A

BDC(AB)(CD)

AC

BD

(AB)(CD)=(AD)(BC)A

BDC(AB)(CD)

BC

AD

[P77例4.2]判断等式是否成立

(2)(AB)

(CD)=(AC

)

(B

D)

<x,y>

(AB)

(CD)x

(A

B)y

(C

D)(xAxB)(yCy

D)

(xA

yC)

(xA

yD)

(xB

yC)

(xB

y

D)<x,y>(AC)(AD)(BC)(BD)

(AB)(CD)

=(AC)(BD)(AD)(BC)A

BDC(AB)(CD)

BDACADBC[P77例4.2]判断等式是否成立

(2)(AB)

(CD)=(AC

)

(B

D)

例如：A={1},B={2},C={3},D={4}

则

(AB)

(CD)={1,2}

{3,4}

={<1,3>,<1,4>,<2,3>,<2,4>}

而

(AC

)

(BD)

={1}{3}{2}{4}={<1,3>,<2,4>}

A

BDC(AB)(CD)

BDAC[P78例4.3]判断命题的真假

<x,y>AB

xAyB

ABC

D(1)若AB且CD，则有AC

BD

证：任取<x,y><x,y>AC

xA

yC

xByD

<x,y>BD

(2)若ABCD，则有AC且BD

解：不一定，反例如下：

当A={1},B=C=D

=

时

A

B=C

D=，但A⊈C设A、B、C和D为任意集合二元关系的定义定义：如果一个集合满足以下条件之一：（1）集合非空,且它的元素都是有序对,（2）集合是空集。

则称该集合为一个二元关系,简称为关系，记作R.如果<x,y>R,可记作xRy；如果<x,y>R,则记作xRy实例：R={<1,2>,<a,b>},S={<1,2>,a,b}.可以记为1R2,aRb,aRc，<1,2>

S等.

实数间的“>”关系可定义如下：“>”={<x,y>|x,y均为实数且x>y}注意：R是二元关系,当a、b不是有序对时，S不是二元关系从A到B的关系与A上的关系定义设A,B为集合,AB的任何子集所定义的二元关系叫做从A到B的二元关系,若A=B时则叫A上的二元关系.例：A={0,1},B={1,2,3},

R1={<0,2>},R2=AB,R3=,R4={<1,1>}.

R1,R2,R3,R4是从A到B的二元关系,

同时R3和R4也分别是A上的和B上的二元关系。计数|A|=n,|AA|=n2,AA的子集有2n2

个.

所以A上有2n2个不同的二元关系.例如:|A|=3,则A上有=512个不同的二元关系.A上重要关系及实例设A为任意集合，是A上的关系，称为空关系。EA,IA分别称为全域关系与恒等关系：全域关系EA={<x,y>|xA∧yA}=AA

恒等关系IA={<x,x>|xA}例如,A={1,2},则EA={<1,1>,<1,2>,<2,1>,<2,2>}

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

A上重要关系及实例小于等于关系

LALA={<x,y>|

x,y

A∧x≤y},

AR，R为实数集合整除关系DADA={<x,y>|

x,yA∧x整除y}

AZ*,Z*为非0整数集

包含关系R：

R={<x,y>|x,yA∧xy},

A是集合族.类似的还可以定义大于等于关系,小于关系,大于关系,真包含关系等等.A上重要关系及实例例如A={1,2,3},B={a,b},则小于等于关系LA

={<1,1>,<1,2>,<1,3>,<2,2>,<2,3>,<3,3>}整除关系DA={<1,1>,<1,2>,<1,3>,<2,2>,<3,3>}C=P(B)={,{a},{b},{a,b}},则

C上的包含关系是R={<,>,<,{a}>,<,{b}>,<,{a,b}>,<{a},{a}>,<{a},{a,b}>,<{b},{b}>,<{b},{a,b}>,<{a,b},{a,b}>}二元关系的表示用列举法表示二元关系例:设A={a,b}，B={1,2}A到B的全域关系E为

E=A×B={a,1,a,2,b,1,b,2}

A上的恒等关系：IA={a,a,b,b}用描述法表示二元关系例:设R是实数集，LR={x,y|xR∧yR∧x≤y}

LR是实数集R上的二元关系二元关系的表示

用矩阵表示二元关系设A，B分别为A={a1,a2,…,am},B={b1,b2,…,bn}，R是A到B的二元关系，R的关系矩阵MR定义为：用关系图表示二元关系xy<x,y>R从A到B的二元关系的表示设A={a1,a2,a3,a4}，B={b1,b2,b3}，R是A到B的二元关系，定义为：R={a1,b1,a1,b3,a2,b2,a2,b3,a3,b1,a4,b1,a4,b2}则其关系矩阵和关系图为:A上的二元关系的表示A={1,2,3,4},R={<1,1>,<1,2>,<2,3>,<2,4>,<4,2>},其关系矩阵和关系图如下：4.2关系的运算定义域、值域

和域定义域：domR={x|y(<x,y>R)}值域：ranR={y|x(<x,y>R)}域：fldR=domR

ranR例:

R={<1,2>,<1,3>,<2,4>,<4,3>},则

domR={1,2,4}ranR={2,3,4}fldR={1,2,3,4}关系的逆和合成运算关系F的逆F1

={<y,x>|<x,y>F}如

R={<1,2>,<2,3>,<1,4>,<2,2>}则R1={<2,1>,<3,2>,<4,1>,<2,2>}关系F和G的合成F∘GF∘G={<x,y>|z(<x,z>G<z,y>F)}

x1x2z3z2z1y1y2FGF

∘

G关系的合成运算F∘G={<x,y>|z(<x,z>G<z,y>F)}

如：

R={<1,2>,<2,3>,<1,4>,<2,2>}S={<1,1>,<1,3>,<2,3>,<3,2>,<3,3>}

则R∘S={<1,2>,<1,4>,<3,2>,<3,3>}S∘R={<1,3>,<2,2>,<2,3>}

x1x2z3z2z1y1y2FGF

∘G关系的合成运算F∘G

={<x,y>|

z

(<x,z>G<z,y>F)}

设F、G均是P上的关系，P是所有人的集合。F={<x,y>|x,yP

x是y的父亲

}G

={<x,y>|x,yP

x是y的母亲

}F∘F

={<x,y>|x,yP

x是y的

}G∘G={<x,y>|x,yP

x是y的}F∘G={<x,y>|x,yP

x是y的

}G-1∘F={<x,y>|x,yP

x是y的

}x1x2z3z2z1y1y2FGF

∘

G爷爷外婆奶奶丈夫限制与像F在A上的限制

F↾A={<x,y>|xFy

xA}A在F下的像F[A]=ran(F↾A)实例：R={<1,2>,<2,3>,<1,4>,<2,2>}

R↾{1}={<1,2>,<1,4>}（R在{1}上的限制）

R[{1}]={2,4}（{1}在R下的像）

R↾=

R[{1,2}]={2,3,4}注意：F↾A