,第四章 二元关系,离散数学 陈志奎主编 人民邮电出版社,前言,在日常生活中，我们都十分熟悉关系这个词的含义，例如夫妻关系，同事关系，上下级关系，位置关系等。在数学中，关系可表达集合中元素间的联系。在计算机科学中，关系的概念也具有重要意义。例如，数字计算机的逻辑设计和时序设计中，都应用了等价关系和相容关系的概念。在编译程序设计、讯息检索、数据结构等领域中，关系的概念都是不可缺少的，常常使用复合数据结构，诸如阵列、表格或者树去表达数据集合。而这些数据集合的元素间往往存在着某种关系。在算法分析和程序结构中，关系的概念起着重要作用。与关系相联系着的，是对客体进行比较，这些被比较的客体当然是有关系的。根据比较结果的不同，计算机将去执行不同的任务。,2019/5/25,2,多重序元与笛卡尔乘积,主要内容,PART 01,关系的基本概念,PART 02,关系的运算,PART 03,关系的性质,PART 04,关系的表示,PART 05,关系的闭包运算,PART 06,特殊关系,PART 07,关系型数据库,PART 08,2019/5/25,3,4.1 多重序元与笛卡尔乘积,定义4.1 由两个元素 x 和 y 按一定顺序排列成的二元组叫作序偶或有序对，记作，其中 x 是序偶的第一元素， y 是序偶的第二元素。 与集合不同，序偶是元素顺序相关的概念，即 ，而两个序偶相等的充要条件是两个序偶的第一元素相等且第二元素相等，即 例如集合 1 , 2 和 2 , 1 表示同一个集合，而 和 则表示平面上不同的点，即不同的序偶。,4,序偶,2019/5/25,4.1 多重序元与笛卡尔乘积,例4.1 已知 ，求 x 和 y 。 解：由序偶相等的充要条件可得 解得 x = 3 , y = -2 。 应该指出的是，序偶 两个元素不一定来自同一个集合，他们可以代表不同类型的事务。例如，a 代表操作码，b 代表地址码，则序偶 就代表一条单址指令。,5,序偶,2019/5/25,4.1 多重序元与笛卡尔乘积,把序偶的概念加以推广，可以定义 n 重序元。例如，三重序元是一个序偶，它的第一元素是一个序偶，一般记作, z ，为方便起见把它简记为 。 依此类推， 重序元是一个序偶，它的第一元素是 (n-1)重序元，并可记作 。给定两个 n 重序元 和 ，于是可有 因此可把 n 重序元改写成 ，其中第 i 个元素通常称作 n 重序元的第 i 个坐标。,6,序偶,2019/5/25,4.1 多重序元与笛卡尔乘积,定义4.2 设 A 和 B 是任意两个集合。若序偶的第一元素是 A 的一个元素，第二元素是 B 的一个元素，则所有这样的序偶集合，称为 A 和 B 的笛卡儿乘积，记作 A x B ，即,7,笛卡尔乘积,2019/5/25,4.1 多重序元与笛卡尔乘积,由排列组合的知识不难证明，如果 ， ，则 。 笛卡儿乘积运算具有以下性质。 1对任意集合 A ，根据定义有 一般来说，笛卡儿乘积运算不满足交换律，即 （当 时）,8,笛卡尔乘积,2019/5/25,4.1 多重序元与笛卡尔乘积,笛卡儿乘积运算具有以下性质。 3笛卡儿乘积运算不满足结合律，即,9,笛卡尔乘积,2019/5/25,4.1 多重序元与笛卡尔乘积,笛卡儿乘积运算具有以下性质。 4笛卡儿乘积运算对并和交运算满足分配率，即 （1） （2） （3） （4） 5 .,10,笛卡尔乘积,2019/5/25,4.1 多重序元与笛卡尔乘积,设 是加标集合，与 A 对应的指标集合是集合 的笛卡儿乘积可以表示成 例如： 对于n个集合的笛卡尔乘积来说，同理可有,11,笛卡尔乘积,2019/5/25,多重序元与笛卡尔乘积,主要内容,PART 01,关系的基本概念,PART 02,关系的运算,PART 03,关系的性质,PART 04,关系的表示,PART 05,关系的闭包运算,PART 06,特殊关系,PART 07,关系型数据库,PART 08,2019/5/25,12,4.2 关系的基本概念,定义4.3 设 且 为 n 个任意集合，若集合 ，则称 R 为 间的 n 元关系；当 n = 2 ，则称 R 为 到 的二元关系，简称关系；若 ，则称 R 为空关系；若 ，则称 R 为全关系；若 ，则称 R 为 A上的 n 元关系。 例4.4 设集合 ，试给出集合 A 上的小于或等于关系，大于或等于关系。 解：令集合 A 上的小于或等于关系为 ，大于或等于关系为 ，根据定义4.1应有：,13,2019/5/25,4.2 关系的基本概念,例4.5 令 根据上面的定义可知， 是 上的一元关系， 是 上的二元关系， 是 上的三元关系。 若序偶 属于 ，则记作 或 ，否则记作 或 。,14,2019/5/25,4.2 关系的基本概念,定义4.4 设 为 间的 n 元关系， 为 间的 n 元关系，如果 （1）n = m ； （2）若 ，则 ； （3）把 和 作为集合看， 则称 n 元关系 和 m 元关系 相等，记作 。,15,2019/5/25,4.2 关系的基本概念,定义4.5 对任意集合 A ，定义 A 上的全域关系 和 A 上的等价关系 为：,16,2019/5/25,4.2 关系的基本概念,例4.7 设 ，求以下关系 （1） （2） （3） （4） 解： （1） （2） （3） （4）,17,2019/5/25,多重序元与笛卡尔乘积,主要内容,PART 01,关系的基本概念,PART 02,关系的运算,PART 03,关系的性质,PART 04,关系的表示,PART 05,关系的闭包运算,PART 06,特殊关系,PART 07,关系型数据库,PART 08,2019/5/25,18,4.3 关系的运算,关系作为序偶的集合，集合的运算并、交、相对补、绝对补和对称差都可以作为关系的运算。除此之外，关系特有的基本运算还有以下七种。,19,2019/5/25,4.3 关系的运算,定义4.6 设 R 是二元关系 （1）R 中所有序偶的第一元素构成的集合称为 R 的定义域，记作 ，其形式化表示为 （2）R 中所有序偶的第二元素构成的集合称为 的值域，记作 ，其形式化表示为 （3）R 的定义域和值域的并集称为R的域，记作 ，其形式化表示为,20,2019/5/25,4.3 关系的运算,例4.8 ，则,21,2019/5/25,4.3 关系的运算,定义4.7 设 R 是二元关系，将 R 中每个序偶的第一元素同第二元素交换后所得到的关系称为 R 的逆关系，简称 R 的逆，记作 ，其形式化表示为 定义4.8 设 F，G 为二元关系，G 对 F 的右合成记作 ，其形式化定义为,22,2019/5/25,4.3 关系的运算,例4.9 设 ， ，则 类似的也可以定义关系的左合成，即,23,2019/5/25,4.3 关系的运算,定义4.9 设 R 是二元关系，A 是集合 （1）R 在 A上的限制记作 ，其形式化定义为 （2）R 在 A下的像记作 ，其形式化定义为 不难看出 是 R 的子关系，而 是 的子集。,24,2019/5/25,4.3 关系的运算,例4.10 设 ，则 为了使关系运算表达式更为简洁，我们对关系运算的优先级作了进一步规定：首先，关系运算中的逆运算优先于其他运算，而所有关系特有的运算都优先于其从集合继承而得的运算，最后，对于没有规定优先权的运算以括号决定运算顺序。,25,2019/5/25,4.3 关系的运算,定理4.1 设 F 是任意关系，则 （1） （2） , 定理4.2 设 F，G，H 是任意关