首页  思维导图  详情

离散数学

2025-09-11 10:41:54   1  举报





AI智能生成

大学离散数据，期末复习必备

离散数据

作者其他创作

大纲/内容

第1章命题逻辑的基本概念

1.1 命题与联结词

1.命题与真值

命题：判断结果唯一(非真即假)的陈述句 命题的真值：判断的结果 真值的取值：真(用1表示)与假(用0表示) 真命题与假命题

判断一个给定的句子是否为命题的一般步骤： ①是否式陈述句； ②是否具有唯一的真值

例题

2.命题分类

命题分类：简单命题（也称原子命题）与复合命题 简单命题：不能被分解成更简单的命题。 复合命题：由简单命题通过联接词联接而组成的命题。

3.命题符号化

简单命题符号化

复合命题符号化

4.否定、合取、析取联结词

相容或与排斥或： 析取联结词“v”与自然语言中的“或”不完全一样，由于自然语言中的“或”具有二义性,用它有时具有相容性（即它联结的二个命题可以同时为真），有时具有排斥性（即只有当一个为真，另一个为假时才为真),对应的分别称作相容或和排斥或。

例题：

合取联结词的实例

析取联结词的实例

5.蕴涵联结词

蕴涵联结词的实例

注：在自然语言中，如果p则q中的前件p和后件q往往有着某种内在联系，而数理逻辑是研究抽象的推理，p和q可以无任何内在联系。

6.等价联结词

例子：

小结：

练习：

1.2 命题公式及其赋值

1.命题变项与合式公式

命题变项

命题常项：简单命题是命题逻辑中最基本的研究单位，其真值是确定的。 命题变项（命题变元）：取值1或0的变元。 常项与变项均用 p, q, r, …, pi, qi, ri, …, 等表示.

合式公式

命题公式：将命题变项用联结词和圆括号按照一定的逻辑关系联结起来的符号串称作合式公式。

对于定义1.6做以下说明：

1.定义中引进了A，B等符号，用他们表示任意的合式公式，称作元语言符号，而某个具体的公式，如p，pVq，.....等称作对象语言符号。

2.在公式中也可以出现0和1，此时把它们看作p∧﹁q和p∨﹁q的缩写，同样，当公式出现p∧﹁q和p∨﹁q时，也常把它们写成0和1.

合式公式的层次

2.公式的赋值

公式赋值

真值表

如果二个公式A与B的真值表对所有赋值最后一列都相同，即最后结果都相同，则称这二个真值表相同，而不考虑构造真值表的中间过程。

哑元：设公式A,B共含有命题变项，而A或B不全含这些命题变项，称A中不含有的命题变项为A的哑元。A的取值与哑元无关。

例子：

公式类型

第一章习题课

练习1

练习2

练习3

第2章命题逻辑等值演算

1.等值式

例子：

代入定理

举例：

基本等值式

等值演算与置换规则

等值演算的应用举例

判断公式类型

举例：

练习：

2.析取范式与合取范式

范式概念

范式的性质

定理2.1 (1) 一个简单析取式是重言式当且仅当它同时含有某 个命题变项和它的否定式. (2) 一个简单合取式是矛盾式当且仅当它同时含有某个命题 变项和它的否定式.

定理2.2 (1) 一个析取范式是矛盾式当且仅当它每个简单合 取式都是矛盾式. (2) 一个合取范式是重言式当且仅当它的每个简单析取式都 是重言式.

定理2.3（范式存在定理） 任何命题公式都存在与之等值的析取范式与合取范式

命题公式的范式

求公式的范式

范式的不惟一性

举例：

极小项与极大项

举例：

极小项和极大项的性质

主析取范式与主合取范式

求公式主范式的步骤

举例：

主范式的应用

例题：

主析取范式和主合取范式之间的转换

主析取范式→主合取范式

主合取范式→主析取范式

举例：

用真值表确定主范式

步骤方法：

举例：

3.联结词的完备集

真值函数

联结词完备集

复合联结词：

第二章习题课

练习1:概念

练习2: 判断公式类型

练习3：求公式的主范式

练习4：联结词完备集

练习5：应用题

第3章命题逻辑的推理理论

1.推理的形式结构

数理逻辑的主要任务是用数学的方法研究推理。所谓推理是指从前提出发推出结论的思维过程，而前提是已知的命题公式集合，结论是从前提出发应用推理规则推出的命题公式。

推理的形式结构

判断推理是否正确的方法:

推理实例

推理定律——重言蕴涵式

2.自然推理系统P

在自然推理系统P中构造证明

1.直接证明法

2.附加前提证明法

举例：

3.归谬法（反证法）

举例：

第三章习题课

练习1：判断推理是否正确

练习2：构造证明

练习3：构造证明

第4章一阶逻辑基本概念

1.一阶逻辑命题符号化

谓词

量词

实例：

特性谓词加入命题函数的两个原则

实例：

2.一阶逻辑公式及其解释

一阶语言L 的项与原子公式

一阶语言L 的公式

封闭的公式

公式的解释

实例：

公式的类型

代换实例

实例:

第四章习题课

练习1

练习2

练习3

练习4

练习5

第6章集合代数

1.集合的基本概念

元素与集合

集合与集合

空集

全集和幂集

2.集合的基本运算

初级运算(集合的基本运算)

集合运算的表示：文氏图

几点说明

广义运算

运算的优先权规定

有穷集合元素的计数

实例：

3.集合恒等式

集合算律

集合证明题

集合等式的证明

第六章习题课

练习1

方法分析

练习2

练习3

练习4

第7章二元关系

1.有序对与笛卡儿积

有序对

笛卡儿积

笛卡儿积的性质

性质证明

实例：

2.二元关系的定义与表示法

二元关系

A到B的关系与A上的关系

A上重要关系的实例

关系的表示

3.关系的运算

关系的基本运算

逆与合成

合成的图示法

限制与像

关系运算的性质

推广

关系的幂运算

幂的求法

关系图

幂运算的性质

4.关系的性质

自反性与反自反

对称性与反对称性

传递性

关系性质成立的充要条件

证明

关系性质的三种等价条件

练习:

关系的性质和运算之间的联系

5.关系的闭包

闭包定义

练习：

闭包的构造方法

闭包的矩阵表示和图表示

实例

闭包的性质

6.等价关系与划分

等价关系的定义与实例

等价类定义 

等价类的性质

商集与划分

划分实例

由划分确定关系

7.偏序关系

定义与实例