二元关系(I).ppt

二元关系 有序对与笛卡儿积 定义7.1 由两个元素x和y（允许x=y）按一定顺序排列成的二元组叫做一个有序对或序偶，记作x,y，其中x是它的第一元素，y是它的第二元素。 有序对x,y具有以下性质： （1）当x≠y时，x,y≠y,x。 （2）x,y＝u,v的充分必要条件是x＝u且y＝v。 笛卡儿积的定义 定义7.2 设A，B为集合,用A中元素为第一元素，B中元素为第二元素构成有序对。所有这样的有序对组成的集合叫做A和B的笛卡儿积，记作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。 （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为任意集合，判断一下等式是否成立。 （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) 二元关系 常用的关系 定义 对任意集合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。 整除关系：DA={x,y|x,y∈A∧x整除y}，其中 A?Z* Z*是非零整数集 包含关系：R?＝{x,y|x,y∈A∧x?y}，其中 A是集合族。 例 设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} 关系的表示方法 关系的三种表示方法： 集合表达式 关系矩阵 关系图 关系矩阵和关系图可以表示有穷集上的关系。 关系矩阵和关系图的定义 关系矩阵和关系图的实例 关系的运算 定义 设R是二元关系。 (1)R中所有有序对的第一元素构成的集合称为R的定义域,记为dom R。形式化表示为： dom R ＝ {x | ?y(x,y∈R )} (2)R中所有有序对的第二元素构成的集合称为R的值域，记作ran R。形式化表示为 ran R＝{y | ? x(x,y∈R)} (3)R的定义域和值域的并集称为R的域，记作fld R。形式化表示为 fld R＝dom R ∪ ran R 关系的逆和右复合运算 定义 设R为二元关系，R的逆关系，简称R的逆，记作R-1,其中 R-1＝{y,x|x,y∈R} 定义 设F,G为二元关系，F 和G的合成记作F?G，其中 F?G＝{x,y | ?t(x,t∈G∧t,y∈F)} 例 设F＝{3,3,6,2},G={2,3}，则 F-1 ＝{3,3,2,6} F?G＝{2,3} G?F＝{6,3} 关系的限制和像 定义