离散数学第二章.ppt

2017-2-15 1第二章第二章二元关系二元关系本章讨论的关系是我们通常的诸如大小关系、整除关系、上下级等关系的共同的数学模型,掌握关系运算极其关系运算的性质、、关系图、关系矩阵之间的联系,熟练地掌握两类特殊的关系—等价关系与偏序关系;熟练地用 Warshall 算法求关系的传递闭包;理解映射的意义,本章为第三、六、七章的基础. 返回首页 2017-2-15 2第一节第一节序偶与笛卡尔积序偶与笛卡尔积?本节是通过 n元有序组的概念来定义序偶与笛卡尔积的概念,主要讨论两个集合的笛卡尔积,. 返回本章首页 2017-2-15 3第二节第二节关系的概念关系的概念本节在笛卡尔积的基础上给出二元关系定义,并推广成 n元关系,不过我们以讨论二元关系为主. 主要内容为:,如空关系、恒等关系、全关系;,如关系的并、交、补、差、对称差极其运算规律;(即关系矩阵与关系图), ,我们定义了布尔矩阵的概念及布尔矩阵的三种运算(即布尔非、布尔与、布尔或). 返回本章首页 2017-2-15 4第三节第三节复合关系与逆关系复合关系与逆关系?本节讨论关系的复合运算与逆运算极其性质;主要考虑了下列问题: ?、结合律、关系的复合对于集合的并(交)是否有分配律; ?; ?. 返回本章首页 2017-2-15 5第四节第四节关系的性质关系的性质?本节我们讨论关系的一些常见性质,主要内容是: 1. 给出了关系的自反性、对称性、反对称性、传递性的定义; 2. 给出了关系的自反性、对称性、反对称性、传递性等在关系矩阵及关系图上的反应,其中用关系矩阵及关系图来判断传递性较为困难; 3. 讨论了关系的各种运算对上述特性的影响. 返回本章首页 2017-2-15 6第五节第五节关系的闭包关系的闭包(1) (1) 我们希望某个关系具有比较好的性质,比如我们希望它具有自反性,对称性,传递性. 但如果该关系又不具有上述性质,那么我们就要对该关系进行适当的改造,即在该关系中适当添加一些元素得到一个新的关系,使这个新关系具有我们需要的性质,同时新关系与原来的关系不要相差得太多,, 使得到的具有我们需要的性质的新关系称为原关系的闭包,我们通常考虑关系的三种闭包,即自反闭包,对称闭包,传递闭包. 返回本章首页 2017-2-15 7第五节第五节关系的闭包关系的闭包(2) (2) ?本节的内容较丰富,主要有: 1. 给出了关系的自反闭包、对称闭包、传递闭包的定义; 2. 从理论上证明了自反闭包、对称闭包、传递闭包的存在性,其中传递闭包较为复杂, 是本节重点; 3. 给出了上述三种闭包的具体计算公式; 4. Warshall 算法是求有限集合上的二元关系的传递闭包的有效算法; 5. 考虑了关系的闭包与关系的其它运算的联系. 返回本章首页 2017-2-15 8第六节第六节等价关系等价关系?等价关系是一类最为重要的关系,因为等价关系与集合的分类密切相关,内容有 1. 以同余关系为例给出等价关系的定义; 2. 给出了商集的概念 3. 主要结论是:等价关系与集合的分类相互惟一确定; 返回本章首页 2017-2-15 9第七节第七节偏序关系偏序关系?数的大小,集合中元素的排列次序,计算机程序的执行顺序等都牵涉到次序关系,这些在数学上都表现为序关系的研究,本节主要内容有: 、反对称性、传递性的关系称为偏序关系;—哈斯图,哈斯图与原图的关系是一种压缩与解压缩的关系; (如书中定理 ); ,如最大、最小元,极大、极小元,上界、下界等; ,如全序关系,良序关系等. 返回本章首页 2017-2-15 10第八节第八节映射映射?映射是高等数学中所研究的单值函数的推广,因此映射也称为函数,这里我们把映射视为一种特殊的二元关系,内容有: 1. 映射的定义、象与原象、定义域与值域、映射的相等、映射的限制与扩充; 2. 一些特殊的映射,如满射、单射、双射. 返回本章首页