《离散数学导学》精炼：第1-3章（导论，数，命题逻辑）-Toy模板网

这篇具有很好参考价值的文章主要介绍了《离散数学导学》精炼：第1-3章（导论，数，命题逻辑）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

勤学苦练莫懈怠，求知问道不辞难。
脚踏实地披荆斩棘，铸就辉煌不负韶华。
知识点滴如珠玉，汲取精华莫放弃。
勤奋学习方成才，未来辉煌走向前。

引言

我一直觉得在计算机这一学科的学习中，离散数学是极为重要的知识基础。离散化的思想体现在计算机学科的方方面面。举例来说，“像素”这一概念是我们日常生活中耳熟能详的，我们将一个图片拆分成一个个极微小的像素，就是利用了离散化的思想。为了帮助大家打好离散数学的思维基础，我新开一个专栏，对《离散数学导学》这本书做一个精炼，使其更易理解。这篇文章是这个专栏的第一部分，主要介绍1-3章。

正文

第一章导论

导论这一章节中，指出了本书的知识结构。在这里用图给大家直观的展示一下：《离散数学导学》精炼：第1-3章（导论，数，命题逻辑）
（箭头指的是一章是另一章的前置知识，为想要只学习部分内容的同学加以参考。但要注意，就算不是必要的前置知识，后面章节的说明还是多多少少用到了前几章的知识的，请要速读的同学酌情考虑）

第二章数

Peano算术（皮亚诺算术）

Peano算术用四条公理描述了自然数的基本性质：

0是自然数
若x是自然数，则x+1也是自然数
不存在满足x+1=0的自然数x
给定自然数x、y，若x+1=y+1，则x=y

Peano算术的前两条形式化定义了什么是“自然数”：自然数从0开始，向后递推。第三条界定了0是最开始的自然数。第四条则给出了“相等”这一性质的定义。
我们可以利用递推这一思想定义其他的运算符或数进行定义。例如，当我们定义“乘法”这一运算符的时候，我们就可以列出如下的式子：

0* n=0(从0开始）
(0+1)* n=(0* n)+n(向后递推1位）
(m+1)* n=(m* n)+n(继续向后递推)

看到这里，我想你已经想到某个不愿意透露姓名的dp算法了，那么这里顺便推荐一下我之前写的一个很经典的dp题解，大家可以以Peano思想的角度重新看一下这道dp经典例题——堆石头，相信你会有新的认识。

第三章命题逻辑

原子命题

一个不能再拆成多个命题的命题就是原子命题，比如：“今天是星期二”

真值

通俗来讲，真值指的就是一个命题是真是假。一般来说，只有两种真值：true（真）和false（假）。
注意：

有时可能会看到第三种真值“未定义”，但未定义意味着它也只可能是true或者false，没有第三种可能性。
true和false本身就可以是命题。

逻辑运算符（重点）

这是一个大重点，计算机编码中的逻辑门就是以逻辑运算符为基础。

逻辑运算符将多个原子命题“拼”起来，产生复合命题。常见的逻辑运算符就那几个，大家中学时都学过（也就是∧，∨，¬这些），这里提一下→（蕴含运算符）和↔（等值运算符）：

→（蕴含运算符）：p→q意为“如果p是真的，则q是真的”。注意，我们可以将它看作是一个约定，当p为假的时候，我们视作违反约定，此时整个命题是真的。
↔（等值运算符）：p↔q意为“p→q∧q→p”。

运算的优先级

就一句话，如果你不确定运算顺序的话，加括号就好了。

重言式，矛盾式，不定式

重言式：永远为true的命题
矛盾式：永远为false的命题
不定式：除了重言式和矛盾式以外的所有命题

真值表

直接上例子，这是(p∧q)∨(p→q)的真值表：
《离散数学导学》精炼：第1-3章（导论，数，命题逻辑）
我们为原子命题赋真值，然后由原子命题的真值算出上一级复合命题的真值，然后再上一级…直到最大的复合命题的真值。将这个过程列成表格，就是真值表。

等值推理

等值推理，和我们平时化简式子很像，看个例子：
《离散数学导学》精炼：第1-3章（导论，数，命题逻辑）
注意：我们这里在每一步前要写成⇔符号而不是=符号。
下面是一些我们常用的定理，我只列出了我认为需要特殊记住的定理：

分配律：p ∧ (q ∨ r) ⇔ (p ∧ q) ∨ (p ∧ r)，p ∨ (q ∧ r) ⇔ (p ∨ q) ∧ (p ∨ r)

吸收律：p ∧ (p ∨ q) ⇔ p，p ∨ (p ∧ q) ⇔ p

德摩根定律：¬(p ∧ q) ⇔ ¬p ∨ ¬q，¬(p ∨ q) ⇔ ¬p ∧ ¬q

蕴含式的等效形式：p → q ⇔ ¬p ∨ q，¬(p → q) ⇔ p ∧ ¬q

剩下的定理一看就能看明白，接触的多了自然就记住了。

自然演绎

自然演绎法/证明树是另一种证明定理正确性的方法，其一般形式如下：
《离散数学导学》精炼：第1-3章（导论，数，命题逻辑）
树的上层是前提，下层是由上层的一部分前提推导出来的结论。注意，在这里我们默认前提都是真的。

我们先说明自然演绎法用到的定理，然后举一个例子来说明这个过程。

自然演绎法的定理

蕴含消去规则
蕴含引入规则

说明一下这个规则，这个规则的意思是：如果p是真的，p通过若干步推导得出q是真的，那么p→q。
这里p被套上中括号后，我们假定p是真的。证明树的最顶端一定是这些被套上中括号的命题。
真引入规则
合取消去规则

这里结论是p是真的或者q是真的都可以
合取引入规则
析取引入规则

和合取引入一样，这里p为前提或q为前提都可以
析取消去规则

这个规则说明一下，这个规则的意思是：如果假设p是真的，则p能推出r；假设q是真的，则q也能推出r；p和q中至少有一个是真的，则r是真的。
等值消去规则

9.等值引入规则