离散数学复习提纲(完整版)..docVIP

《离散数学》期末复习大纲（完整版）（含例题和考试说明） 一、　命题逻辑 [复习知识点] 1、命题与联结词（否定￢、析取∨、合取∧、蕴涵→、等价?），复合命题 2、命题公式与赋值（成真、成假），真值表，公式类型（重言、矛盾、可满足），公式的基本等值式 3、范式：析取范式、合取范式，极大（小）项，主析取范式、主合取范式 4、公式类型的判别方法（真值表法、等值演算法、主析取/合取范式法） 5、命题逻辑的推理理论 本章重点内容：命题与联结词、公式与解释、（主）析取范式与（主）合取范式、公式类型的判定、命题逻辑的推理 [复习要求] 1、理解命题的概念；了解命题联结词的概念；理解用联结词产生复合命题的方法。 2、理解公式与赋值的概念；掌握求给定公式真值表的方法，用基本等值式化简其它公式，公式在解释下的真值。 3、了解析取（合取）范式的概念；理解极大（小）项的概念和主析取（合取）范式的概念；掌握用基本等值式或真值表将公式化为主析取（合取）范式的方法。 4、掌握利用真值表、等值演算法和主析取/合取范式的唯一性判别公式类型和公式等价方法。 5、掌握命题逻辑的推理理论。 [疑难解析] 1、公式类型的判定 判定公式的类型，包括判定公式是重言的、矛盾的或是可满足的。具体方法有两种，一是真值表法，二是等值演算法。 2、范式 求范式，包括求析取范式、合取范式、主析取范式和主合取范式。关键有两点：一是准确理解掌握定义；另一是巧妙使用基本等值式中的分配律、同一律和互补律（排中律、矛盾律），结果的前一步适当使用幂等律，使相同的短语（或子句）只保留一个。 3、逻辑推理 掌握逻辑推理时，要理解并掌握12个（除第10，11）推理规则和3种证明法（直接证明法、附加前提证明法和归谬法）。 例1.试求下列公式的主析取范式： （1）；（2） （ ） 2．用真值表判断下列公式是恒真？恒假？可满足？ （1）（P??P）?Q （2）?（P?Q）?Q （3）（（P?Q）?（Q?R））?（P?R） 解： 真值表 P Q ?P P??P （P??P）?Q 0 0 1 0 1 0 1 1 0 0 1 0 0 0 1 1 1 0 0 0 因此公式（1）为可满足。 真值表 P Q P?Q ?（P?Q） ?（P?Q）?Q 0 0 1 0 0 0 1 1 0 0 1 0 0 1 0 1 1 1 0 0 因此公式（2）为恒假。 真值表 P Q R P?Q Q?R P?R （（P?Q）?（Q?R））?（P?R） 0 0 0 1 1 1 1 0 0 1 1 1 1 1 0 1 0 1 0 1 1 0 1 1 1 1 1 1 1 0 0 0 1 0 1 1 0 1 0 1 1 1 1 1 0 1 0 0 1 1 1 1 1 1 1 1 因此公式（3）为恒真。 3．┐Q?（P→Q）蕴涵 ┐P （an: 法1：真值表 法2：若┐Q?（P→Q）为真，则 ┐Q，P→Q为真， 所以Q为假，P为假，所以┐P为真。 法3：若┐P为假，则P为真，再分二种情况： ①若Q为真，则┐Qù（P→Q）为假 ②若Q为假，则P→Q为假，则┐Q?（P→Q）为假 根据① ②，所以 ┐Q?（P→Q）蕴涵 ┐P。） 4．利用基本等价式证明下