离散数学教案88897

《离散数学教案88897》由会员分享，可在线阅读，更多相关《离散数学教案88897（39页珍藏版）》请在金锄头文库上搜索。

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

2、、最大（小）元。主要内容：1集合的基本概念及其运算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-

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

7、偶就代表一条单地址指令；当然亦可将代表地址码，代表操作码，仍代表一条单地址指令。但上述这种约定，一经确定，序偶的次序就不能再予以变化了。在序偶中，称第一元素，称第二元素。序偶的概念可以推广到有序三元组的情况。有序三元组是一个序偶，其第一元素本身也是一个序偶，可形式化表示为。由序偶相等的定义，可以知道当且仅当，即，我们约定有序三元组可记作。注意：，因为不是有序三元组。同理，有序四元组被定义为一个序偶，其第一元素为有序三元组，故有序四元组有形式为，可记作，且这样，有序元组(Ordered n-tuple)定义为，记作，且 一般地，有序元组中的称作有序元组的第个坐标。3.4.2 笛卡尔积 定义3.4

8、.2 设和是任意两个集合，若序偶的第一个成员是的元素，第二个成员是的元素，所有这样的序偶集合，称为集合和的笛卡尔乘积或直积(Cartesian Product)，记作。即例3.4.1 若, 求以及解 显然，我们有：（1）；（2）如果，则。我们约定：若或，则。由笛卡尔积定义可知： 由于不是三元组，所以定理3.4.1 设、和为任意三个集合，则有（1）（2）（3）（4）证明 （1）设 因此， 。（4）设 因此， 。定理3.4.2 设、和为三个非空集合，则有 证明 设，对任意的，因此， 。反之，若，取，则对，有因此，。定理的第二部分，证明类似。定理3.4.3 设、和为四个非空集合，则的充要条件为且。证

9、明 若，对任意的，有 即 。反之，若且，设任意，有 因此， 。对于有限个集合可以进行多次笛卡尔积运算。为了与有序元组一致，我们约定：一般地，故是有序元组构成的集合。特别地，同一集合的次直积，记为, 这里。例如， 此处，。一般地，若 。3.5 关系及其表示3.5.1 关系的定义 在日常生活中我们都熟悉关系这词的含义，例如，父子关系、上下级关系、朋友关系等。我们知道，序偶可以表达两个客体、三个客体或个客体之间的联系，因此可以用序偶表达关系这个概念。例如，机票与舱位之间有对号关系。设表示机票的集合，表示舱位的集合，则对于任意的和，必有与有对号关系和与没有对号关系两种情况的一种。令表示“对号”关系，则

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

11、作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全域关系因为，所以是一个由到的关系，称为由到的全域关系(Universal Relation)。是上的一个关系，称为上的全

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