以下为《离散数学复习大纲》的无排版文字预览,完整格式请下载
下载前请仔细阅读文字预览以及下方图片预览。图片预览是什么样的,下载的文档就是什么样的。
2018-2019学年度离散数学考试大纲
第一部分 数理逻辑
第1章 命题逻辑
考核内容:
1、命题符号化;
2、命题公式的真值表:
(1)利用真值表给出公式的成真与成假赋值
(2)利用真值表给出命题公式的主析取范式;
(3)利用真值有判断公式的类型;
(4)利用真值表证明两个公式等值。
3、等值演算:
(1)用等值演算证明两个命题公式等值
(2)判断公式的类型
(3)求解公式的成真与成假赋值;
(4)求解公式的主析取范
4、命题逻辑的推理理论:利用命题逻辑推理理论证明推理的有效性。
主要知识点:
一、命题符号及联结词
1、命题联结词
2、命题符号化
例1.6
二、命题公式及分类
1、命题公式的定义
2、真值表
3、命题公式类型及判断
4、命题公式的成真赋值与成假赋值
例1.7
三、等值演算
1、基本等值式
2、等值演算
3、用等值演算判断公式类型
4、用等值演算判断公式是否等值
例1.9、例1.10
四、析取范式与合取范式
1、主析取范式
2、主合取范式
3、用主析取范式判断公式类型
4、用主析取范式判断公式是否等值
例1.13、例1.14、例1.15
五、推理理论
1、推理的形式结构
2、推理是否正确的判断方法(等值演算、主析取范式)
3、推理定律(P23页)
4、自然推理系统
5、推理规则(P23页)
6、推理证明(例1.21 、例1.22、例1.23、例1.24
六、教材作业:P33-35 1.7(2,4,6)、1.8(2)、1.19(5)、1.20、1.21
第2章 一阶逻辑
考核内容:
1、一阶逻辑命题符号化:个体词、谓词、量词
2、一阶逻辑公式及解释:
(1)指导变元、辖域、约束出现、自由出现;
(2)求解一个命题公式在特定解释下的真值;
3、一阶逻辑等值式
4、一阶逻辑前束范式:
5、一阶逻辑的推理理论:利用一阶逻辑推理理论证明推理的有效性。
主要知识点:
一、一阶逻辑命题
1、一阶逻辑命题符号化的三个基本要素:个体词、谓词、量词
2、一阶逻辑命题的符号化
例2.3、例2.4
二、一阶逻辑命题公式
1、一阶逻辑合式公式的定义
2、一阶逻辑公式的解释
(1)指导变元、辖域、约束出现、自由出现
(2)一阶逻辑公式的解释
3、一阶逻辑公式的类型
例2.6、例2.7、例2.8
三、一阶逻辑等值式与前束范式(P46页- P49页)
1、一阶逻辑等值式
2、一阶逻辑等值演算规则
3、一阶逻辑前束范式
四、一阶逻辑推理理论
1、一阶逻辑推理定律(课件)
2、一阶逻辑自然推理(课件)
(例2. 11)课件上例2.13、2.14
五、教材作业
1、P52-54页2.3题、2.11题、2.14题
第二部分 集合论
第3章 集合代数
考核内容:
属于关系与包含的关系;
2、求解n元集的幂集合与幂集合的基数
3、集合的运算
4、有穷集合的计数
主要知识点:
一、集合
1、集合及集合的表示方法:列举法与描述法
2、集合的基数
3、集合的子集及幂集
二、集合间的关系
1、集合间的包含关系
2、集合间的相等关系
3、集合间的真包含关系
三、集合的运算
1、集合的并、交
2、集合的绝对补与相对补运算
3、集合的对称 内容过长,仅展示头部和尾部部分文字预览,全文请查看图片预览。 四、格
1、偏序集的定义
2、用哈斯图表示偏序集
3、偏序集中几特殊元素
4、格的定义、性质、判定及满足的算律
5、偏序集与格的关系
6、利用哈斯图判断一个偏序集是否为格
五、几种特殊的格
1、分配格及判断
2、有补格及判断
3、有补分配格判断
4、布尔格及判定(利用五角格与钻石格判断)
六、布尔代数的性质
七、教材作业
1、P223页-P229页9.16题、9.20题、9.23题、9.25题
第四部分 图论总结
第5章 图论(P118-161)
考核内容:
图的阶、顶点数及边某某
2、结点的度
3、握手定理及推论的应用:已知边某某与部分结点的度,计算共有几个顶点(P120例5.1)
4、简单图与完全图
5、完全图
6、图的连通性
(1)无向图的连通性:点割集与边某某,边连通度与点连通度
(2)有向图的连通性:强连通、单向连通、弱连通
7、有向图的邻接矩阵(P127-P128图5-13通路, 回路的计算;可达矩阵与有向图的连通性的判断)
主要知识点:
一、图及其基本概念
图的定义与图的表示(边某某、结点集)
图的阶、顶点数及边某某
顶点相邻、边相邻及边与顶点的关联
结点的度
简单图
完全图
图的同构
通路及回路
图的连通性
(1)无向图的连通性:点割集与边某某,边连通度与点连通度
(2)有向图的连通性:强连通、单向连通、弱连通
10、图的矩阵表示
(1)有向图的邻接矩阵(图5-13通路与回路的计算)
(2)无向图的关联矩阵
二、图的基本性质
握手定理及推论
握手定理及推论的应用
三、图的着色
例5.1、例5.6、P127-128通路与回路计算。
四、教材作业
P137页-P139页 5.1题、5.5题、5.18题
几种特殊的图
考核内容:
1、二部图的定义与二部图的最大匹配、完备匹配、完美匹配
2、欧拉图定义、判定及寻找欧拉通路、欧拉回路
3、哈密顿图定义、判定与求解哈密顿通路、哈密顿回路;哈密图的应用(P154作业6.15)
主要知识点:
一、二部图
1、定义、判定、互补结点子集
2、二部图的最大匹配、完备匹配、完美匹配
二、欧拉图
1、欧拉图定义、判定(充要条件);
2、寻找欧拉通路、欧拉回路。
三、哈密顿图
1、哈密顿图定义、判定(必要条件、充分条件);
2、求解哈密顿通路、哈密顿回路;哈密图的应用。
课件上哈密图应用用举例
四、完全图
定义、判定及结点与边的关系
五、教材作业
P154页-P156页6.15题
第7章 树
考核内容:
1、无向树的定义与性质
2、欧拉图定义、判定及寻找欧拉通路、欧拉回路
3、哈密顿图定义、判定与求解哈密顿通路、哈密顿回路;哈密图的应用(P154作业6.15)
主要知识点:
一、无向树
1、定义、性质、判定及结点与边的关系
2、生成树与最小生成树(例7.2)
四、教材作业
1、P171页- P173页 7.1题、7.2题
复习要求:
1、认真把教材上本学期所讲内容看一遍。另外,把大纲中指定的例题及书后习题认真做一做。
2、第二遍按照复习大纲把课程内容进行总结复习,并做一些练习题目检验一下主要内容的掌握情况。
[文章尾部最后300字内容到此结束,中间部分内容请查看底下的图片预览]
以上为《离散数学复习大纲》的无排版文字预览,完整格式请下载
下载前请仔细阅读上面文字预览以及下方图片预览。图片预览是什么样的,下载的文档就是什么样的。