1、离散数学复习类型离散数学复习类型一、填空题一、填空题二、判断题二、判断题三、综合题三、综合题 第一部分第一部分基本知识点基本知识点：联结词，命题公式类型，极小项，极大项，成真赋值联结词，命题公式类型，极小项，极大项，成真赋值（成假赋值），基本等值式，推理定律，符号化（命题、谓词）（成假赋值），基本等值式，推理定律，符号化（命题、谓词）1、求命题公式两种主范式（重点、求命题公式两种主范式（重点3元）元）2、结构命题公式序列证实（正确推理证实方法）、结构命题公式序列证实（正确推理证实方法）另外，还需掌握真值表法、等值演算法、主范式法另外，还需掌握真值表法、等值演算法、主范式法 第二部分第二部分基本
2、知识点基本知识点：集合（含关系）运算，幂集，二元关系及性质，集合（含关系）运算，幂集，二元关系及性质，等价关系，划分，偏序关系，哈斯图，函数及性质等价关系，划分，偏序关系，哈斯图，函数及性质1、结构给定集合上等价关系、偏序关系、结构给定集合上等价关系、偏序关系2、判定一关系是否是函数？若是，问函数含有哪些性质？、判定一关系是否是函数？若是，问函数含有哪些性质？1/5 第四部分第四部分基本知识点基本知识点：简单图，子图，简单图，子图，Kn,n阶有向完全图，可图化，同构，路径，阶有向完全图，可图化，同构，路径，圈，连通图（强连通图，弱连通图），割点，桥，二部图，圈，连通图（强连通图，弱连通图），割
3、点，桥，二部图，邻接矩阵，欧拉图、哈密顿图，无向树，最小生成树，根数，最优二叉树邻接矩阵，欧拉图、哈密顿图，无向树，最小生成树，根数，最优二叉树1、作出、作出K4生成子图（非同构）生成子图（非同构）2、作出三阶有向完全图生成子图（非同构）、作出三阶有向完全图生成子图（非同构）3、作出满足一定条件欧拉图、哈密顿图、作出满足一定条件欧拉图、哈密顿图4、作出满足一定条件无向树、最小生成树、最优、作出满足一定条件无向树、最小生成树、最优2叉树叉树5、利用邻接矩阵求一有向图中两顶点之间通路、回路数、利用邻接矩阵求一有向图中两顶点之间通路、回路数二、判断题二、判断题、命题都是陈说句、命题都是陈说句 、命题
4、公式包含矛盾式和可满足式两类、命题公式包含矛盾式和可满足式两类、命题是元谓词，、命题是元谓词，元谓词是命题元谓词是命题、命题公式等值就是同真值、命题公式等值就是同真值、任一命题公式都存在唯一两种范式、任一命题公式都存在唯一两种范式、任一谓词公式都存在唯一前束范式、任一谓词公式都存在唯一前束范式、含、含n个命题变元全部命题公式主析取范式最多有有限种，个命题变元全部命题公式主析取范式最多有有限种，而且为而且为 2/5、命题之间等值关系是等价关系、命题之间等值关系是等价关系(偏序关系偏序关系)10、任意一个命题公式赋值不是成真赋值就是成假赋值、任意一个命题公式赋值不是成真赋值就是成假赋值 11、真值
5、表是表示命题公式一个方式、真值表是表示命题公式一个方式 12、任意一个命题公式层数都为正整数、任意一个命题公式层数都为正整数 13、同一个命题公式可能既是析取范式又是合取范式、同一个命题公式可能既是析取范式又是合取范式 14、同一个命题公式可能既是主析取范式又是主合取范式、同一个命题公式可能既是主析取范式又是主合取范式（A=p）15、一个命题公式有唯一极小项而且有唯一极大项、一个命题公式有唯一极小项而且有唯一极大项 16、一个正确推理其结论未必是真命题、一个正确推理其结论未必是真命题 17、推理定律对应公式都是永真式、推理定律对应公式都是永真式 18、封闭公式在一确定解释下，其真值是唯一、封闭
6、公式在一确定解释下，其真值是唯一 19、同一个命题符号化后形式可能不唯一、同一个命题符号化后形式可能不唯一、集合是二元关系，二元关系是集合、集合是二元关系，二元关系是集合 、集合能够表示函数、集合能够表示函数 、二元关系是函数，函数是二元关系、二元关系是函数，函数是二元关系、非空集上一个关系可能既是自反关系又是反自反关系、非空集上一个关系可能既是自反关系又是反自反关系 3/5、一个关系可能既是对称关系又是反对称关系、一个关系可能既是对称关系又是反对称关系、一个关系可能既是等价关系又是偏序关系、一个关系可能既是等价关系又是偏序关系 1、图分为简单图和多重图、图分为简单图和多重图 2、欧拉、欧拉(
7、哈密顿哈密顿)图都是连通图图都是连通图3、欧拉、欧拉 图都是哈密顿图图都是哈密顿图 4、哈密顿图都是欧拉、哈密顿图都是欧拉 图图 5、半欧拉、半欧拉 图都是半哈密顿图图都是半哈密顿图 6、半哈密顿图都是半欧拉、半哈密顿图都是半欧拉 图图 7、任一个有限图都能够用矩阵、图形和集合表示、任一个有限图都能够用矩阵、图形和集合表示 8、图分为欧拉、图分为欧拉 图和半欧拉图和半欧拉 图图 9、图分为哈密顿图和半哈密顿图、图分为哈密顿图和半哈密顿图 10、树都是连通图、树都是连通图 11、任一棵树都是自己生成树、任一棵树都是自己生成树 12、任一连通图都有生成树、任一连通图都有生成树 4/513、含、含n
8、个顶点，个顶点，n-1条边图一定是生成树条边图一定是生成树 14、一棵树余树不一定是树、一棵树余树不一定是树 15、可图化非负整数列在同构意义下，非负整数列、可图化非负整数列在同构意义下，非负整数列与图不一定是一一对应与图不一定是一一对应 16、边带权无向（连通）图一定有最小生成树、边带权无向（连通）图一定有最小生成树 17、根树顶点分为分支点和树叶、根树顶点分为分支点和树叶 18、最优、最优2叉树一定是叉树一定是2叉正则树叉正则树 19、含、含t片树叶最优片树叶最优2叉树一定含有叉树一定含有t-1个分支点个分支点 20、含、含t片树叶而且树叶带权片树叶而且树叶带权2叉树一定存在最优叉树一定存在最优2叉树叉树 21、一欧拉图不一定是二分之一欧拉图。、一欧拉图不一定是二分之一欧拉图。（）22、在集合表示式中，关系运算优先于集合运算。、在集合表示式中，关系运算优先于集合运算。（）23、在图论中，平凡图是一棵树。、在图论中，平凡图是一棵树。（）24、连通图中顶点之间可达关系是等价关系。、连通图中顶点之间可达关系是等价关系。（）25、非空集上偏序关系与集合划分是一一对应、非空集上偏序关系与集合划分是一一对应.（）5/5
