[理学]二元关系与函数.ppt

第四章 二元关系和函数 §4.1 集合的笛卡儿集与二元关系 1. 有序对 定义4.1 由两个元素 x 和 y，按照一定的顺序组成的二元组称为有序对（序偶），记作x,y. 有序对性质: (1) 有序性 x,y?y,x （当x?y时） (2) x,y=u,v ? x=u?y=v. 定义4.1 n元有序组 x1, x2 ,…. , xn = x1, x2 ,…. , xn-1 , xn 2. 笛卡儿积 定义4.3 集合A与B的笛卡儿积记作A?B， A?B = {x,y| x?A?y?B}. 例1 求集合的笛卡儿积 1） A={1,2}, B={a,b}；求A?B， B?A 2）A={?}, B =?；求P(A)?A ， P(A)?B 集合笛卡儿积的计数 若 |A| = m, |B| = n, 则 |A?B| = mn 笛卡儿积的性质 不适合交换律 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 ? C ? B ? D ? (A?B） ? (C?D) 笛卡儿积的推广 A1? A2? …? An ; An 3. 实例 例2 (1) 证明 A=B,C=D ? A?C=B?D (2) A?C = B?D是否推出 A=B,C=D? 为什么？ 例3 已知A、B、C是任意集合 (1)证明 (A ? B)?(C ? D) = (A?C) ?(B?D) (2)说明 (A ? B)?(C ? D) = (A?C) ?(B?D) (A － B)?(C－ D) = (A?C) －(B?D) (A ? B)?(C ? D) = (A?C) ?(B?D) 不成立。 4. 二元关系 定义4.5 如果一个集合满足以下条件之一： (1) 集合非空, 且它的元素都是有序对 (2) 集合是空集 则称该集合为一个二元关系, 简称为关系，记作R. 记号：x,y∈R, 记作xRy； x,y?R, 记作 定义4.6 设A,B为集合, A×B的任何子集所定义的二元关系叫做从A到B的二元关系, 当A=B时则叫做A上的二元关系. 集合A上关系的计数: 若|A|=n, A上有 个不同的二元关系. 定义4.7 设 A 为集合, 空关系 ?是A上的关系，称为空关系 全域关系 EA = {x,y| x∈A∧y∈A} = A×A 恒等关系 IA = {x,x| x∈A} 小于等于关系 LA = {x,y| x,y∈A∧x≤y}, A为实数子集 整除关系 DB = {x,y| x,y∈B∧x整除y}, A为非0整数子集 包含关系 R? = {x,y| x,y∈A∧x?y}, A是集合族. 例4 已知集合A={1, 2}, 求全域关系、恒等关系、小于等于关系和整除关系. 例5 已知 B = {a,b}, 求P(B)上的包含关系R? . 类似的还可以定义：大于等于关系, 小于关系, 大于关系, 真包含关系等. 5. 关系的表示 1. 关系矩阵 若A={x1, x2, …, xm}，B={y1, y2, …, yn}，R是从A到B的关系，R的关系矩阵是布尔矩阵MR = [ rij ] m?n, 其中rij = 1? xi, yj ?R. 2. 关系图 若A= {x1, x2, …, xm}，R是从A上的关系，R的关系图是GR=V, E, 其中V为顶点集，E为边集. 如果xi,xj属于关系R，在图中就有一条从 xi 到 xj 的有向边. 注意： 关系矩阵适合表示从A到B的关系或A上的关系（A,B为有穷集） 关系图适合表示有穷集A上的关系 §4.2 关系的运算 1. 关系的基本运算 定义4.8 关系的