离散数学复习１.pptVIP

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