离散数学第四章二元关系.ppt

《离散数学第四章二元关系.ppt》由会员分享，可在线阅读，更多相关《离散数学第四章二元关系.ppt（100页珍藏版）》请在三一办公上搜索。

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

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

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

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

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

6、容,PART 01,关系的基本概念,PART 02,关系的运算,PART 03,关系的性质,PART 04,关系的表示,PART 05,关系的闭包运算,PART 06,特殊关系,PART 07,关系型数据库,PART 08,2023/11/16,12,4.2 关系的基本概念,定义4.3 设 且 为 n 个任意集合，若集合，则称 R 为 间的 n 元关系；当 n=2，则称 R 为 到 的二元关系，简称关系；若，则称 R 为空关系；若，则称 R 为全关系；若，则称 R 为 A上的 n 元关系。例4.4 设集合，试给出集合 A 上的小于或等于关系，大于或等于关系。解：令集合 A 上的小于或等于关系为

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

8、,4.2 关系的基本概念,例4.7 设，求以下关系（1）（2）（3）（4）解：（1）（2）（3）（4）,17,2023/11/16,多重序元与笛卡尔乘积,主要内容,PART 01,关系的基本概念,PART 02,关系的运算,PART 03,关系的性质,PART 04,关系的表示,PART 05,关系的闭包运算,PART 06,特殊关系,PART 07,关系型数据库,PART 08,2023/11/16,18,4.3 关系的运算,关系作为序偶的集合，集合的运算并、交、相对补、绝对补和对称差都可以作为关系的运算。除此之外，关系特有的基本运算还有以下七种。,19,2023/11/16,4.3 关系的

9、运算,定义4.6 设 R 是二元关系（1）R 中所有序偶的第一元素构成的集合称为 R 的定义域，记作，其形式化表示为（2）R 中所有序偶的第二元素构成的集合称为 的值域，记作，其形式化表示为（3）R 的定义域和值域的并集称为R的域，记作，其形式化表示为,20,2023/11/16,4.3 关系的运算,例4.8，则,21,2023/11/16,4.3 关系的运算,定义4.7 设 R 是二元关系，将 R 中每个序偶的第一元素同第二元素交换后所得到的关系称为 R 的逆关系，简称 R 的逆，记作，其形式化表示为定义4.8 设 F，G 为二元关系，G 对 F 的右合成记作，其形式化定义为,22,2023

10、/11/16,4.3 关系的运算,例4.9 设，则类似的也可以定义关系的左合成，即,23,2023/11/16,4.3 关系的运算,定义4.9 设 R 是二元关系，A 是集合（1）R 在 A上的限制记作，其形式化定义为（2）R 在 A下的像记作，其形式化定义为不难看出 是 R 的子关系，而 是 的子集。,24,2023/11/16,4.3 关系的运算,例4.10 设，则为了使关系运算表达式更为简洁，我们对关系运算的优先级作了进一步规定：首先，关系运算中的逆运算优先于其他运算，而所有关系特有的运算都优先于其从集合继承而得的运算，最后，对于没有规定优先权的运算以括号决定运算顺序。,25,2023/

11、11/16,4.3 关系的运算,定理4.1 设 F 是任意关系，则（1）（2）,定理4.2 设 F，G，H 是任意关系，则（1）（2）,26,2023/11/16,4.3 关系的运算,定理4.3 设 F，G 为任意关系，则（1）（2）定理4.4 设 R为 A上的关系，则,27,2023/11/16,4.3 关系的运算,定理4.5 设 F，G，H 为任意关系，则（1）（2）（3）（4）,28,2023/11/16,4.3 关系的运算,定理4.6 设 F 为关系，A，B 为集合，则,29,2023/11/16,4.3 关系的运算,上述的对关系的合成运算可以推广到一般情况。如果 是从 到 的关系，是

12、从 到 的关系，是从 到 的关系，则无括号表达式 表达了从 到 的关系。特别，当 和 时，也就是说当集合 A上的所有 都是同样的关系时，A 上的合成关系 可表达成，并称作关系R的幂。,30,2023/11/16,4.3 关系的运算,31,2023/11/16,4.3 关系的运算,32,2023/11/16,多重序元与笛卡尔乘积,主要内容,PART 01,关系的基本概念,PART 02,关系的运算,PART 03,关系的性质,PART 04,关系的表示,PART 05,关系的闭包运算,PART 06,特殊关系,PART 07,关系型数据库,PART 08,2023/11/16,33,4.4 关系

13、的性质,定义4.11 设 R 为集合 A上的二元关系（1）若对每个，皆有，则称 R 为自反的。其形式化表示为 R是自反的（2）若对每个，皆有，则称 R 为反自反的。其形式化表示为 R是反自反的（3）对任意的，若，则，就称 R 为对称的。其形式化表示为 R是对称的（4）对任意的，若，且，则x=y，就称 R 为反对称的。其形式化表示为 R是反对称的,34,2023/11/16,4.4 关系的性质,定义4.11 设 R 为集合 A上的二元关系（5）对任意的，若 且，则 就称 R 为可传递的。其形式化表示为 R是可传递的（6）存在，并且 而，则称 R 为不可传递的。其形式化表示为 R是不可传递的,35

14、,2023/11/16,4.4 关系的性质,例4.11 考虑自然数集合 上的普通相等关系“”，大于关系“”和大于等于关系“”，则显然有（1）“”关系是自反的、对称的、反对称的、可传递的。（2）“”关系是反自反的、反对称的、可传递的。（3）“”关系是自反的、反对称的、可传递的。例4.12 空集 R上的二元空关系显然是自反的、对称的、反对称的、反自反的、可传递的。,36,2023/11/16,4.4 关系的性质,定理4.10 设 R为 A 的二元关系，则（1）R 在 A上自反当且仅当（2）R 在 A 上反自反当且仅当（3）R 在 A 上对称当且仅当（4）R 在 A 上反对称当且仅当（5）R 在 A

15、 上可传递当且仅当,37,2023/11/16,多重序元与笛卡尔乘积,主要内容,PART 01,关系的基本概念,PART 02,关系的运算,PART 03,关系的性质,PART 04,关系的表示,PART 05,关系的闭包运算,PART 06,特殊关系,PART 07,关系型数据库,PART 08,2023/11/16,38,4.5 关系的表示,定义4.12 设 A 和 B为任意的非空有限集，R 为任意一个从A 到 B 的二元关系。以 中的每个元素为结点。对每个皆画一条从 x 到 y 的有向边，这样得到的一个图称为关系 的关系图。例4.14 设，从 A 到 B 的二元关系 R 为，于是有,39

16、,关系图,R的关系图,2023/11/16,4.5 关系的表示,可以看出关系图明确地反映了关系的某些性质。如果关系 是自反的，则每个结点上都有一条从自身出发又指向自身的环边；如果关系是反自反的，则任何结点上部没有带环的边；如果一个关系 既不是自反的，也不是反自反的，则在某些结点上有带环的边，而在某些结点上没有带环的边。如果关系是对称的，则从一个结点到另一个结点间必定有往返两条弧线。如果关系是反对称的，则在两个结点间只会存在单向弧线。,40,关系图,2023/11/16,4.5 关系的表示,图4.2给出了具有各种性质的关系的关系图。当集合中元素的数目较大时，关系的图解表示就不是很方便了，由于计算

17、机上表达矩阵并不困难，所以我们试图寻求关系的矩阵表示。,41,关系图,2023/11/16,4.5 关系的表示,定义4.13 给定两个有限集合 和，R 是从 X 到 Y 的二元关系。如果有则称 是 R 的关系矩阵，记作,42,关系图,2023/11/16,4.5 关系的表示,43,关系图,2023/11/16,4.5 关系的表示,44,关系图,2023/11/16,4.5 关系的表示,45,关系图,2023/11/16,4.5 关系的表示,46,关系图,2023/11/16,多重序元与笛卡尔乘积,主要内容,PART 01,关系的基本概念,PART 02,关系的运算,PART 03,关系的性质,

18、PART 04,关系的表示,PART 05,关系的闭包运算,PART 06,特殊关系,PART 07,关系型数据库,PART 08,2023/11/16,47,4.6 关系的闭包运算,前面我们已经介绍了如何使用关系的合成运算去构成新的关系，下面我们讨论如何由给定的关系 R 构成一个新的关系 并且 和 应具有某些性质。把确保这些性质的那些序偶补充到 R 中去就可构成。给定一个二元关系，它规定了局部的性质，希望求得的是具有全面性质的另一个二元关系。例如，由 R 构成一个可传递关系。在日常家族关系中也有类似的情形。如果 R是个父子关系，则 可能是个祖先关系；如果 R 是个子父关系，则 可能是个后代关

19、系。,48,2023/11/16,4.6 关系的闭包运算,定义4.14 给定集合 A，R 是 A上的二元关系。如果有另一个关系 满足（1）是自反的（对称的、可传递的）。（2）。（3）对于任何自反的(对称的、可传递的)关系，如果有，则，则称关系 为 的自反的（对称的，可传递的）闭包。并用 表示 的自反闭包，用 表示 的对称闭包，用 表示 的可传递闭包。,49,2023/11/16,4.6 关系的闭包运算,定理4.11 给定集合 X，R 是 X上的关系。于是可有（1）R是自反的当且仅当（2）R是对称的当且仅当（3）R是可传递的当且仅当 定理4.12 设 R 是 上的二元关系，则有（1）（2）（3）

20、,50,2023/11/16,4.6 关系的闭包运算,不难看出，整数集合中，小于关系“”的自反闭包是“”，对称闭包是不等关系“”；恒等关系 的自反闭包是；对称闭包是；不等关系“”的自反闭包是全域关系，对称闭包是不等关系“”；空关系的自反闭包是恒等关系，对称闭包是空关系。,51,2023/11/16,4.6 关系的闭包运算,例4.20 给定集合，和 是 A 上的关系，试求出 和，并画出相应的关系图来。解：关系 R，S 及其传递闭包，的关系图如图4.6所示。,52,2023/11/16,4.6 关系的闭包运算,定理4.13 设 X 是含有 n个元素的集合，R 是 X上的二元关系。于是可有例4.21

21、 设集合，R 是X中的二元关系，R 的关系图如图4.7所示，试画出 R 的可传递闭包 的关系图。解：R 的可传递闭包 的关系图如图4.8所示。,53,图4.7 R的关系图,图4.8 t(R)的关系图,2023/11/16,4.6 关系的闭包运算,定理4.15 设 A 是集合，R 是集合 A上的二元关系。于是可有（1）（2）（3）,54,2023/11/16,多重序元与笛卡尔乘积,主要内容,PART 01,关系的基本概念,PART 02,关系的运算,PART 03,关系的性质,PART 04,关系的表示,PART 05,关系的闭包运算,PART 06,特殊关系,PART 07,关系型数据库,PA

22、RT 08,2023/11/16,55,4.7 特殊关系,定义4.15 给定非空集合S，及非空集合，如果有（1）（2）则称集合A 是集合 S 的覆盖。例如，设集合，并且给定S 的各子集的集合 和；显然集合 A 和集合 B 都是集合 S 的覆盖。即覆盖不唯一。,56,集合的覆盖,2023/11/16,4.7 特殊关系,定义4.16 给定非空集合 S，及非空集，如果有（1）（2）或（3）则称集合A 是集合 的一个划分。划分中的元素 称为划分的类。如果划分是个有限集合，则划分的秩是划分的类的数目。若划分是个无限集合，则划分的秩是无限的。划分是覆盖的特定情况，即 A中元素互不相交的特定情况。,57,集

23、合的划分,2023/11/16,4.7 特殊关系,例如 设，试考察 S 的各子集的下列集合。显然集合 A和 B是S 的覆盖，当然 C，D，E 也都是 S的覆盖；同时 C，D，E 也还是 S 的划分，并且C 的秩是2，D 的秩是1，E 的秩是3；而F 既不是覆盖也不是划分；集合S 的最大划分是以S 的单个元素为类的划分，如上面的 E；S 的最小划分是以S 为类的划分，如上面的 D。,58,集合的划分和覆盖,2023/11/16,4.7 特殊关系,定义4.17 设 A和 是非空集合S 的两种划分，并可表示成 如果 的每一个类，都是A 的某一个类 的子集，则称划分 是划分 A 的加细，并说成是 加细

24、了A。如果 是A 的加细和，则称 是A 的真加细。划分全集 E的过程，可看成是在表达全集 E的文氏图上划出分界线的过程。设 A，B，C 是全集E 的三个子集。由 A，B 和 C生成的E 的划分的类，称为极小项或完全交集。对于三个子集 A，B 和C 来说，共有 个极小项，分别用 来表示。,59,集合的划分和覆盖,2023/11/16,4.7 特殊关系,由图4.可知并且 是互不相交的，一般情况，如果 是全集E 的 n个子集，则由这n 个子集能够生成 个极小项，分别用 来表示它们。这些极小项互不相交，并且并起来等于全集E。,60,集合的划分和覆盖,2023/11/16,4.7 特殊关系,定义4.18

25、 设 X是任意集合,R是集合X 中的二元关系。如果 R是自反的、对称的和可传递的，也就是说,如果有（1）（2）（3）则称 R 是等价关系。如果 R 是集合 A上的等价关系，则 R的定义域 是集合 A 自身，所以称 R 是定义于集合A 上的关系。实数集合中数的等于关系，全集的各子集间的相等关系，命题集合中等价命题间的恒等关系等，都是等价关系。,61,等价关系,2023/11/16,4.7 特殊关系,例4.22 给定集合，R 是 A上的二元关系，并且 R 给定成，试证明 R 是一个等价关系，并画出 R 的关系图和写出 R 的关系矩阵。解：R 的关系矩阵如下：在图4.10中给出了 R 的关系图。由

26、R 的关系矩阵和关系图可以看出，R 是等价关系。,62,等价关系,R的关系图,2023/11/16,4.7 特殊关系,设 是正整数集合，m 是正整数。对于 来说，可将 R 定义成 这里，“”等价于命题“当用 m去除x 和y 时，它们都有同样的余数”。故关系 R 也称为模 m 同余关系。,63,等价关系,2023/11/16,4.7 特殊关系,定义4.19 设 m是个正整数和。如果对于某一个整数 n，有,则称 x 模等价于 y，并记作整数m 称为等价的模数。显然，这里是用“”表示模 m 等价关系 R。定理4.17 任何集合 中的模 m 相等关系 是一个等价关系。,64,等价关系,2023/11/

27、16,4.7 特殊关系,定义4.20 设 R 是集合 A 上的等价关系：对于任何 来说，可把集合 规定成 并称它是由 x关于 R 的等价类。为了简单起见，有时也把 就写成 或。不难看出，集合 应是由集合 A中与 x 有等价关系 R的那些元素所组成的。,65,等价类,2023/11/16,4.7 特殊关系,例4.23 设，R 是 A上的等价关系，并把 R给定成试画出等价关系图，求出 A中各元素关于 R的等价类。解：等价关系如图4.11所示。由等价关系图不难看出 图4.11 等价关系图,66,等价类,2023/11/16,4.7 特殊关系,定理4.18 设 A是一个集合，R 是 A上的等价关系。如

28、果，则 定理4.19 设 R是集合 A上的等价关系。于是可有（1）对于所有的，或者 或者。（2）,67,等价类,2023/11/16,4.7 特殊关系,定理4.20 设 R是非空集合 A上的等价关系。R 的等价类的集合 是A 的一个划分。根据定理4.18和定理4.19就能够证明此定理。此定理说明非空集合的划分和集合中的等价关系之间，存在一种自然对应关系。定义4.21 设R 是非空集合 A上的等价关系。以 R的所有等价类作为元素的集合 称为S 关于R 的商集，记作，也可写成,68,商集,2023/11/16,4.7 特殊关系,下面来考察集合 A中的两个特殊等价关系：全域关系 和恒等关系。显然这两

29、种关系都是 A上的等价关系。由全域关系所生成的商集 仅包含一个元素 A，而由恒等关系所生成的商集 中的每个元素都是由 A中的单个元素所组成的。所对应的划分是A 的最小划分，所对应的划分是 A的最大划分。这两种划分被称为 A上的平凡划分。,69,2023/11/16,4.7 特殊关系,例4.24 令R 是整数集合 Z中的“模3同余”关系，R 可给定成试求 Z 的元素所生成的 R 等价类。解：等价类是,70,等价类,2023/11/16,4.7 特殊关系,定理4.21 设C 是非空集合A 的一个划分，则由这个划分所确定的下述关系R：必定是个等价关系，并称 R为由划分 C导出的 A上的等价关系。,7

30、1,等价类,2023/11/16,4.7 特殊关系,72,等价类,2023/11/16,4.7 特殊关系,定义4.22 给定集合 A中的二元关系 R，如果R是自反的、对称的，则称 是相容关系。也就是说，可以把 规定成：（1）（2）显然，所有的等价关系都是相容关系，但相容关系并不一定是等价关系。下面举例说明相容关系。设集合，A 中的关系不难看出 R是自反的和对称的，因此R是个相容关系。如果，则称 x 和 y 是相容的。,73,相容关系,2023/11/16,4.7 特殊关系,令，。这里 并且 但，即该相容关系不是可传递的。把R写出来是：图4.12给出了该相容关系R的图。由于相容关系的自反性和对称

31、性，关系图中的所有结点上都有环边；有相容关系的两个结点间都有往返弧线。如果找们删除全部结点上的环边，并且用一条直线取代两结点间的两条弧线，这样就可以把图4.12化简成图4.13。,74,相容关系,2023/11/16,4.7 特殊关系,还可写出该关系R的矩阵如下：由于相容关系是自反的，因而矩阵对角线上的各元素都应是l；相容关系是对称的，所以矩阵关于主对角线也是对称的。这样，仅给出关系矩阵下部的三角形部分也就够了。简化后的关系矩阵如图4.14所示 令，和。在集合，和 中，同一个集合内的元素都是相容的。这些集合的并集就是给定的集合X，亦即。因此，集合 定义了集合X 的一个覆盖，但它不能构成集合的一

32、个划分。,75,相容关系,2023/11/16,4.7 特殊关系,定义4.23 设 是集合X中的相容关系。假定。如果任何一个，都与其他所有的元素有相容关系，而 中没有能与 A中所有元素都有相容关系的元素，则子集 称为最大相容类。寻找最大相容类的方法有两种：关系图法和关系矩阵法。,76,最大相容类,2023/11/16,4.7 特殊关系,关系图法。关系图法的实质在于寻找出“最大完全多边形”。所谓最大完全多边形，系指每一个顶点都与其他所有顶点相连结的多边形。（1）集合中仅关系到它自身的结点，是一个最大完全多边形。（2）不都与其它的结点相连接的一条直线所连接的两个结点构成一个最大完全多边形。（3）三

33、角形的三个顶点构成一个最大完全多边形，对角线相连的四边形的四个顶点构成一个最大完全多边形，正五角星的五个顶点构成一个最大完全多边形，正六边形的六个顶点也是一个最大完全多边形。一个最大完全多边形对应一个最大相容类。,77,关系图法,2023/11/16,4.7 特殊关系,例4.27 在图4.15中，给出了两个相容关系图。试求出它们的所有最大完全多边形,并求出与它们相应的最大相容类。解：图（a）的最大完全多边形有：四边形1234线段25，36和56；与它们相应的最大相容类分别是：1，2，3，4，2，5，3，6)，5，6。图（b）的最大完全多边形有：三角形123，136，356和孤立结点4；与它们相

34、对应的最大相容类分别是：1，2，3，1，3，6，3，5，6和4。图4.15 相容关系图,78,关系图法,2023/11/16,4.7 特殊关系,关系矩阵法。首先制定简化了的关系矩阵，继之按下列步骤求出各最大相容类。（1）仅与它们自身有相容关系的那些元素，能够分别单独地构成最大相容类，因此从矩阵中删除这些元素所在的行和列。（2）从简化矩阵的最右一列开始向左扫描，直到发现至少有一个非零记入值的列。该列中的非零记入值，表达了相应的相容偶对。列举出所有这样的偶对。（3）继续往左扫描，直到发现下一个至少有一个非零记入值的列。列举出对应于该列中所有非零记入值的相容偶对。在这些后发现的相容偶对中，如果有某一

35、个元素与先前确定了的相容类中的所有元素都有相容关系，则将此元素合并到该相容类中去；如果某一个元素仅与先前确定了的相容类中的部分元素有相容关系，则可用这些互为相容的元素组成一个新的相容类。删除已被包括在任何相容类中的那些相容偶对，并列举出尚未被包含在任何相容类中的所有相容偶对。（4）重复步骤（3），直到扫描过简化矩阵的所有列。最后，仅包含孤立元素的那些相容类，也是最大相容类。,79,关系矩阵法,2023/11/16,4.7 特殊关系,例4.29 与图4.15（b）中的相容关系图相对应的简化矩阵如下图所示，试求各最大相容类。解：这里结点4是个孤立结点，故在矩阵中删除了相应的行和列。根据步骤（2）和

36、（3）可有：（a）4（b）4，5，6（c）4，5，6，3，5，3，6，合并后有 4，3,5,6（d）4，3，5，6，2，3（e）4，3，5，6，2，3，1，2，1,3，1，6，合并后有 4，3,5,6，1，2，3，1,3，6 这些相容类都是最大相容类。,80,关系矩阵法,2023/11/16,4.7 特殊关系,定义4.24 设 R是集合A 上的二元关系。如果 R是自反的、反对称的和可传递的，亦即有（1）（2）（3）则称 R 是集合 A中的偏序关系，简称偏序。序偶 称为偏序集合。这里用符号“”表示偏序。这样，符号“”就不单纯意味着实数中的“小于或等于”关系。事实上，这是从特定情况中，借用符号“”

37、去表示更为普遍的偏序关系。对于偏序关系来说，如果有 且 xy，则按不同情况称它是“x 小于或等于y”，“y包含x”，“x 在 y 之前”等等。,81,次序关系,2023/11/16,4.7 特殊关系,设 R 是实数集合。“小于或等于”关系是 R 中的偏序关系；这个关系的逆关系“大于或等于”关系也是 中的偏序关系。设 是 A 的幂集，亦即 X 是 A 的子集的集和。X中的包含关系，是个偏序关系；这个关系的逆关系 也是个偏序关系。设 是正整数集合，且,当且仅当存在 z，能使，才有“x 整除 y”(可写成 x|y)，换言之，“y 是 x 的整倍数”。“整除”和“整倍数”互为逆关系，它们都是 中的偏序

38、关系。,82,次序关系,2023/11/16,4.7 特殊关系,例4.30 设，是 中的“整除”关系。试表达出“整除”和“整倍数”关系。解：“整除”关系可规定成“整倍数”关系是 实数集合 R 中的“小于“关系，都不是偏序关系，因为它们都不是自反的。但它们是实数集合中的另一种关系拟序关系。,83,次序关系,2023/11/16,4.7 特殊关系,定义4.25 设 R 是集合 A中的二元关系。如果 R是反自反的和可传递的，亦即有（1）（2）则称 R是拟序关系，并借用符号“都是拟序关系。子集的集合中的真包含关系 和 都是拟序关系。,84,次序关系,2023/11/16,4.7 特殊关系,定理4.22

39、 设 R 是集合 A 上的二元关系。于是可有（1）如果 R 是个拟序关系，则 是一个偏序关系。（2）如果 R 是个偏序关系，则 是个拟序关系。定理4.23 设是个偏序集合。如果对于每一个，或者 或者，亦即则称偏序关系是全序关系简称全序，序偶 称为全序集合。A中具有全序关系的各元素，总能按线性次序 排列起来，这里当且仅当 i j，才有,故全序也称为简单序或线性序，因此，序偶 在这种情况下也被称为线性序集或链。,85,次序关系,2023/11/16,4.7 特殊关系,设是集合 P 中的偏序关系。对于，如果有 xy 或 yx,则A 中的元素 x 和 y 称为可比的。在偏序集合中，并非任何两个元素x

40、和y 都存在有 xy 或 yx 的关系。事实上，对于某些x 和 y来说，x 和 y可能没有关系。在这种情况下，称 x和y 是不可比的。正是由于这种原因，才把称作“偏”序关系。在全序集合中，任何两个元素都是可比的。设 R 是实数集合，a 和 b是 R 的元素。对于每一个实数 a，设 和 S是集合并且 0。如果 ab，则，因此 是一个全序集合。如果A 是个含有多于一个元素的集和，则 不是一个全序集合。例如，设，于是,86,次序关系,2023/11/16,4.7 特殊关系,设 R是实数集合且。假定 R上的关系 是一般的“大于或等于”关系。对于P 中的任何两个序偶 和，可以定义一个关系S 如果，则有,

41、因此 S是 P 中的全序关系。并称它是字母次序关系或字母序。例如，试考察下列序偶可以看出，这些序偶之间有字母次序关系。,87,次序关系,2023/11/16,4.7 特殊关系,定义4.26 设 是一个偏序集，如果对任何，xy 和，而且不存在任何其他元素 能使 xz 和 zy，即(x z 成立，则称元素 y 盖覆x。在哈斯图中，用小圈表示每个元素。如果有，且 x y 和，则把表示x 的小圈画在表示 y 的小圈之下。如果y 盖覆x，则在x 和y 之间画上一条直线。如果 xy 和，但是 y不盖覆x，则不能把x 和y 直接用直线联结起来，而是要经过A 的一个或多个元素把它们联结起来。这样，所有的边的方

42、向都是自下朝上，故可略去边上的全部箭头表示。,88,偏序集,2023/11/16,4.7 特殊关系,例4.32 设集合，是X上的偏序关系。并定义成：如果 x 整除 y，则 xy。试画 的哈斯图。解：在图4.19给出了整除关系的哈斯图。例4.33 设集合，是它的幂集。的元素间的偏序关系是包含关系。试画出 的哈斯图。解：在图4.19中给出了 的哈斯图,89,哈斯图,图4.19 整除关系的哈斯图,图4.20,2023/11/16,4.7 特殊关系,定义4.27 设 是一个偏序集合，并有，（1）若 成立，则称元素y为Q的最小元，通常记作0。（2）若 成立，则称元素y称为Q的最大元，通常记作1。（3）若

43、 成立，则称元素y称为Q 的极小元。（4）若 成立，则称元素y称为Q 的极大元。定理4.24 设 X 是一个偏序集合，且有。如果x 和 y都是Q 的最小(最大)元,则,90,2023/11/16,4.7 特殊关系,定义4.28 设 是个偏序集合，且有，。（1）若 y)成立，则称元素y 是Q 的上界。（2）若 x)成立，则称元素 y是Q 的下界。（3）令，则称C 的最小元为 Q的最小上界，通常记作 LUB。（4）令，则称D 的最大元为Q 的最大下界，通常记作 GLB。,91,2023/11/16,4.7 特殊关系,92,2023/11/16,4.7 特殊关系,定义4.29 给定集合 X，R 是

44、X 中的二元关系。如果 R是个全序关系，且 X 的每一个非空子集都有一个最小成员，则称 R是个良序关系。与此对应，序偶 称为良序集合。显然，每一个良序集合必定是全序集台，因为对于任何子集来说，其本身必定有一个元素是它的最小成员。但是每一个全序集合不一定都是良序的，有限全序集合必定是良序的。,93,2023/11/16,多重序元与笛卡尔乘积,主要内容,PART 01,关系的基本概念,PART 02,关系的运算,PART 03,关系的性质,PART 04,关系的表示,PART 05,关系的闭包运算,PART 06,特殊关系,PART 07,关系型数据库,PART 08,2023/11/16,94,

45、4.8*关系型数据库,数据库是由计算机操作的一种记录的汇集。例如，一个航空公司数据库可能包含乘客的预约记录、飞行调动的记录和设备的记录等。计算机系统能够把大量的信息的信息储存在数据库中。各种各样的应用场合都可以使用这些数据。数据库管理系统是帮助用户在数据库中访问信息的程序。由E.F.Codd提出的关系数据库模型基于 元关系的概念。一个 元关系的列称为属性。一个属性的定义域是包含该属性中所有元素的一个集合。,95,2023/11/16,4.8*关系型数据库,例如，在表4.1中，属性“年龄”可以取为所有小于100的正整数的集合。属性“姓名”可以取为所有长度不超过30的英文字符串。如果关系的一个单个

46、属性或属性组合的值能唯一的定义一个 元组，则属性或属性组合是一个关键字。例如，在表4.1中，可以取属性“ID号”作为一个关键字。属性“姓名”不是关键字，因为不同的人可以有相同的名字。同样的原因，不能取属性“位置”和“年龄”作为关键字。对于表，“姓名”和“位置”的组合可以用作关键字，以为在例子中一个运动员由姓名和位置唯一定义,96,2023/11/16,4.8*关系型数据库,定义4.30 设有 n元关系 R，它由 m个n 重序元组成，则 是一个k元关系，它由 m个k 重序元组成，其中每一个k 元序偶由属性 组成，这个运算叫做 在属性 上的投影运算。例4.35 对于表4.1给出的关系R，给出其在姓名和位置上的投影。解：,97,2023/11/16,4.8*关系型数据库,98,2023/11/16,4.8*关系型数据库,99,解:,2023/11/16,4.8*关系型数据库,100,谢谢！,2023/11/16,