离散数学第四章 二元关系

《离散数学第四章 二元关系》由会员分享，可在线阅读，更多相关《离散数学第四章 二元关系（100页珍藏版）》请在金锄头文库上搜索。

1、,第四章 二元关系,离散数学 陈志奎主编 人民邮电出版社,前言,在日常生活中，我们都十分熟悉关系这个词的含义，例如夫妻关系，同事关系，上下级关系，位置关系等。在数学中，关系可表达集合中元素间的联系。在计算机科学中，关系的概念也具有重要意义。例如，数字计算机的逻辑设计和时序设计中，都应用了等价关系和相容关系的概念。在编译程序设计、讯息检索、数据结构等领域中，关系的概念都是不可缺少的，常常使用复合数据结构，诸如阵列、表格或者树去表达数据集合。而这些数据集合的元素间往往存在着某种关系。在算法分析和程序结构中，关系的概念起着重要作用。与关系相联系着的，是对客体进行比较，这些被比较的客体当然是有关系的。

2、根据比较结果的不同，计算机将去执行不同的任务。,2018/9/12,2,多重序元与笛卡尔乘积,主要内容,PART 01,关系的基本概念,PART 02,关系的运算,PART 03,关系的性质,PART 04,关系的表示,PART 05,关系的闭包运算,PART 06,特殊关系,PART 07,关系型数据库,PART 08,2018/9/12,3,4.1 多重序元与笛卡尔乘积,定义4.1 由两个元素 x 和 y 按一定顺序排列成的二元组叫作序偶或有序对，记作，其中 x 是序偶的第一元素， y 是序偶的第二元素。与集合不同，序偶是元素顺序相关的概念，即 ，而两个序偶相等的充要条件是两个序偶的第一元

3、素相等且第二元素相等，即 例如集合 1 , 2 和 2 , 1 表示同一个集合，而 和 则表示平面上不同的点，即不同的序偶。,4,序偶,2018/9/12,4.1 多重序元与笛卡尔乘积,例4.1 已知 ，求 x 和 y 。 解：由序偶相等的充要条件可得解得 x = 3 , y = -2 。应该指出的是，序偶 两个元素不一定来自同一个集合，他们可以代表不同类型的事务。例如，a 代表操作码，b 代表地址码，则序偶 就代表一条单址指令。,5,序偶,2018/9/12,4.1 多重序元与笛卡尔乘积,把序偶的概念加以推广，可以定义 n 重序元。例如，三重序元是一个序偶，它的第一元素是一个序偶，一般记作,

4、 z ，为方便起见把它简记为 。 依此类推， 重序元是一个序偶，它的第一元素是 (n-1)重序元，并可记作 。给定两个 n 重序元 和 ，于是可有因此可把 n 重序元改写成 ，其中第 i 个元素通常称作 n 重序元的第 i 个坐标。,6,序偶,2018/9/12,4.1 多重序元与笛卡尔乘积,定义4.2 设 A 和 B 是任意两个集合。若序偶的第一元素是 A 的一个元素，第二元素是 B 的一个元素，则所有这样的序偶集合，称为 A 和 B 的笛卡儿乘积，记作 A x B ，即,7,笛卡尔乘积,2018/9/12,4.1 多重序元与笛卡尔乘积,由排列组合的知识不难证明，如果 ， ，则 。 笛卡儿乘

5、积运算具有以下性质。 1对任意集合 A ，根据定义有一般来说，笛卡儿乘积运算不满足交换律，即（当 时）,8,笛卡尔乘积,2018/9/12,4.1 多重序元与笛卡尔乘积,笛卡儿乘积运算具有以下性质。 3笛卡儿乘积运算不满足结合律，即,9,笛卡尔乘积,2018/9/12,4.1 多重序元与笛卡尔乘积,笛卡儿乘积运算具有以下性质。 4笛卡儿乘积运算对并和交运算满足分配率，即 （1） （2） （3） （4）5 .,10,笛卡尔乘积,2018/9/12,4.1 多重序元与笛卡尔乘积,设 是加标集合，与 A 对应的指标集合是集合 的笛卡儿乘积可以表示成例如： 对于n个集合的笛卡尔乘积来说，同理可有,11

6、,笛卡尔乘积,2018/9/12,多重序元与笛卡尔乘积,主要内容,PART 01,关系的基本概念,PART 02,关系的运算,PART 03,关系的性质,PART 04,关系的表示,PART 05,关系的闭包运算,PART 06,特殊关系,PART 07,关系型数据库,PART 08,2018/9/12,12,4.2 关系的基本概念,定义4.3 设 且 为 n 个任意集合，若集合 ，则称 R 为 间的 n 元关系；当 n = 2 ，则称 R 为 到 的二元关系，简称关系；若 ，则称 R 为空关系；若 ，则称 R 为全关系；若 ，则称 R 为 A上的 n 元关系。例4.4 设集合 ，试给出集合

7、A 上的小于或等于关系，大于或等于关系。 解：令集合 A 上的小于或等于关系为 ，大于或等于关系为 ，根据定义4.1应有：,13,2018/9/12,4.2 关系的基本概念,例4.5 令 根据上面的定义可知， 是 上的一元关系， 是 上的二元关系， 是 上的三元关系。 若序偶 属于 ，则记作 或 ，否则记作 或 。,14,2018/9/12,4.2 关系的基本概念,定义4.4 设 为 间的 n 元关系， 为 间的 n 元关系，如果 （1）n = m ； （2）若 ，则 ； （3）把 和 作为集合看， 则称 n 元关系 和 m 元关系 相等，记作 。,15,2018/9/12,4.2 关系的基本

8、概念,定义4.5 对任意集合 A ，定义 A 上的全域关系 和 A 上的等价关系 为：,16,2018/9/12,4.2 关系的基本概念,例4.7 设 ，求以下关系 （1） （2） （3） （4） 解： （1） （2） （3） （4）,17,2018/9/12,多重序元与笛卡尔乘积,主要内容,PART 01,关系的基本概念,PART 02,关系的运算,PART 03,关系的性质,PART 04,关系的表示,PART 05,关系的闭包运算,PART 06,特殊关系,PART 07,关系型数据库,PART 08,2018/9/12,18,4.3 关系的运算,关系作为序偶的集合，集合的运算并、交、相

9、对补、绝对补和对称差都可以作为关系的运算。除此之外，关系特有的基本运算还有以下七种。,19,2018/9/12,4.3 关系的运算,定义4.6 设 R 是二元关系 （1）R 中所有序偶的第一元素构成的集合称为 R 的定义域，记作 ，其形式化表示为 （2）R 中所有序偶的第二元素构成的集合称为 的值域，记作 ，其形式化表示为 （3）R 的定义域和值域的并集称为R的域，记作 ，其形式化表示为,20,2018/9/12,4.3 关系的运算,例4.8 ，则,21,2018/9/12,4.3 关系的运算,定义4.7 设 R 是二元关系，将 R 中每个序偶的第一元素同第二元素交换后所得到的关系称为 R 的逆关系，简称 R 的逆，记作 ，其形式化表示为定义4.8 设 F，G 为二元关系，G 对 F 的右合成记作 ，其形式化定义为,22,2018/9/12,4.3 关系的运算,例4.9 设 ， ，则类似的也可以定义关系的左合成，即,23,2018/9/12,4.3 关系的运算,定义4.9 设 R 是二元关系，A 是集合 （1）R 在 A上的限制记作 ，其形式化定义为（2）R 在 A下的像记作 ，其形式化定义为不难看出 是 R 的子关系，而 是 的子集。,24,