离散完整ppt课件4.12

1、1第第4章章 二元关系与函数二元关系与函数n4.1 集合的笛卡儿积与二元关系集合的笛卡儿积与二元关系n4.2 关系的运算关系的运算n4.3 关系的性质关系的性质n4.4 关系的闭包关系的闭包n4.5 等价关系和偏序关系等价关系和偏序关系n4.6 函数的定义和性质函数的定义和性质n4.7 函数的复合和反函数函数的复合和反函数24.1 集合的笛卡儿积和二元关系集合的笛卡儿积和二元关系n 有序对有序对n 笛卡儿积及其性质笛卡儿积及其性质n 二元关系的定义二元关系的定义n 二元关系的表示二元关系的表示3有序对有序对定义定义 由两个客体由两个客体 x 和和 y，按照一定的顺序组成的，按照一定的顺序组成的

2、 二元组称为二元组称为有序对有序对，记作，记作实例：点的直角坐标实例：点的直角坐标(3, 4) 有序对性质有序对性质 有序性有序性 （当（当x y时）时） 与与 相等的充分必要条件是相等的充分必要条件是 = x=u y=v例例1 = ，求，求 x, y. 解解 3y 4 = 2, x+5 = y y = 2, x = 3 4有序有序 n 元组元组定义定义 一个一个有序有序 n (n 3) 元组元组 是一个是一个有序对，其中第一个元素是一个有序有序对，其中第一个元素是一个有序 n-1元组，即元组，即 = , xn 当当 n=1时时, 形式上可以看成有序形式上可以看成有序 1 元组元组. 实例实例

3、 n 维向量是有序维向量是有序 n元组元组. 5笛卡儿积笛卡儿积定义定义 设设a,b为集合，为集合，a与与b 的的笛卡儿积笛卡儿积记作记作a b， 即即 a b = | x a y b 例例2 a=1,2,3, b=a,b,c a b =, , b a =, , , a=, p(a) a=, 6笛卡儿积的性质笛卡儿积的性质不适合交换律不适合交换律 a b b a (a b, a, b)不适合结合律不适合结合律 (a b) c a (b c) (a, b)对于并或交运算满足分配律对于并或交运算满足分配律 a (b c)=(a b) (a c) (b c) a=(b a) (c a) a (b c

4、)=(a b) (a c) (b c) a=(b a) (c a) 若若a或或b中有一个为空集，则中有一个为空集，则a b就是空集就是空集. a=b= 若若|a|=m, |b|=n, 则则 |a b|=mn 7性质的证明性质的证明证明证明 a (b c)=(a b) (a c)证证 任取任取 a(bc) xaybc xa(ybyc) (xayb)(xayc) abac (ab)(ac)所以有所以有a(bc) = (ab)(ac).8例题例题 解解 (1) 任取任取 a c x a y c x b y d b d 例例3 (1) 证明证明 a=b c=d a c=b d (2) a c=b d是

5、否推出是否推出 a=b c=d ? 为什么？为什么？(2) 不一定不一定. 反例如下：反例如下： a=1，b=2, c=d=, 则则 a c=b d 但是但是 a b.9二元关系的定义二元关系的定义定义定义 如果一个集合满足以下条件之一：如果一个集合满足以下条件之一：（1）集合非空）集合非空, 且它的元素都是有序对且它的元素都是有序对（2）集合是空集）集合是空集则称该集合为一个则称该集合为一个二元关系二元关系, 简称为简称为关系关系，记作，记作r.如如r, 可记作可记作 xry；如果；如果 r, 则记作则记作x y实例：实例：r=, s=,a,b. r是二元关系是二元关系, 当当a, b不是有

6、序对时，不是有序对时，s不是二元关系不是二元关系根据上面的记法，可以写根据上面的记法，可以写 1r2, arb, a c 等等. 10从从a到到b的关系与的关系与a上上的关系的关系定义定义 设设a,b为集合为集合, ab的任何子集所定义的二元的任何子集所定义的二元关系叫做关系叫做从从a到到b的二元关系的二元关系, 当当a=b时则叫做时则叫做 a上上的二元关系的二元关系.例例4 a=0,1, b=1,2,3, r1=, r2=ab, r3=, r4=. 那么那么 r1, r2, r3, r4是从是从 a 到到 b 的二元关系的二元关系, r3和和r4同时也是同时也是 a上的二元关系上的二元关系.

7、 计数计数|a|=n, |aa|=n2, aa的子集有的子集有 个个. 所以所以 a上有上有 个不同的二元关系个不同的二元关系. 例如例如 |a|=3, 则则 a上有上有=512个不同的二元关系个不同的二元关系. 22n22n11a上重要关系的实例上重要关系的实例设设 a 为任意集合，为任意集合，是是 a 上的关系，称为上的关系，称为空关系空关系ea, ia 分别称为分别称为全域关系全域关系与与恒等关系恒等关系，定义如下：，定义如下： ea=|xaya=aa ia=|xa例如例如, a=1,2, 则则 ea=, ia=,12a上重要关系的实例（续）上重要关系的实例（续）小于等于关系小于等于关系

8、 la, 整除关系整除关系da, 包含关系包含关系r 定义：定义： la=| x,yaxy, a r，r为实数集合为实数集合 db=| x,ybx整除整除y, b z*, z*为非为非0整数集整数集 r =| x,yax y, a是集合族是集合族.类似的还可以定义大于等于关系类似的还可以定义大于等于关系, 小于关系小于关系, 大于大于关系关系, 真包含关系等等真包含关系等等. 13实例实例例如例如 a = 1, 2, 3, b =a, b, 则则 la=, da=, a=p(b)=,a,b,a,b, 则则 a上的包含关系是上的包含关系是 r =, ,14关系的表示关系的表示表示方式：关系的集合

9、表达式、关系矩阵、关系图表示方式：关系的集合表达式、关系矩阵、关系图 关系矩阵关系矩阵：若：若a=a1, a2, , am，b=b1, b2, , bn，r是从是从a到到b的关系，的关系，r的关系矩阵是布尔矩阵的关系矩阵是布尔矩阵mr = rij m n, 其中其中 rij = 1 r. 关系图关系图：若：若a= x1, x2, , xm，r是从是从a上的关系，上的关系，r的关系图是的关系图是gr=, 其中其中a为结点集，为结点集，r为边集为边集.如果如果属于关系属于关系r，在图中就有一条从，在图中就有一条从 xi 到到 xj 的有向边的有向边. 注意：注意：a, b为有穷集，关系矩阵适于表示

10、从为有穷集，关系矩阵适于表示从a到到b的的关系或者关系或者a上的关系，关系图适于表示上的关系，关系图适于表示a上的关系上的关系 15实例实例a=1,2,3,4, r=,r的关系矩阵的关系矩阵mr和关系图和关系图gr如下：如下： 0010000011000011rm16n基本运算定义基本运算定义定义域、值域、域定义域、值域、域逆、合成、限制、像逆、合成、限制、像n基本运算的性质基本运算的性质n幂运算幂运算定义定义求法求法性质性质4.2 关系的运算关系的运算17关系的基本运算定义关系的基本运算定义定义域定义域、值域值域 和和 域域 domr = x | y ( r) ranr = y | x (

11、r) fldr = domr ranr 例例1 r=, 则则 domr=1, 2, 4 ranr=2, 3, 4 fldr=1, 2, 3, 4 18关系的基本运算定义（续）关系的基本运算定义（续）逆逆与与合成合成 r 1 = | r r s = | | y ( r s) 例例2 r=, , , s=, , , , r 1=, , , r s =, , s r =, , , 19合成运算的图示方法合成运算的图示方法 利用图示（不是关系图）方法求合成利用图示（不是关系图）方法求合成 r s =, , s r =, , , 20限制与像限制与像定义定义 f 在在a上的上的限制限制 f a = |

12、xfy x a a 在在f下的下的像像 fa = ran(f a) 实例实例 r=, , , r 1=, r1=2,4 r = r1,2=2,3,4注意：注意：f a f, fa ranf 21关系基本运算的性质关系基本运算的性质 定理定理1 设设f是任意的关系是任意的关系, 则则(1) (f 1) 1=f(2) domf 1=ranf, ranf 1=domf证证 (1) 任取任取, 由逆的定义有由逆的定义有 (f 1) 1 f 1 f所以有所以有 (f 1) 1=f (2) 任取任取x, xdomf 1 y(f 1) y(f) xranf 所以有所以有domf 1= ranf. 同理可证同

13、理可证 ranf 1 = domf.22定理定理2 设设f, g, h是任意的关系是任意的关系, 则则 (1) (f g) h=f (g h) (2) (f g) 1= g 1 f 1 证证 (1) 任取任取, (f g) h t(f gh) t ( s(fg)h) t s (fgh) s (f t (gh) s (fg h) f (g h) 所以所以 (f g) h = f (g h)关系基本运算的性质（续）关系基本运算的性质（续） 23 (2) 任取任取, (f g) 1 f g t (f(t,x)g) t (g 1(t,y)f 1) g 1 f 1 所以所以 (f g) 1 = g 1

14、f 1 关系基本运算的性质（续）关系基本运算的性质（续） 24a上关系的幂运算上关系的幂运算设设r为为a上的关系上的关系, n为自然数为自然数, 则则 r 的的 n次幂次幂定义为：定义为： (1) r0= | xa =ia (2) rn+1 = rn r 注意：注意： 对于对于a上的任何关系上的任何关系r1和和r2都有都有 r10 = r20 = ia 对于对于a上的任何关系上的任何关系 r 都有都有 r1 = r 25幂的求法幂的求法对于集合表示的关系对于集合表示的关系r，计算，计算 rn 就是就是n个个r右复合右复合 . 矩阵表示就是矩阵表示就是n个矩阵相乘个矩阵相乘, 其中相加采用逻辑加

15、其中相加采用逻辑加. 例例3 设设a=a,b,c,d, r=, 求求r的各次幂的各次幂, 分别用矩阵和关系图表示分别用矩阵和关系图表示.解解 r与与r2的关系矩阵分别为的关系矩阵分别为 0000100001010010m 0000000010100101000010000101001000001000010100102m26同理，同理，r0=ia, r3和和r4的矩阵分别是：的矩阵分别是：因此因此m4=m2, 即即r4=r2. 因此可以得到因此可以得到r2=r4=r6=, r3=r5=r7= 0000000010100101,000000000101101043mm 1000010000100

16、0010m幂的求法（续）幂的求法（续）27r0, r1, r2, r3,的关系图如下图所示的关系图如下图所示幂的求法（续）幂的求法（续）28幂运算的性质幂运算的性质定理定理3 设设a为为n元集元集, r是是a上的关系上的关系, 则存在自然则存在自然数数 s 和和 t, 使得使得 rs = rt.证证 r为为a上的关系上的关系, 由于由于|a|=n, a上的不同关系只上的不同关系只有有 个个. 当列出当列出 r 的各次幂的各次幂 r0, r1, r2, , , , 必存在自然数必存在自然数 s 和和 t 使得使得 rs=rt.22n29定理定理4 设设 r 是是 a 上的关系上的关系, m, nn, 则则 (1) rm rn=rm+n (2) (rm)n=rmn 证证 用归纳法用归纳法 (1) 对于任意给定的对于任意给定的mn, 施归纳于施归纳于n.若若n=0, 则有则有 rm r0=rm ia=rm=rm+0 假设假设rm rn=rm+n, 则有则有rm rn+1=r