计算机数学基础(上)离散数学部分

1、计算机数学基础(上)离散数学部分期末复习中央电大基础部数理教研室计算机数学基础是中央广播电视大学本科开放教育计算机科学与技术专业学生必修的一门专业基础课程，是学习专业理论必不可少的数学工具。 本课程分两个学期学习，本学期的教学内容是“计算机数学基础(上)¾¾离散数学”部分，共计72学时，4学分。本学期使用的教材是由任现淼主编、吴裕树副主编的计算机数学基础(上)¾¾离散数学，由中央广播电视大学出版社出版。一、期末考试题型试题类型及分数分别为单项选择题和填空题各有5题，分数约占25；化简解答题与计算题，分数约占56；证明题，分数约占19。各章分数的比例大致与

2、其所用课时比例相同。单项选择题和填空题主要涉及基本概念、基本理论、重要性质和结论、公式及其简单计算。单项选择题给出四个备选答案，其一正确。填空题只需填写正确结论，不写计算、推论过程或理由。化简解答题与计算题主要考核学员的基本运算技能和速度，要求写出计算过程。证明题主要考查应用概念、性质、定理及重要结论进行逻辑推理的能力，要求写出推理过程。 本学期期末复习应以中央电大考试处编发的计算机数学基础(上)离散数学部分考核说明为依据。 二、各章复习要求和重点第1章 命题逻辑 复习要求1. 理解命题概念，掌握判断语句是不是命题的方法。 判断一个语句是否为命题，应首先判断它是否为陈述句。再判断它是否有唯一的

3、真值。因此，命题必须具备二个条件：其一，语句是陈述句；其二，语句有唯一确定的真假意义。2. 了解六个联结词概念，掌握由它们构成的公式及真值表：ØP(否定式); PÙQ(合取式);PÚQ(析取式);P® Q (蕴含式);P« Q (等价式)；PÚ Q (不可兼析取式)。会将命题符号化。 熟练掌握求给定公式真值表的方法。3. 理解公式、公式解释、永真式(重言式)、永假式(矛盾式)和可满足式等概念。 掌握基本等值式以及用真值表法和等值演算法判别公式类型和公式等值的方法。判别公式类型的真值表法：对于任给一个公式，列出该公式的真值表，观察真值表

4、的最后一列的情况。若真值表的最后一列全部为1，则该公式为永真式；若真值表的最后一列全部为0，则该公式是永假式；若真值表的最后一列既非全部为1，又非全部为0，则该公式是可满足式。 判别公式类型的等值演算法：利用基本等值式(双重否定律、幂等律、交换律、结合律、分配律、吸收律、摩根律、同一律、零律、否定律、蕴含等值式、等价等值式、假言易位和等价否定等值式等)，对给定公式进行等值推导，若该公式的真值为1，则该公式是永真式；若该公式的真值为0，则该公式为永假式。 4. 了解析取(合取)范式概念，理解极小(大)项的概念和主析取(合取)范式概念，熟练掌握用基本等值式或真值表将公式化为主析取(合取)范式的方法

5、。求析取(合取)范式的步骤： 将公式中的联结词都化成Ø，Ù，Ú，在析取(合取)范式中不能有联结词®，«，Ú； 将否定联结词Ø消去或移到各命题变项之前； 利用分配律、结合律等，将公式化为析取(合取)范式。求命题公式A的主析取(合取)范式的步骤 求公式A的析取(合取)范式； “消去”析取(合取)范式中所有永假式(永真式)的析取项(合取项)，如PÙØP(PÚØP)用0(1)替代。用幂等律将析取(合取)范式中重复出现的合取项(析取项)或相同的变项合并，如P Ù P (P Ú

6、 P)用P替代，miÚ mi (Mi Ù Mi)用mi (Mi)替代。 若析取(合取)范式的某个合取项(析取项)B不含有命题变项Pi或Ø Pi ，则添加Pi ÚØ Pi (Pi ÙØ Pi )，再利用分配律展开，使得每个合取项(析取项)的命题变项齐全； 将极小(极大)项按由小到大的顺序排列，用S(P)表示。5. 了解有效结论(逻辑结果)的概念，掌握判断重言蕴含式(推理是否有效)的五种方法 (1) 真值表法；(2) 等值演算法(记住基本等值式)；(3) 主析取(合取)范式法；(4) 直接证法：掌握P规则和T规则，及常用重言蕴含

7、式、等值式。 (5) 间接证法(反证法)：掌握CP规则。本章重点：命题与联结词，公式与解释，真值表，(主)析取(合取)范式，重言式的判定。第2章谓词逻辑 复习要求1. 理解谓词、量词、个体词、个体域、原子公式、谓词公式和变元等概念。会将命题符号化。在谓词逻辑，使用量词应注意以下几点：(1) 在不同个体域中，命题符号化的形式可能不同，命题的真值也可能会改变。(2) 在考虑命题符号化时，如果对个体域未作说明，一律使用全个体域。 (3) 多个量词出现时，不能随意颠倒它们的顺序，否则可能会改变命题的涵义。 2. 掌握在有限个体域下消去公式的量词和求公式在给定解释下真值的方法。 谓词公式只是一个符号串，

8、没有什么意义，但我们给这个符号串一个解释，使它具有真值，就变成一个命题。所谓解释就是使公式中的每一个变项都有个体域中的元素相对应。解释有四部分组成：(1) 非空个体域D；(2) D中有一部分特定元素，用来解释个体常项；(3) D上一些特定函数，用来解释出现的函数变项； (4) D上一些特定谓词，用来解释谓词变项。 3. 掌握谓词演算的等值式和重言蕴含式，并进行谓词公式的等值演算。 谓词演算的等值式和重言蕴含式的六种情况：(1) 命题公式的推广；(2) 量词否定式的等值式；(3) 量词辖域扩张和收缩的等值式；(4) 量词与联结词Ú，Ù，®的等值式；(5) 量词与联结

9、词的重言蕴含式；(6) 两个量词公式间的等值式与重言蕴含式。4. 了解前束范式的概念，掌握求公式的前束范式的方法。每个谓词公式F都可以变换成与它等值的前束范式。其步骤如下： 消去联结词®，«，Ú； 将联结词Ø向内深入，使之只作用于原子谓词公式； 利用换名或代入规则使所有约束变元的符号均不同，并且自由变元与约束变元的符号也不同； 利用量词辖域的扩张和收缩律，扩大量词的辖域至整个公式； 利用分配律将公式化为前束范式。 5. 了解谓词逻辑推理的规则：全量词消去规则(US规则)；全量词附加规则(UG规则)；存在量词消去规则(ES规则)；存在量词附加规则(EG规则

10、)，会给出推理证明。 谓词演算的推理是命题演算推理的推广和扩充，命题演算中的一些规则，如基本等值公式，重言蕴含式以及P，T，CP规则在谓词演算中仍然使用。但是在谓词演算推理中，某些前提和结论可能受到量词的限制，为了使用这些推理，必须在推理过程中，有消去和附加量词的规则，即US规则(全称量词消去规则)，UG规则(全称量词附加规则)，ES规则(存在量词消去规则)，EG规则(存在量词附加规则)等，以便使谓词演算公式的推理过程可类似于命题演算的推理进行。本章重点：谓词与量词，公式与解释，前束范式，谓词逻辑推理证明。第3章 集合及其运算 复习要求1. 理解集合、元素、全集、空集等概念。2. 理解集合的包

11、含、子集、相等和幂集等概念，熟练掌握集合的表示方法和集合的并、交、补、差和对称差等运算，会用文氏图表示集合的各种运算。 3. 掌握用集合运算基本规律证明集合恒等式的方法。 集合的运算主要有集合的运算、集合运算式的化简和集合恒等式的推理证明等三个方面的问题。集合恒等式证明的目的有两个，其一是通过证明的练习，加深对集合性质和第1章命题公式基本等值式的理解和掌握；其二是为第8章学习布尔代数中部分性质的应用打下良好的基础。集合恒等式的证明方法通常有两种：其一，要证明AB，就需要证明AÍ B；在证明A Ê B 。其二，通过运算律进行等式推导。 4. 了解有序对和笛卡儿积的概念，掌握笛

12、卡儿积的运算。 本章重点：集合概念，集合的运算，集合恒等式的证明。笛卡儿积。第4章 关系与函数 复习要求1. 理解关系的概念：二元关系、空关系、全关系、恒等关系。掌握关系的集合表示、关系矩阵和关系图，掌握关系的运算。2. 掌握求复合关系和逆关系的方法。3. 理解关系的五种性质，掌握其判别方法(定义、矩阵或图)。 关系的性质及判别方法 自反性：；矩阵的主对角线元素全为1；关系图的每个结点都有自回路。 反自反性：；矩阵的主对角线元素全为0；关系图的每个结点都没有自回路。 对称性：若，则；矩阵是对称矩阵，即；有向关系图中有向弧成对出现。 反对称性：若，则x = y或若，则；矩阵不出现对称元素；关系图

13、中没有成对弧出现。 传递性：若，则；在关系图中，有从A到B的弧，有从B到c的弧，则有从A到c的弧。 4. 理解等价关系和偏序关系概念，掌握等价类的求法和作偏序关系哈斯图的方法。知道极大(小)元，最大(小)元的概念，会求极大(小)元、最大(小)元、最小上界和最大下界。 等价关系和偏序关系是两种最重要的关系。它们具有不同的性质。等价关系图的特点是：每一个结点都有一个自回路，两个结点间如有有向弧线，则一定是双向弧线，如果从A到B，从B到c各有一条有向弧线，则从A到c一定有有向弧线。若R是等价关系，与R中的某个元素等价的所有元素作为整体，就是一个等价类。就可以把R分成若干个等价类(子集)。偏序关系是第

14、8章偏序格的基础，理解和掌握偏序关系和偏序集概念的关键是哈斯图。哈斯图的画法掌握了，对于确定任一子集的最大(小)元，极大(小)元也就容易了。这里要注意，最大(小)元与极大(小)元只能在子集内确定。而上界与下界可在子集之外的全集中确定，最小上界是所有上界中最小者，最小上界再小也不会小于子集中的任一元素；可以与某一元素相等，最大下界也是同样。 5. 理解函数概念：函数(映射)，函数相等，复合函数和反函数。 函数是一种特殊的关系，集合A×B的任何子集都是关系，但不一定是函数。函数要求对于定义域A中每一个元素A，B中有且仅有一个元素与A对应，而关系没有这个限制。二函数相等是指：定义域相同，对

15、应关系相同，而且定义域内每个对应值都相同。 6. 理解单射、满射和双射等概念，掌握其判别方法。 函数的类型（单射、满射、双射）：判定的方法除定义外，还可借助于关系图。而实数集的子集上的函数，也可以用直角坐标表示，尤其是初等函数。本章重点：关系概念与其性质，等价关系和偏序关系，函数。第5章 图的基本概念 复习要求1. 理解图的概念：结点、边、有向图，无向图、图的同构、简单图、完全图、结点的度数、子图、边的重数和平行边等理解握手定理：。2. 了解通路与回路概念：通路(简单通路、初级通路和复杂通路)，回路(简单回路、初级回路和复杂回路) 会求通路和回路的长度。3. 了解无向图的连通性，会求无向图的连通分支。了解点割集、割点、边割集、割边、点连通度、边连通度等概念。4. 了解有向图的强连通强性；会判别其类型5. 了解(