离散数学复习笔记（已完结）

本篇为《离散数学》学科的个人复习笔记，知识点有所偏重。 课本是上海科学技术文献出版社左孝凌版的《离散数学》。 课本中定义和定理过多，文章中只记录课本中和课堂上重要常用的的定义和定理，不会做深入的解释，会有一些疏漏。 因为部分符号打不出来，所以中间插入的图片会比较多。 已完结。如有错误烦请提出。 以下是正文

离散数学主要分为四部分：

古典逻辑

亚里士多德的三段论：

大前提 --> 小前提 --> 结论

莱布尼兹把推理归纳为符号计算，提出思维运算的思想。 布尔发明布尔代数,（亦可解释为集合代数） 摩根几乎同时独立地作出重要贡献 弗雷格第一个提出公理化谓语逻辑系统“概念文字”，是亚里士多德以来逻辑的重大进展，基本实现莱布尼兹的梦想。

数理逻辑的内容：

命题逻辑 谓词逻辑 公理化集合论 递归论 证明论

定义：

命题是一个能判断真假的陈述句

命题不能是疑问句、命令句、感叹句等

真值的几点说明：

时间性 区域性 标准性

定义：

对于一个任意给定的命题，如果不能分解为更简单的命题，就称为原子命题，反之，成为复合命题。

命题联结词

否定，合取，析取，蕴含(条件)、等值

需要注意的有：

否定 > 合取 > 析取 > 条件 > 双条件

例题： 公式分类

赋值永远是“真”值的式子称为永真公式，又称重言式。

赋值永远是“假”值的式子称为永假公式，又称矛盾式。

既有真值又有假值的式子称为可满足式

定义

如果对两个公式Ａ，Ｂ不论作何种指派，它们的真值均相同，则称Ａ，Ｂ是逻辑等价的，亦说Ａ等价于Ｂ，记A⇔B.

定理

命题公式A⇔B的充要条件是A↔B为永真式。

常用等价式：

除了利用真值表的方法证明两个命题公式的等价，还可以采用等价代换（等价置换）的方法进行证明。

利用公式的等值演算，可以实现以下三个基本目的 判定命题公式的基本类型，即判定或证明一个命题公式为永真或永假 证明两个命题公式之间具有等值关系 对复杂的命题公式进行化简。

定义

命题公式Ａ称为永真蕴含命题公式Ｂ，当且仅当Ａ→Ｂ是一个永真式，记作：Ａ=>Ｂ 注意 A=>B 与 A→Ｂ 的区别

其他联结词的补充：

对偶

范式 简单合取式又称小项，真值表中小项为“真”，全体小项的析取式（即为主析取范式）为永真式。 简单析取式又称大项，真值表中大项为“假”，全体大项的合取式（即为主合取范式）为永假式。

对于任意命题公式，都存在与其等值的析取范式和合取范式。 真值表中小项为真，大项为假。

例：离散数学程序实验（C语言）——程序求主析取范式和主合取范式 输入一个逻辑表达式，根据真值表法求取该表达式的主合取范式和主析取范式。

算法思路： 把命题公式改为后缀表达式，并把后缀处理的结果保存在结构体里，对各个逻辑运算符号进行优先级的定义，按照后缀表达式的方法进行赋值计算并将结果输出存储为真值表。按照真值表选择输出主合取范式和主析取范式。 （此处附上实验代码仅供参考）