(涵盖第 1 个讲义(Lecture Note))

离散数学 Discrete Mathematics

• 是什么？

  数学的一个研究”可数、不连续且独立“对象的分支

• 研究什么？

  命题、逻辑、数学证明、集合论、函数映射、排列组合、图论、群、复杂性(P/NP problem)…

• 为什么要学？

  计算机的底层逻辑和离散数学的底层逻辑都是布尔运算、布尔函数… 0 和 1

LN1 Propositions and Operations 命题与算子

Induction 数学归纳法：命题逻辑 (Propositional Logic)

1. Base Case 证明在最小的自然数（如 n=1 或 n=0）时命题成立。
2. Inductive Hypothesis 假设命题在 n=k 时成立。
3. Inductive Step 在假设的基础上，证明命题在 n=k+1 时也成立。

Boolean Algebra 布尔代数

布尔代数 (Boolean algebra) 跟普通代数有类比关系： 在布尔代数里只有两个离散数值，即 “真 (1)” 和 “假 (0)”。

布尔操作符：

• AND (∧) 对应 product (×)，因为真的可能少，称作 minterm： 因为只要有 0 就是 0，对应数字里只有 1×1=1。
• OR (∨) 对应 无溢出的 sum (+)，因为真的可能多，称作 maxterm： 因为只要有一个 1 就是 1，对应数字里 1+0=1, 1+1=1。
• NOT (¬) 对应补运算，类似于 1−x。
• XOR (⊕) 对应有溢出的 sum (+)： 1+0=1, 1+1=2=0。

功能完备性 (functional completeness)：表示一个操作符集合可以表示出所有操作符，e.g.，{AND, NOT} 是不完备的，但 {AND, NOT, OR} 是完备的。

Logic Operators 逻辑算子

• Proposition/Statement（命题）是在没有额外条件下一定正确或一定错误的判断句。

• x>0 不是有效命题

• 算子是一种布尔函数，描述布尔代数中的逻辑运算

• Truth table 是将所有真假组合以及某种函数运算结果全列出来的表格 三种基本算子： $$非：NOT\ P=¬P= \overline{P}$$ $$与：P\ AND\ Q=P∧Q\ \ (iff\ both\ true\ then\ true)$$ $$或：P\ OR\ Q=P∨Q\ \ (iff\ both\ false\ then\ false)$$

• 一切算子都可以用三种基本算子表达，有两种规范形（canonical forms）可用于构造一切算子等价公式：

  1. 只对(运算结果为真的)“真行”做 Sum-of-Products (SOP，与再或)——把每一行的每个输入(通过 NOT)作为真项用 AND 连接(minterm)，所有行再用 OR 连接。
  2. 只对(运算结果为假的)“假行”做 Product-of-Sums (POS，或再与)——把每一行的每个输入(通过 NOT)作为假项用 OR 连接(maxterm)，所有行再用 AND 连接。 (两者互为德摩根定律中的等价式)

  e.g. 异或 XOR：

  

  $$P\oplus Q \equiv (P\land \neg Q)\ \lor\ (\neg P\land Q) \equiv (\neg P \lor \neg Q)\land(P\lor Q) \equiv (P\lor Q)\land \neg(P\land Q)$$

• 对于三项及以上的多元函数，也适用这两种规范型。

De Morgan’s Law of Equivalence 德摩根律

$$\neg(P\land Q)\ \equiv\ (\neg P)\ \lor\ (\neg Q)\qquad \neg(P\lor Q)\ \equiv\ (\neg P)\ \land\ (\neg Q)$$

• “某数可被 3 或 5 整除” 的否定是 “既不能被 3 整除 也 不能被 5 整除”

• “我是男孩"的否定是“我是女性 或 我是成人”

  以下是除了德摩根定律外布尔运算遵守的其他普适性定律：

• 

• 注意第五条定律，P∧¬P 是恒假命题(t)；P∨¬P为恒真命题(c)。

Conditional Statements 条件命题

If

• if P then Q: P→Q (P implies Q)
• 只有 P 真且 Q 假时，该命题才假(因为 P 假时没有直接说明命题为假)
• 因此：“¬(P→Q) ≡ P ∧ ¬Q” → “P→Q ≡ ¬P ∨ Q”

Contrapositive 逆否命题

• P→Q ≡ ¬Q→¬P
• 只否不逆不等价

Iff 当且仅当

• P↔Q ≡ (P→Q) ∧ (Q→P)

Arguments 论证

Modus Ponens(肯定式)：(P, P→Q) → Q Modus Tollens(否定式)：(¬Q, P→Q) → ¬P

“自指"谬误

在布尔代数中，命题向自己或互相赋予真假很容易导致悖论，破坏二值性(bivalence)

• “P ≡ ¬P”：导致 P 自相矛盾

• “P: Q ≡ c，Q: P ≡ t”：导致 P 和 Q 相互矛盾

类似于命题，集合也不能随意自指或互指

• LEC2 会提到的 Russell’s Paradox 罗素悖论：$$W={,S\mid S\ \text{是集合且}\ S\notin S,},\ W\ 自相矛盾$$

• Barber’s Paradox 理发师悖论：理发师只给“不自己理发”的人理发——那么理发师给不给自己理？无论“给/不给”都矛盾。

问题出在 “naive comprehension”：允许以上这些毫无约束的自指或互指定义，会导致自相矛盾。

• CSC3001