前言

离散数学对于我而言一直是比较神秘的角色，脑海里面很难形成相应的概念。
线性代数，我们可以理解成描述空间变化的东西，微积分，帮助研究变化的方式方法。这个在 bilibili 当中也看过不少的教程，对其也存在一定程度的理解。

然而离散数学这个词，就很离散，离散的对象之间，不存在变化，是我比较困惑的一个点。

离散数学及应用这本书，帮我比较好的解释了这些问题。

离散数学是研究什么的？

离散数学就是研究集合的一门学问， 关于集合的定义，就是一堆相同的东西（比如说人）的合集。
一堆相同的东西， 我们可以将其指代为对象；

简单的举几个例子，在离散数学当中，研究的东西有：

1. 数： 整数的集合
2. 图： 若干个给定的顶点，以及每个顶点连接，形成的图形的集合
3. 树： N 个有限节点组成的具有层次关系的集合。 …

基本概念

逻辑

逻辑是离散数学当中的基本单位，其实在计算机的基础当中，也很常见，比如说指令集当中最基本的运算方法 and or not，就是最基本的一个逻辑结构。
而在离散数学当中，把最基本的逻辑单元罗列出来，相当于一把瑞士军刀，将很多复杂抽象的概念，具象成公式，进而再进行研究。

命题

p: 明天晴天 q: 我去打球

命题逻辑

表达命题与命题之间的关系.
符号包括

我是人,也是工程师
我要么去打球, 要么去洗碗
如果明天晴天, 我就去打球.
我不是外星人.

复合命题

多个命题之间, 用命题逻辑连接起来, 形成复合命题.

1. 有限个体域当中消去量词 有限个体域 D={a1, a2, a3, … , an} ForAll A(x) <=> A(a1) ^ A(a2) ^ A(a3) ^ … ^ A(an) ThereExist A(x) <=> A(a1) v A(a2) v A(a3) v … v A(an)

2. 量词否定 Not ForAll A(x) <=> ThereExist Not A(x) Not ThereExist A(x) <=> ForAll Not A(x)

3. 量词管辖域的收缩与扩张 B 中不包含 x ForAll x (A(x) v B) <=> ForAll x A(x) v B ForAll x (A(x) ^ B) <=> ForAll x A(x) ^ B ForAll x (A(x) -> B) <=> ThereExist x A(x) -> B ForAll x (B -> A(x)) <=> B -> ForAll x A(x)

4. 量词分配

ForAll x (A(x)^B(x)) <=> ForAll x A(x) ^ ForAll B(x) ThereExist x (A(x)vB(X)) <=> ThereExist x A(x) v ThereExist B(x)

1. 前束范式( 所有的量词都在前面, 每一个量词作用域达到公式的结尾 ) 任何一个公式都可以化成前束范式. ForAll x F(x) v Not ThereExist x G(x,y) <=> ForAll x F(x) v ForAll Not x G(x,y) <=> ForAll x F(x) v ForAll Not z G(z, y) <=> ForAll x (F(x) v ForAll Not z G(z,y)) <=> ForAll x ForAll z(F(x) v Not z G(z,y)) # 前束范式 <=> ForAll x ForAll z(G(z,y) -> F(x)) # 前束范式

等值演算

两个符合命题拥有相同的真值表, 那么可以说两个命题是等价的, 既然存在等价的命题. 那么命题之间就可以进行转换, 也就是命题演算.

    p -> (q -> r)  
<=> p -> (~q v r)  
<=> ~p v (~q v r)  
<=> (~p v ~q) v r  
<=> ~(p ^ q) v r  
<=> (p ^ q) -> r  

命题演算

复合命题可以通过演算进行简化, 那么一般的简化方法被总结成为规律. 行程所谓定律.

难以理解的一些定律如何与直观建立联系?

• 吸 收 率: p v (p ^ q) <=> p ; p ^ (p v q) <=> p

  p 吸收了 q. 或者说 q 的真假并不会影响整体的结果.

• 德摩根定律: ~(p v q) <=> ~p ^ ~q ; ~(p ^ q) <=> ~p v ~q

  p: 我是外星人
  q: 我是小狗
  我是外星人或者我是小狗这件事情是假的.
  我不是外星人,我也不是小狗
  明天晴天或者我去打球是不会发生的. 等价于 明天既不会晴天,我也不会去打球.
  明天晴天并且我去打球是不会发生的. 等价于 要么明天不是晴天,要么明天我不会去打球

• 蕴含等值式: p->q <=> ~p v q

  如果明天晴天, 我就去打球. 等价于 要么明天不晴天, 要么我就去打球.

证明与推理

有了各种命题逻辑, 那么我们可以将一般的证明也符号化.
一般的形式是 A1 ^ A2 ^ A3 ^ A4 -> P

在这个基础上, 我们也有一些一般的推理逻辑, 表述如下:

• 析取三段论:

  (A v B) ^ ~A => B
  要么 A 为真, 要么 B 为真, A 不为真, ^所以 B 为真.

• 拒取式:

  (A -> B) ^ ~B => ~A
  因为 A, 所以 B, 非 B, 那么非 A.

• 假言推理:

  (A->B) ^ A => B 因为 A, 所以 B, A, 所以B.

• 附加律:

  A => (A v B)
  A 为真, A 或 B 为真.

• 化简律:

  (A ^ B) => A
  (A ^ B) => B

• 构造性两难:

  (A -> B) ^ (C -> D) ^ (A v C) => (B v D)
  A 发展经济 -> B 带来污染
  C 不发展经济 -> D 贫穷
  A 发展经济 v C 不发展经济
  B 忍受污染 v D 忍受贫穷

集合

有了逻辑, 推理之后, 我们可以将这些东西应用到具体的实体. 也就是我们的集合.
集合论这个概念是为了定义数学的基础. 有了集合论, 再加上逻辑演算, 就可以开始定义数学的基本运算.
集合会有朴素集合论,以及其他的公理集合论.
“{}” 定义一個集合, 集合是无序的.

存在集合之后, 集合与集合之间,就可以进行运算. 其中涉及到

• 交集
• 并集
• 补集
• 差集
• 对称差 “⊕”
• 取反
• 容斥原理: 多个集合相加的法则

而有了集合之后, 可以定义一个有序对.其集合上的定义是:

‘(a,b) = {{a}, {a,b}}’

在有序对的基础上, 我们可以定义笛卡尔积.或者称之为卡氏积.
有两个集合, A, B, A x B 就形成了笛卡尔积. 最典型的笛卡尔积就是两条实数轴 X轴 X Y轴 构成的坐标系.
也就是 X x Y, 笛卡尔坐标系.
X x Y 通俗来讲,就是所有的有序对,其中第一个元素属于 X, 第二个元素属于 Y.

关系

有了有序对之后, 我们就可以在有序对的基础上, 再定义关系.

二元关系

考虑这样一个集合, 其所有元素全部都是有序对, 这样的集合, 可以称之为二元关系.
研究有序的集合元素超过三个以上, 则称之为多元关系.

举例: 小于关系, 一个集合,所有的元素都是二元组, 并且二元组的第一个元素小于第二个元素.
对于二元关系而言, 我们可以有多种表达方式 R 为关系:

• xRy
• (x,y) ∈ R
• R(x,y)

举例仍然可以是小于关系.

• x < y
• (x,y) ∈ <
• <(x,y)

外延式的关系: 穷举所有的可能性.
内涵式的关系: 例如 a - b > 0, 则 a > b

A 到 B 的二元关系

A x B 的任意子集. 或者说 R ∈ A x B
R 是 P(A x B) 的子集(子集符号打不出来)

A 上的二元关系

A x A 的 任意子集. 有趣的运算在于:
A 的元素个数为 2 , 那么 A 存在多少个二元关系?
“|A| x |A| = 4”, 2^4 = 16 个二元关系.

A 的元素为 3, 那么 A 存在 2^(3*3) = 512 个二元关系.
有趣的例子是, 三个和尚没水吃, 因为他们的关系太多 ~

函数

函数，是针对集合的特殊的操作，一般是从集合中运算出唯一结果的一个方法。
比如说，从图当中，寻找到路径，对集合进行求和，最终的目的，就是计算出一个结果。

数论

数论更多的是研究数字的理论，比如说素数，最大公约数这些数字，以及与其相关的一些算法，譬如说同余算法
数论当中，数字的基本概念，以及其算法，在计算机领域当中有不少应用。
最为经典的就是利用素数的 RSA 不对成加密算法。

计数

就是如何计算数字，和数论的区别在于，数论更多的是在谈数字的基本概念，基于这些基本概念的算法。
而计数，则是存粹的运算。更多的注重与结果本身。

递归 & 数学归纳法

数学归纳法，就是证明基础是正确的，然后证明基础+1 的情况下也是正确的， 那么，就可以证明整个集合都是符合条件的。