离散数学教学课件-ch7.pptVIP

第七章 二元关系 主要内容 有序对与笛卡儿积 关系的运算、性质、闭包 等价关系与划分 偏序关系 7.1 有序对与笛卡儿积 定义1 由两个元素 x 和 y按照一定顺序排列而成的二元组称为有序对（序偶），记作x, y或(x, y). 注: (1) x, y中允许x=y (2)当x?y时，x,y?y,x (3) x,y=u,v当且仅当 x=u，y=v (4)有序对之间不能比较大小. 笛卡儿积 定义2 设A, B为集合，称集合 A?B = {x,y| x?A?y?B}为A和B的笛卡儿积. 笛卡儿积的性质 (1) A?? = ??B = ? (2) A?B ? B?A (A?B, A??, B??) (3) (A?B)?C ? A?(B?C) (A??, B??, C??) (4) 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) (5) 若|A| = m, |B| = n, 则|A?B| = mn. 性质证明 证明 A?(B?C) = (A?B)?(A?C) 实例 例2 设A,B,C,D为任意集合, 判断以下命题是否为真 (1) (A∩B)?(C∩D)= (A?C)∩(B?D) (2) (A∪B)?(C∪D)= (A?C)∪(B?D) (3) (A?B)?(C?D)= (A?C)?(B?D) (4) (A?B)?(C?D)= (A?C)?(B?D) 实例 例2 设A,B,C,D为任意集合, 判断以下命题是否为真 (1) (A∩B)?(C∩D)= (A?C)∩(B?D) (2) (A∪B)?(C∪D)= (A?C)∪(B?D) (3) (A?B)?(C?D)= (A?C)?(B?D) (4) (A?B)?(C?D)= (A?C)?(B?D) 实例 例2 设A,B,C,D为任意集合, 判断以下命题是否为真 (1) (A∩B)?(C∩D)= (A?C)∩(B?D) (2) (A∪B)?(C∪D)= (A?C)∪(B?D) (3) (A?B)?(C?D)= (A?C)?(B?D) (4) (A?B)?(C?D)= (A?C)?(B?D) 实例 例2 设A,B,C,D为任意集合, 判断以下命题是否为真 (1) (A∩B)?(C∩D)= (A?C)∩(B?D) (2) (A∪B)?(C∪D)= (A?C)∪(B?D) (3) (A?B)?(C?D)= (A?C)?(B?D) (4) (A?B)?(C?D)= (A?C)?(B?D) 7.2 二元关系 定义1 (1) 若集合中所有元素都是有序对, 则称此集合为二元关系, 简称关系，记作R. 若x,y∈R, 可记作xRy； 问：若|A|=n, 则A上有多少种关系？ 例1. A={微积分, 线性代数, 离散数学, 英语} B={5, 4, 4.5, 2} R={x,y|课程x的学分为y} 若A?R, 可以定义以下关系： L={x,y|x,y?A ? xy} A上的小于关系 L≤={x,y|x,y?A ? x?y} A上的小于等于关系 关系的表示 (2) 设A= {x1, x2, …, xn}，以A中元素为顶点, 若 xi , xj ?R，则从 xi 向 xj 引有向边，所得的有向图为R的关系图, 记作GR. 实例 例2 设A={1,2,3,4}, R={1,1,1,2,2,3,2,4,4,2}, 求R的关系矩阵MR和关系图GR. 7.3 关系的运算 定义1 设R是二元关系. (1) R中所有有序对的第一个元素构成的集合称为R的定义域, 记作domR (2) R中所有有序对的第二个元素构成的集合称为R的值域, 记作ranR (3) domR ? ranR = fldR, 称为R的域 关系运算 定义2 设R为二元关系. R的逆(关系) R?1 = { y, x | x, y?R } 性质1 设R为二元关系. (1) (R?1)?1 = R (2) domR?1 = ranR ranR?1 = domR 定义3 设F, G为二元关系, G对F的右复合 F?G = { x, y | ? t ( x, t ?F ? t, y ?G) } 例2 R = {1,2, 2,3, 1,4, 2,2} S = {1,1,