华东交通大学：《离散数学》课程教学资源（PPT课件讲稿）第四章 二元关系和函数

、关系的定义域与值域(块) 例5:分别求出下列关系的定义域和值城。 (1)R1={<x,y>|x,y∈ZAx≤y} (2)R2={<x,y>|x, VEZAX2y2=1} (3)R3={<x,y>|x,y∈{1,2,3,4}Ax>y} 解:(1)domR1= ran r1=Z (2)R2={0,1>,<0,-1>,<1,0>,<-1,0} lom r 2 R2={0,1,-1 (3)R3={2,1>,3,1>,4,1>,3,2>,<4,2>,<43>} domR3={2,3,4},runR3={1,2,3}心 2021/2/24 离散数学 16

2021/2/24 离散数学 16 一、关系的定义域与值域（续） 例5：分别求出下列关系的定义域和值域。 (1) R1 = { < x, y > | x, yZ  x  y }; (2) R2 = { < x, y > | x, yZ  x 2 + y 2 = 1 }; (3) R3 = { < x, y > | x, y{1, 2, 3, 4}  x > y } 解：(1) dom R1 = ran R1 = Z (2) R2 = {<0, 1>, <0, -1>, <1, 0>, < -1, 0>} (3) R3 = {<2, 1>,<3, 1>,<4, 1>,<3, 2>, <4, 2>, <4, 3>} dom R2 = ran R2 = { 0, 1, -1 } dom R3 = { 2, 3, 4 }，ran R3 = { 1, 2, 3 }

二、关系的常用运算 1、逆:F是任意关系,F的逆F={<x,y>|yFx} 2、合任意两个关系F与G的合成,记作:F°G FoG={<x,y>|3( xFzAzG)}(右复合) 3、限系F在集合A上的限制,记作:F|A F|A={<x,y>|xFAx∈A} 4、象:集合A在F下的象,记作:F[A FI [A]=ran(FA) 2021/2/24 离散数学

2021/2/24 离散数学 17 1、逆： 2、合成： 3、限制： 4、象： 任意两个关系F与G的合成，记作：F  G F  G = { < x, y > |  z( xFz  zGy ) } (右复合) 二、关系的常用运算 F是任意关系，F 的逆F -1 ={ < x, y > | yFx } 关系F在集合A上的限制，记作：F | A F | A = { < x, y > | xFy  xA } 集合A在F 下的象，记作：F [A] F [A] = ran (F | A)

例:设F={3,3>,6,2},G={<2,3>,3,6}, 则F1={3,3>,<2,6>}, FSG={3,6>,{<6,3},G°F={<2,3>,3,2>} 例:设R={<1,2>,<1,3>,<2,2>,<2,4>,<3,2} R|[1}=【<1,2>,<1,3 R|[2,3]={2,2>,<2,4},<3,2) R[]={2,3 R[{3}]={2 2021/2/24 离散数学

2021/2/24 离散数学 18 例: 设F＝{<3,3>,<6,2>}, G={<2,3>,<3,6>}， 则F-1 ＝{<3,3>,<2,6>}, FG＝ {<3,6>, {<6,3>} , GF＝ {<2,3>,<3,2>} 例: 设R＝{<1,2>，<1,3>，<2,2>，<2,4>，<3,2>} R | {1}＝ {<1,2>，<1,3>} R | {2,3}＝ {<2,2>，<2,4>}，<3,2>} R[{1}]＝ {2,3} R[{3}]＝ {2}

、关系的常用运算(续) 例6:设F,G是N上的关系,其定义为 F=<x,y>x, yENAy=x2) G=K<X,y>x,vENAy=x+ 1 求G,FoG,G。F,F|{1,2},F1,2} 解:G1={y,x>|x,yeN∧y=x+1} 列出G1的元素即为 G-={<1,0>,<2,1>,<3,2 x+1,x 2021/2/24 离散数学 19

2021/2/24 离散数学 19 二、关系的常用运算（续） 例6：设F, G是N上的关系，其定义为 F = { < x, y > | x, yN  y = x 2 } G = { < x, y > | x, yN  y = x + 1 } 求G –1 , F  G, G  F, F | {1, 2}, F [{1, 2}]。 解：G –1 = { < y, x > | x, yN  y = x + 1 } 列出G –1中的元素即为 G –1 = {<1, 0>, <2, 1>, <3, 2>, … , < x + 1, x >, … }

、关系的常用运算(续) 例6:设F,G是N上的关系,其定义为 F=(x,y>lx,yeNAy=x2) G=K<X,y>x,vENAy=x+ 1 求G,FoG,G。F,F|{1,2},FⅣ 1,2}lo 解:为了求F。G可以先直观表示如下: 对任何x∈N G+1=y 即y=x2+1 因此F。G={x,y>|x,yEN^y=x2+ 1} 2021/2/24 离散数学 20

2021/2/24 离散数学 20 二、关系的常用运算（续） 例6：设F, G是N上的关系，其定义为 F = { < x, y > | x, yN  y = x 2 } G = { < x, y > | x, yN  y = x + 1 } 求G –1 , F  G, G  F, F | {1, 2}, F [{1, 2}]。 解：为了求F  G可以先直观表示如下： 对任何xN x x 2 = z z+1 = y F G 因此F  G = {< x, y > | x, yN  y = x 2+ 1} 即 y = x 2+ 1