离散数学教案.doc

《离散数学教案.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、学习目标：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集合的基本概念

4、集合(set)（或称为集）是数学中的一个最基本的概念。所谓集合，就是指具有共同性质的或适合一定条件的事物的全体，组成集合的这些“事物”称为集合的元素。集合常用大写字母表示，集合的元素常用小写字母表示。若是集合，是的元素，则称属于，记作；若不是的元素，则称不属于，记作。若组成集合的元素个数是有限的，则称该集合为有限集(FiniteSet)，否则称为无限集(InfiniteSet)。常见集合专用字符的约定：—自然数集合(非负整数集)(或)—整数集合(，)—有理数集合(，)—实数集合(，)—分数集合(，)脚

5、标+和-是对正、负的区分—复数集合—素数集合—奇数集合—偶数集合幂集定义3.1.1对于每一个集合，由的所有子集组成的集合，称为集合的幂集(PowerSet)，记为或．即。例如：,。定理3.1.1如果有限集有个元素，则其幂集有个元素。证明的所有由个元素组成的子集数为从个元素中取个的组合数。另外，因，故的元素个数可表示为又因令得故的元素个数是。人们常常给有限集的子集编码，用以表示的幂集的各个元素。具体方法是：设，则子集按照含记、不含记的规定依次写成一个位二进制数，便得子集的编码。例如，若，则的编码是，当然

6、还可将它化成十进制数。如果，那么这个十进制数为，此时特别记为。3.2集合的对称差运算定义3.2.1设、是两个集合，要么属于，要么属于，但不能同时属于和的所有元素组成的集合，称为和的对称差集，记为。即例如，若，，则。对称差的定义如图3-1所示。图3-1由对称差的定义容易推得如下性质：（1）（2）（3）（4）（5）证明（5）但=故又因为故因此对称差运算的结合性亦可用图3-2说明。图3-2对称差运算的结合性从文氏图3-3亦可以看出以下关系式成立。图3-33.4序偶与笛卡尔积3.4.1序偶在日常生活中，有许多

7、事物是成对出现的，而且这种成对出现的事物，具有一定的顺序。例如，上，下；；男生9名而女生6；中国地处亚洲；平面上点的坐标等。一般的说，两个具有固定次序的客体组成一个序偶(OrderedPair)，记作。上述各例可分别表示为〈上，下〉；；；〈中国，亚洲〉；等。序偶可以看作是具有两个元素的集合，但它与一般集合不同的是序偶具有确定的次序。在集合中，，但对序偶，当时，。定义3.4.1两个序偶相等，，当且仅当。这里指出：序偶中两个元素不一定来自同一个集合，它们可以代表不同类型的事物。例如，代表操作码，代表地址码

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