离散数学复习１ppt课件

1、离散数学复习类型离散数学复习类型一、填空题一、填空题二、判别题二、判别题三、综合题三、综合题 第一部分根本知识点：结合词，命题公式的类型，极小项，极大项，成真赋值成假赋值，根本等值式，推理定律，符号化命题、谓词1、求命题公式的两种主范式重点3元2、构造命题公式序列证明正确推理的证明方法 另外，还需掌握真值表法、等值演算法、主范式法 第二部分根本知识点：集合含关系的运算，幂集，二元关系及性质，等价关系，划分，偏序关系，哈斯图，函数及性质1、构造给定集合上的等价关系、偏序关系2、断定一关系能否是函数？假设是，问函数具有哪些性质？ 第四部分根本知识点：简单图，子图，Kn, n阶有向完全图，可图化，同

2、构，途径，圈，连通图强连通图，弱连通图，割点，桥，二部图，邻接矩阵，欧拉图、哈密顿图，无向树，最小生成树，根数，最优二叉树1、作出K4的生成子图非同构2、作出三阶有向完全图的生成子图非同构3、作出满足一定条件的欧拉图、哈密顿图4、作出满足一定条件的无向树、最小生成树、最优2叉树5、利用邻接矩阵求一有向图中两顶点之间的通路、回路数二、判别题二、判别题、命题都是陈说句、命题都是陈说句 、命题公式包括矛盾式和可满足式两类、命题公式包括矛盾式和可满足式两类、命题是元谓词，、命题是元谓词， 元谓词是命题元谓词是命题、命题公式等值就是同真值、命题公式等值就是同真值、任一命题公式都存在独一的两种范式、任一命

3、题公式都存在独一的两种范式、任一谓词公式都存在独一的前束范式、任一谓词公式都存在独一的前束范式、含、含n个命题变元的一切命题公式的主析取范式最多有有限种，个命题变元的一切命题公式的主析取范式最多有有限种，并且为并且为 n22、命题之间的等值关系是等价关系、命题之间的等值关系是等价关系(偏序关系偏序关系) )(9必要条件、充要条件的充分条件是的逻辑关系为、pqqp 10、恣意一个命题公式的赋值不是成真赋值就是成假赋值、恣意一个命题公式的赋值不是成真赋值就是成假赋值11、真值表是表示命题公式的一种方式、真值表是表示命题公式的一种方式 12、恣意一个命题公式的层数都为正整数、恣意一个命题公式的层数都

4、为正整数 13、同一个命题公式能够既是析取范式又是合取范式、同一个命题公式能够既是析取范式又是合取范式14、同一个命题公式能够既是主析取范式又是主合取范式、同一个命题公式能够既是主析取范式又是主合取范式A=p15、一个命题公式有独一的极小项并且有独一的极大项、一个命题公式有独一的极小项并且有独一的极大项16、一个正确的推理其结论未必是真命题、一个正确的推理其结论未必是真命题17、推理定律对应的公式都是永真式、推理定律对应的公式都是永真式18、封锁的公式在一确定解释下，其真值是独一的、封锁的公式在一确定解释下，其真值是独一的19 、同一个命题符号化后的方式能够不独一、同一个命题符号化后的方式能够

5、不独一、集合是二元关系，二元关系是集合、集合是二元关系，二元关系是集合 、集合可以表示函数、集合可以表示函数 、二元关系是函数，函数是二元关系、二元关系是函数，函数是二元关系、非空集上一个关系能够既是自反关系又是反自反关系、非空集上一个关系能够既是自反关系又是反自反关系、一个关系能够既是对称关系又是反对称关系、一个关系能够既是对称关系又是反对称关系、一个关系能够既是等价关系又是偏序关系、一个关系能够既是等价关系又是偏序关系1、图分为简单图和多重图、图分为简单图和多重图2、欧拉、欧拉 (哈密顿哈密顿)图都是连通图图都是连通图3、欧拉、欧拉 图都是哈密顿图图都是哈密顿图4、哈密顿图都是欧拉、哈密顿

6、图都是欧拉 图图5、半欧拉、半欧拉 图都是半哈密顿图图都是半哈密顿图6、半哈密顿图都是半欧拉、半哈密顿图都是半欧拉 图图7、任一个有限图都可以用矩阵、图形和集合表示、任一个有限图都可以用矩阵、图形和集合表示8、图分为欧拉、图分为欧拉 图和半欧拉图和半欧拉 图图9 、图分为哈密顿图和半哈密顿图、图分为哈密顿图和半哈密顿图10、树都是连通图、树都是连通图11、任一棵树都是本人生成树、任一棵树都是本人生成树12、任一连通图都有生成树、任一连通图都有生成树13、含、含n个顶点，个顶点，n-1条边的图一定是生成树条边的图一定是生成树14、一棵树的余树不一定是树、一棵树的余树不一定是树15、可图化的非负整

7、数列在同构的意义下，非负整数列、可图化的非负整数列在同构的意义下，非负整数列与图不一定是一一对应的与图不一定是一一对应的16、边带权的无向连通图一定有最小生成树、边带权的无向连通图一定有最小生成树 17、根树的顶点分为分支点和树叶、根树的顶点分为分支点和树叶18、最优、最优2叉树一定是叉树一定是2叉正那么树叉正那么树19、含、含t片树叶的最优片树叶的最优2叉树一定含有叉树一定含有t-1个分支点个分支点20、含、含t片树叶并且树叶带权的片树叶并且树叶带权的2叉树一定存在最优叉树一定存在最优2叉树叉树21、一欧拉图不一定是一半欧拉图。、一欧拉图不一定是一半欧拉图。 22、在集合表达式中，关系运算优先于集合运算。、在集合表达式中，关系运算优先于集合运算。 23、在图论中