《离散复习提纲.doc》由会员分享，可在线阅读，更多相关《离散复习提纲.doc（4页珍藏版）》请在金锄头文库上搜索。
1、1. 命题及其表示1) 判断哪些是命题（悖论，真值不能确定的，非陈述句）a) 我正在说假话！b) X=2c) 今天天气真好啊！2) 分清简单命题与复合命题a) 蓝色和黄色可以调配成绿色。b) 蓝色和黄色是常用的颜色。3) 区别相容或与排斥或a) 李和平是山西人或陕西人。b) 李冰选学英语或法语。4) 蕴涵式的逻辑关系，准确地找出蕴涵式的前件与后件（只有才，除非否则非，除非才，仅当）a) 除非4是奇数，否则5不是奇数。b) 只有4是偶数，则5才是偶数。c) 5是偶数仅当4是奇数。2. 求复合公式的成真赋值，成假赋值，类型以及真值。（真值表法）3. 等值式与基本等值式4. 等值演算，置换规则5.
2、重言式与矛盾式的判别法A为重言式当且仅当, A为矛盾式当且仅当6. 主析取范式与主合取范式1) 求公式A的主析取范式的方法与步骤a) 等值演算法 1）求公式的析取范式； （1）消去除，以外公式中出现的所有逻辑联结词。（2）将否定联结词消去或内移到各命题变元之前。如，；。（3）利用分配律、结合律将公式转化为合取范式或析取范式。如，；。2）除去中所有永假的析取项；3） 若的某个简单合取式中不含有某个命题变元，也不含，则将展成形式4）将重复出现的命题变元、矛盾式及重复出现的极小项都消去。5）将极小项按顺序排列。b) 真值表法c) 由主合取范式求析取范式主析取范式的用途1. 求公式的成真赋值与成假赋值
3、2. 判断公式的类型3. 判断公式A与B是否等值。4. 解实际问题7. 推理的形式结构（）8. 判断推理是否正确的方法1) 真值表法2) 等值演算法3) 主析取范式法9. 推理定律（9条）10. 在自然推理系统P中构造证明直接证明法附加前提证明法归谬法11. 一阶逻辑命题的符号化a) “D中所有x都有性质F”，符号化为b) “D中有的x有性质F”，符号化为c) “对D中所有x而言，如果有性质F，x就有性质G”，符号化为d) “对D中有的x有性质F且有性质G”，符号化为e) “对于D中所有x,y而言，若x有性质F，y有性质G，则x与y就有关系H”,符号化为f) “对于D中所有x而言，若x有性质F
4、，就存在y有性质G，使得x与y有关系H”，符号化为g) “存在着D中x有性质F，并且对D中所有y而言，如果y有性质G，则x与y就有关系H”，符号化为12. 一阶逻辑公式及解释13. 一阶逻辑等值式与置换规则1) 等值式2) 基本的等值式a) 命题逻辑中基本等值式的代换实例。b) 一阶逻辑中重要的等值式14. 求一阶逻辑前束范式15. 约束变元与自由变元16. 一阶逻辑的推理理论（）17. 一阶逻辑中重要的推理定律18. 自然推理系统F第二部分1. 集合的基本概念2. 集合的基本运算3. 有穷集合元素的计数（文氏图或包含排斥原理）4. 鸽笼原理的应用5. 集合恒等式（基本证明方法）a) 命题演算
5、法b) 利用包含哦传递性c) 反证法命题演算证明法的书写规范 (以下的X和Y代表集合公式)（1）证XY 任取x， xX xY （2）证X=Y 方法一 分别证明XY和YX 方法二 任取x， xX xY注意：在使用方法二的格式时，必须保证每步推理都是充分必要的6. 有序对与笛卡尔积7. 二元关系8. 关系的表示（关系矩阵，关系图）9. 关系的性质（自反，反自反，对称，反对称，传递）表格（1） 若x(xAR), 则称R在A上是自反的（2） 若x(xAR), 则称R在A上是反自反的.（3） 若xy(x,yARR), 则称R为A上对称的关系.（4） 若xy(x,yARRx=y), 则称R为A上的反对称关
6、系.（5） xyz(x,y,zARRR), 则称R是A上的传递关系.。证明：R在A上自反 任取x，有 xA R 前提 推理过程 结论 R在A上对称 任取，有 R RR在A上反对称 任取，有 R R x=yR在A上传递 任取，有 R R R10. 关系运算的定义（定义域，值域，域，逆，复合，限制，像，幂，自反闭包，对称闭包，传递闭包及其构造）11. 关系运算的性质12. 等价关系与划分（等价关系证明，等价类，等价类的性质，商集，集合A的划分，一一对应）13. 偏序关系与偏序集（哈斯图，特殊元素）14. *函数（满射，单射，双射第三部分（）1. 代数系统，运算规律，特殊元的概念及计算，半群，群概念
7、及判别2. 格的定义1） 格的偏序集定义2） 格的代数系统定义2. *格的性质对偶原理格的运算性质偏序与运算的关系保序性质3. *子格与子格的判别 *子格判别：S非空，且S关于格L中的运算封闭。4. 分配格，有界格，有补格的概念分配格的判别方法：1) 根据定义判别：注意在证明L为分配格时，只须证明其中的一个等式即可2) 设L是格，则L是分配个当且仅当L不含有与钻石格或五角格同构的子格。3) 格L是分配格当且仅当第四部分1. 图的定义（平凡图，零图，基图，完全图与竞赛图，子图，补图）2. 图的矩阵表示（关联矩阵，邻接矩阵，可达矩阵），通路与回路的计数3. *无向图的边连通度，点连通度，边割集，点割集4. 二部图定义及判别5. 结点的度数及其相关性质（握手定理）；6. 树、非同构树、生成树、最小生成树7. 有关树的几个等价命题及其证明；8. 最小生成树的Kruscal算法
