离散数学教案.docx

《离散数学教案.docx》由会员分享，可在线阅读，更多相关《离散数学教案.docx（32页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、学习目标：1深刻理解序偶、笛卡尔积、关系、集合的划分及覆盖、等价关系、等价类、商集、相容关系、（最大）相容类、偏序关系、极大元、极小元、上（下）界、上（下）确界、最大（小）元、全序关系、良序关系等概念；2掌握集合的交、并、差、补、对称差的运算及其运算规律；3掌握关系的交、并、逆、复合运算、闭包运算及其性质；4掌握关系的矩阵表示和关系图；5深刻理解关系的自反性、反自反性、对称性、反对称性和传递性，掌握其判别方法；6掌握集合的覆盖及划分的联系及区别；7掌握偏序关系的判别及其哈斯图的画法；会求偏序集中给定集合的极大元、极小元、上（下）界、上（下）确界、最大（小）元。主要内容：1集合的基本概念及其运算

2、2序偶及笛卡尔积3关系及其表示4关系的性质及其判定方法5复合关系和逆关系6关系的闭包运算7等价关系及相容关系8偏序关系重点： 1关系的性质及其判别；2关系的复合运算及其性质；3等价关系及等价类、等价关系及集合的划分的联系；4偏序关系判别及其哈斯图的画法、偏序集中特异位置元素的理解。 难点：1关系的传递性及其判别；2等价关系的特性；3偏序关系的哈斯图的画法；偏序集中特异位置元素的求法。教学手段： 通过多个实例的精讲帮助同学理解重点和难点的内容，并通过大量的练习使同学们巩固和掌握关系的性质及其判别、关系的复合运算及其性质、等价关系的特性、偏序关系的哈斯图的画法及偏序集中特异位置元素的求法。习题：

3、习题3.1：4，6；习题3.2：3（8），4（12），6（m）；习题3.4：1 （2）、(4)，3；习题3.5：1，4；习题3.6：2，5，6；习题3.7：2，5，6；习题3.8：1（1）-（6）；习题3.9：3（2）、（4），4（3）；习题3.10：1 ，4，5。3.1 集合的基本概念集合(set)（或称为集）是数学中的一个最基本的概念。所谓集合，就是指具有共同性质的或适合一定条件的事物的全体，组成集合的这些“事物”称为集合的元素。集合常用大写字母表示，集合的元素常用小写字母表示。若是集合，是的元素，则称属于，记作；若不是的元素，则称不属于，记作。若组成集合的元素个数是有限的，则称该集合为有

4、限集(Finite Set)，否则称为无限集(Infinite Set)。常见集合专用字符的约定： 自然数集合(非负整数集) (或)整数集合(，)有理数集合(，)实数集合(，)分数集合(，)脚标+和-是对正、负的区分复数集合素数集合奇数集合偶数集合幂集定义3.1.1 对于每一个集合，由的所有子集组成的集合，称为集合的幂集(Power Set)，记为 或即。例如：, 。定理3.1.1 如果有限集有个元素，则其幂集有个元素。证明 的所有由个元素组成的子集数为从个元素中取个的组合数。另外，因，故的元素个数可表示为又因 令 得 故的元素个数是。人们常常给有限集的子集编码，用以表示的幂集的各个元素。具体

5、方法是：设，则子集按照含记、不含记的规定依次写成一个位二进制数，便得子集的编码。例如，若，则的编码是，当然还可将它化成十进制数。如果，那么这个十进制数为，此时特别记为。 3.2 集合的对称差运算定义3.2.1 设、是两个集合，要么属于，要么属于，但不能同时属于和的所有元素组成的集合，称为和的对称差集，记为。即例如，若，则。对称差的定义如图3-1所示。图3-1由对称差的定义容易推得如下性质：（1）（2）（3）（4）（5）证明 （5）但 故 又 因为 故 因此 对称差运算的结合性亦可用图3-2说明。图3-2 对称差运算的结合性从文氏图3-3亦可以看出以下关系式成立。 图3-3 3.4 序偶及笛卡尔

6、积 序偶 在日常生活中，有许多事物是成对出现的，而且这种成对出现的事物，具有一定的顺序。例如，上，下；男生9名而女生6；中国地处亚洲；平面上点的坐标等。一般的说，两个具有固定次序的客体组成一个序偶(Ordered Pair)，记作。上述各例可分别表示为上，下；中国，亚洲；等。 序偶可以看作是具有两个元素的集合，但它及一般集合不同的是序偶具有确定的次序。在集合中，但对序偶，当时，。定义 两个序偶相等，当且仅当。这里指出：序偶中两个元素不一定来自同一个集合，它们可以代表不同类型的事物。例如，代表操作码，代表地址码，则序偶就代表一条单地址指令；当然亦可将代表地址码，代表操作码，仍代表一条单地址指令。

7、但上述这种约定，一经确定，序偶的次序就不能再予以变化了。在序偶中，称第一元素，称第二元素。序偶的概念可以推广到有序三元组的情况。有序三元组是一个序偶，其第一元素本身也是一个序偶，可形式化表示为。由序偶相等的定义，可以知道当且仅当，即，我们约定有序三元组可记作。注意：，因为不是有序三元组。同理，有序四元组被定义为一个序偶，其第一元素为有序三元组，故有序四元组有形式为，可记作，且这样，有序元组(Ordered n-tuple)定义为，记作，且 一般地，有序元组中的称作有序元组的第个坐标。 笛卡尔积 定义 设和是任意两个集合，若序偶的第一个成员是的元素，第二个成员是的元素，所有这样的序偶集合，称为集

8、合和的笛卡尔乘积或直积(Cartesian Product)，记作。即例 若, 求以及解 显然，我们有：（1）；（2）如果，则。我们约定：若或，则。由笛卡尔积定义可知：由于不是三元组，所以定理 设、和为任意三个集合，则有（1）（2）（3）（4）证明 （1）设因此， 。（4）设 因此， 。定理 设、和为三个非空集合，则有证明 设，对任意的，因此， 。反之，若，取，则对，有因此，。定理的第二部分，证明类似。定理 设、和为四个非空集合，则的充要条件为且。证明 若，对任意的，有即 。反之，若且，设任意，有因此， 。对于有限个集合可以进行多次笛卡尔积运算。为了及有序元组一致，我们约定：一般地，故是有序元

9、组构成的集合。特别地，同一集合的次直积，记为, 这里。例如，此处，。一般地，若 。3.5 关系及其表示 关系的定义 在日常生活中我们都熟悉关系这词的含义，例如，父子关系、上下级关系、朋友关系等。我们知道，序偶可以表达两个客体、三个客体或个客体之间的联系，因此可以用序偶表达关系这个概念。例如，机票及舱位之间有对号关系。设表示机票的集合，表示舱位的集合，则对于任意的和，必有及有对号关系和及没有对号关系两种情况的一种。令表示“对号”关系，则上述问题可以表达为或，亦可记为或，因此，我们看到对号关系是序偶的集合。定义 设、是任意两个集合，则称直积的任一子集为从到的一个二元关系(Binary Relati

10、on )。二元关系亦简称关系，记为，。到的二元关系，如图3-4所示。图3-4集合到的二元关系是第一坐标取自、第二坐标取自的序偶集合。如果序偶，也说及有关系，记为；如果序偶，则说及没有关系，记为。当时，关系是的子集，这时称为集合上的二元关系。例 （1）设，则令因为，所以，和均是由到的关系。（2）=是实数且是实数集上的大于关系。定义 设为到的二元关系，由的所有组成的集合称为的定义域或前域(Domain)，记作dom或，即 dom使的所有组成的集合称为的值域(Range)，记作ran，即ran。的定义域和值域一起称作的域(Field)，记作FLD，即FLD domran显然，dom，ran，FLDd

11、omran例3.5.2 设，求dom，ran 和FLD。解 dom，ran ，FLD。 例3.5.3 设，求集合上的关系“”、dom及ran。 解 domran3.5.2 几种特殊的关系1空关系对任意集合，所以是由到的关系，也是上的关系，称为空关系(Empty Relation)。2全域关系因为，所以是一个由到的关系，称为由到的全域关系(Universal Relation)。是上的一个关系，称为上的全域关系，通常记作，即例3.5.4 若表示家庭中父、母、子、女四个人的集合，确定上的全域关系和空关系，另外再确定上的一个关系，并指出该关系的前域和值域。解 设上同一家庭的成员的关系为，设上的互不相

12、识的关系为，则为全域关系，为空关系。设上的长幼关系为，domran3恒等关系定义 设是上的二元关系且满足，则称是上的恒等关系(Identical Relation)。例如，则。因为关系是序偶的集合，因此，可以进行集合的所有运算。定理 若和是从集合到集合的两个关系，则、的并、交、补、差仍是到的关系。证明 因为 故 例3.5.5 若，求 ，和。解 ，3.5.3 关系的表示 1集合表示法因为关系是序偶的集合，因此可用表示集合的列举法或描述法来表示关系。例如，例的（1）中的关系，和及例中的关系，均是用列举法表示的关系；而例的（2）中的关系和例中的关系，都是用描述法表示的关系。有限集合间的二元关系除了可

13、以用序偶集合的形式表达以外，还可用矩阵和图形表示，以便引入线性代数和图论的知识来讨论。2矩阵表示法 设给定两个有限集合，则对应于从到的二元关系有一个关系矩阵，其中 如果是有限集合上的二元关系或和含有相同数量的有限个元素，则是方阵。例3.5.6 若，写出关系矩阵。解 例3.5.7 设，写出集合上的大于关系的关系矩阵。 解 3关系图表示法有限集合的二元关系也可用图形来表示。设集合到上的一个二元关系为，首先我们在平面上做出个结点分别记作，另外做个结点分别记作。如果，则从结点至结点做一有向弧，其箭头指向，如果，则之间没有线段连接。用这种方法连接起来的图称为的关系图。例3.5.8 画出例3.5.6的关系

14、图。解 本题的关系图如图3-11所示： 图3-11 例3.5.8的关系图例3.5.9 设，画出的关系图。 解 因为是上的关系，故只需画出中的每个元素即可。如果，就画一条由到的有向弧。若，则画出的是一条自回路。本题的关系图如图3-12所示。 3 2 1 45 图3-12 例3.5.9的关系图关系图主要表达结点及结点之间的邻接关系，故关系图及结点位置和线段的长短无关。从到的关系是的子集，即，而，所以，。令，则。因此，我们今后通常限于讨论同一集合上的关系。3.6 关系的性质及其判定方法3.6.1 关系的性质定义设是定义在集合上的二元关系，如果（1）对于每一个，都有，则称是自反的(Reflexive)

15、。即在上自反（2）对于每一个，都有，则称是反自反的(Antireflexive)。即在上反自反（3）对于任意，若，就有，则称是对称的(Symmetric)。即在上对称（4）对于任意，若，必有，则称在上是反对称的(Antisymmetric)。即在上反对称（5）对于任意，若，就有，则称在上是传递的(Transitive)。即在上传递例 设，则集合上的关系是自反而不是反自反的关系；是反自反而不是自反的关系；是既不是自反也不是反自反的关系；是对称的而不是反对称的关系；是反对称的而不是对称的关系；是既对称也反对称的关系；是既不对称也不反对称关系。，是可传递的关系；是不可传递的关系，因为，但。由定义及例

16、可知：（1）对任意一个关系，若自反则它一定不反自反，若反自反则它也一定不自反；但不自反，它未必反自反，若不反自反，也未必自反。（2）存在着既对称也反对称的关系。图3-5表明了自反及反自反、对称及反对称性之间的关系。图3-5例 (1) 集合之间的关系是自反的、反对称的和可传递的。因为：1） 对于任意集合，均有成立，所以是自反的；2） 对于任意集合，若且，则，所以是反对称的；3） 对于任意集合，若且，则，所以是可传递的。（2）平面上三角形集合中的相似关系是自反的、对称的和可传递的。因为：任意一个三角形都及自身相似；若三角形相似于三角形，则三角形必相似于三角形；若三角形相似于三角形，且三角形相似于三

17、角形，则三角形必相似于三角形。（3）人类的祖先关系是反自反、反对称和可传递的。（4）实数集上的“”关系是反自反、反对称和可传递的。（5）实数集上的“”关系是自反、反对称和可传递的。（6）实数集上的“=”关系是自反、对称、反对称和可传递的。（7）人群中的父子关系是反自反和反对称的。（8）正整数集上的整除关系是自反、反对称和可传递的。（9）是反自反、对称、反对称和可传递的。（10）任意非空集合上的全关系是自反的、对称的和可传递的。例3.6.3 设整数集上的二元关系定义如下：是整数，验证在上是自反和对称的。证明 ，即，故是自反的。又设，如果，即是整数，则也必是整数，即，因此是对称的。3.6.2 由关

18、系图、关系矩阵判别关系的性质例 集合，上的关系的关系矩阵为：的关系图如图3-6所示。讨论的性质。图3-6解 从的关系矩阵和关系图容易看出，是自反的、对称的。一般地，我们有：（1）若关系是自反的，当且仅当其关系矩阵的主对角线上的所有元素都是1；其关系图上每个结点都有自环。（2）若关系是对称的，当且仅当其关系矩阵是对称矩阵；其关系图上任意两个结点间若有定向弧，必是成对出现的。（3）若关系是反自反的，当且仅当其关系矩阵的主对角线上的元素皆为0；关系图上每个结点都没有自环。（4）若关系是反对称的，当且仅当其关系矩阵中关于主对角线对称的元素不能同时为1；其关系图上任意两个不同结点间至多出现一条定向弧。（

19、5）若关系是可传递的，当且仅当其关系矩阵满足：对，若且，则；其关系图满足：对，若有弧由指向，且又有弧由指向，则必有一条弧由指向。 例 图3-7是由关系图所表示的上的5个二元关系。 （1） （2）（3） （4） （5）图3-7请判断它们的性质。解 (1) 是反对称、传递但不是对称的关系，而且是既不自反也不反自反的关系；(2) 是自反、传递、反对称的关系，但不是对称也不是反自反的关系；(3) 是反自反但不是对称、不是反对称、不是自反也不是传递的关系；(4) 是不自反、不反自反但是传递的关系，而且既是对称也是反对称的关系； (5) 是自反、反对称但不是传递、不是对称也不是反自反的关系。3.7 复合关

20、系和逆关系 复合关系 1. 复合关系的定义定义 设是从到的关系，是从到的关系，则称为和的复合关系(Compositive Relation)，表示为从和求，称为关系的复合运算。复合运算是关系的二元运算，它能够由两个关系生成一个新的关系，以此类推。例如，是从到的关系，是从到的关系，是从到的关系，则是从到的关系。例设是由到的关系，是由到 的关系，分别定义为：于是复合关系例3.7.2 设是所有人的集合。那么而例3.7.3 设和是集合上的关系，或，求、和。解 2. 关系的复合运算的性质定理 设是由集合到的关系，则。定理3.7.2 设是从到的关系，是从到的关系，则有（1）（2）（3）若，则。证 （1）和

21、（2）是显然的，下面我们证明（3）。用反证法。反设，则必存在，使，从而，使，故且 ，所以，这就及矛盾，因此，。定理3.7.3 （1）设、和分别是从到、到和到的关系，则即关系的复合运算满足结合律。（2）设和都是从到的关系，是从到的关系，则1）2）（3）设是从到的关系，和都是从到的关系，则1） 2）证 我们只证明（2），其它证明类似。 1）所以 2）所以 。注意：一般来说，（1）；（2）关系的复合运算不满足交换律。 例3.7.4 （1）设，和都是从到的关系，是从到的关系，则可见，但。（2）设，和都是集合上的关系，则，而，所以。由于关系的复合运算满足结合律，所以可以写成。一般地，若是一由到的关系，是

22、由到的关系，是一由到的关系，则不加括号的表达式唯一地表示一由到的关系，在计算这一关系时，可以运用结合律将其中任意两个相邻的关系先结合。特别地，当 ，即是集合上的关系时，复合关系 简记作，它也是集上的一个关系。 复合关系的矩阵表示及图形表示 因为关系可用矩阵表示，所以复合关系也可用矩阵表示。已知从集合到集合上的关系为，关系矩阵，从集合到集合的关系，关系矩阵，表示复合关系的矩阵可构造如下：若，使得且，则。在集合中能够满足这样条件的元素可能不止一个，例如另有也满足且。在所有这样的情况下，都是成立的。这样，当我们扫描的第行和的第列时，若发现至少有一个这样的，使得第行的第个位置上的记入值和第列的第个位置

23、上的记入值都是1时，则的第行和第列上的记入值为1；否则为0。因此可以用类似于矩阵乘法的方法得到：其中 式中代表逻辑加，满足，；代表逻辑乘，满足，。例3.7.5 给定集合，在集合上定义两种关系：，求和的矩阵。解因为关系可用图形表示，所以复合关系也可用图形表示。例3.7.6 例3.7.1中的两个关系及的复合很容易通过下面的关系图（见图3-8）得到。图3-8 示意图由该图立即可得。 逆关系关系是序偶的集合，由于序偶的有序性，关系还有一些特殊的运算。定义 设是从到的二元关系，若将中每一序偶的元素顺序互换，得到的集合称为的逆关系(Inverse Relation)，记为。即例如，在实数集上，关系“”。从

24、逆关系的定义，我们容易看出 。定理3.7.4 设、和都是从到的二元关系，则下列各式成立。（1）（2）(3) (4) 这里 -(5) 证明 （1）（4）（5）因为，故有 其它自证。定理3.7.5 设为从到的关系，是从到的关系，则（1）（2）证明 （1）所以 （2）自证。定理3.7.6 设是上的二元关系，则（1）是对称的，当且仅当；（2）是反对称的，当且仅当；（3）是传递的，当且仅当；（4）是自反的，当且仅当；（5）是反自反的，当且仅当证明 （1）若是对称的，则对，所以，；若 ，则对，所以，是对称的。（3）若，则对，所以，是传递的；若是传递的，所以，。其它证明留为作业。关系的图形，是关系图形中将其

25、弧的箭头方向反置。的关系矩阵是的转置矩阵。例3.7.7 设是到的二元关系，是到的二元关系，且，求和。解 或从 ， 得 故取到同样的序元素；而 故取到同样的序元素。例3.7.8 给定集合，是上的二元关系，的关系矩阵求和的关系矩阵解 3.8 关系的闭包运算关系作为集合, 在其上已经定义了并、交、差、补、复合及逆运算。现在再来考虑一种新的关系运算关系的闭包运算，它是由已知关系，通过增加最少的序偶生成满足某种指定性质的关系的运算。 例如, 设，上的二元关系，则上含且最小的自反关系是：上含且最小的对称关系是：上含且最小的传递关系是：定义 设是上的二元关系，如果有另一个上的关系满足：（1）是自反的（对称的

26、，传递的）；（2）；（3）对于任何上的自反的（对称的，传递的）关系，若，就有。则称关系为的自反（对称，传递） 闭包(Reflexive (Symmetric，Transitive) Closure)，记作。显然，自反（对称，传递）闭包是包含的最小自反（对称，传递）关系。定理 设是上的二元关系，那么（1）是自反的，当且仅当（2）是对称的，当且仅当（3）是传递的，当且仅当证明 （1）若是自反的，对任何包含的自反关系，有，故；若，根据闭包定义，必是自反的。（2）、（3）的证明完全类似。 下面讨论由给定关系，求取的方法。定理 设是集合上的二元关系，则（1）；（2）（3），通常也记作。证明 （1）令，因

27、为，故，于是在上是自反的。又即。若有自反关系且，显然有，于是 ，所以 。 （2）令，因为 所以是对称的。若是对称的且，则。当时，；当时，。因此 ，故 。（3）令，先证是传递的。 ，则存在自然数，有 ，因此 ，所以，是传递的。显然，。若有传递关系且，则存在自然数，有 ，则 ，使得 ，因此，由于是传递关系，则，所以。故例 设，是上的二元关系，求。解 为了求得，先写出即继续这个运算有：从以上例题中看到，若有限，譬如含有个元素，那么求取上二元关系的传递闭包不必计算到对的无限大次复合，而最多不超过次复合。定理3.8.3 设是含有个元素的集合，是上的二元关系，则存在一个正整数，使得证明 设，记。若，则存在

28、整数，使得成立，既存在序列，有。设满足上述条件的最小大于，不妨，则序列中必有，使得或。不妨，此时序列就成为这表明存在，其中，这及是最小的假设矛盾，所以，不成立，即。所以 （）一般地，取，式中的给出了复合次数的上限。 例 设，给定上的关系，求。解 所以 即 为计算元素较多的有限集合上二元关系的传递闭包， Warshall在1962年提出了一个有效的算法（假定集合含有个元素）：（） 置新矩阵：；（） 置：；（） 对，若（），则置：，；（） 如果，则转到步骤（3），否则停止。例3.8.3 已知，求。 解 按照Warshall算法，从出发，只要遵循“置行查列遍寻真，见真行上析当今，行推列移下右再，行穷

29、列尽闭包成”便可直接求得。 对集合上关系，首先将其关系矩阵赋予：而后的每后一次循环重复操作， 均在前一次操作结果的矩阵上进行。置当今行为第1行，查看第1列中1，对有1的行进行改写，改写方法是：将当今行的元素及列中有1的行的元素分别做析取。对本例，时，第1列中只有，将第一行及第一行各对应元素进行逻辑加，仍记于第一行：置当今行为第2行， 查看第2列中1， 对有1的行进行改写。对本例，时，第二列中，将第二行及第一行各对应元素进行逻辑加，仍记于第一行：置当今行为第3行，重复上述操作并结束。对本例，时，第三列中，将第三行分别及第一行、第二行、第三行各对应元素进行逻辑加，仍分别记于第一行、第二行、第三行：

30、得 。结果及例3.8.2一致。传递闭包在语法分析中有很多应用，先以下列说明/例3.8.4 设有一字母表并给定下面六条规则：为定义在上的二元关系且，即是从出发用一条规则推出一串字符，使其第一个字符恰为。说明每个字母连续应用上述规则可能推出的头字符。解 则表示从出发，经过多次连续推导而得的字符串，其第一个字符恰为的关系，此关系即是。按照Warshall算法计算的过程中，时，由于第五行的元素都等于零，的赋值不变。时，由于第3、6、7列各元素均为零，的赋值不变。经计算得因此。 这说明应用给定的六条规则，从出发推导的头字符有三种可能，而从出发推导的头字符有两种可能，而从推出的头字符有两种可能，从出发推导

31、的头字符只可能为。从一种性质的闭包关系出发，求取另一种性质的闭包关系，具有以下运算律： 定理3.8.4 设是集合上的二元关系，则（1）（2）（3）证明 （1）这里，。（2）这里，（）。（3）留作练习请读者自证。3.9 等价关系及相容关系 本节讨论两类特殊关系等价关系及相容关系。在讨论之前，我们先引进两个概念集合的划分及覆盖。 集合的划分和覆盖 设是某一所综合性大学本科学生全体组成的集合，是对的某种分类的集合（）。若按文理科分类，则有，其中表示理科学生全体的集合、表示文科学生全体的集合；若按年级分类，则有，其中表示该大学年级学生全体的集合；若按系分类，则有，这说明这所大学有六个系。分类法尽管给出

32、了三种，但是它们有个共同的特点：(1) 的元素都是的非空子集；(2) 的元素求交是空集、求并就是。 此时，我们就说是集合的一个划分。 定义 设是非空集合，的子集的集合，如果满足： （1）都是非空集合； （2）则称集合是集合的覆盖(Cover)，称是覆盖的分块。如果除以上条件外，另有（），则称是的划分（或分划）(Partition)。显然，若是划分则必是覆盖，其逆不真。若，则有两个简单的划分：一是，称为的最大划分(分块最多)；二是，称为的最小划分(分块最少)。 例如，考虑下列子集：则是的覆盖；是的划分，其中是最小划分，是最大划分；既不是划分也不是覆盖。 定义 若及是同一集合的两种划分，则其中所有

33、组成的集合，称为和的交叉划分，即 注意：和的交叉划分一般不是，而是以及元素之间的所有非空交集作元素的集合。 例如，所有生物的集合，可分割成，其中表示所有植物的集合，表示所有动物的集合；又也可分割成，其中表示史前生物，表示史后生物。则其交叉划分为，其中表示史前植物，表示史后植物，表示史前动物，表示史后动物。 定理 设及是同一集合的两种划分，则其交叉划分也是原集合的一种划分。 证明 和的交叉划分是：在交叉划分中，任取两元素和，（），因为 ，所以 ；其次，交叉划分中所有元素的并为所以，和的交叉划分也是的一种划分。定义 给定的任意两个划分及，若对于每一个均有，使（），则称为的加细。若还有，则称为的真加

34、细。定理 任何两种划分的交叉划分，都是原来各划分的一种加细。证明 设及的交叉划分为，对中任意元素必有和，则分别是和的加细。 等价关系及等价类1. 等价关系 定义 设为定义在集合上的一个关系，若是自反的、对称的和传递的，则称为等价关系(Equivalence Relation)。例 3 . 9. 1 （1） 平面上三角形集合中，三角形的相似关系是等价关系。（） 数的相等关系是任何数集上的等价关系。（3）一群人的集合中姓氏相同的关系也是等价关系。（4）设是任意非空集合，则上的恒等关系和全域关系均是上的等价关系。例3.9.2 设集合，验证是上的等价关系。证明 的关系矩阵：关系图如图3-9所示。图3-

35、9关系矩阵中，对角线上的所有元素都是1，关系图上每个结点都有自环，说明是自反的。关系矩阵是对称的，关系图上任意两结点间或没有弧线连接，或有成对弧出现，故是对称的。从的序偶表示式中，可以看出是传递的。故是上的等价关系。例3.9.3 设为整数集，其中当且仅当，使得，证明是等价关系。证明 设任意（1），所以，是自反的；（2）若，(为整数)，则 ，所以，是对称的；（3）若，则， (为整数)，所以，是传递的。因此，是等价关系。我们称之为整数集上的模同余关系(Congruence Modulo )。2等价类定义 设是集合上的等价关系，对任何，若，则称及等价。对任何，集合中等价于的所有元素组成的集合称为以为

36、代表元的（关于等价关系的）等价类(Equivalence Class)，记作。即由等价类的定义可知是非空的，因为，。因此，任给集合及其上的等价关系，必可写出上各个元素的等价类。例如，在例3.9.2中，的各个元素的等价类为：可见，上的等价关系的不同的等价类有两个。例3.9.4 设是整数集合，是模同余关系，即确定由的元素所产生的等价类。解 例3.9.3已证明整数集合上的模同余的关系是等价关系，故本例中由的元素所产生的等价类是从本例可以看到，在集合上模3同余等价关系所构成的等价类有：定理 设给定集合上的等价关系，对于有当且仅当。证明 若 ，因为 ，故，即 ，则。若 ，则，即 ；，即 。所以，。定义

37、集合上的等价关系，其所有等价类的集合称作关于的商集(Quotient Set )，记作，即例如，例3.9.2中，商集： 例3.9.4中商集： 我们注意到商集中，且任意两个等价类的交为，于是我们有下述重要定理。定理 集合上的等价关系，决定了的一个划分，该划分就是商集。为证定理，我们需要证明非空集合在其上的等价关系下形成的等价类的全体的集合商集满足：(1) 每一等价类都是的子集， 中任一元素均属于某一等价类， 即等价类全体的并集是；(2) 不同的等价类之间交是空集。 证明 ，因为 ，所以，从而；因为自反，即，所以，则 ；故 。(1) 得证。为证明（2），用反证法：设，且 则 ，使成立，由对称性得

38、，再由传递性得 ，据定理，必有 ，这及题设矛盾，（2）得证。所以，是的对应于的一个划分。定理设是集合的一个划分，则存在上的一个等价关系，使得是关于的商集。证明 在集合上定义关系，对任意，当且仅当在同一分块中。可以证明这样定义的关系是一个等价关系。因为：（1）及在同一分块中，故必有，即是自反的。（2）若及在同一分块中，及也必在同一分块中，即 ，故是对称的。（3）若及在同一分块中，及在同一分块中，因为 ，即属于且仅属于一个分块，故及必在同一分块中，即 ，故是传递的。所以，是等价关系。由的定义可知： 。由定理可知：由集合的划分所确定的上的等价关系为：定理和定理说明：非空集合上的等价关系及的划分一一对

39、应。例3.9.5 设的划分，试由划分确定上的一个等价关系。解 显然，。定理 设和为非空集合上的等价关系，则证明 ，。若 ，故 ，即；若，即，则对，必有，使得，故所以， ；类似地有 ，因此，。 相容关系定义3.9.4 给定集合上的关系，若是自反的、对称的，则称是上的相容关系Cconsistent Relation)。相容关系只要求满足自反性及对称性，因此，等价关系必定是相容关系但反之不真。 例3.9.6 设是由下列英文单词组成的集合，定义关系：，且和有相同的字母显然，是一个相容关系。令的关系图如图3-10所示。 图3-10的关系矩阵为。由于相容关系是自反和对称的，因此，其关系矩阵的对角线元素都是

40、，且矩阵是对称的。为此我们可将矩阵用梯形表示。同理，在相容关系的关系图中，每个结点处都有自环且每两个相关联的结点间的弧线都是成对出现的，为了简化图形，我们今后对相容关系图，不画自环，并用单线代替双向弧线，因此，上例的关系矩阵和关系图可简化为表3-1和图3-11。表3-1 例的简化关系矩阵 图3-11定义3.9.5 设是集合上的相容关系， ，如果对于中任意两个元素 有，就称是由相容关系产生的相容类(Consistent Class)。例如，上例中相容关系可产生相容类等等。对于前三个相容类，都能加进新的元素组成新的相容类，而后两个相容类，加入任一新元素，就不再组成相容类，称它们为最大相容类(Max

41、imal Consistent Class)。定义3.9.6 设是集合上的相容关系，不能真包含在任何其它相容类中的相容类，称作最大相容类，记作。若为最大相容类，显然它是的子集，对于任意，必及中的所有元素有相容关系。而在中没有任何元素及所有元素有相容关系。根据最大相容类的定义，它可以从相容关系的简化关系图求得，具体方法是：（1）在相容关系的简化关系图中，每一个最大完全多边形的顶点集合，就是一个最大相容类。所谓完全多边形(Complete Polygon)，就是其每个顶点都及其它顶点连接的多边形。例如一个三角形是完全多边形，一个四边形加上两条对角线就是完全多边形。（2）在的简化关系图中，每一个孤立

42、结点的单点集合，是一个最大相容类。（3）在的简化关系图中，不在完全多边形中的边的两个端点的集合，是一个最大相容类。例3.9.7 由例3.9.6中相容关系的简化关系图3-11可得其全部最大相容类为：定理3.9.7 设是集合上的相容关系，是一个相容类，那么必存在一个最大相容类，使得。证明 设，构造相容类序列，其中，且，其中是满足而 及中各元素都有相容关系的最小下标。由于的元素个数， 所以至多经过步，就使这个过程终止，而此序列的最后一个相容类，就是所要找的最大相容类。从定理3.9.7中可以看到，的任一元素，它可以组成相容类，因此必包含在一个最大相容类中，因此，如由所有最大相容类作出一个集合，则中每一

43、个元素至少属于该集合的一个成员之中，所以最大相容类集合必覆盖集合。定义3.9.6 在集合上给定相容关系，其最大相容类的集合称作集合的完全覆盖(Complete Cover)，记作。例3.9.8 设集合，上二元关系求的完全覆盖。 解 是上的相容关系(自反，对称)。 的简化关系图如图3-12所示：图3-12的最大相容类是确定的，即。因此，集合是的完全覆盖。定理3.9.8 给定集合的覆盖，由它确定的关系是上的相容关系。证明 因为 ，对于任意，必存在某个， 使得 ，所以， ，即 ， 因此，是自反的。其次，若有任意，且，则必存在某个，使 ，故必有 ，即，所以是对称的。因此，是上的相容关系。从上述定理可以看到，给定集合上的任意一个覆盖，必可在上构造对应于此覆盖的一个相容关系，但是不同的覆盖却能构造相同的相容关系。例如，设，集合和都是的覆盖，但它们可以产生相同的相容关系：因此，相容关系及覆盖之间不是一一对应的。但是我们有：定理3.9.9 集合上相容关系及完全覆盖一一对应。习题3.91设是集合的划分，试证明是集合的划分。其中。