离散数学
离散数学研究的是彼此分开、可以一个个数出来的东西：真或假，在集合里或不在，走这条路或那条路。它是计算机赖以运行的数学，而一切都从可以随手切换开关的逻辑开始。
最后更新
离散数学研究的是彼此分开、可以一个个数出来的东西。一个命题要么真要么假，一个元素要么在集合里要么不在，一个网络的两点之间要么有连线要么没有。中间状态是不存在的，这正是“离散”的含义，也正是计算机看待世界的方式。
入门课程涵盖六个主题：逻辑、集合、计数、图论、数论和证明。逻辑排在最前面，因为其他主题都要用它来表述。在下面选一个联结词，然后切换 p 和 q 的值。
p ∧ q 的真值表
| p | q | p ∧ q |
|---|---|---|
| 真 | 真 | 真 |
| 真 | 假 | 假 |
| 假 | 真 | 假 |
| 假 | 假 | 假 |
切换 p 和 q，或者点击某一行。高亮的就是它们选中的那一行。
把 p 读作“x 属于 A”，把 q 读作“x 属于 B”。涂色区域是命题为真的地方，圆点表示当前这一行。
p ∧ q
读作 p 且 q
在这组取值下，p ∧ q 为真。
只有 p 和 q 都为真时才为真。
用集合表示 AND 就是交集：x 属于 A ∩ B，恰好当 x 属于 A 且 x 属于 B。
逻辑：命题与联结词
命题是一个非真即假的句子，比如“7 是质数”或“现在在下雨”。逻辑用几个联结词把小命题组合成大命题，而真值表列出每一种输入组合下的结果。
| 符号 | 名称 | 读作 | 何时为真 |
|---|---|---|---|
| ∧ | AND，合取 | “p 且 q” | 两者都为真 |
| ∨ | OR，析取 | “p 或 q” | 至少一个为真 |
| ¬ | NOT，否定 | “非 p” | p 为假 |
| ⊕ | XOR，异或 | “p 或 q，但不同时成立” | 恰好一个为真 |
| → | IMPLIES，蕴含 | “如果 p，那么 q” | 除了 p 真 q 假之外的所有情况 |
| ↔ | IFF，双条件 | “p 当且仅当 q” | p 和 q 的值相同 |
其中有两个常常让人意外。逻辑里的 OR 是相容的：p 和 q 都为真时，“p 或 q”也为真，这和日常说的“喝茶还是喝咖啡？”不一样。排他的版本有自己的名字，叫 XOR。
另一个是 IMPLIES。p → q 只在一行为假，也就是 p 为真而 q 为假的时候。可以把它看成一个承诺：“如果下雨，我就带伞。”只有下了雨却没带伞，这个承诺才算被打破。天晴的时候，不管你带了什么，承诺都没有被打破，所以这个命题算作真。
等价的命题
如果两个命题的真值表在每一行都相同，它们就是等价的。在上面的工具中选择 OR 并对 p 取反：¬p ∨ q 的那一列与 p → q 的那一列完全一样，所以两者说的是同一件事。
最有用的等价式是德摩根定律，它说明 NOT 如何穿过 AND 和 OR：
¬(p ∧ q) ≡ ¬p ∨ ¬q
¬(p ∨ q) ≡ ¬p ∧ ¬q
用文字来说：“不是两者都成立”等于“至少有一个不成立”，“两者都不”等于“两者都为假”。程序员每天都用它们改写条件，比如“not (已登录 and 已验证)”。
逻辑和集合是同一个想法
把 p 读作“x 在 A 中”，把 q 读作“x 在 B 中”。这样 AND 就是交集，OR 就是并集，NOT 就是补集，每张真值表都是一张涂了阴影的韦恩图，这也是工具在表格旁边画出韦恩图的原因。德摩根定律于是变成了关于集合的规则：
(A ∩ B)′ = A′ ∪ B′
集合符号页面会在一张可以点击的图上把这些运算逐一涂出来。
计数
离散数学里的计数，指的是不把所有情况列出来就数清楚。大部分工作靠两条规则完成。
乘法原理。 如果第一个选择有 m 种做法，第二个选择有 n 种做法，那么两者合起来有 m × n 种做法。4 位数的 PIN 码每一位有 10 种选择，所以一共有 10^4 = 10000 种可能的 PIN 码。
组合。 从 n 个东西中选出 k 个、不考虑顺序的方法数，记作 C(n, k)。从 8 种配料中选 3 种：
C(8, 3) = (8 × 7 × 6) / (3 × 2 × 1) = 56
分子数的是有顺序的选法，除以 3 × 2 × 1 则去掉了同样三种配料可能被选出的 6 种顺序。
答案是 6 × 5 再除以 2，等于 15。如果你算出的是 30，说明每一对你都按两种顺序各数了一次。
图
图是一组点（称为顶点）以及连接它们的线（称为边）。任何由连接构成的东西都可以用图来描述：城镇之间的道路、社交网络中的好友、网页之间的链接。
一个入门结论：如果 5 个人两两之间各握一次手，一共有 C(5, 2) = 10 次握手。每个人握 4 次手，合计 5 × 4 = 20 个“手端”，而每次握手有两端，所以是 20 / 2 = 10。这个论证就是握手定理：所有顶点的度数之和等于边数的两倍。
数论与证明
模运算就是表盘上的算术。17 mod 5 等于 2，也就是 17 除以 5 的余数。8 点之后再过 9 个小时是 5 点，因为 17 mod 12 等于 5。同样的思路用在非常大的数上，就是安全网站背后 RSA 加密的工作原理。
数学归纳法分两步证明一个命题对每个正整数 n 都成立：先验证 n = 1 时成立，再证明如果它对某个 n 成立，那么对 n + 1 也成立。比如，下面这个等式就是这样证明的：
1 + 2 + ... + n = n(n + 1) / 2
它对每一个 n 都成立，而不只是你试过的那几个值。
离散数学有什么用
- 编程：每个 if 语句都是逻辑，德摩根定律可以用来改写条件。
- 数据库：连接或筛选表的查询，就是集合运算。
- 算法：计数告诉你随着输入变大，一个程序要执行多少步。
- 网络与地图：最短路线和社交网络都是图论问题。
- 安全：加密建立在数论和模运算之上。
- 硬件：处理器由逻辑门构成，而逻辑门就是刻在硅片上的真值表。
离散数学难吗？
它的难和代数、微积分不一样。要记的公式不多，计算量也小，但很多题目要求你证明一件事，而不是把它算出来，而写出有说服力的论证，对大多数学生来说是一项新技能。
最有帮助的做法，是先用手算几个小例子，再去找规律：画出韦恩图，写出真值表，把每种情况都列出来。符号一开始看起来很繁重，但大部分不过就是本页和集合符号页面上的那些符号。
常见问题
离散数学是什么？
离散数学是研究彼此分开、可数的对象，而不是连续变化的量的数学分支。它的主要内容有逻辑、集合、计数、图论、数论和证明。微积分关心事物如何连续变化；离散数学关心有多少个、是哪些，以及一个命题是否为真。
离散数学难吗？
它的难和微积分不一样。要套用的公式更少，要构建的论证更多，对很多学生来说，这是第一门以写证明为核心的课。代数运算通常很轻。觉得吃力的学生，大多是还在适应证明，而多用小例子练习，这一点很快就会好转。
离散数学有什么用？
几乎用在计算机科学的每个角落。电路和 if 语句靠的是逻辑，数据库查询建立在集合之上，计数告诉你一个算法要跑多久，图用来描述网络和地图，数论则是保护网上支付的加密技术的基础。
离散数学包括哪些内容？
一门典型的入门课会讲命题逻辑和真值表、集合与韦恩图、函数与关系、包括归纳法在内的证明方法、用排列组合计数、基础概率、图与树，以及模运算。有些课程还会加上递推关系和布尔代数。
学计算机科学需要离散数学吗？
需要。几乎所有计算机科学专业都把它列为必修课，通常在大一或大二，因为算法、数据结构和计算理论都以它为前提。如果只是学编程，你可以先不学它，但逻辑、集合和计数在日常代码中出现得比大多数人预想的要早。
离散数学和连续数学有什么区别？
离散数学处理可以一个一个列出来的值，比如整数、真与假，或者网络中的节点。连续数学，比如微积分，处理的是在某个范围内可以取任意值的量，比如时间、距离或温度。
真值表是什么？
真值表列出一个逻辑命题的输入取真、假的每一种组合，以及每种组合下命题的值。有 p 和 q 两个输入时，共有四行。真值表可以用来证明两个命题等价：如果它们的列在每一行都相同，它们就永远一致。
