chapter4_12(1)

1、1 集合论集合论2集合论部分集合论部分第第3章章 集合的基本概念和运算集合的基本概念和运算第第4章章 二元关系和函数二元关系和函数3 第四章第四章 二元关系与函数二元关系与函数44.1 集合的笛卡儿积和二元关系集合的笛卡儿积和二元关系l 有序对有序对l 笛卡儿积及其性质笛卡儿积及其性质l 二元关系的定义二元关系的定义l 二元关系的表示二元关系的表示5定义定义4.1 由两个元素由两个元素 x 和和 y，按照一定的顺序组成的，按照一定的顺序组成的 二元组称为二元组称为有序对有序对，记作，记作.例例1：点的坐标点的坐标. 有序对性质有序对性质 有序性有序性 (当当x y时时) 与与 相等的充分必要条

2、件是相等的充分必要条件是 = x=u y=v有序对有序对6有序有序 n 元组元组定义定义4.2 一个一个有序有序 n (n 3) 元组元组 是一个是一个 有序对，其中第一个元素是一个有序有序对，其中第一个元素是一个有序 n-1 元组，即元组，即 = , xn 当当 n=1时时, 形式上可以看成有序形式上可以看成有序 1 元组元组. 例例2: n 维向量是有序维向量是有序 n元组元组. 7笛卡儿积笛卡儿积定义定义 设设A,B为集合，为集合，A与与B 的的笛卡儿积笛卡儿积记作记作A B， 即即 A B = | x A y B 例例3: 1) A=1,2,3, B=a,b,c，计算，计算 A B、

3、B A . 2) A=, 计算计算P(A) A.8笛卡儿积笛卡儿积解：解：1） A B =, , B A =, , , 2） P(A) A=, 9例例4： (1) A=a，b，B=c，d，求，求AB。 (2) A=a，b，B=c，d，求，求BA。 (3) A=a,b,B=1,2,C=c, 求求(AB)C和和A(BC)。笛卡儿积笛卡儿积10解：解： (1)AB=a,bc,d=, 。(2) BA=c,da,b=, 。笛卡儿积笛卡儿积11(3) AB=a,b1,2=, 。(AB)C=,c, ,c, ,c, ,cBC=1，2c=，。 A(BC)=a,a, b, b, 12笛卡儿积的性质笛卡儿积的性质不

4、适合交换律不适合交换律 A B B A (A B, A, B)不适合结合律不适合结合律 (A B) C A (B C) (A, B,C)对于并或交运算满足分配律对于并或交运算满足分配律 A (B C)=(A B) (A C) (B C) A=(B A) (C A) A (B C)=(A B) (A C) (B C) A=(B A) (C A) 若若A或或B中有一个为空集，则中有一个为空集，则A B就是空集就是空集. A=B= 若若|A|=m, |B|=n, 则则 |A B|=mn 13性质的证明性质的证明证明证明: A (B C)=(A B) (A C)证证: 任取任取 A(BC) xAyBC

5、 xA(yByC) (xAyB)(xAyC) ABAC (AB)(AC) 所以有所以有A(BC) = (AB)(AC).14练习练习 解：解： (1) 任取任取 A C x A y C x B y D B D 例例5： (1) 证明证明 A=B C=D A C=B D (2) A C=B D是否推出是否推出 A=B C=D ? 为什么？为什么？(2) 不一定不一定. 反例如下：反例如下： A=1，B=2, C=D=, 则则 A C=B D 但是但是 A B.15定义定义4.5 如果一个集合满足以下条件之一：如果一个集合满足以下条件之一： (1)集合非空集合非空, 且它的元素都是有序对且它的元素

6、都是有序对 (2)集合是空集集合是空集则称该集合为一个则称该集合为一个二元关系二元关系, 简称为简称为关系关系，记作，记作R.如如R, 可记作可记作 xRy；如果；如果 R, 则记作则记作x y二元关系的定义二元关系的定义R 例例6：R=, S=,a,b. R是二元关系是二元关系, 当当a, b不是有序对时，不是有序对时，S不是二元关系不是二元关系根据上面的记法，可以写根据上面的记法，可以写 1R2, aRb, a c 等等. R 16从从A到到B的关系与的关系与A上上的关系的关系定义定义4.6 设设A,B为集合为集合, AB的任何子集所定义的任何子集所定义的二元关系叫做的二元关系叫做从从A到

7、到B的二元关系的二元关系, 当当A=B时则时则叫做叫做 A上的二元关系上的二元关系.17从从A到到B的关系与的关系与A上上的关系的关系例例7： A=0,1, B=1,2,3, R1=, R2=AB, R3=, R4=. 那么那么 R1, R2, R3, R4是从是从 A到到 B的二元关系的二元关系, R3和和R4同同时也是时也是 A上的二元关系上的二元关系. 计数计数|A|=n, |AA|=n2, AA的子集有的子集有 个个. 所以所以 A上上有有 个不同的二元关系个不同的二元关系. 例例8：若若 |A|=3, 则则 A上有上有29=512个不同的二元关系个不同的二元关系. 22n22n18A

8、上重要关系的实例上重要关系的实例设设 A 为任意集合，为任意集合，是是 A 上的关系，称为上的关系，称为空关系空关系EA, IA 分别称为分别称为全域关系全域关系与与恒等关系恒等关系，定义如下：，定义如下： EA=|xAyA=AA IA=|xA例例9：设设A=1,2, 求求EA、IA。解：解：EA=, IA=,.19A上重要关系的实例上重要关系的实例(续续)小于等于关系小于等于关系 LA, 整除关系整除关系DB, P(A)上的上的包含关系包含关系R 定义：定义： LA=| x,yAxy, A R，R为实数集合为实数集合 DB=| x,yBx整除整除y, B Z*, Z*为非为非0整数集整数集

9、R =| x,yP(A)x y, A是集合族是集合族.类似的还可以定义大于等于关系类似的还可以定义大于等于关系, 小于关系小于关系, 大于关大于关系系, 真包含关系等等真包含关系等等. 20实例实例例例10：如如 A = 1, 2, 3, B =a, b, 则则 LA=, DA=, A=P(B)=,a,b,a,b, 则则 A上的包含关系是上的包含关系是 R =, ,21关系的表示关系的表示表示方式：表示方式：p关系的集合表达式：关系的集合表达式：p关系矩阵关系矩阵：若：若A=x1, x2, , xm， B=y1, y2, , yn， R是从是从A到到B的关系，的关系，R的关系矩阵是布尔矩阵的关

10、系矩阵是布尔矩阵MR = rij m n, 其中其中 rij = 1 R. 22关系的表示关系的表示p关系图关系图：若：若A= x1, x2, , xm，R是是A上的关系，上的关系，R 的关系图是的关系图是GR=, 其中其中A为结点为结点 集，集，R为边集为边集.如果如果属于关系属于关系R，在，在 图中就有一条从图中就有一条从 xi 到到 xj 的有向边的有向边. 注意：注意：A, B为有穷集，关系矩阵适于表示从为有穷集，关系矩阵适于表示从A到到B的的 关系或者关系或者A上的关系，关系图适于表示上的关系，关系图适于表示A上的上的 关系。关系。23实例实例A=1,2,3,4, R=,R的关系矩阵

11、的关系矩阵MR和关系图和关系图GR如下：如下：0010000011000011RM例例1124l基本运算定义基本运算定义l定义域、值域、域定义域、值域、域l逆、合成、限制、像逆、合成、限制、像l基本运算的性质基本运算的性质l幂运算幂运算l定义定义l求法求法l性质性质4.2 关系的运算关系的运算25关系的运算关系的运算域域定义定义4.8 关系关系R的的定义域定义域、值域值域 和和域域分别是分别是 domR = x | y ( R) ranR = y | x ( R) fldR = domR ranR 例例12 R=, 则则 domR=1, 2, 4 ranR=2, 3, 4 fldR=1, 2,

12、 3, 4 26例例13 设设A=a，b，c，d，e，B=1，2，3， R=，求，求R的的 定义域和值域。定义域和值域。关系的运算关系的运算域域解解 : domR = a，b，c， ranR = 2，3。27关系的运算关系的运算域域例例14 分别求以下关系的定义域和值域。分别求以下关系的定义域和值域。 (1) 1,Rx y x yZxy(2) 222,1Rx y x yZxy(3) 3,2Rx y x yZyx(4) 4,3Rx y x yZxy28关系的运算关系的运算域域22domran0,1, 1RR解：解： 11domranRRZ3domRZ3ran |2Rt tkkZ 即偶数集 44d

13、omran3, 3RR29关系的运算关系的运算域域例例15：A=1，2，3，4，B=5，6，7， R=，R的图解如图所示：的图解如图所示：domRranR30关系的运算关系的运算逆和合成逆和合成定义定义4.9 关系关系R的逆、的逆、关系关系R与关系与关系S的的合成合成定义为：定义为： R 1 = | R R S = | | z ( S R) 31关系的运算关系的运算逆和合成逆和合成例例16 设设R=, , , ， S=, , , , ， 求求R-1,R S,S R.R. 解：解：R R 1 1=, , , =, , , R R S S =, , , =, , , S S R R =, , =,

14、 , 32合成运算的图示方法合成运算的图示方法 利用图示利用图示(不是关系图不是关系图)方法求合成方法求合成R=, , , S=, , , , R S =, , , S R =, , 33逆和合成运算的矩阵方法逆和合成运算的矩阵方法0000000001101010RM0000011001000101SM00010010001100001RM0000000001100100RsM=MR*Ms，元元素和为逻辑素和为逻辑和。和。34例例 设设R，S关系为：关系为： R=, ， S=，, 求求S R。35合成运算的图示方法合成运算的图示方法例例17 A=1，2，3，4，B=3，5，7，C=1，2，3，

15、 S=， R =，求，求R S图解图解,如图所示：如图所示：R S = ， 。36例例18 设设R，S都是都是A上的关系，上的关系，A=1，2，3，4。S=，R=，即，即R为为A上的恒等上的恒等关系，则关系，则R S=S R= S 。求求R S关系图关系图,如图所示：如图所示：R S = S R = S。124337限制与像限制与像定义定义4.9 F 在在A上的上的限制限制 F A = | xFy x A A 在在F下的下的像像 FA = ran(F A) 38限制与像限制与像例例19 R=, , , 求：求：R 1、R1、 R 、R1,2。 R 1=, R1=2,4 R = R1,2=2,3

16、,4注意：注意：F A F, FA ranF 39关系基本运算的性质关系基本运算的性质 定理定理1 设设F、G、H是任意的关系是任意的关系, 则则 (1) (F 1) 1=F (2) domF 1=ranF, ranF 1=domF (3) (F G) H=F (G H) (4) (F G) 1= G 1 F 1 40关系基本运算的性质关系基本运算的性质 证明：证明：(1) 任取任取, 由逆的定义有由逆的定义有 (F 1) 1 F 1 F 所以有所以有 (F 1) 1=F (2) 任取任取x, xdomF 1 y(F 1) y(F) xranF 所以有所以有domF 1= ranF. 同理可证

17、同理可证 ranF 1 = domF.41关系基本运算的性质关系基本运算的性质(续续)定理定理2 设设F F、G G、H H为任意的关系，则有为任意的关系，则有 （1 1）F F (G(GH) = FH) = F G G F F H; H; （2) F2) F (G(GH) H) F F G G F F H;H; (3) (GH) (3) (GH) F = GF = G FHFH F; F; (4) (GH) (4) (GH) F F G G FHFH F F。P47: P47: 量词分配等值式量词分配等值式42A上关系的幂运算上关系的幂运算设设R为为A上的关系上的关系, n为自然数为自然数,

18、 则则 R 的的 n次幂次幂定义为：定义为： (1) R0= | xA =IA (2) Rn+1 = Rn R 注意：注意： 对于对于A上的任何关系上的任何关系R1和和R2都有都有 R10 = R20 = IA 对于对于A上的任何关系上的任何关系 R 都有都有 R1 = R 43幂的求法幂的求法对于集合表示的关系对于集合表示的关系R，计算，计算 Rn ：1）关系图表示，即）关系图表示，即n个个R的复合，的复合，2）矩阵表示，即）矩阵表示，即n个矩阵相乘个矩阵相乘, 其中相加采用逻辑其中相加采用逻辑 加加. 例例20 设设A=a,b,c,d, R=, 求求R的各次幂的各次幂, 分别用矩阵和关系图

19、表分别用矩阵和关系图表 示示.44幂的求法幂的求法解解 R与与R2的关系矩阵分别为：的关系矩阵分别为： 0000100001010010M 0000000010100101000010000101001000001000010100102M45同理，同理，R0=IA, R3和和R4的矩阵分别是：的矩阵分别是：因此因此M4=M2, 即即R4=R2. 因此可以得到因此可以得到R2=R4=R6=, R3=R5=R7= 0000000010100101,000000000101101043MM 10000100001000010M幂的求法幂的求法(续续)46R0, R1, R2, R3,的关系图如下图所示的关系图如下图所示幂的求法幂的求法(续续)47幂运算的性质幂运算的性质定理定理3 设设A为为n元集元集, R是是A上的关系上的关系, 则存在自然则存在自然数数 s 和和 t, 使得使得 Rs = Rt.22n证明：证明：R为为A上的关系上的关系, 由于由于|A|=n, A上的不同关上的不