离散数学电子教材3a(共35页).doc

《离散数学电子教材3a(共35页).doc》由会员分享，可在线阅读，更多相关《离散数学电子教材3a(共35页).doc（35页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选优质文档-倾情为你奉上第3章 集合与关系集合是数学中最基本的概念之一，是现代数学的重要基础，并且已渗透到各种科学与技术领域中。对计算机工作者来说，集合论是不可缺少的数学工具，例如在编译原理、开关理论、数据库原理、有限状态机和形式语言等领域中，都已得到广泛的应用。集合论的创始人是康托（G.Cantor，18451918）。他所做的工作一般称为朴素集合论。由于朴素集合论在定义集合的方法上缺乏限制，从而出现了称之为悖论的某些矛盾。为了消除这些悖论，很多数学家，象Hilbert、Fraenkel和Zermelo等都认真研究了产生悖论的原因，并在致力于问题解决的过程中，获得了种种出色的发现，由此导致

2、了公理化的集合论系统的建立，使集合理论日臻完善。本章介绍的集合论十分类似于朴素集合论，它具有数学分支的基本特征，象平面几何中的点、线、面一样，采纳不加定义的原始概念，提出符合客观实际的公设，确立推理关系的定理。在我们规定的范围内，既不会导致悖论，也不会影响结论的正确性。本章重点讨论关系（主要是二元关系），它仍然是一种集合，但它是一种更为复杂的集合。它的元素是序偶，这些序偶中的两个元素来自于两个不同或者相同的集合。因此，关系是建立在其它集合基础之上的集合。关系中的序偶反映了不同集合中元素与元素之间的关系，或者同一集合中元素之间的关系。本章将讨论这些关系的表示方法、关系的运算以及关系的性质，最后讨

3、论集合上几类特殊的关系。 3.1 集合的基本概念3.1.1 集合与元素 集合(set)（或称为集）是数学中的一个最基本的概念。所谓集合，就是指具有共同性质的或适合一定条件的事物的全体，组成集合的这些“事物”称为集合的元素。例如：班里的全体同学、全国的高等学校、自然数的全体、直线上的所有点等，均分别构成一个集合，而同学、高等学校、每个自然数、直线上的点等分别是所对应集合的元素。集合常用大写字母表示，集合的元素常用小写字母表示。若是集合，是的元素，则称属于，记作；若不是的元素，则称不属于，记作。若组成集合的元素个数是有限的，则称该集合为有限集(Finite Set)，否则称为无限集(Infinit

4、e Set)。表示集合的方法通常采用列举法和描述法。如果集合的所有元素都能列举出来，则可把它们写在大括号里表示该集合，此为列举法。例如，课桌，灯泡，自然数，老虎，。应该注意，与是不同的。表示一个元素；而表示仅含有一个元素的集合，称之为单元素集。如果可利用一项规则，以便决定某一事物是否属于该集合，此为描述法。例如： 是正奇数，是中国的省，或。如果我们用表示任何谓词，则可表示集合。设集合为，如果为真，那么，否则。3.1.2 集合间的关系外延性原理：如果、是集合, 则当且仅当的每一元素都是的元素而且的每一元素都是的元素时，有。当且仅当。 两个集合相等，记作；两个集合不相等，则记作。 集合的元素还可以

5、允许是一个集合。例如： 必须指出：但；同理，但。例题3.1.1(1) 但 在讨论的集合中，元素具有无序性且同一元素的重复没有意义。 (2) 设谓词：“为的元素或为的元素自身独自构成的集合”且设，则。 (3) 常见集合专用字符的约定： 自然数集合(非负整数集) (或)整数集合(，)有理数集合(，)实数集合(，)分数集合(，)脚标+和-是对正、负的区分复数集合素数集合奇数集合偶数集合(4)集合表示式的互换： 描述式列举式 定义3.1.1 设、是任意两个集合，假如的每一个元素是的元素，则称是的子集(Subset)，或包含在内，或包含，记作，或。例如：，则。定理3.1.1 集合和集合相等的充分必要条件

6、是这两个集合互为子集。证明： 设任意两个集合、且，故为真，且也为真，即且。反之，且，假设，则与的元素不完全相同，设有一元素且，这与矛盾；或设某一元素，但，这就与矛盾。故、的元素必须相同，即。根据子集的定义及定理3.1.1显然有：对任意两个集合，； （自反性） （反对称性） （传递性）定义3.1.2 若集合的每一个元素都属于，但集合中至少有一个元素不属于，则称是的真子集(Proper Subset)，记作，读作真包含于。 例如：整数集是有理数集的真子集。定义3.1.3 不包含任何元素的集合是空集(Empty Set)，记作。，是任意谓词。例如：是一个空集。注意：，但。定理3.1.2 对于任意一个

7、集合，。证明： 假设是假，则至少有一个元素，使且，因为空集不包含任何元素，所以这是不可能的。对于每个非空集合，至少有两个不同的子集：和，即和，我们称和是的平凡子集。一般的说，的每个元素都能确定的一个子集，即若，则。定义3.1.4 在一定范围内，如果所有集合均为某一集合的子集，则称该集合为全集(Universal Set)，记作。对于任一，因，故，即恒真 ，是任意谓词。全集的概念相当于论域，如在初等数论中，全体整数组成了全集。在考虑某大学的部分学生组成的集合（如系、班级等）时，该大学的全体学生组成了全集。3.1.3 幂集定义3.1.5 对于每一个集合，由的所有子集组成的集合，称为集合的幂集(Po

8、wer Set)，记为 或即。例如：, 。定理3.1.3 如果有限集有个元素，则其幂集有个元素。证明 的所有由个元素组成的子集数为从个元素中取个的组合数。另外，因，故的元素个数可表示为 又因 令 得 故的元素个数是。人们常常给有限集的子集编码，用以表示的幂集的各个元素。具体方法是：设，则子集按照含记、不含记的规定依次写成一个位二进制数，便得子集的编码。例如，若，则的编码是，当然还可将它化成十进制数。如果，那么这个十进制数为，此时特别记为。 习题3.11列举下列集合的元素：（1）小于的素数集合； （2）；（3）； （4）2给出下列集合的另一描述，并指出那些是无限集：（1）； (2) ； (3)

9、地球上的所有国家3确定下列命题是真还是假，并简要的说明为什么。（1）； （2）； （3）； （4）；（5）； （6）； （7）； （8）4对任意集合，试确定下列命题是否为真，并说明理由。（1）若且，则； （2）若且，则；（3）若且，则； （4）若且，则5设A，B，C为任意集合，证明或反驳下列命题：（1）； （2）；（3）； （4）；（5）； （6）； （7）； （8）； （9）6求下列集合的幂集：（1）； （2）； （3）； （4）的幂集； （5）7(1)设，1）是否？是否？2）是否？是否？3）是否？是否？ (2) 设，1）是否？是否？是否？是否？2）是否？是否？是否？是否？8设，由和所表达的

10、子集是什么？如何表达子集及？3.2 集合的运算3.2.1 集合的交与并定义3.2.1 设、是两个集合，由既属于又属于的元素构成的集合，称为与的交集，记为。即若以矩形表示全集，矩形内的圆表示任意集合，则交集的定义可如图3-1所示，并称这样表示的图为文氏图（Venn图）。 图3-1例如，（1）设，则；（2）设是所有矩形的集合，是平面上所有菱形的集合，是所有正方形的集合；（3）设是所有被除尽的整数的集合，是所有被除尽的整数的集合，则是被与最小公倍数除尽的整数的集合。例3.2.1 设，求证证明 若则，对任一，则且，即且，故，因此，。集合的交运算具有以下性质：（1）（2）（3）（4）（5）现对（5）证明

11、如下：证明 因此，。此外，从交的定义还可以得到，。若集合、没有共同的元素，则，此时亦称与不相交。个集合的交可记为例如，则。定义3.2.2 设、是两个集合，由所有属于或者属于B的元素构成的集合，称为与的并集，记为。即并集的定义如图3-2 所示。图3-2例如，若，则。集合并的运算具有以下性质：（1）（2）（3）（4）（5）此外，从并的定义还可以得到，。例3.2.2 设，则证明 对任意，则有或。若，由则，故；若，由，则，故。因此，。显然，当时， 。个集合的并可记为例如，设，则。定理3.2.1 设、为三个集合，则下列分配律成立。（1）（2）证明 （1）设，若，则且，即且或且，或即，所以。反之，若，则或

12、，且或且，即且，于是，所以。因此，。（2）同理可证。定理3.2.2 设、为任意两个集合，则下列关系式成立。（1）（2）证明 （1）（2）这就是著名的吸收律。定理3.2.3 （1），当且仅当（2），当且仅当证明 （1）若，对任意必有，对任意，则或，即，所以。又，故得到。反之，若，因为，故。（2）同理可证。3.2.2 集合的差与补定义3.2.3 设、为两个集合，由属于集合而不属于集合的所有元素组成的集合，称为与的差集，记作。即例如，若，则，而。再如，若是素数集合，是奇数集合，则。的定义如图3-3所示。图3-3 图3-4 定义3.2.4 设是一个集合，全集与的差集称为的补集，记为。即的定义如图3-4

13、所示。由补的定义可知：（1）（2）（3）（4）（5）定理3.2.4 设、为两个集合，则下列关系成立。（1）（2）上面两式称为de Morgen 公式。证明 （1）（2）对（1）式两端取余集得到 由于上式对任意的集合成立，若把换成，把换成，则（2）式得证。定理3.2.5 设、为两个集合，则下列关系成立。（1）（2）证明 （1）的证明请读者自己完成。下面我们证明（2）。（2）设，即且。因必有，故，即。又设，则且，即且，且或，但且是不可能的，故且，即，得到。因此，。定理3.2.6 设、为三个集合，则下列关系成立。（1）（2）证明 （1） （2）从略。定理3.2.7 设、为三个集合，则。证明 又 因此

14、， 特别， 注意： 即：一般 定理3.2.8 设、为两个集合，若，则(1)(2)(3)(4)证明（1）若，则，因此必有，故必有，即。（2）、（3）、(4) 从略。3.2.3 集合的对称差定义3.2.5 设、是两个集合，要么属于，要么属于，但不能同时属于和的所有元素组成的集合，称为和的对称差集，记为。即例如，若，则。对称差的定义如图3-5所示。图3-5由对称差的定义容易推得如下性质：（1）（2）（3）（4）（5）证明 （5）但 =故 又 因为 故 因此 对称差运算的结合性亦可用图3-6说明。 图3-6 对称差运算的结合性从文氏图3-7亦可以看出以下关系式成立。 图3-7 习题3.21设，求下列集

15、合：（1）； （2）；（3）； （4）；（5）； （6）； （7）； （6）2分别求下列各集合族的交与并：（1）（2）（3）3设是的子集，（4） 若且，是否？为什么？（5） 若且，是否？为什么？（6） 若，是否？为什么？（7） 若，是否？为什么？（8） 若，是否？为什么？（9） 是否？为什么？将改为，又如何？4如分别满足下列条件，则有何关系？（10） ；（11） ；（12）（13） ；（14） ；（15） .5设是任意集合，问在什么情况下下列等式成立？（16） ；（17） ；（18） ；（19） .6 证明下列等式：a) ；b) ；c) ；d) ；e) ；f) ；g) ；h) ；i) ；j)

16、；k) ；l) ；m) ；n) 。7 证明下列各对条件是等价的：（1）； （2）；（3）； （4）；（5）； （6）。8设是全集的子集，试用文氏图说明下列命题是否为真：(1) (2) (3) (4) (5) (6) (7) (8) (9) *3.3 包含排斥原理集合的运算，可用于有限个元素的计数问题。我们记为所含元素的个数，设是有限集合，根据集合运算的定义，有以下关系式成立。 这些公式可由文氏图3-8直接得到说明。图3-8 与的运算性质示意图求几个有限的集合的并集合的元素个数是一个实用且有趣的问题。定理3.3.1 设为有限集合，其元素个数分别为，则证明 （1）若不相交，即，则，而 ，公式显然成

17、立。（2）若，则所以 但 所以 这个定理常称作包含排斥原理。例 3.3.1 一个班级有名学生，有人第一次考试优秀，有人第二次考试优秀，其中人两次考试均优秀，问两次考试均未达优秀的学生有几名？解： 设第一次考试优秀者的集合为，第二次考试优秀者的集合为，根据题意有：，。又因为，则 （）=所以两次考试均未达优秀的学生有29名。对于任意三个集合和，我们可以推广定理3.3.1的结果为这个公式可以通过图3-9予以验证。图3-9 例 3.3.2 设、是3家计算机公司，它们的固定客户分别有，和家。已知与、与、与的公共固定客户分别为、和家，、3家的公共固定客户有家，求、3家计算机公司拥有的固定客户总数。 解 就

18、以、分别记三家计算机公司的客户集合，则有，和。由包含排斥原理得： 例 3.3.3 在某工厂装配30辆汽车，可供选择的设备是收音机、空气调节器和对讲机。已知其中辆汽车有收音机，辆汽车有空气调节器，辆汽车有对讲机，而其中辆汽车这三样设备都有。请问至少有多少辆汽车没有提供任何设备？解 设、和分别表示配有收音机、空气调节器和对讲机的汽车集合。因此， 并且 故 因为 我们得到 即至多有23辆汽车有一个或几个供选择的设备，因此至少有7辆汽车不提供任何可选择的设备。 对于包含排斥原理，可以推广到个集合的情况。定理3.3.2 设为有限集合，其元素个数分别为，则 (3-1)证明 用归纳法证明。（1） 归纳基础

19、（2） 归纳步骤设对个集合成立（归纳假设）。对个集合由归纳基础可得 (3-2)对于个集合，由归纳假设有 (3-3)另外对个集合，由归纳假设有 (3-4)将(3-3)、(3-4)带入(3-2)得（）整理后得 例 3.3.4 求到之间能被或任何一个整除的整数个数。解 设表示1到200间能被2整除的整数集合，表示1到200间能被3整除的整数集合，表示1到200间能被5整除的整数集合，表示1到200间能被7整除的整数集合。 表示小于或等于的最大整数。 于是得到习题3.31求11000之间（包含1和1000）既不能被5和6 整除，也不能被8整除的整数有多少个？2在1300的整数中（包括1和300），分别

20、求满足以下条件的整数的个数：（1）同时能被3，5和7 整除。（2）既不能被3和5 整除，也不能被7整除。（3）可以被3整除，但不能被5和7整除。（4）可以被3或5整除，但不能被7整除。（5）只能被3，5和7中的一个数整除。 3某班有25个学生，其中14人会打篮球，12人会打排球，6人会打篮球和排球，5人会打篮球和网球，还有2人会打这三种球。已知6个会打网球的人都会打篮球或排球。求不会打球的人数。3.4 序偶与笛卡尔积3.4.1 序偶 在日常生活中，有许多事物是成对出现的，而且这种成对出现的事物，具有一定的顺序。例如，上，下；男生9名而女生6；中国地处亚洲；平面上点的坐标等。一般的说，两个具有固

21、定次序的客体组成一个序偶(Ordered Pair)，记作。上述各例可分别表示为上，下；中国，亚洲；等。 序偶可以看作是具有两个元素的集合，但它与一般集合不同的是序偶具有确定的次序。在集合中，但对序偶，当时，。定义3.4.1 两个序偶相等，当且仅当。这里指出：序偶中两个元素不一定来自同一个集合，它们可以代表不同类型的事物。例如，代表操作码，代表地址码，则序偶就代表一条单地址指令；当然亦可将代表地址码，代表操作码，仍代表一条单地址指令。但上述这种约定，一经确定，序偶的次序就不能再予以变化了。在序偶中，称第一元素，称第二元素。序偶的概念可以推广到有序三元组的情况。有序三元组是一个序偶，其第一元素本

22、身也是一个序偶，可形式化表示为。由序偶相等的定义，可以知道当且仅当，即，我们约定有序三元组可记作。注意：，因为不是有序三元组。同理，有序四元组被定义为一个序偶，其第一元素为有序三元组，故有序四元组有形式为，可记作，且这样，有序元组(Ordered n-tuple)定义为，记作，且 一般地，有序元组中的称作有序元组的第个坐标。3.4.2 笛卡尔积 定义3.4.2 设和是任意两个集合，若序偶的第一个成员是的元素，第二个成员是的元素，所有这样的序偶集合，称为集合和的笛卡尔乘积或直积(Cartesian Product)，记作。即例3.4.1 若, 求以及解 显然，我们有：（1）；（2）如果，则。我们

23、约定：若或，则。由笛卡尔积定义可知： 由于不是三元组，所以定理3.4.1 设、和为任意三个集合，则有（1）（2）（3）（4）证明 （1）设 因此， 。（4）设 因此， 。定理3.4.2 设、和为三个非空集合，则有 证明 设，对任意的，因此， 。反之，若，取，则对，有因此，。定理的第二部分，证明类似。定理3.4.3 设、和为四个非空集合，则的充要条件为且。证明 若，对任意的，有 即 。反之，若且，设任意，有 因此， 。对于有限个集合可以进行多次笛卡尔积运算。为了与有序元组一致，我们约定：一般地，故是有序元组构成的集合。特别地，同一集合的次直积，记为, 这里。例如， 此处，。一般地，若 。习题3.

24、41设，试写出：(1) ； (2) ； (3) ；(4) ； (5) ； (6) 2试证：(1) ； (2) ； (3) 若，则；(4) ； (5) ；(6) 若，则；反之，若，则 3下列等式能否成立？ (1) ； (2) ；(3) ；(4) ；(5) ；(6) ；(7) ；(8) ；(9) ；(10) 3.5 关系及其表示3.5.1 关系的定义 在日常生活中我们都熟悉关系这词的含义，例如，父子关系、上下级关系、朋友关系等。我们知道，序偶可以表达两个客体、三个客体或个客体之间的联系，因此可以用序偶表达关系这个概念。例如，机票与舱位之间有对号关系。设表示机票的集合，表示舱位的集合，则对于任意的和

25、，必有与有对号关系和与没有对号关系两种情况的一种。令表示“对号”关系，则上述问题可以表达为或，亦可记为或，因此，我们看到对号关系是序偶的集合。定义3.5.1 设、是任意两个集合，则称直积的任一子集为从到的一个二元关系(Binary Relation )。二元关系亦简称关系，记为，。到的二元关系，如图3-10所示。 图3-10集合到的二元关系是第一坐标取自、第二坐标取自的序偶集合。如果序偶，也说与有关系，记为；如果序偶，则说与没有关系，记为。当时，关系是的子集，这时称为集合上的二元关系。例3.5.1 （1）设，则，令因为，所以，和均是由到的关系。（2）=是实数且是实数集上的大于关系。定义3.5.

26、2 设为到的二元关系，由的所有组成的集合称为的定义域或前域(Domain)，记作dom或，即 dom使的所有组成的集合称为的值域(Range)，记作ran，即ran。的定义域和值域一起称作的域(Field)，记作FLD，即FLD domran显然，dom，ran，FLDdomran例3.5.2 设，求dom，ran 和FLD。解 dom，ran ，FLD。 例3.5.3 设，求集合上的关系“”、dom及ran。 解 domran3.5.2 几种特殊的关系1空关系对任意集合，所以是由到的关系，也是上的关系，称为空关系(Empty Relation)。2全域关系因为，所以是一个由到的关系，称为由到

27、的全域关系(Universal Relation)。是上的一个关系，称为上的全域关系，通常记作，即。例3.5.4 若表示家庭中父、母、子、女四个人的集合，确定上的全域关系和空关系，另外再确定上的一个关系，并指出该关系的前域和值域。解 设上同一家庭的成员的关系为， 设上的互不相识的关系为，则为全域关系，为空关系。设上的长幼关系为，domran3恒等关系定义3.5.3 设是上的二元关系且满足，则称是上的恒等关系(Identical Relation)。例如，则。因为关系是序偶的集合，因此，可以进行集合的所有运算。定理3.5.1 若和是从集合到集合的两个关系，则、的并、交、补、差仍是到的关系。证明

28、因为 故 例3.5.5 若，求 ，和。解 ， 3.5.3 关系的表示 1集合表示法因为关系是序偶的集合，因此可用表示集合的列举法或描述法来表示关系。例如，例3.5.1的（1）中的关系，和及例3.5.2中的关系，均是用列举法表示的关系；而例3.5.1的（2）中的关系和例3.5.5中的关系，都是用描述法表示的关系。有限集合间的二元关系除了可以用序偶集合的形式表达以外，还可用矩阵和图形表示，以便引入线性代数和图论的知识来讨论。2矩阵表示法 设给定两个有限集合，则对应于从到的二元关系有一个关系矩阵，其中 。 如果是有限集合上的二元关系或和含有相同数量的有限个元素，则是方阵。例3.5.6 若，写出关系矩

29、阵。解 例3.5.7 设，写出集合上的大于关系的关系矩阵。 解 3关系图表示法有限集合的二元关系也可用图形来表示。设集合到上的一个二元关系为，首先我们在平面上做出个结点分别记作，另外做个结点分别记作。如果，则从结点至结点做一有向弧，其箭头指向，如果，则之间没有线段连接。用这种方法连接起来的图称为的关系图。例3.5.8 画出例3.5.6的关系图。解 本题的关系图如图3-11所示： 图3-11 例3.5.8的关系图例3.5.9 设，画出的关系图。 解 因为是上的关系，故只需画出中的每个元素即可。如果，就画一条由到的有向弧。若，则画出的是一条自回路。本题的关系图如图3-12所示。 3 2 1 45

30、图3-12 例3.5.9的关系图关系图主要表达结点与结点之间的邻接关系，故关系图与结点位置和线段的长短无关。从到的关系是的子集，即，而，所以，。令，则。因此，我们今后通常限于讨论同一集合上的关系。习题3.51对于下列各种情况，用列举法求出到的关系，dom，ran，画出的关系图，写出的关系矩阵。 (1) (2) 2设，求出。并证明：；。3用表示“小于或等于”，表示“整除”，和的定义域均是，试将和表示成集合，并求出。4设集合的基数为，上的不同关系共有多少种？3.6 关系的性质及其判定方法3.6.1 关系的性质定义3.6.1设是定义在集合上的二元关系，如果（1）对于每一个，都有，则称是自反的(Ref

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

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

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

34、即是整数，则也必是整数，即，因此是对称的。3.6.2 由关系图、关系矩阵判别关系的性质例3.6.4 集合，上的关系的关系矩阵为：，的关系图如图3-14所示。讨论的性质。图3-14解 从的关系矩阵和关系图容易看出，是自反的、对称的。一般地，我们有：（1）若关系是自反的，当且仅当其关系矩阵的主对角线上的所有元素都是1；其关系图上每个结点都有自环。（2）若关系是对称的，当且仅当其关系矩阵是对称矩阵；其关系图上任意两个结点间若有定向弧，必是成对出现的。（3）若关系是反自反的，当且仅当其关系矩阵的主对角线上的元素皆为0；关系图上每个结点都没有自环。（4）若关系是反对称的，当且仅当其关系矩阵中关于主对角线

35、对称的元素不能同时为1；其关系图上任意两个不同结点间至多出现一条定向弧。（5）若关系是可传递的，当且仅当其关系矩阵满足：对，若且，则；其关系图满足：对，若有弧由指向，且又有弧由指向，则必有一条弧由指向。 例3.6.5 图3-15是由关系图所表示的上的5个二元关系。 （1） （2）（3） （4） （5）图3-15请判断它们的性质。解 (1) 是反对称、传递但不是对称的关系，而且是既不自反也不反自反的关系；(2) 是自反、传递、反对称的关系，但不是对称也不是反自反的关系；(3) 是反自反但不是对称、不是反对称、不是自反也不是传递的关系；(4) 是不自反、不反自反但是传递的关系，而且既是对称也是反对

36、称的关系； (5) 是自反、反对称但不是传递、不是对称也不是反自反的关系。 习题3.61设集合及其上的关系如下给定，试问关系有哪些性质？（1） 为正整数集，为偶数；（2） 为整数集，被整除；（3） 为4维实欧氏空间，当且仅当2设是任一非空集合上的二元关系，如果某一集合的运算施于关系后，所得关系仍具有相同的性质，那么说一个关系的性质在该集合运算下是保持的，否则称是不保持的。按照在指出的集合运算下给出的性质是否保持，填充下表，对每一个是的给出证明，对每一个非的给出反例。 自反的反自反的对称的反对称的传递的3下面哪些关系是传递的？哪些不是？为什么？对于不是传递的关系，求一个关系且是可传递的。能否再找

37、出一个具有此性质的关系？ 。4设，上的关系，试给出的关系图及对应的关系矩阵。5设，上的关系的关系矩阵如下，试问是不是自反的、反自反的、对称的、反对称的和传递的？（1） （2） （3）（4） （5）6设为具有个元素的集合，试问（1）上共有多少种二元关系？ （2）既为对称又为反对称的二元关系有多少？（3）为反对称的二元关系有多少？ （4）为自反的二元关系有多少？7在平面上画出下述关系的关系图，并确定每一关系具有哪些基本性质。 （1）； （2）； （3）3.7 复合关系和逆关系3.7.1 复合关系 1. 复合关系的定义定义3.7.1 设是从到的关系，是从到的关系，则称为和的复合关系(Composit

38、ive Relation)，表示为从和求，称为关系的复合运算。复合运算是关系的二元运算，它能够由两个关系生成一个新的关系，以此类推。例如，是从到的关系，是从到的关系，是从到的关系，则是从到的关系。例3.7.1设是由到的关系，是由到 的关系，分别定义为：于是复合关系。例3.7.2 设是所有人的集合。，那么；而。例3.7.3 设和是集合上的关系，或，求、和。解 2. 关系的复合运算的性质定理3.7.1 设是由集合到的关系，则。定理3.7.2 设是从到的关系，是从到的关系，则有（1）（2）（3）若，则。证 （1）和（2）是显然的，下面我们证明（3）。用反证法。反设，则必存在，使，从而，使，故且 ，所以，这就与矛盾，因此，。定理3.7.3 （1）设、和分别是从到、到和到的关系，则即关系的复合运算满足结合律。（2）设和都是从到的关系，是从到的关系，则1）2）（3）设是从到的关系，和都是从到的关系，则1） 2）证 我们只证明（