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

《计算机数学基础(上)离散数学部分》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

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ÚP)用P替代，miÚmi(MiÙMi)用m

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

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

8、每一个变项都有个体域中的元素相对应。解释有四部分组成：(1)非空个体域D；(2)