《离散数学教案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 若,