CH07二元关系.ppt

本章说明 本章内容 7.1 有序对与笛卡儿积 7.2 二元关系 7.3 关系的运算 7.4 关系的性质 7.5 关系的闭包 7.6 等价关系与划分 7.7 偏序关系 本章小结 习题 作业 7.1 有序对与笛卡儿积 定义7.1 由两个元素x和y（允许x=y）按一定顺序排列成的二元组叫做一个有序对(ordered pair)或序偶，记作x,y，其中x是它的第一元素，y是它的第二元素。 有序对x,y具有以下性质： （1）当x≠y时，x,y≠y,x。 （2）x,y＝u,v的充分必要条件是x＝u且y＝v。 例7.1 笛卡儿积的定义 定义7.2 设A，B为集合,用A中元素为第一元素，B中元素为第二元素构成有序对。所有这样的有序对组成的集合叫做A和B的笛卡儿积(Cartesian product)，记作A×B。 笛卡儿积的符号化表示为 A×B＝{x,y|x∈A∧y∈B} 笛卡尔积举例 笛卡儿积的运算性质 (1)对任意集合A，根据定义有 A×?＝?, ?×A＝? (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?C ∧ B?D ? A×B ? C×D 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) 关于A?C∧B?D ? A×B?C×D的讨论 该性质的逆命题不成立，可分以下情况讨论。 （1）当A=B=?时，显然有A?C 和 B?D 成立。 （2）当A≠?且B≠?时，也有A?C和B?D成立，证明如下： 任取x∈A，由于B≠?,必存在y∈B,因此有 x∈A∧y∈B ? x,y∈A×B ? x,y∈C×D ? x∈C∧y∈D ? x∈C 从而证明了 A?C。 同理可证 B?D。 关于A?C∧B?D ? A×B?C×D的讨论 该性质的逆命题不成立，可分以下情况讨论。 （3）当A＝?而B≠?时，有A?C成立，但不一定有B?D成立。 反例：令A＝?,B＝{1},C＝{3},D＝{4}。 （4）当A≠?而B＝?时，有B?D成立，但不一定有A?C成立。 反例略。 从上述的讨论得到的结论是： 设集合A，B，C,D为四个非空集合，则A×B?C×D 的充要条件是 A?C∧B?D。（证明略） 例7.2 例7.3 7.2 二元关系(binary relation) 7.2 二元关系 常用的关系 定义7.5 对任意集合A，定义 全域关系 EA={x,y|x∈A∧y∈A}=A×A 恒等关系 IA={x,x|x∈A} 空关系 ? 其它常用的关系 小于或等于关系：LA={x,y|x,y∈A∧x≤y}，其中 A?R。 整除关系：DB={x,y|x,y∈B∧x整除y}，其中 B?Z* Z*是非零整数集 包含关系：R?＝{x,y|x,y∈A∧x?y}，其中 A是集合族。 例7.4 例7.4 设A={1,2,3,4}，下面各式定义的R都是A上的关系，试用列元素法表示R。 (1) R={x,y | x是y的倍数}(2) R={x,y | (x-y)2∈A}(3) R={x,y | x/y是素数}(4) R={x,y | x≠y} 关系的表示方法 关系的三种表示方法： 集合表达式 关系矩阵 关系图 关系矩阵和关系图可以表示有穷集上的关系。 关系矩阵和关系图的定义 关系矩阵和关系图的实例 7.3 关系的运算 定义7.6 设R是二元关系。 (1)R中所有有序对的第一元素构成的集合称为R的定义域(domain)，记为dom R。形式化表示为： dom R ＝ {x | ?y(x,y∈R )} (2)R中所有有序对的第二元素构成的集合称为R的值域(range) ，记作ran R。形式化表示为 ran R＝{y | ? x(x,y∈R)} (3)R的定义域和值域的并集称为R的域(field)，记作fld R。形式化表示为 fld R＝dom R ∪ ran R 关系的逆和右复合运算