离散数学的特点.ppt

* 第4章 二元关系与函数 4.1 集合的笛卡儿积与二元关系 4.2 关系的运算 4.3 关系的性质 4.4 关系的闭包 4.5 等价关系和偏序关系 4.6 函数的定义和性质 4.7 函数的复合和反函数 * 4.1 集合的笛卡儿积和二元关系 有序对 笛卡儿积及其性质 二元关系的定义 二元关系的表示 * 有序对 定义 由两个客体 x 和 y，按照一定的顺序组成的 二元组称为有序对，记作x,y 实例：点的直角坐标(3,?4) 有序对性质 有序性 x,y?y,x （当x? y时） x,y 与 u,v 相等的充分必要条件是 x,y=u,v ? x=u ? y=v 例1 2, x+5 = 3y? 4, y，求 x, y. 解 3y? 4 = 2, x+5 = y ? y = 2, x = ? 3 * 有序 n 元组 定义 一个有序 n (n?3) 元组 x1, x2, …, xn 是一个 有序对，其中第一个元素是一个有序 n-1元组，即 x1, x2, …, xn = x1, x2, …, xn-1, xn 当 n=1时, x 形式上可以看成有序 1 元组. 实例 n 维向量是有序 n元组. * 笛卡儿积 定义 设A,B为集合，A与B 的笛卡儿积记作A?B， 即 A?B ={ x,y | x?A ? y?B } 例2 A={1,2,3}, B={a,b,c} A?B ={1,a,1,b,1,c,2,a,2,b,2,c, 3,a,3,b,3,c} B?A ={a,1,b,1,c,1,a,2,b,2,c,2, a,3, b,3,c,3} A={?}, P(A)?A={?,?, {?},?} * 笛卡儿积的性质 不适合交换律 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)=(A?B)?(A?C) (B?C)?A=(B?A)?(C?A) 若A或B中有一个为空集，则A?B就是空集. A??=??B=? 若|A|=m, |B|=n, 则 |A?B|=mn * 性质的证明 证明 A?(B?C)=(A?B)?(A?C) 证 任取x,y x,y∈A×(B∪C)  ? x∈A∧y∈B∪C ? x∈A∧(y∈B∨y∈C)  ? (x∈A∧y∈B)∨(x∈A∧y∈C)  ? x,y∈A×B∨x,y∈A×C  ? x,y∈(A×B)∪(A×C) 所以有A×(B∪C) = (A×B)∪(A×C). * 例题 解 (1) 任取x,y x,y?A?C ? x?A ? y?C ? x?B ? y?D ? x,y?B?D 例3 (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. * 二元关系的定义 定义 如果一个集合满足以下条件之一： （1）集合非空, 且它的元素都是有序对 （2）集合是空集 则称该集合为一个二元关系, 简称为关系，记作R. 如x,y∈R, 可记作 xRy；如果x,y?R, 则记作x y 实例：R={1,2,a,b}, S={1,2,a,b}. R是二元关系, 当a, b不是有序对时，S不是二元关系 根据上面的记法，可以写 1R2, aRb, a c 等. * 从A到B的关系与A上的关系 定义 设A,B为集合, A×B的任何子集所定义的二元 关系叫做从A到B的二元关系, 当A=B时则叫做 A上 的二元关系. 例4 A={0,1}, B={1,2,3}, R1={0,2}, R2=A×B, R3=?, R4={0,1}. 那么 R1, R2, R3, R4是从 A 到 B 的二元关系, R3和R4同时也是 A上的二元关系. 计数 |A|=n, |A×A|=n2, A×A的子集有 个. 所以 A上有 个不同的二元关系