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

《离散数学复习提纲(完整版)》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、《离散数学》期末复习大纲（完整版）（含例题和考试说明）一、　命题逻辑[复习知识点]1、命题与联结词（否定￢、析取∨、合取∧、蕴涵→、等价↔），复合命题2、命题公式与赋值（成真、成假），真值表，公式类型（重言、矛盾、可满足），公式的基本等值式3、范式：析取范式、合取范式，极大（小）项，主析取范式、主合取范式4、公式类型的判别方法（真值表法、等值演算法、主析取/合取范式法）5、命题逻辑的推理理论本章重点内容：命题与联结词、公式与解释、（主）析取范式与（主）合取范式、公式类型的判定、命题逻辑的推理[复习要求]1、理解命题的概念；了解命题联

2、结词的概念；理解用联结词产生复合命题的方法。2、理解公式与赋值的概念；掌握求给定公式真值表的方法，用基本等值式化简其它公式，公式在解释下的真值。3、了解析取（合取）范式的概念；理解极大（小）项的概念和主析取（合取）范式的概念；掌握用基本等值式或真值表将公式化为主析取（合取）范式的方法。4、掌握利用真值表、等值演算法和主析取/合取范式的唯一性判别公式类型和公式等价方法。5、掌握命题逻辑的推理理论。[疑难解析]1、公式类型的判定判定公式的类型，包括判定公式是重言的、矛盾的或是可满足的。具体方法有两种，一是真值表法，二是等值演算法。2、范

3、式求范式，包括求析取范式、合取范式、主析取范式和主合取范式。关键有两点：一是准确理解掌握定义；另一是巧妙使用基本等值式中的分配律、同一律和互补律（排中律、矛盾律），结果的前一步适当使用幂等律，使相同的短语（或子句）只保留一个。3、逻辑推理掌握逻辑推理时，要理解并掌握12个（除第10，11）推理规则和3种证明法（直接证明法、附加前提证明法和归谬法）。例1.试求下列公式的主析取范式：（1）；（2）（）2．用真值表判断下列公式是恒真？恒假？可满足？（1）（PÙØP）«Q（2）Ø（P®Q）ÙQ（3）（（P®Q）Ù（Q®R））®（P®R）解：

4、（1）真值表PQØPPÙØP（PÙØP）«Q00101011001000111000因此公式（1）为可满足。（2）真值表PQP®QØ（P®Q）Ø（P®Q）ÙQ00100011001001011100因此公式（2）为恒假。（3）真值表PQRP®QQ®RP®R（（P®Q）Ù（Q®R））®（P®R）00011110011111010101101111111000101101011111010011111111因此公式（3）为恒真。3．┐QÙ（P→Q）蕴涵┐P（an:法1：真值表法2：若┐QÙ（P→Q）为真，则┐Q，P→Q为真，所以Q为假，

5、P为假，所以┐P为真。法3：若┐P为假，则P为真，再分二种情况：①若Q为真，则┐QÙ（P→Q）为假②若Q为假，则P→Q为假，则┐QÙ（P→Q）为假根据①②，所以┐QÙ（P→Q）蕴涵┐P。）4．利用基本等价式证明下列命题公式为恒真公式。（（P®Q）Ù（Q®R））®（P®R）（（PÚQ）ÙØ（ØPÙ（ØQÚØR）））Ú（ØPÙØQ）Ú（ØPÙØR）（1、证明：（（P®Q）Ù（Q®R））®（P®R）=（（ØPÚQ）Ù（ØQÚR））®（ØPÚR）=Ø（（ØPÚQ）Ù（ØQÚR））Ú（ØPÚR）=（PÙØQ）Ú（QÙØR）ÚØPÚR=（（PÙ

6、ØQ）ÚØP）Ú（（QÙØR）ÚR）=（1Ù（ØQÚØP））Ú（（QÚR）Ù1）=ØQÚØPÚQÚR=（ØQÚQ）ÚØPÚR=1ÚØPÚR=1（（PÚQ）ÙØ（ØPÙ（ØQÚØR）））Ú（ØPÙØQ）Ú（ØPÙØR）=（（PÚQ）Ù（PÚ（QÙR）））Ú（ØPÙ（ØQÚØR））=（PÚ（QÙQÙR））Ú（ØPÙ（ØQÚØR））=（PÚ（QÙR））ÚØ（PÚ（QÙR））=1）5．用形式演绎法证明：{}蕴涵证明：（1）规则P（2）规则Q（1）（3）规则P（4）规则Q（3）（5）规则Q（2）（4）（6）R®S规则P（7）P®S规则Q（5）

7、（6）)6．用形式演绎法证明：（蕴涵A证明：(改()（1）A规则D（2）A∨B规则Q（1）（3）规则P（4）规则Q（2）（3）（5）D规则Q（4）（6）规则Q（5）（7）规则P（8）E规则Q（6）（7）（9）规则Q（1）（8））7．┐（P∧┐Q），┐Q∨R，┐R蕴涵┐P（1）┐Q∨R（2）┐R（3）┐Q（4）┐（P∧┐Q）（5）┐P∨Q（6）┐P）8．某案涉及甲、乙、丙、丁四个，根据已有线索，已知：（1）若甲、乙均未作案，则丙、丁也均未作案；（2）若丙、丁均未作案，则甲、乙也均未作案；（3）若甲与乙同时作案，则丙与丁有一人且只有一人

8、作案；（4）若乙与丙同时作案，则甲与丁同时作案或同未作案。办案人员由此得出结论：甲是作案者。这个结论是否正确？为什么？解：对问题中的四个简单命题用P1，P2，P3，P4分别表示甲，乙，丙，丁作案，则办案人员的推理如下：前提：1)ØP1