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

《离散数学》期末复习大纲（完整版）（含例题和考试说明）
一、命题逻辑
[复习知识点]
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）
解：
真值表
PQPPP（PP）Q00101011001000111000因此公式（1）为可满足。
真值表
PQPQ（PQ）（PQ）Q00100011001001011100因此公式（2）为恒假。
真值表
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为假，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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）（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．某案涉及甲、乙、丙、丁四个，根据已有线索，已知：
若甲、乙均未作案，则丙、丁也均未作案；
若丙、丁均未作案，则甲、乙也均未作案；
若甲与乙同时作案，则丙与丁有一人且只有一人作案；
若乙与丙同时作案，则