离散数学及应用 课件 4.2 关系的运算

DiscreteMathematics鄢小虎

离散数学2基本运算定义定义域、值域、域逆、合成、限制、像基本运算的性质幂运算定义求法性质4.2关系的运算3关系的基本运算定义定义域、值域

和域

domR={x|

y(<x,y>

R)}所有第一个元素构成ranR={y|

x(<x,y>

R)}所有第二个元素构成fldR=domR

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

domR={1,2,4}ranR={2,3,4}fldR={1,2,3,4}关系的基本运算定义（续）逆与合成

R

1={<y,x>|<x,y>

R}(调换顺序)

R∘S=|<x,z>|

y(<x,y>

R

<y,z>

S)}(首尾相连)例2R={<1,2>,<2,3>,<1,4>,<2,2>}

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

R

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

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

S∘R={<1,2>,<1,4>,<3,2>,<3,3>}课堂练习：课本第117页第4.13题。

5课堂编程通过编程实现给定集合R和S的逆与合成操作？提示：

R

1={<y,x>|<x,y>

R}

R∘S=|<x,z>|

y(<x,y>

R

<y,z>

S)}。实例：R={<1,2>,<2,3>,<1,4>,<2,2>}

S={<1,1>,<1,3>,<2,3>,<3,2>,<3,3>}封装为函数ni(),hecheng()6限制与像定义

F在A上的限制

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

x

A}A在F下的像

F[A]=ran(F↾A)实例R={<1,2>,<2,3>,<1,4>,<2,2>}

R↾{1}={<1,2>,<1,4>}

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

F,F[A]ranF

7课堂练习第114页，第4.3题8课堂编程通过编程求解F在A上的限制，A在F下的像。提示：

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

x

A}

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

A={1}课程回顾关系的表达：有序对集合、关系矩阵、关系图基本运算定义定义域、值域、域逆、合成、限制、像

练习：课本114页，第4.3题。如何通过编程验证算律？10关系基本运算的性质定理1设F是任意的关系,则

(1)(F

1)

1=F(2)domF

1=ranF,ranF

1=domF（否定律）编程练习：通过逆与合成操作的函数，验证以上的公式(1)实例：F={<1,2>,<2,3>,<1,4>,<2,2>}11定理2设F,G,H是任意的关系,则

(1)(F∘G)∘H=F∘(G∘H)

（结合律）(2)(F∘G)

1=G

1∘F

1（交换位置）关系基本运算的性质（续）

编程练习：通过逆与合成操作的函数，验证以上两个公式实例：F={<1,2>,<2,3>,<1,4>,<2,2>}

G={<1,1>,<2,3>},H={<2,3>,<3,2>,<3,3>}12定理3设F,G,H是任意的关系,则(1)F∘(G

H)=F∘G

F∘H(2)F∘(G

H)

F∘G

F∘H关系基本运算的性质（续）

编程练习：通过并、交、合成操作的函数，验证以上两个公式提示：当A中的所有元素都在B中，则A

B实例：F={<1,2>,<2,3>,<1,4>,<2,2>}

G={<1,1>,<2,3>},H={<2,3>,<3,2>,<3,3>}13定理3设F,G,H是任意的关系,则(3)(G

H)∘

F=G

∘F

H∘F(4)(G

H)

∘

F

G∘F

H∘F关系基本运算的性质编程练习：通过并、交、合成操作的函数，验证以上两个公式提示：当A中的所有元素都在B中，则A

B；交的函数？实例：F={<1,2>,<2,3>,<1,4>,<2,2>}

G={<1,1>,<2,3>},H={<2,3>,<3,2>,<3,3>}14A上关系的幂运算设R为A上的关系,n为自然数,则R的n次幂定义为：

(1)R0={<x,x>|x∈A}=IA

(2)Rn+1=Rn∘R例如：A={1,2}，R为A上的关系，

则：R0={<1,1>,<2,2>}R3=R2∘R=R∘R∘R更高次幂该怎么计算？

15幂的求法（了解）对于集合表示的关系R，计算Rn就是n个R右复合.矩阵表示就是n个矩阵相乘,其中相加采用逻辑加.例3设A={a,b,c,d},R={<a,b>,<b,a>,<b,c>,<c,d>},求R2、R3、R4、R5的值，并通过程序验证

16幂的求法（续）分别用矩阵和关系图表示各次幂，R与R2的关系矩阵分别为注意：先乘后加.

矩阵的元素相加时使用逻辑加，即为：0+0=00+1=11+0=11+1=1(课后)编程练习：编程计算R2

，R3，R4，R5的关系矩阵

提示：难度较大17同理，R3和R4的矩阵分别是：因此M4=M2,即R4=R2.因此