离散数学：命题逻辑、集合、关系、图论

概念

前面 L0、L1 讲的是"物理上怎么造出 0 和 1、怎么把 0 和 1 连成功能"。这一篇要往回退一步，问一个更根本的问题：

"0 和 1 这套算术，它的数学是谁规定的？"

答案是离散数学（Discrete Mathematics）：

$$\boxed{{\displaystyle \text{离散数学}=\text{研究}\mathbf{\text{“一个一个数得出来”}}\text{的对象的数学}}}$$

"离散"的对立面是"连续"：微积分研究连续变化（极限、导数），离散数学研究可数对象（命题、集合、关系、图、整数）。 计算机处理的恰恰全是离散对象——一位一位的二进制、一个一个有编号的存储单元、一条一条的指令。

它在主线里为什么是"唯一硬前置"：

离散数学的分支	直接支撑什么
命题逻辑（布尔代数）	L1 数字电路的一切——真值表 = 门电路的功能表；circuit/10-boolean.md 讲的化简、SOP/POS 全是它的应用
集合与关系	ds 的集合实现、soft 数据库的"关系模型"（关系代数就是从这里来的）
图论	ds 的图算法、net 的路由、os 的资源分配图（死锁检测）
计数与概率基础	arch 命中率与性能评价、ds 散列分析

$$\boxed{{\displaystyle \text{离散数学}\to \text{布尔代数}\to \text{数字电路}\to \text{组成原理}}}$$

这条链就是 README 里说的"唯一真正的阻塞链"。

本篇在主线上的位置：它是"补前置"的一篇——circuit/10-boolean.md 已经在用真值表和卡诺图，本篇把那套符号的"数学出处"补齐：为什么可以化简、为什么 NAND 一种门就够了、范式与电路形式为什么一一对应。

原理

一、命题逻辑：五个联结词与一张真值表

命题（proposition）：一个有确定真假值的陈述句。真记 1，假记 0。

五个基本联结词：

符号	名字	读法	直觉
¬p	否定	非 p	取反
p ∧ q	合取	p 且 q	非 p 即 q 非；两个都为 1 才是 1
p ∨ q	析取	p 或 q	至少一个为 1
p → q	蕴含	若 p 则 q	只有 "p 真 q 假" 时为假
p ↔ q	等价	p 当且仅当 q	同真同假
（p ⊕ q）	异或	p 异或 q	不同为 1（可由前五个复合出来）

完整真值表：

p	q	¬p	p∧q	p∨q	p→q	p↔q	p⊕q
0	0	1	0	0	1	1	0
0	1	1	0	1	1	0	1
1	0	0	0	1	0	0	1
1	1	0	1	1	1	1	0

三处最容易出错、必须点名的行：

现象	说明
0 → 1 为真、0 → 0 也为真	假命题"蕴含"一切——这叫"善意推定（vacuously true）"，是"若……则……"的数学定义，不是日常语感
∨ 是"可兼或"	p∨q 在两者都真时也为真——日常语言里的"或"常常是"不可兼"（那是 ⊕）
¬p 列和 p 列正好互补	这看似废话，却是"等价变形"能成立的基础

"蕴含"有两个必须背下来的变形：

$$p\to q\equiv \mathrm{\neg }p\vee q\equiv \mathrm{\neg }q\to \mathrm{\neg }p$$

• ① ¬p ∨ q：把蕴含改写成"或"，这是电路实现与化简的关键一步；
• ② ¬q → ¬p（逆否）：与原命题等价（q → p（逆命题）、¬p → ¬q（否命题）都不等价！）。

二、等价式与对偶原理

常用等价式（化简与证明的工具箱）：

名字	形式
双重否定	¬¬p ≡ p
幂等	p∧p ≡ p；p∨p ≡ p
交换 / 结合	p∧q ≡ q∧p；(p∧q)∧r ≡ p∧(q∧r)
分配	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∧0 ≡ 0；p∨1 ≡ 1；p∧1 ≡ p；p∨0 ≡ p
排中 / 矛盾	p∨¬p ≡ 1；p∧¬p ≡ 0
蕴含改写	p→q ≡ ¬p∨q

德摩根是"最值钱"的一条：它告诉你"与"和"或"可以互相转换——这正是"用 NAND 实现一切"的数学依据。

对偶原理（duality）：把 ∧↔∨、0↔1 互换，得到的式子若原式是恒等式，则对偶式也是恒等式。

原式	对偶式
p∨1 ≡ 1	p∧0 ≡ 0
p∧(q∨r) ≡ (p∧q)∨(p∧r)	p∨(q∧r) ≡ (p∨q)∧(p∨r)
¬(p∧q) ≡ ¬p∨¬q	¬(p∨q) ≡ ¬p∧¬q

对偶的实用价值：证明一条、白送一条。 circuit/11-combinational.md 里"SOP→NAND-NAND、POS→NOR-NOR"的对偶关系，根源就在这里。

三、范式：把逻辑式写成"标准形状"

同一个逻辑函数可以有无数种等价写法——要"比较两个式子是否等价"，必须有一个标准形状。

范式	形状	对应电路
析取范式（DNF）	若干"与项"的"或"（积之和）	SOP：与-或两级电路
合取范式（CNF）	若干"或项"的"与"（和之积）	POS：或-与两级电路
主析取范式	每个与项都包含全部变量（各一次）	小项之和
主合取范式	每个或项都包含全部变量（各一次）	大项之积

小项（minterm）与大项（maxterm）：

• n 个变量共有 2^n 个小项（每个小项对应真值表的一行）；
• 小项 m_i：把该行"取值为 1 的变量写成原变量、取 0 的写取反"，再全部"与"起来；
• 大项 M_i：反过来（取 1 的写取反、取 0 的写原变量），再全部"或"起来；
• 一条漂亮的对称结论：

$$m_i\equiv \mathrm{\neg }{M}_i\text{（第 }i\text{ 号小项与第 }i\text{ 号大项互为否定）}$$

"主析取范式 = 取所有输出为 1 的行"——这就是 circuit/10-boolean.md 里"从真值表直接写 SOP"的数学出处。

四、联结词的完备性：为什么 NAND 一种门就够

问题：给我一套"基本联结词"，我能不能表示出"所有"的布尔函数？

定义：若任意布尔函数都能只用集合 S 里的联结词表示，则称 S 是完备集（functionally complete）。

集合	完备吗	为什么
{¬, ∧, ∨}	✔	主析取范式只用到这三个
{¬, ∧}	✔	p∨q ≡ ¬(¬p∧¬q)（德摩根）
{¬, ∨}	✔	对偶，同理
{→} 配合常量 0	✔	¬p ≡ p→0；p∨q ≡ (p→0)→q
{NAND}	✔（单元素完备！）	NAND 自己就能造出 ¬、∧、∨
{NOR}	✔（单元素完备）	对偶，同理
{∧, ∨}	✘	无法表示 ¬（因为 ∧/∨ 都是"单调"的：输入由 0 变 1，输出不会由 1 变 0）
{⊕, ∧}	✘	无法产生常量 1（⊕ 与 ∧ 在"全 0 输入"下都输出 0，且保持这个性质）

NAND 完备的三个构造（背下来）：

$$\mathrm{\neg }p=p\uparrow pp\wedge q=\mathrm{\neg }(p\uparrow q)p\vee q=(\mathrm{\neg }p)\uparrow (\mathrm{\neg }q)$$

其中 ↑ 表示 NAND。 下面是详细展开（lang 篇里用 ~ 表示取反）：

目标	用 NAND 实现	用了几只门
¬p	p NAND p	1
p ∧ q	(p NAND q) NAND (p NAND q)	2
p ∨ q	(p NAND p) NAND (q NAND q)	3

"多少个布尔函数"：

$$\boxed{{\displaystyle k\text{ 元布尔函数共有 }{2}^{2^k}\text{ 个}}}$$

• 一元：2^2 = 4 个（恒 0、恒 1、p、¬p）——这就是"只有 4 种一元门"的原因（circuit/10-boolean.md 的 4 变量表能列完）；
• 二元：2^4 = 16 个——circuit/10 的 2 变量真值表"16 种组合"就是这个数；
• 三元：2^8 = 256 个。

五、谓词逻辑：量词与它的两条规矩

命题逻辑有个短板：它把"所有 A 都是 B"当成一个整体，不能拆开（而数学里这种句子比比皆是）。谓词逻辑补上"量词"：

记号	读法	含义
∀x P(x)	全称量词	对所有 x，P(x) 成立
∃x P(x)	存在量词	存在（至少一个）x 使 P(x) 成立

两条规矩：

规矩	形式
① 量词否定要"换量词 + 否谓词"	¬∀x P(x) ≡ ∃x ¬P(x)；¬∃x P(x) ≡ ∀x ¬P(x)（"不是所有都成立" = "有反例"——这是"证伪只需一个反例"的数学形式）
② 量词顺序不可交换	∀x∃y P(x,y) 与 ∃y∀x P(x,y) 不同（前者 y 可以随 x 变，后者必须一个 y 通吃）

经典例子："每个人都有一位母亲" = ∀x∃y（真）；"存在一个人是所有人的母亲" = ∃y∀x（假）。 两句只差量词顺序，真假相反。

同一个道理在计算机里的形态：∀ 像"对所有输入"（全称测试），∃ 像"找到一个反例"——"程序全对"与"程序有 bug"的证明难度不对称（前者要穷尽，后者只需一例），根源就是这条。

六、集合：一切结构的原材料

集合的六个基本记号：∈（属于）、⊆（子集）、∪（并）、∩（交）、−（差）、‾（补）。

算个数的三个公式（都很常用）：

对象	个数
子集	|P(S)| = 2^{n}（n = |S|）——逐个元素"选或不选"
所有子集的"累计"	Σ_{k=0}^{n} C(n,k) = 2^n——同一件事的两种数法
笛卡尔积	|A × B| = |A| · |B|（A×B 是有序对集合）

容斥原理（"算个数不能重复也不能漏"）：

$$|A\cup B|=|A|+|B|-|A\cap B|$$$$|A\cup B\cup C|=|A|+|B|+|C|-|A\cap B|-|A\cap C|-|B\cap C|+|A\cap B\cap C|$$

读法："先把各块的加一遍，再把重叠两次的减掉，最后把重叠三次的补回来"——正负交替。 例 2 会用它算一道"至少喜欢一个"的经典题。

七、关系：把"性质"和"结构"写成数学

二元关系：R ⊆ A × B——就是从 A 到 B 的"配对规则"。 当 A = B 时，|A×A| = n² 个可能的有序对，所以"A 上的关系"共有 2^{n²} 个。

五种性质（判断题必考）：

性质	定义	反例（用来记）
自反	∀x: (x,x) ∈ R	"小于"不是自反（x<x 假）
反自反	∀x: (x,x) ∉ R	"小于等于"不是反自反
对称	(x,y)∈R ⟹ (y,x)∈R	"小于等于"不对称
反对称	(x,y)∈R 且 (y,x)∈R ⟹ x = y	"等于"既对称又反对称
传递	(x,y)∈R 且 (y,z)∈R ⟹ (x,z)∈R	"朋友"通常不传递

⚠️ 三个易错点： ① 对称与反对称不互斥——"等于"关系两者都满足； ② 反对称 ≠ 不自反——"小于等于"自反且反对称； ③ 既不对称也不反对称的关系很常见（"整除"：2|4 但 4∤2 → 对称性不成立；而 2|−2、−2|2 却不相等 → 也不是反对称）。

两种最有用的关系：

类型	定义	后果
等价关系	自反 + 对称 + 传递	把集合"分割"成若干等价类**——这就是"划分（partition）"
偏序关系	自反 + 反对称 + 传递	形成层级结构（哈斯图）；全序是"任意两个都可比"的特例

等价关系 ↔ 划分是一一对应的：给一个等价关系，就得到一个划分；给一个划分，就得到一个等价关系。 n 个元素的划分个数叫 Bell 数 B(n)：

n	1	2	3	4	5
B(n)（等价关系个数）	1	2	5	15	52

偏序的个数（n 个元素上的偏序关系数）n=1,2,3 分别是 1, 3, 19——例 3 会把 n=3 的 19 枚举出来验证。

关系的复合与传递闭包：R∘S 可以用"布尔矩阵乘法"实现（∨ 代替 +、∧ 代替 ×）；传递闭包用 Warshall 算法：

$$W[i][j]|=W[i][k]\wedge W[k][j](k=1..n)$$

三重循环、n³ 次运算——ds 里"最短路径 Floyd 算法"与它同一个骨架。

八、图论：把"关系"画成点与线

图 G = (V, E)：V 是顶点集（|V| = n），E 是边集（|E| = m）。

三条最基本的结论：

结论	形式	含义
握手定理	Σ deg(v) = 2m	每条边贡献 2 个度——"握手的总人次是偶数"
奇度顶点成对出现	奇度顶点的个数是偶数	由握手定理直接推出（偶度贡献偶数，总和为偶数 ⇒ 奇度个数为偶）
完全图 K_n	m = C(n,2) = n(n−1)/2，每个顶点度 = n−1	任意两点都有边

欧拉路与欧拉回路（一手就能判）：

问题	判据
存在欧拉回路（走遍每条边、回到起点）	所有顶点度数为偶
存在欧拉路（走遍每条边、起点终点不同）	恰好 2 个奇度顶点（它们就是起点与终点）
都不存在	奇度顶点 4 个及以上

$$\boxed{{\displaystyle \text{欧拉回路的判据是}\mathbf{\text{全局}}\text{的（看度数），所以它是多项式时间可判的}}}$$

对照：哈密顿路（走遍每个顶点一次）——至今没有简单的充要条件，判定是 NP 完全问题。 "欧拉易、哈密顿难"是图论里最有名的对比。

树的三条等价定义（任一条都够）：

定义	说法
①	连通 + 无环
②	连通 + m = n − 1
③	无环 + m = n − 1

推论：树上任意两点之间有且仅有一条路径；去掉任一条边就不连通（n−1 条边都是"桥"）。K_n 的生成树个数用 Cayley 公式：

$$\boxed{{\displaystyle |T(K_n)|=n^{n-2}}}$$

二分图判定：G 是二分图 ⟺ G 中不含奇环——判定方法就是 BFS/DFS 二染色（遇到"相邻同色"就说明有奇环）。

平面图与欧拉公式（连通平面图）：

$$\boxed{{\displaystyle V-E+F=2}}$$

其中 F 是面数（含最外面的无限面）。 推论：K_5 与 K_{3,3} 都不是平面图（这两个"最小非平面图"是库拉托夫斯基定理的核心）。

示例

例 1：真值表、等价式与"NAND 单独完备"的机器验证

任务：用程序把等价式验一遍，并验证"任意二元布尔函数都能用 NAND 造出来"。

/* logic_demo.c —— 位运算枚举真值表，验证德摩根与蕴含改写（人工审查用） */
#include <stdio.h>

int main(void) {
    printf("p q | p&q p|q  !(p&q) (!p)|(!q)  p->q  !p|q\n");
    for (int p = 0; p <= 1; p++) {
        for (int q = 0; q <= 1; q++) {
            int and_pq = p && q;
            int or_pq  = p || q;
            int impl   = (!p) || q;                /* p -> q 等价于 !p | q */
            printf("%d %d |  %d   %d     %d       %d       %d     %d\n",
                   p, q, and_pq, or_pq, !and_pq, (!p) || (!q), impl, impl);
        }
    }
    printf("\n德摩根：!(p&q) 列与 (!p)|(!q) 列应逐行相同\n");
    printf("蕴含改写：p->q 列与 !p|q 列同一列（本程序里就是同一表达式）\n");
    return 0;
}

输出示意：

p q | p&q p|q  !(p&q) (!p)|(!q)  p->q  !p|q
0 0 |  0   0     1       1        1     1
0 1 |  0   1     1       1        1     1
1 0 |  0   1     1       1        0     0
1 1 |  1   1     0       0        1     1

德摩根：!(p&q) 列与 (!p)|(!q) 列应逐行相同
蕴含改写：p->q 列与 !p|q 列同一列（本程序里就是同一表达式）

用 Python 做完整枚举：等价式验证 + NAND 完备性：

import itertools, unicodedata

def w(s):
    return sum(2 if unicodedata.east_asian_width(c) in "WF" else 1 for c in s)

def pad(s, n):
    return s + " " * max(0, n - w(s))

print("=== ① 基本真值表（含异或） ===")
print("  " + pad("p", 4) + pad("q", 4) + pad("~p", 5) + pad("p&q", 5) + pad("p|q", 5)
      + pad("p->q", 7) + pad("p<->q", 7) + "p^q")
for p, q in [(0, 0), (0, 1), (1, 0), (1, 1)]:
    print("  " + pad(str(p), 4) + pad(str(q), 4) + pad(str(1 - p), 5)
          + pad(str(p & q), 5) + pad(str(p | q), 5)
          + pad(str(int((not p) or q)), 7)
          + pad(str(int(p == q)), 7) + str(p ^ q))

print()
print("=== ② 等价式逐行验证（穷举所有赋值） ===")
def eq(f, g):
    return all(f(p, q) == g(p, q) for p, q in [(0, 0), (0, 1), (1, 0), (1, 1)])

CHECKS = [
    ("德摩根（与）",   lambda p, q: not (p and q),      lambda p, q: (not p) or (not q)),
    ("德摩根（或）",   lambda p, q: not (p or q),       lambda p, q: (not p) and (not q)),
    ("蕴含改写",       lambda p, q: (not p) or q,       lambda p, q: int(not (p and not q))),
    ("逆否等价",       lambda p, q: (not p) or q,       lambda p, q: (not (not q)) or (not p)),
    ("分配律",         lambda p, q: (p and (q or p)),   lambda p, q: (p and q) or (p and p)),
    ("吸收律",         lambda p, q: p or (p and q),     lambda p, q: p),
    ("排中律",         lambda p, q: p or (not p),       lambda p, q: 1),
]
print("  " + pad("等价式", 18) + pad("左右两边是否处处相等", 22) + "结论")
for name, f, g in CHECKS:
    ok = eq(f, g)
    print("  " + pad(name, 18) + pad("是" if ok else "否", 22) + ("✔ 成立" if ok else "✘ 不成立"))

print()
print("=== ③ 主析取范式：取输出为 1 的行 ===")
def f_impl(p, q):
    return (not p) or q
ones = [(p, q) for p, q in [(0, 0), (0, 1), (1, 0), (1, 1)] if f_impl(p, q)]
terms = []
for p, q in ones:
    lit = [("p" if p else "~p"), ("q" if q else "~q")]
    terms.append("(" + " & ".join(lit) + ")")
print("  f = p -> q 的真值：", [int(f_impl(p, q)) for p, q in [(0, 0), (0, 1), (1, 0), (1, 1)]])
print("  取 1 的行（小项）：" + "、".join("m%d" % (p * 2 + q) for p, q in ones))
print("  主析取范式：f = " + " | ".join(terms))
print("  小项总数 = 2^2 = 4；本例用到 %d 个" % len(ones))

print()
print("=== ④ NAND 单独完备：先造出三个基本联结词 ===")
def NAND(p, q):
    return 0 if (p and q) else 1

NOT_n  = lambda p: NAND(p, p)
AND_n  = lambda p, q: NAND(NAND(p, q), NAND(p, q))
OR_n   = lambda p, q: NAND(NAND(p, p), NAND(q, q))
ROW = [(0, 0), (0, 1), (1, 0), (1, 1)]

print("  " + pad("构造", 24) + pad("结果（4 行）", 22) + "与目标一致？")
CASES = [
    ("~p  = p NAND p",        [NOT_n(p) for p, q in ROW],        [1 - p for p, q in ROW]),
    ("p&q = (pNq) NAND (pNq)", [AND_n(p, q) for p, q in ROW],    [p & q for p, q in ROW]),
    ("p|q = (pNp) NAND (qNq)", [OR_n(p, q) for p, q in ROW],     [p | q for p, q in ROW]),
]
for name, got, want in CASES:
    print("  " + pad(name, 24) + pad(str(got), 22) + ("✔" if got == want else "✘"))

print()
print("=== ⑤ 任意二元布尔函数都能用 NAND 网络实现（穷举 16 个） ===")
INPUTS = [(0, 0), (0, 1), (1, 0), (1, 1)]

def truth_table(fn):
    return tuple(fn(p, q) for p, q in INPUTS)

def nand_net_from_truth(tt):
    """按主析取范式构造：每个 1 行做一个与项（用 NAND 造与），最后或起来（用 NAND 造或）"""
    terms = []
    for idx, out in enumerate(tt):
        if not out:
            continue
        p = (idx >> 1) & 1
        q = idx & 1
        # 与项：先 NAND 再取反 —— 这里直接用等价表达式，验证的是“可达性”而非门数
        a = (lambda x, y: x)(p, q)
        terms.append((p, q))
    def net(p, q):
        # 逐项算“与”（用 NAND 两级），再做“或”（用 NAND 造或），整体用 NAND 表达
        vals = []
        for lp, lq in terms:
            x = p if lp else NOT_n(p)
            y = q if lq else NOT_n(q)
            vals.append(AND_n(x, y))
        acc = 0
        for v in vals:
            acc = OR_n(acc, v)
        return acc
    return net

all_ok = True
reported = 0
for idx in range(16):
    tt = tuple((idx >> (3 - i)) & 1 for i in range(4))   # 16 种真值表
    net = nand_net_from_truth(tt)
    got = truth_table(net)
    ok = (got == tt)
    all_ok = all_ok and ok
    if idx < 4 or not ok:
        print("  " + pad("函数 #%d 真值表" % idx, 24) + pad(str(tt), 22)
              + pad(str(got), 22) + ("✔" if ok else "✘"))
    reported += 1
print("  ……（其余函数略）")
print("  16 个二元布尔函数全部可由 NAND 网络实现：%s" % ("✔ 是" if all_ok else "✘ 否"))
print("  ★ 一般结论：k 元布尔函数共 2^(2^k) 个（一元 4 个、二元 16 个、三元 256 个）")

print()
print("=== ⑥ 哪些联结词集合是完备的 ===")
print("  " + pad("集合", 14) + pad("完备", 8) + "理由")
FULL = [
    ("{~, &, |}", "✔", "主析取范式只用这三个"),
    ("{~, &}",    "✔", "p|q = ~(~p & ~q)（德摩根）"),
    ("{~, |}",    "✔", "对偶，同理"),
    ("{NAND}",    "✔", "单元素完备：能造出 ~、&、|"),
    ("{NOR}",     "✔", "单元素完备：对偶"),
    ("{&, |}",    "✘", "两者都单调，造不出 ~"),
    ("{^, &}",    "✘", "全 0 输入下都输出 0，造不出常量 1"),
]
for a, b, c in FULL:
    print("  " + pad(a, 14) + pad(b, 8) + c)

预期输出：

=== ① 基本真值表（含异或） ===
  p   q   ~p   p&q  p|q  p->q   p<->q  p^q
  0   0   1    0    0    1      1      0
  0   1   1    0    1    1      0      1
  1   0   0    0    1    0      0      1
  1   1   0    1    1    1      1      0

=== ② 等价式逐行验证（穷举所有赋值） ===
  等价式            左右两边是否处处相等  结论
  德摩根（与）      是                    ✔ 成立
  德摩根（或）      是                    ✔ 成立
  蕴含改写          是                    ✔ 成立
  逆否等价          是                    ✔ 成立
  分配律            是                    ✔ 成立
  吸收律            是                    ✔ 成立
  排中律            是                    ✔ 成立

=== ③ 主析取范式：取输出为 1 的行 ===
  f = p -> q 的真值： [1, 1, 0, 1]
  取 1 的行（小项）：m0、m1、m3
  主析取范式：f = (~p & ~q) | (~p & q) | (p & q)
  小项总数 = 2^2 = 4；本例用到 3 个

=== ④ NAND 单独完备：先造出三个基本联结词 ===
  构造                    结果（4 行）          与目标一致？
  ~p  = p NAND p          [1, 1, 0, 0]          ✔
  p&q = (pNq) NAND (pNq)  [0, 0, 0, 1]          ✔
  p|q = (pNp) NAND (qNq)  [0, 1, 1, 1]          ✔

=== ⑤ 任意二元布尔函数都能用 NAND 网络实现（穷举 16 个） ===
  函数 #0 真值表          (0, 0, 0, 0)          (0, 0, 0, 0)          ✔
  函数 #1 真值表          (0, 0, 0, 1)          (0, 0, 0, 1)          ✔
  函数 #2 真值表          (0, 0, 1, 0)          (0, 0, 1, 0)          ✔
  函数 #3 真值表          (0, 0, 1, 1)          (0, 0, 1, 1)          ✔
  ……（其余函数略）
  16 个二元布尔函数全部可由 NAND 网络实现：✔ 是
  ★ 一般结论：k 元布尔函数共 2^(2^k) 个（一元 4 个、二元 16 个、三元 256 个）

=== ⑥ 哪些联结词集合是完备的 ===
  集合          完备    理由
  {~, &, |}     ✔       主析取范式只用这三个
  {~, &}        ✔       p|q = ~(~p & ~q)（德摩根）
  {~, |}        ✔       对偶，同理
  {NAND}        ✔       单元素完备：能造出 ~、&、|
  {NOR}         ✔       单元素完备：对偶
  {&, |}        ✘       两者都单调，造不出 ~
  {^, &}        ✘       全 0 输入下都输出 0，造不出常量 1

三条结论：

结论	说明
等价式可以用"穷举所有赋值"来证明	n 个变量只有 2^n 种赋值——小规模时这是最可靠的验证法（也正是真值表法的数学依据）
NAND 单独完备	¬、∧、∨ 都能用 NAND 造出来——所以"只有 NAND 门"也能造出任何逻辑（circuit/05-gates.md 的工艺优势 + 这里的数学保证 = 实际芯片大量用 NAND 的原因）
{∧, ∨} 不完备	因为它们"单调"：输入由 0 变 1，输出绝不会由 1 变 0——而 ¬ 恰恰是"反向"的

例 2：集合计数与容斥原理

任务：用容斥算一道"调查问卷"的经典题。

import unicodedata

def w(s):
    return sum(2 if unicodedata.east_asian_width(c) in "WF" else 1 for c in s)

def pad(s, n):
    return s + " " * max(0, n - w(s))

print("=== ① 子集与幂集 ===")
for n in range(0, 6):
    print("  集合大小 n = %d → 子集个数 2^%d = %d" % (n, n, 2 ** n))
print("  ★ 逐个元素“选或不选”，每个元素 2 种选择 → 2^n")
print()
print("  Σ C(n,k) 也应等于 2^n：")
from math import comb
for n in (3, 4):
    parts = ["C(%d,%d)=%d" % (n, k, comb(n, k)) for k in range(n + 1)]
    print("    n=%d: %s → 合计 %d" % (n, " + ".join(parts), sum(comb(n, k) for k in range(n + 1))))

print()
print("=== ② 笛卡尔积 ===")
A, B = 3, 4
print("  |A| = %d, |B| = %d → |A × B| = %d × %d = %d 个有序对" % (A, B, A, B, A * B))
print("  注意 A × B 与 B × A 的“元素个数”相同，但元素本身不同（有序对）")

print()
print("=== ③ 容斥原理：两集合调查题 ===")
N       = 100      # 总人数
LIKE_A  = 60       # 喜欢 A
LIKE_B  = 50       # 喜欢 B
BOTH    = 30       # 两个都喜欢
print("  总人数 %d；喜欢 A 的 %d 人，喜欢 B 的 %d 人，两个都喜欢的 %d 人" % (N, LIKE_A, LIKE_B, BOTH))
print("  |A ∪ B| = |A| + |B| - |A ∩ B| = %d + %d - %d = %d" % (LIKE_A, LIKE_B, BOTH,
                                                              LIKE_A + LIKE_B - BOTH))
neither = N - (LIKE_A + LIKE_B - BOTH)
print("  一个都不喜欢 = %d - %d = %d 人" % (N, LIKE_A + LIKE_B - BOTH, neither))
print("  ★ 不减交集就会把“两个都喜欢”的人算两遍，结果是 %d（> 实际并集）" % (LIKE_A + LIKE_B))

print()
print("=== ④ 三集合容斥 ===")
A3, B3, C3 = 40, 35, 30
AB, AC, BC = 15, 12, 10
ABC = 5
print("  参数：|A|=%d |B|=%d |C|=%d；两两交集 %d %d %d；三交集 %d"
      % (A3, B3, C3, AB, AC, BC, ABC))
union = A3 + B3 + C3 - (AB + AC + BC) + ABC
print("  |A∪B∪C| = (%d+%d+%d) - (%d+%d+%d) + %d" % (A3, B3, C3, AB, AC, BC, ABC))
print("           = %d - %d + %d = %d" % (A3 + B3 + C3, AB + AC + BC, ABC, union))
print("  ★ 口诀：加单块、减双交、加三交 —— 符号交替，奇数个集合取正")

print()
print("=== ⑤ 用“恰好属于 k 个集合”的口径再算一遍 ===")
exactly3 = ABC
exactly2 = (AB - ABC) + (AC - ABC) + (BC - ABC)
exactly1 = (A3 - AB - AC + ABC) + (B3 - AB - BC + ABC) + (C3 - AC - BC + ABC)
print("  恰好 3 个：%d" % exactly3)
print("  恰好 2 个：(%d-%d)+(%d-%d)+(%d-%d) = %d" % (AB, ABC, AC, ABC, BC, ABC, exactly2))
print("  恰好 1 个：%d" % exactly1)
print("  校验：1×%d + 2×%d + 3×%d = %d（应等于 |A|+|B|+|C| = %d）"
      % (exactly1, exactly2, exactly3,
         exactly1 + 2 * exactly2 + 3 * exactly3, A3 + B3 + C3))
print("  ★ “恰好 k 个”要把更高阶的交集修正回来，不能直接用两两交集")

预期输出：

=== ① 子集与幂集 ===
  集合大小 n = 0 → 子集个数 2^0 = 1
  集合大小 n = 1 → 子集个数 2^1 = 2
  集合大小 n = 2 → 子集个数 2^2 = 4
  集合大小 n = 3 → 子集个数 2^3 = 8
  集合大小 n = 4 → 子集个数 2^4 = 16
  集合大小 n = 5 → 子集个数 2^5 = 32
  ★ 逐个元素“选或不选”，每个元素 2 种选择 → 2^n

  Σ C(n,k) 也应等于 2^n：
    n=3: C(3,0)=1 + C(3,1)=3 + C(3,2)=3 + C(3,3)=1 → 合计 8
    n=4: C(4,0)=1 + C(4,1)=4 + C(4,2)=6 + C(4,3)=4 + C(4,4)=1 → 合计 16

=== ② 笛卡尔积 ===
  |A| = 3, |B| = 4 → |A × B| = 3 × 4 = 12 个有序对
  注意 A × B 与 B × A 的“元素个数”相同，但元素本身不同（有序对）

=== ③ 容斥原理：两集合调查题 ===
  总人数 100；喜欢 A 的 60 人，喜欢 B 的 50 人，两个都喜欢的 30 人
  |A ∪ B| = |A| + |B| - |A ∩ B| = 60 + 50 - 30 = 80
  一个都不喜欢 = 100 - 80 = 20 人
  ★ 不减交集就会把“两个都喜欢”的人算两遍，结果是 110（> 实际并集）

=== ④ 三集合容斥 ===
  参数：|A|=40 |B|=35 |C|=30；两两交集 15 12 10；三交集 5
  |A∪B∪C| = (40+35+30) - (15+12+10) + 5
           = 105 - 37 + 5 = 73
  ★ 口诀：加单块、减双交、加三交 —— 符号交替，奇数个集合取正

=== ⑤ 用“恰好属于 k 个集合”的口径再算一遍 ===
  恰好 3 个：5
  恰好 2 个：(15-5)+(12-5)+(10-5) = 22
  恰好 1 个：46
  校验：1×46 + 2×22 + 3×5 = 105（应等于 |A|+|B|+|C| = 105）
  ★ “恰好 k 个”要把更高阶的交集修正回来，不能直接用两两交集

三条结论：

结论	说明
子集是 2^n 个	因为每个元素独立地"选或不选"——这与"ΣC(n,k) = 2^n"是同一件事的两种数法
容斥的符号是交替的	加单块、减双交、加三交——本质是"补回被减多的、去掉被加多的"
"恰好 k 个"≠"交集"	求"恰好"必须用"更高阶交集"修正——这是容斥题最常见的失分点

例 3：关系、等价类与传递闭包

任务：枚举 n = 3 时的关系，验证"等价关系个数 = Bell 数 = 5"，并列出 5 个划分；再算传递闭包。

import itertools, unicodedata
from math import comb

def w(s):
    return sum(2 if unicodedata.east_asian_width(c) in "WF" else 1 for c in s)

def pad(s, n):
    return s + " " * max(0, n - w(s))

N = 3
ELEMS = list(range(1, N + 1))
PAIRS = [(a, b) for a in ELEMS for b in ELEMS]
print("=== ① 关系有多少个 ===")
print("  n = %d，有序对 |A×A| = %d^2 = %d 个" % (N, N, len(PAIRS)))
print("  每个有序对“在或不在”关系里 → 关系总数 = 2^%d = %d" % (len(PAIRS), 2 ** len(PAIRS)))
print("  ★ 这就是 2^(n^2)：n=2 时 16 个，n=3 时 512 个，n=4 时 65536 个")

def is_reflexive(R):
    return all((x, x) in R for x in ELEMS)

def is_symmetric(R):
    return all((b, a) in R for a, b in R)

def is_transitive(R):
    return all((a, c) in R for a, b in R for x, c in R if b == x)

print()
print("=== ② 枚举全部 512 个关系，筛出等价关系 ===")
equiv, partial = [], []
for mask in range(1 << len(PAIRS)):
    R = frozenset(PAIRS[i] for i in range(len(PAIRS)) if (mask >> i) & 1)
    if is_reflexive(R) and is_symmetric(R) and is_transitive(R):
        equiv.append(R)
    is_antisym = all((b, a) not in R for a, b in R if a != b)
    if is_reflexive(R) and is_antisym and is_transitive(R):
        partial.append(R)
print("  等价关系（自反+对称+传递）个数 = %d" % len(equiv))
print("  ★ 这就是 Bell 数 B(3) = 5（B(1..5) = 1, 2, 5, 15, 52）")
print()
print("  五个划分（每个等价关系对应一个划分）：")
for i, R in enumerate(equiv, 1):
    # 由等价关系还原划分
    blocks, seen = [], set()
    for x in ELEMS:
        if x in seen:
            continue
        block = sorted(y for y in ELEMS if (x, y) in R)
        seen.update(block)
        blocks.append(block)
    print("    %d) %s" % (i, " | ".join("{" + ",".join(map(str, b)) + "}" for b in blocks)))
print()
print("  偏序关系（自反+反对称+传递）个数 = %d" % len(partial))
print("  ★ 已知结论：n=1,2,3 分别为 1, 3, 19")

print()
print("=== ③ 传递闭包：Warshall 算法 ===")
# 一个有向图的邻接矩阵（1 表示有边）
M = [
    [0, 1, 0, 0],
    [0, 0, 1, 0],
    [0, 0, 0, 1],
    [1, 0, 0, 0],
]
def show(mat, label):
    print("  " + label)
    for row in mat:
        print("      " + " ".join(str(x) for x in row))

show(M, "原邻接矩阵（4 个点围成一圈 1→2→3→4→1）：")
W = [row[:] for row in M]
n = len(W)
for k in range(n):
    for i in range(n):
        for j in range(n):
            if W[i][k] and W[k][j]:
                W[i][j] = 1
show(W, "传递闭包（每对点都互相可达）：")
ones = sum(sum(row) for row in W)
print("  闭包中 1 的个数 = %d（n^2 = %d，全部可达）" % (ones, n * n))
print("  运算次数 = n^3 = %d 次（三重循环的代价）" % (n ** 3))
print("  ★ ds 里 Floyd 最短路与它同一骨架：把“或/与”换成“min/+”")

print()
print("=== ④ 关系的性质：三个易错案例 ===")
CASES = [
    ("等于 = （1=1,2=2,3=3）", [(1, 1), (2, 2), (3, 3)],
     "既对称又反对称；自反、传递"),
    ("小于 <", [(1, 2), (1, 3), (2, 3)],
     "反自反、反对称、传递；不对称"),
    ("整除（正数范围内）", [(1, 1), (1, 2), (1, 3), (2, 2), (3, 3)],
     "自反、反对称、传递 → 偏序"),
]
print("  " + pad("关系", 24) + pad("自反", 6) + pad("对称", 6) + pad("反对称", 8) + "传递")
for name, R, _ in CASES:
    R = set(R)
    print("  " + pad(name, 24)
          + pad("是" if is_reflexive(R) else "否", 6)
          + pad("是" if is_symmetric(R) else "否", 6)
          + pad("是" if all((b, a) not in R for a, b in R if a != b) else "否", 8)
          + ("是" if is_transitive(R) else "否"))

预期输出：

=== ① 关系有多少个 ===
  n = 3，有序对 |A×A| = 3^2 = 9 个
  每个有序对“在或不在”关系里 → 关系总数 = 2^9 = 512
  ★ 这就是 2^(n^2)：n=2 时 16 个，n=3 时 512 个，n=4 时 65536 个

=== ② 枚举全部 512 个关系，筛出等价关系 ===
  等价关系（自反+对称+传递）个数 = 5
  ★ 这就是 Bell 数 B(3) = 5（B(1..5) = 1, 2, 5, 15, 52）

  五个划分（每个等价关系对应一个划分）：
    1) {1} | {2} | {3}
    2) {1,2} | {3}
    3) {1,3} | {2}
    4) {1} | {2,3}
    5) {1,2,3}

  偏序关系（自反+反对称+传递）个数 = 19
  ★ 已知结论：n=1,2,3 分别为 1, 3, 19

=== ③ 传递闭包：Warshall 算法 ===
  原邻接矩阵（4 个点围成一圈 1→2→3→4→1）：
      0 1 0 0
      0 0 1 0
      0 0 0 1
      1 0 0 0
  传递闭包（每对点都互相可达）：
      1 1 1 1
      1 1 1 1
      1 1 1 1
      1 1 1 1
  闭包中 1 的个数 = 16（n^2 = 16，全部可达）
  运算次数 = n^3 = 64 次（三重循环的代价）
  ★ ds 里 Floyd 最短路与它同一骨架：把“或/与”换成“min/+”

=== ④ 关系的性质：三个易错案例 ===
  关系                    自反  对称  反对称  传递
  等于 = （1=1,2=2,3=3）  是    是    是      是
  小于 <                  否    否    是      是
  整除（正数范围内）      是    否    是      是

三条结论：

结论	说明
n 个元素上的关系共 2^{n²} 个	n=3 时 512 个，其中等价关系只有 5 个（Bell 数）
等价关系 ↔ 划分一一对应	"分类"这件事的数学形式——soft 里数据库的"关系"、ds 里的"集合划分"都源于此
传递闭包是 n³ 的三重循环	Warshall 与 Floyd 同骨架——"把布尔运算换成 min/+ 就是最短路"

例 4：图论——度数、欧拉路、树与二分图

任务：验证握手定理、判定欧拉路、算生成树个数、判定二分图。

import unicodedata
from collections import deque
from math import comb

def w(s):
    return sum(2 if unicodedata.east_asian_width(c) in "WF" else 1 for c in s)

def pad(s, n):
    return s + " " * max(0, n - w(s))

print("=== ① 握手定理：Σdeg = 2m ===")
GRAPHS = [
    ("K4（完全图，四个奇度点）", {1: [2, 3, 4], 2: [1, 3, 4], 3: [1, 2, 4], 4: [1, 2, 3]}),
    ("路径 P3（两个奇度点）",     {1: [2], 2: [1, 3], 3: [2]}),
    ("三角形 K3（零个奇度点）",   {1: [2, 3], 2: [1, 3], 3: [1, 2]}),
    ("4 点围一圈 C4",             {1: [2, 4], 2: [1, 3], 3: [2, 4], 4: [1, 3]}),
]
for name, adj in GRAPHS:
    deg = {v: len(nb) for v, nb in adj.items()}
    m = sum(deg.values()) // 2
    odd = [v for v, d in deg.items() if d % 2 == 1]
    print("  " + name)
    print("    度序列 = %s" % sorted(deg.values(), reverse=True))
    print("    Σdeg = %d，边数 m = %d（%d ÷ 2）" % (sum(deg.values()), m, sum(deg.values())))
    print("    奇度顶点 %d 个 → %s" % (len(odd),
          "存在欧拉回路" if len(odd) == 0 else
          ("存在欧拉路" if len(odd) == 2 else "两者都不存在")))

print()
print("=== ② 欧拉路判据表 ===")
print("  " + pad("奇度顶点个数", 14) + pad("欧拉回路", 10) + "欧拉路")
for k in (0, 2, 4, 6):
    print("  " + pad(str(k), 14) + pad("有" if k == 0 else "无", 10)
          + ("有（两个奇度点即起点终点）" if k == 2 else "无"))
print("  ★ 判据只看度数 → 多项式时间可判；哈密顿路没有这样的判据（NP 完全）")

print()
print("=== ③ 完全图与生成树 ===")
for n in range(2, 7):
    print("  K%d：顶点 %d 个，每个顶点度 %d，边数 C(%d,2) = %d，生成树 %d^(%d-2) = %d"
          % (n, n, n - 1, n, comb(n, 2), n, n, n ** (n - 2)))
print("  ★ Cayley 公式 |T(K_n)| = n^(n-2)；K3 有 3 棵生成树，K4 有 16 棵")

print()
print("=== ④ 树的三条等价定义（任一条都够） ===")
TREE_EQUIV = [
    ("连通 + 无环", "定义"),
    ("连通 + m = n - 1", "等价"),
    ("无环 + m = n - 1", "等价"),
]
print("  " + pad("条件", 20) + "说明")
for a, b in TREE_EQUIV:
    print("  " + pad(a, 20) + b)
print("  推论：树上任意两点间有且仅有一条路径；每条边都是桥")
print("  校验：n = 5 的树边数 = 5 - 1 = 4（比 K5 的 10 条边少 6 条）")

print()
print("=== ⑤ 二分图判定（BFS 二染色） ===")
def is_bipartite(adj, n):
    color = {}
    for s in range(1, n + 1):
        if s in color:
            continue
        color[s] = 0
        q = deque([s])
        while q:
            u = q.popleft()
            for v in adj.get(u, []):
                if v not in color:
                    color[v] = 1 - color[u]
                    q.append(v)
                elif color[v] == color[u]:
                    return False, color, (u, v)
    return True, color, None

TESTS = [
    ("C4（偶环）", {1: [2, 4], 2: [1, 3], 3: [2, 4], 4: [1, 3]}, 4),
    ("C5（奇环）", {1: [2, 5], 2: [1, 3], 3: [2, 4], 4: [3, 5], 5: [4, 1]}, 5),
    ("K3,3", {1: [4, 5, 6], 2: [4, 5, 6], 3: [4, 5, 6],
              4: [1, 2, 3], 5: [1, 2, 3], 6: [1, 2, 3]}, 6),
]
print("  " + pad("图", 12) + pad("是二分图", 10) + "说明")
for name, adj, n in TESTS:
    ok, color, conf = is_bipartite(adj, n)
    note = "染色成功" if ok else "在边 (%d,%d) 上出现同色冲突 → 含奇环" % conf
    print("  " + pad(name, 12) + pad("是" if ok else "否", 10) + note)
print("  ★ 二分图 ⟺ 无奇环；判定就是二染色")

print()
print("=== ⑥ 平面图欧拉公式 V - E + F = 2 ===")
PLANAR = [
    ("四面体图 K4（平面）",  4, 6,  "3V-6 = 6 ≥ E = 6 ✔"),
    ("立方体图（平面）",     8, 12, "3V-6 = 18 ≥ E = 12 ✔"),
    ("K3,3（非平面）",       6, 9,  "2V-4 = 8 < E = 9 ✘"),
    ("K5（非平面）",         5, 10, "3V-6 = 9 < E = 10 ✘"),
]
print("  " + pad("图", 22) + pad("V", 5) + pad("E", 5) + pad("V-E+2", 8) + "不等式判据")
for name, v, e, judge in PLANAR:
    print("  " + pad(name, 22) + pad(str(v), 5) + pad(str(e), 5) + pad(str(2 - v + e), 8) + judge)
print("  ★ 连通平面图满足 V - E + F = 2（F 含最外无限面）")
print("  ★ 判非平面的实用不等式：简单平面图 E ≤ 3V-6；二分平面图更强，E ≤ 2V-4")
print("    K5：E=10 > 3×5-6=9 → 非平面；K3,3：E=9 > 2×6-4=8 → 非平面")

预期输出：

=== ① 握手定理：Σdeg = 2m ===
  K4（完全图，四个奇度点）
    度序列 = [3, 3, 3, 3]
    Σdeg = 12，边数 m = 6（12 ÷ 2）
    奇度顶点 4 个 → 两者都不存在
  路径 P3（两个奇度点）
    度序列 = [2, 1, 1]
    Σdeg = 4，边数 m = 2（4 ÷ 2）
    奇度顶点 2 个 → 存在欧拉路
  三角形 K3（零个奇度点）
    度序列 = [2, 2, 2]
    Σdeg = 6，边数 m = 3（6 ÷ 2）
    奇度顶点 0 个 → 存在欧拉回路
  4 点围一圈 C4
    度序列 = [2, 2, 2, 2]
    Σdeg = 8，边数 m = 4（8 ÷ 2）
    奇度顶点 0 个 → 存在欧拉回路

=== ② 欧拉路判据表 ===
  奇度顶点个数  欧拉回路  欧拉路
  0             有        无
  2             无        有（两个奇度点即起点终点）
  4             无        无
  6             无        无
  ★ 判据只看度数 → 多项式时间可判；哈密顿路没有这样的判据（NP 完全）

=== ③ 完全图与生成树 ===
  K2：顶点 2 个，每个顶点度 1，边数 C(2,2) = 1，生成树 2^(2-2) = 1
  K3：顶点 3 个，每个顶点度 2，边数 C(3,2) = 3，生成树 3^(3-2) = 3
  K4：顶点 4 个，每个顶点度 3，边数 C(4,2) = 6，生成树 4^(4-2) = 16
  K5：顶点 5 个，每个顶点度 4，边数 C(5,2) = 10，生成树 5^(5-2) = 125
  K6：顶点 6 个，每个顶点度 5，边数 C(6,2) = 15，生成树 6^(6-2) = 1296
  ★ Cayley 公式 |T(K_n)| = n^(n-2)；K3 有 3 棵生成树，K4 有 16 棵

=== ④ 树的三条等价定义（任一条都够） ===
  条件                说明
  连通 + 无环         定义
  连通 + m = n - 1    等价
  无环 + m = n - 1    等价
  推论：树上任意两点间有且仅有一条路径；每条边都是桥
  校验：n = 5 的树边数 = 5 - 1 = 4（比 K5 的 10 条边少 6 条）

=== ⑤ 二分图判定（BFS 二染色） ===
  图          是二分图  说明
  C4（偶环）  是        染色成功
  C5（奇环）  否        在边 (3,4) 上出现同色冲突 → 含奇环
  K3,3        是        染色成功
  ★ 二分图 ⟺ 无奇环；判定就是二染色

=== ⑥ 平面图欧拉公式 V - E + F = 2 ===
  图                    V    E    V-E+2   不等式判据
  四面体图 K4（平面）   4    6    4       3V-6 = 6 ≥ E = 6 ✔
  立方体图（平面）      8    12   6       3V-6 = 18 ≥ E = 12 ✔
  K3,3（非平面）        6    9    5       2V-4 = 8 < E = 9 ✘
  K5（非平面）          5    10   7       3V-6 = 9 < E = 10 ✘
  ★ 连通平面图满足 V - E + F = 2（F 含最外无限面）
  ★ 判非平面的实用不等式：简单平面图 E ≤ 3V-6；二分平面图更强，E ≤ 2V-4
    K5：E=10 > 3×5-6=9 → 非平面；K3,3：E=9 > 2×6-4=8 → 非平面

三条结论：

结论	说明
握手定理是"算边数"的万能式	Σdeg = 2m——顺带推出"奇度顶点个数必为偶数"，这是欧拉路判据的基础
欧拉易、哈密顿难	欧拉路只看度数（多项式可判）；哈密顿路是 NP 完全问题
二分图 ⟺ 无奇环	判定就是二染色——ds 里"判断能否二部划分"、os 里"死锁检测"都用到这类结构

考点

考点

1. 五个联结词的真值表（必须能默写）

• ¬：取反；
• ∧：两个都为 1 才是 1；
• ∨：至少一个为 1（可兼或）；
• →：只有 1→0 为假（0→1、0→0 都为真——这是最反直觉的一处）；
• ↔：同真同假为真；
• ⊕：不同为 1。

2. 三条必背变形

• p → q ≡ ¬p ∨ q（蕴含改"或"）；
• ¬(p∧q) ≡ ¬p∨¬q、¬(p∨q) ≡ ¬p∧¬q（德摩根）；
• 逆否等价：p→q ≡ ¬q→¬p；但逆命题 q→p 与否命题 ¬p→¬q 都不等价。

3. 完备集（"为什么 NAND 够用"）

集合	完备	关键理由
{¬, ∧, ∨}	✔	主析取范式
{¬, ∧}	✔	p∨q ≡ ¬(¬p∧¬q)
{NAND}	✔（单元素）	¬p=p↑p、p∧q=(p↑q)↑(p↑q)、p∨q=(p↑p)↑(q↑q)
{NOR}	✔（单元素）	对偶
{∧, ∨}	✘	单调，造不出 ¬
{⊕, ∧}	✘	造不出常量 1

• k 元布尔函数共 2^{2^k} 个：一元 4、二元 16、三元 256；
• circuit/11-combinational.md 的"SOP→NAND-NAND、POS→NOR-NOR"就建立在这里。

4. 范式与小项/大项

• DNF = 积之和（SOP）；CNF = 和之积（POS）；
• 主析取范式 = 取输出为 1 的那些行，每行写一个小项；
• n 个变量有 2^n 个小项、2^n 个大项；
• m_i ≡ ¬M_i（第 i 号小项与第 i 号大项互为否定）。

5. 谓词逻辑的两条规矩

• 量词否定：¬∀x P ≡ ∃x ¬P、¬∃x P ≡ ∀x ¬P（"不是全对" = "有反例"）；
• 量词顺序不可交换：∀x∃y ≠ ∃y∀x（"每人都有母亲" ≠ "有人是所有人的母亲"）。

6. 集合的三个计数公式

• 子集个数 2^n（逐元素"选或不选"）；ΣC(n,k) = 2^n；
• |A×B| = |A|·|B|；
• 容斥：|A∪B| = |A|+|B|−|A∩B|；三集合"加单块、减双交、加三交"。

7. 关系的性质与两类特殊关系

• 五种性质：自反、反自反、对称、反对称、传递；
• 易错："对称"与"反对称"不互斥（"等于"两者都满足）；"反对称"与"反自反"是两件事；
• 等价关系 = 自反+对称+传递 → 划分；n 元素的划分个数 = Bell 数 1,2,5,15,52；
• 偏序 = 自反+反对称+传递 → 哈斯图；n=3 的偏序有 19 个；
• n 元素上的关系共 2^{n²} 个。

8. 图论的六个结论（本课最常考）

结论	形式
握手定理	Σdeg(v) = 2m
奇度点成对	奇度顶点个数为偶数
完全图	m = C(n,2)，每点度 n−1
欧拉回路 / 欧拉路	全偶度 / 恰 2 个奇度点
树	连通无环 ⟺ 连通且 m=n−1 ⟺ 无环且 m=n−1；生成树数 n^{n−2}
二分图	⟺ 无奇环；平面图 V−E+F=2

9. 高频易错点

• p→q 在 p 为假时恒为真——别用日常语感判断；
• "必要条件/充分条件"的方向：p→q 表示 p 是 q 的充分条件、q 是 p 的必要条件（这一句在数学与算法分析里天天用）；
• {∧, ∨} 不完备的原因不是"数量不够"，而是"单调"；
• ⊕ 不是"或"（"或"可兼、⊕ 不可兼）；
• 欧拉路看边、哈密顿看顶点（别把两条判据搞混：欧拉有简单判据，哈密顿没有）；
• 奇度顶点个数为偶数 ≠ 存在欧拉路（恰好 0 或 2 个才行，4 个不行）；
• 关系复合的顺序：R∘S 表示"先 S 后 R"（不同教材约定不同，看定义）；
• Warshall 的三重循环顺序：k 必须在最外层——写成 i,j,k 的次序就错了（Floyd 同理）。

小结

• 离散数学是"可数对象"的数学，布尔代数 → 数字电路 → 组成原理是本站唯一的硬前置链。
• 命题逻辑：五个联结词 + 真值表；p→q ≡ ¬p∨q；0→x 恒真是最反直觉的一处。
• 等价变形：德摩根、分配、吸收、排中；对偶原理让"证明一条白送一条"。
• 范式：DNF（SOP）/ CNF（POS）；主析取范式 = 取真值表里为 1 的行；m_i ≡ ¬M_i。
• 完备集：{¬,∧,∨}、{¬,∧}、{NAND}、{NOR} 完备；{∧,∨} 不完备（单调）；k 元布尔函数共 2^{2^k} 个。
• 谓词逻辑：量词否定要换量词；量词顺序不可交换。
• 集合：子集 2^n、|A×B| = |A||B|、容斥"加单块减双交加三交"。
• 关系：五种性质；等价关系 ↔ 划分（Bell 数）；偏序 ↔ 哈斯图；传递闭包 = Warshall 三重循环。
• 图论：握手定理 Σdeg = 2m；欧拉路看度数、哈密顿没有简单判据；树的三条等价定义与 n^{n−2}；二分图 ⟺ 无奇环；平面图 V−E+F=2。
• 一句话记住它的地位："电路之所以能被化简、程序之所以能被分析，都因为这套符号早已把规则定好了。"

回到主线：这是"补前置"的一篇，也是一次向上回链。

它直接回答了 L1 的三个悬着的问题： ① circuit/10-boolean.md 里"从真值表写 SOP"凭什么成立？——因为那是主析取范式。② circuit/11-combinational.md 里"为什么只用 NAND 也能造出全部逻辑"？——因为 {NAND} 是完备集。③ 卡诺图化简、对偶关系、低有效输出配 NAND —— 全都是等价式与对偶原理的应用。

同时它也是 ds（图算法、集合与映射）与 soft（关系模型、编译中的语法分析）的共同地基——所以 math 这门课不做独立体系，只按"主线用到什么就补什么"来写。

下一篇：高等数学：极限、微分、积分