《离散数学教学课件 ppt 作者 陈志奎 第四章 二元关系》由会员分享，可在线阅读，更多相关《离散数学教学课件 ppt 作者 陈志奎 第四章 二元关系（100页珍藏版）》请在金锄头文库上搜索。
1、,第四章 二元关系,离散数学 陈志奎主编 人民邮电出版社,前言,在日常生活中，我们都十分熟悉关系这个词的含义，例如夫妻关系，同事关系，上下级关系，位置关系等。在数学中，关系可表达集合中元素间的联系。在计算机科学中，关系的概念也具有重要意义。例如，数字计算机的逻辑设计和时序设计中，都应用了等价关系和相容关系的概念。在编译程序设计、讯息检索、数据结构等领域中，关系的概念都是不可缺少的，常常使用复合数据结构，诸如阵列、表格或者树去表达数据集合。而这些数据集合的元素间往往存在着某种关系。在算法分析和程序结构中，关系的概念起着重要作用。与关系相联系着的，是对客体进行比较，这些被比较的客体当然是有关系的。
2、根据比较结果的不同，计算机将去执行不同的任务。,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 是序偶的第二元素。 与集合不同，序偶是元素顺序相关的概念，即 ，而两个序偶相等的充要条件是两个序偶的第一
3、元素相等且第二元素相等，即 例如集合 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 重序元。例如，三重序元是一个序偶，它的第一元素是一个序偶，一般
4、记作, 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 多重序元与笛卡尔乘积,由排列组合的知识不难证明，如果 ， ，则 。
5、笛卡儿乘积运算具有以下性质。 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个集合的笛卡尔乘积来说
6、，同理可有,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 设集
7、合 ，试给出集合 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,
8、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 关系的运算,关系作为序偶的集合，集
9、合的运算并、交、相对补、绝对补和对称差都可以作为关系的运算。除此之外，关系特有的基本运算还有以下七种。,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 中每个序偶的第一元素同第二元素交换后所得到
10、的关系称为 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 是任意关
