离散数学期末复习提要.pdfVIP

《离散数学》期末复习提要

一、命题逻辑

[复习知识点]

1、命题与联结词（否定、析取、合取、条件、等值），复合命题

2、命题与赋值（成真、成假），真值表，类型（重言、、可满足），的基

本等值式

3、命题之间的关系：蕴含、等价

4、析取范式、合取范式，极小（大）项，主析取范式、主合取范式

5、类型的判别方法（真值表法、等值演算法、主析取/合取范式法）

6、命题逻辑的推理理论：真值表法、直接证明法、间接证明法

本章重点内容：命题与联结词、与解释、（主）析取范式与（主）合取范式、类

型的判定、命题逻辑的推理

[复]

1、理解命题的概念；了解命题联结词的概念；理解用联结词产生复合命题的方法。

2、理解与赋值的概念；掌握求给定真值表的方法，用基本等值式化简其它，

在解释下的真值。

3、了解析取（合取）范式的概念；理解极大（小）项的概念和主析取（合取）范式的概念；

掌握用基本等值式或真值表将化为主析取（合取）范式的方法。

4、掌握利用真值表、等值演算法和主析取/合取范式的唯一性判别类型和等价方法。

5、掌握命题逻辑的推理理论。P规则、T规则、附加前提证明法、CP规则

[疑难解析]

1、类型的判定

判定的类型，包括判定是重言的、的或是可满足的。具体方法有两种，一

是真值表法，二是等值演算法。

2、范式

求范式，包括求析取范式、合取范式、主析取范式和主合取范式。关键有两点：一是准

确理解掌握定义；另一是巧妙使用基本等值式中的分配律、同一律和互补律（排中律、

律），结果的前一步适当使用幂等律，使相同的短语（或子句）只保留一个。

3、逻辑推理

掌握逻辑推理时，要理解并掌握12个（除第10，11）推理规则和3种证明法（直接证

明法、附加前提证明法和归谬法）。

二、谓词逻辑（一阶逻辑）

[复习知识点]

1、谓词、量词、词（一阶逻辑3要素）、域、变元（约束出现与自由出现）

2、谓词与解释，谓词的类型（永真、永假、可满足）

3、谓词的等值式（代换实例、消去量词、量词否定和量词辖域收与扩）和置换规则（置

换规则、换名规则和代替规则）

4、谓词推理理论

本章重点内容：谓词与量词、与解释、谓词推理理论（US/UG、ES/EG规则）

[复]

1、理解谓词、量词、词、域、变元的概念；理解用谓词、量词、逻辑联结词描述

一个简单命题；了解命题符号化。

2、理解与解释的概念；掌握在有限域下消去量词，求在给定解释下真值

的方法；了解谓词的类型。

[疑难解析]

1、谓词与量词

理解谓词与量词引入的意义，概念的含义及在谓词与量词作用下变量的自由性、约束性

与改名规则（即换名规则和代替规则）。

2、与解释

能将一阶逻辑表达式中的量词消除，写成与之等价的，然后将解释中的数值代

入，求出真值。

三、集合

[复习知识点]

1、集合、元素、集合的表示方法、子集、空集、全集、集合的包含、相等、幂集

2、集合的交、并、差、补以及对称差等运算及