离散数学期末复习要点与重点

《离散数学期末复习要点与重点》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、离散数学期末复习要点与重点离散数学是中央广播电视大学开放教育本科电气信息类计算机科学与技术专业的一门统设必修学位课程，共72学时，开设一学期．该课程的主要内容包括：集合论、图论、数理逻辑等．下面按章给出复习要点与重点．第1章集合及其运算复习要点1．理解集合、元素、集合的包含、子集、相等，以及全集、空集和幂集等概念，熟练掌握集合的表示方法．具有确定的，可以区分的若干事物的全体称为集合，其中的事物叫元素.．集合的表示方法：列举法和描述法.注意：集合的表示中元素不能重复出现，集合中的元素无顺序之分．掌握集合包含(子集)、真子集、集合相等等概念．注意：元素与集合，集

2、合与子集，子集与幂集，Î与Ì(Í),空集Æ与所有集合等的关系.空集Æ，是惟一的，它是任何集合的子集．集合A的幂集P(A)＝，A的所有子集构成的集合．若½A½＝n，则½P(A)½=2n．2．熟练掌握集合A和B的并AÈB，交AÇB，补集~A(~A补集总相对于一个全集).差集A－B，对称差Å，AÅB＝(A－B)È(B－A)，或AÅB＝(AÈB)－（AÇB）等运算，并会用文氏图表示．掌握集合运算律(见教材第9～11页)(运算的性质).3．掌握用集合运算基本规律证明集合恒等式的方法．集合的运算问题：其一是进行集合运算；其二是运算式的化简；其三是恒等式证明．证明方法有二

3、：(1)要证明A＝B，只需证明AÍB，又AÊB；(2)通过运算律进行等式推导．重点：集合概念，集合的运算，集合恒等式的证明．第2章关系与函数复习要点1．了解有序对和笛卡儿积的概念，掌握笛卡儿积的运算．有序对就是有顺序二元组，如，x,y的位置是确定的，不能随意放置．注意：有序对¹，以a,b为元素的集合{a,b}={b,a}；有序对(a,a)有意义，而集合{a,a}是单元素集合，应记作{a}．集合A，B的笛卡儿积A×B是一个集合，规定A×B＝{½xÎA,yÎB}，是有序对的集合.笛卡儿积也可以多个集合合成，A1×A2×…×

4、An．2．理解关系的概念：二元关系、空关系、全关系、恒等关系.掌握关系的集合表示、关系矩阵和关系图，掌握关系的集合运算和求复合关系、逆关系的方法．二元关系是一个有序对集合，，记作xRy．关系的表示方法有三种：集合表示法，关系矩阵：RÍA×B，R的矩阵.6关系图：R是集合上的二元关系，若ÎR，由结点ai画有向弧到bj构成的图形．空关系Æ是唯一、是任何关系的子集的关系；全关系；恒等关系，恒等关系的矩阵MI是单位矩阵．关系的集合运算有并、交、补、差和对称差．复合关系；复合关系矩阵：(按布尔运算)；有结合律：(R·S)·T＝R·(S·T)，一般不可交换

5、．逆关系；逆关系矩阵满足：；复合关系与逆关系存在：(R·S)－1=S－1·R－1．3．理解关系的性质(自反性和反自反性、对称性和反对称性、传递性的定义以及矩阵表示或关系图表示)，掌握其判别方法(利用定义、矩阵或图，充分条件)，知道关系闭包的定义和求法．注：(1)关系性质的充分必要条件：①R是自反的ÛIAÍR；②R是反自反的ÛIAÇR＝Æ；③R是对称的ÛR＝R－1；④R是反对称的ÛRÇR－1ÍIA；⑤R是传递的ÛR·RÍR.(2)IA具有自反性，对称性、反对称性和传递性．EA具有自反性，对称性和传递性．故IA，EA是等价关系．Æ具有反自反性、对称性、反对称性和

6、传递性．IA也是偏序关系．4．理解等价关系和偏序关系概念，掌握等价类的求法和作偏序集哈斯图的方法．知道极大(小)元，最大(小)元的概念，会求极大(小)元、最大(小)元、最小上界和最大下界．等价关系和偏序关系是具有不同性质的两个关系.知道等价关系图的特点和等价类定义，会求等价类．一个子集的极大(小)元可以有多个，而最大(小)元若有，则惟一.且极元、最元只在该子集内；而上界与下界可以在子集之外．由哈斯图便于确定任一子集的最大(小)元，极大(小)元．5．理解函数概念：函数(映射)，函数相等，复合函数和反函数．理解单射、满射和双射等概念，掌握其判别方法．设f是集合A

7、到B的二元关系，"aÎA，存在惟一bÎB，使得Îf，且Dom(f)=A，f是一个函数(映射)．函数是一种特殊的关系．集合A×B的任何子集都是关系，但不一定是函数．函数要求对于定义域A中每一个元素a，B中有且仅有一个元素与a对应，而关系没有这个限制．二函数相等是指：定义域相同，对应关系相同，而且定义域内的每个元素的对应值都相同．函数有：单射——若；满射——f(A)=B或使得y=f(x)；双射——单射且满射．6复合函数即．复合成立的条件是：．一般，但.反函数——若f：A®B是双射，则有反函数f－1：B®A，，重点：关系概念与其性质，等价关系和偏序关系，

8、函数.第3章图的基本概念复习要点1．理解图的概念：结