离散数学（总复习）

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

1、陈瑜Email：yuchen@scu.edu.cn7/19/2021离散　　数学计算机学院总复习（一）主要内容基本概念基本原理和计算基本证明方法7/19/20212计算机学院第一章一、基本概念命题、命题常元、命题变元、命题的解释或赋值、原子命题(简单命题)、复合命题、否定联结词～、合取、析取、可兼或、不可兼或、条件、双条件、常值命题、命题变量、命题公式、命题公式的解释、真值表、永真公式(重言式)、永假公式(矛盾式，不可满足公式)、可满足公式、公式的等价、对偶（公）式、对偶原理、子句、短语、析取范

2、式、合取范式、主析取（主合取）范式、极小项、极大项7/19/20213计算机学院二、基本要求1、深刻理解五种常用联结词的涵义，并能准确地应用它们将基本复合命题及复合命题符号化，并且由所含简单命题的真值迅速求出复合命题的真值。2、熟练地写出给定命题公式的真值表3、牢记基本等价式的名称及它们的内容；4、熟练地应用基本等价式及置换规则进行等价演算7/19/20214计算机学院5、熟练掌握求主析取（主合取）范式的方法6、理解并牢记9类基本蕴涵关系式和蕴涵的基本性质7、牢记各条推理规则的内容及名称8、熟练

3、掌握推理的各种方法（直接法、利用CP规则、反证法）7/19/20215计算机学院第二章一、基本概念全总个体域（全论域）、全称量词、存在量词、特性谓词、指导（作用）变元、辖域（作用域）、约束变元、自由变元、约束变元的改名规则、自由变元的代入规则、常量符号、变量符号、函数符号、谓词符号、谓词公式、公式的解释、永真公式(重言式)、永假公式(矛盾式，不可满足公式）、可满足公式、前束范式、母式、前束合取(或析取)范式、Skolem范式、US(全称指定规则)、ES(存在指定规则)、UG(全称推广规则)、EG

4、(存在推广规则)7/19/20216计算机学院二、基本要求能准确地将给定命题符号化深刻理解全称量词、存在量词及量词的辖域、全总个体域的概念能准确理解约束变元(量)和自由变元的概念掌握约束变元的改名规则和自由变元的代入规则7/19/20217计算机学院第三章一、基本概念集合、集合的表示法：枚举法、隐式法（叙述法）、归纳法、递归指定、巴科斯范式BNF、文氏图、特征函数、基数、空集、全集、并集、交集、差集、补集、对称差集、幂集、笛卡尔积二、基本要求熟练掌握集合的基本性质和运算7/19/20218计算机

5、学院第四、五章一、基本概念关系、n元关系、空关系、二元关系、全关系、关系矩阵；关系的交、并、补、差、复合、幂、逆；自反闭包、对称闭包、传递闭包；自反对称闭包、自反传递闭包、对称传递闭包、等价关系、以m为模的同余关系、等价类、生成元、偏序关系、偏序集、偏序集的哈斯图、最大元、最小元、极大元、极小元、上界、下界、最小上界、最大下界、全序关系、良序关系、良序集7/19/20219计算机学院二、基本要求1、熟练掌握关系的性质和运算2、熟练运用Warshall算法计算关系的传递闭包3、熟练掌握偏序关系的哈

6、斯图的画法以及由哈斯图给出相应的偏序关系4、熟练掌握求偏序集最大元、最小元、极大元、极小元、上界、下界、最小上界、最大下界5、熟练掌握利用关系的性质和定义进行证明7/19/202110计算机学院第六章一、基本概念复合函数、单射、满射、双射、置换、单位(恒等)置换、循环、逆函数、函数的递归定义、集合的基数、可数集、不可数集、集合的对等（等势）二、基本要求1、熟练掌握判断函数是否为单射、满射、双射的方法2、熟练掌握判断集合是否等势的方法7/19/202111计算机学院第十章一、基本概念无序对、结点、

7、边、阶、无向图、有向图、邻接点、邻接边、环、孤立结点、零图、平凡图、(n，m)图、简单图、基图、广义图（伪图）、多重图、平行边、赋权图、无权图、结点的度数、出度、入度、正则图、k度正则图、子图、真子图、生成子图、平凡子图、删点子图、删边子图、点诱导子图、边诱导子图、完全图、补图、二部图、完全二部图、图的同构7/19/202112计算机学院道路、道路的长度、零道路、开道路、闭道路、简单道路、回路、基本道路、圈、道路图、圈图、距离、连通图、非连通图、图的支、点割集、基本割集、割点、边割集、基本边割集

8、、割边、连通度、边连通度、可达的、单向连通图、强连通图、弱连通图、强分图、单向分图、弱分图、邻接矩阵、零矩阵、单位矩阵、可达性矩阵、关联矩阵、圈矩阵7/19/202113计算机学院二、基本要求1、熟练掌握图的点割集、基本割集、割点的求法2、熟练掌握邻接矩阵、可达性矩阵的计算方法3、熟练掌握强分图的计算方法7/19/202114计算机学院第11-13章一、基本概念树、树叶、枝点、生成树、树枝、树补边、最小生成树、有向树、根树、有序树、子树、二叉树、完全二叉树、最优二叉树、平面图、面、对偶图、欧拉道