离散数学复习课(1)

1、本门课程共有本门课程共有12个知识点：个知识点：1 1、命题逻辑的基本概念、命题逻辑的基本概念2 2、命题逻辑的等值演算、命题逻辑的等值演算3 3、命题逻辑的推理理论、命题逻辑的推理理论4 4、一阶逻辑的基本概念、一阶逻辑的基本概念5 5、一阶逻辑的等值演算与推理、一阶逻辑的等值演算与推理6 6、集合、集合7 7、二元关系、二元关系8 8、函数、函数9 9、图的基本概念及运算、图的基本概念及运算1010、欧拉图与哈密顿图、欧拉图与哈密顿图1111、偶图与平面图、偶图与平面图1212、树、树一、内容提要一、内容提要 1、命题与连接词、命题与连接词 命题与真值：命题与真值：命题，命题的真值，真命题

2、，假命命题，命题的真值，真命题，假命题，简单命题（或原子命题），复合命题。题，简单命题（或原子命题），复合命题。 命题与真值的符号化：命题与真值的符号化：用逻辑变量用逻辑变量P、Q、R表示表示命题；用命题；用 1 代表真，代表真，0 代表假。代表假。知识点知识点1 命题逻辑的基本概念命题逻辑的基本概念 常用联结词及其符号化常用联结词及其符号化：否定词：否定词，合取词，合取词，析，析取词取词，蕴含词，蕴含词，等值词，等值词。 基本复合命题基本复合命题： 否定式：否定式：P 合取式：合取式：PQ 析取式：析取式：PQ 蕴含式：蕴含式：PQ 等价式：等价式：PQ 复合命题复合命题：基本复合命题，以及

3、多次使用联结词：基本复合命题，以及多次使用联结词复合而成的命题。如：异或复合而成的命题。如：异或(PQ)(P Q) 2、命题公式及其赋值、命题公式及其赋值 命题常项与命题变项命题常项与命题变项 命题公式与赋值命题公式与赋值：合式公式（命题公式或公式），：合式公式（命题公式或公式），公式的层次，公式的赋值，真值表。公式的层次，公式的赋值，真值表。 命题公式的类型命题公式的类型：永真式（重言式），永假式：永真式（重言式），永假式（矛盾式），可满足式。（矛盾式），可满足式。 判断公式类型的方法判断公式类型的方法：真值表法。：真值表法。二、基本要求二、基本要求1、分清简单命题与复合命题。、分清简单命题

4、与复合命题。2、理解、理解 5 种常用联结词的含义，并能准确地应用它种常用联结词的含义，并能准确地应用它们将命题符号化，能由简单命题的真值迅速求出复们将命题符号化，能由简单命题的真值迅速求出复合命题的真值。合命题的真值。3、深刻理解命题公式的赋值、永真式、永假式、可、深刻理解命题公式的赋值、永真式、永假式、可满足式等概念。满足式等概念。4、熟练地写出给定命题公式的真值表，并能利用真、熟练地写出给定命题公式的真值表，并能利用真值表判断出公式的类型，或求公式成真（假）赋值。值表判断出公式的类型，或求公式成真（假）赋值。三、主要题型三、主要题型1、命题符号化。、命题符号化。2、求复合命题的真值与命题

5、公式的赋值。、求复合命题的真值与命题公式的赋值。3、判断公式的类型。、判断公式的类型。4、复合命题符号化。、复合命题符号化。一、内容提要一、内容提要 1、等值式与基本等值式、等值式与基本等值式 等值式等值式：若：若PQ为永真式，则称为永真式，则称P与与Q是等值的，是等值的，记为记为 。 基本的等值式基本的等值式：P11表表1.4，共，共24 个。个。 等值演算等值演算：由已知等值式推演出新的等值式的过：由已知等值式推演出新的等值式的过程。程。知识点知识点2 命题逻辑的等值演算命题逻辑的等值演算QP 置换规则置换规则： 永真式与矛盾式的判别方法永真式与矛盾式的判别方法：。则则，若若)()(BAB

6、A。；01AA 2、析取范式与合取范式、析取范式与合取范式 概念概念：文字，简单析取式，简单合取式，最小项，：文字，简单析取式，简单合取式，最小项，最大项，析取范式，合取范式，主析取范式，主合最大项，析取范式，合取范式，主析取范式，主合取范式。取范式。 主要定理主要定理：在命题逻辑中，任何公式都存在着唯：在命题逻辑中，任何公式都存在着唯一的主析取范式和主合取范式。一的主析取范式和主合取范式。 主析取范式的求解方法与步骤主析取范式的求解方法与步骤：等值演算法，真：等值演算法，真值表法，由主合取范式求主析取范式。值表法，由主合取范式求主析取范式。 主合取范式的求解方法与步骤主合取范式的求解方法与步

7、骤：等值演算法，真：等值演算法，真值表法，由主析取范式求主合取范式。值表法，由主析取范式求主合取范式。 主范式的用途主范式的用途：（：（1）求公式的成真（假）的赋值；）求公式的成真（假）的赋值；（2）判断公式的类型；（）判断公式的类型；（3）判断两个公式是否等）判断两个公式是否等值；（值；（4）解决实际问题。）解决实际问题。二、基本要求二、基本要求1、理解等值式的定义，知道公式之间的等值关、理解等值式的定义，知道公式之间的等值关系具有自反性、对称性、传递性。系具有自反性、对称性、传递性。2、牢记基本等值式的名称及它们的内容。、牢记基本等值式的名称及它们的内容。3、熟练地应用基本等值式及置换规则

8、进行等值、熟练地应用基本等值式及置换规则进行等值演算。演算。4、了解文字、简单析取式、简单合取式、析取、了解文字、简单析取式、简单合取式、析取范式、合取范式等概念。范式、合取范式等概念。5、深刻理解最小项、最大项的定义，名称、下脚、深刻理解最小项、最大项的定义，名称、下脚标与成真赋值的关系，主析取范式与主合取范式。标与成真赋值的关系，主析取范式与主合取范式。6、熟练掌握求主析（合）取范式的方法。、熟练掌握求主析（合）取范式的方法。7、会用主范式求公式的成真（假）赋值、判断公、会用主范式求公式的成真（假）赋值、判断公式类型、判断两个公式是否等值。式类型、判断两个公式是否等值。三、主要题型三、主要

9、题型1、用等值演算法证明永真式和永假式。、用等值演算法证明永真式和永假式。2、用等值演算法证明等值式。、用等值演算法证明等值式。3、通过求主范式判断公式的类型。、通过求主范式判断公式的类型。4、用主范式判断两个公式是否等值。、用主范式判断两个公式是否等值。5、用等值演算方法求解实际问题。、用等值演算方法求解实际问题。*一、内容提要一、内容提要 1、推理的形式结构、推理的形式结构 推理，证明与推理规则推理，证明与推理规则： 判断推理是否正确的方法判断推理是否正确的方法：真值表法，等值演算：真值表法，等值演算法，主析取范式法。法，主析取范式法。 常用的推理定律（规则）常用的推理定律（规则）：P25

10、，8个。个。知识点知识点3 命题逻辑的推理理论命题逻辑的推理理论BAAAk21 2、自然推理系统、自然推理系统P（1）前提引入规则；）前提引入规则；（2）结论引入规则；）结论引入规则；（3）置换规则；）置换规则；（4）推理定律。）推理定律。 3、在自然推理系统、在自然推理系统P中构造证明中构造证明 直接证明法直接证明法：由前题出发，应用推理规则，推出：由前题出发，应用推理规则，推出结论。结论。 附加前提法附加前提法 反证法（归谬法）反证法（归谬法） 二、基本要求二、基本要求1、理解并记住推理形式结构的以下两种形式：、理解并记住推理形式结构的以下两种形式： (1) (2) 前提：前提： 结论：结

11、论：2、熟练掌握判断推理是否正确的不同方法。、熟练掌握判断推理是否正确的不同方法。3、牢记、牢记 P 系统中各条推理规则的内容及名称。系统中各条推理规则的内容及名称。4、熟练掌握在、熟练掌握在 P 系统中构造证明的三种方法。系统中构造证明的三种方法。5、能解决实际问题。、能解决实际问题。BAAAk21kAAA,21B三、主要题型三、主要题型1、用等值演算法判断推理是否正确。、用等值演算法判断推理是否正确。2、用主析取范式判断推理是否正确。、用主析取范式判断推理是否正确。3、在自然系统、在自然系统 P 中证明推理。中证明推理。4、在自然系统、在自然系统 P 中，构造用自然语言描述的推理。中，构造

12、用自然语言描述的推理。一、内容提要一、内容提要 1、一阶逻辑命题符号化、一阶逻辑命题符号化 个体词个体词：个体，个体常量，个体变量，个体域。：个体，个体常量，个体变量，个体域。 谓词谓词：一元谓词（表示事物性质），：一元谓词（表示事物性质），n元谓词（表元谓词（表示事物之间的关系）。示事物之间的关系）。 量词及其分类量词及其分类：量词，全称量词，存在量词。：量词，全称量词，存在量词。 命题符号化命题符号化：知识点知识点4 一阶逻辑的基本概念一阶逻辑的基本概念 2、一阶逻辑公式及解释、一阶逻辑公式及解释 一阶语言一阶语言：字母表，项，原子公式，合式公式。：字母表，项，原子公式，合式公式。 公式的

13、解释及分类公式的解释及分类：量词的辖域，自由出现，约：量词的辖域，自由出现，约束出现，自由变元，约束变元，解释，公式的类型；束出现，自由变元，约束变元，解释，公式的类型；永真式，永假式，可满足式。永真式，永假式，可满足式。二、基本要求二、基本要求1、准确地将给定命题符号化。、准确地将给定命题符号化。2、深刻理解永真式、永假式、可满足式的概念、深刻理解永真式、永假式、可满足式的概念及其判别方法。及其判别方法。3、对于给定的解释能判断出命题是真命题还是、对于给定的解释能判断出命题是真命题还是假命题。假命题。三、主要题型三、主要题型1、一阶逻辑中命题符号化。、一阶逻辑中命题符号化。2、给定解释，解释

14、给定公式。、给定解释，解释给定公式。3、证明某些公式不是永真式，也不是永假式。、证明某些公式不是永真式，也不是永假式。4、证明永真式或永假式。、证明永真式或永假式。一、内容提要一、内容提要 1、一阶逻辑等值式与置换规则、一阶逻辑等值式与置换规则 等值式等值式：若：若PQ为永真式，则称为永真式，则称P与与Q是等值的，是等值的，记为记为 。 基本的等值式基本的等值式：5 组组16 个，个，P44表表2.2。 等值演算规则等值演算规则：置换规则，换名规则，代替规则。：置换规则，换名规则，代替规则。知识点知识点5 一阶逻辑的等值演算与推理一阶逻辑的等值演算与推理QP 2、一阶逻辑的前束范式、一阶逻辑的

15、前束范式 前束范式前束范式：定义。：定义。 求前束范式求前束范式：利用等值式及等值演算规则，对给：利用等值式及等值演算规则，对给定公式进行等值演算。定公式进行等值演算。 3、一阶逻辑的推理理论、一阶逻辑的推理理论 推理的形式结构推理的形式结构：与命题逻辑相同。：与命题逻辑相同。 推理正确推理正确：推理式为永真式。：推理式为永真式。 一阶逻辑中重要的推理定律一阶逻辑中重要的推理定律：推理定律的组成。：推理定律的组成。 无量词化处理无量词化处理：规则（：规则（4个）。个）。 自然推理系统自然推理系统 F 的构成的构成： 字母表，合式公式，命题逻辑的推理规则，一阶字母表，合式公式，命题逻辑的推理规则

16、，一阶逻辑的推理定律，无量词化处理。逻辑的推理定律，无量词化处理。二、基本要求二、基本要求1、深刻理解并牢记一阶逻辑中的重要的等值式，、深刻理解并牢记一阶逻辑中的重要的等值式，并能准确而熟练地应用它们。并能准确而熟练地应用它们。2、熟练、正确地使用置换规则、换名规则和代、熟练、正确地使用置换规则、换名规则和代替规则。替规则。3、准确地求出给定公式的前束范式。、准确地求出给定公式的前束范式。4、深刻理解自然推理系统、深刻理解自然推理系统 F 中的各条推理规则，中的各条推理规则，特别是要正确使用特别是要正确使用 US 等等 4 个规则。个规则。5、能正确地证明给定的推理。、能正确地证明给定的推理。

17、三、主要题型三、主要题型1、由已知的等值式证明新的等值式。、由已知的等值式证明新的等值式。2、求给定公式的前束范式。、求给定公式的前束范式。3、在自然推理规则、在自然推理规则 F 中构造推理证明。中构造推理证明。4、在自然推理规则、在自然推理规则 F 中，构造用自然语言描述的中，构造用自然语言描述的推理的证明。推理的证明。一、内容提要一、内容提要 1、集合的基本概念、集合的基本概念 元素与集合元素与集合：集合，元素，属于，不属于。：集合，元素，属于，不属于。 特殊集合特殊集合：N , Q , R , C , , E , 幂集。幂集。 集合的表示方法集合的表示方法：列举法，描述法，归纳定义法。：

18、列举法，描述法，归纳定义法。 集合之间的关系集合之间的关系： 重要结果重要结果：空集是任何集合的子集。：空集是任何集合的子集。知识点知识点6 集合集合, 2、集合的运算、集合的运算 集合的初级计算集合的初级计算：交、并、差、补、环和、环积。：交、并、差、补、环和、环积。 集合的广义运算集合的广义运算：广义交，广义并。：广义交，广义并。 集合的幂集合的幂： 3、集合恒等式、集合恒等式 运算律运算律：交换律等，：交换律等，P65 67，19个。个。 4、有限集合元素的计算、有限集合元素的计算 计数方法计数方法：文氏图或容斥原理。：文氏图或容斥原理。 容斥原理容斥原理：二、基本要求二、基本要求1、熟练掌握集合的两种表示方法。、熟练掌握集合的两种表示方法。2、能够判别元素是否属于给定的集合。、能够判别元素是否属于给定的集合。3、能够判断两个集合之间是否存在包含、相等、能够判断两个集合之间是否存在包含、相等、真包含等关系。真包含等关系。4、熟练掌握