# COMP2022 — 计算模型：语言、机器与逻辑 > Leon | Original study notes [English](COMP2022.md) · [中文](COMP2022.zh.md) ![Leon — 学习路线图](../assets/maps/comp2022.zh.svg) ## 继续深入：完整案例 先读对应章节，再跟着故事预测输出、运行完整程序、核对解释。每个案例都在原有概念上增加一个实际问题。 1. [找到区分两个 DFA 的最短单词](#lab-regular-decision-problems-shortest-dfa-counterexample) — 把等价性转成可达性，并恢复具体反例。 2. [数清语法树，不要默认只有一种解析](#lab-parse-trees-ambiguity-count-expression-trees) — 通过递推式和可见语法树解释歧义。 3. [在有限模型中寻找见证与反例](#lab-predicate-logic-finite-witness-search) — 用见证把量词顺序变成具体问题。 连贯理解正则语言、文法、图灵机与形式逻辑。原创故事和逐步例题把定义变成构造模型、检验主张与解释不可能性的工具。 独立编写的有限自动机、文法、可计算性与逻辑指南。每个主题提供原创完整例题、定义、推理检查与教学补充。 ## 把知识连接起来 ### 描述有限状态行为 - [字符串、语言与规格](#languages-specifications) - [正则表达式：语言的代数](#regular-expressions) - [DFA 状态：概括已经读过的内容](#dfa-state-invariants) - [非确定性与 ε 转移](#nfa-epsilon) - [把 NFA 转为 DFA](#subset-construction) - [从自动机回到表达式](#state-elimination) - [匹配策略与重复工作](#regex-execution) - [正则语言的封闭性与判定过程](#regular-decision-problems) - [证明有限记忆不够](#finite-memory-limits) ### 描述并解析递归结构 - [文法与递归结构](#context-free-grammars) - [解析树与歧义](#parse-trees-ambiguity) - [不改变语言的 Chomsky 范式](#chomsky-normal-form) - [CYK：从短片段构造长解析](#cyk-parsing) ### 理解通用计算及其边界 - [图灵机与配置](#turing-machine-configurations) - [用标记与不变量设计机器](#turing-machine-design) - [模拟、通用性与 Church–Turing 论题](#universality-simulation) - [识别器与判定器](#recognizers-deciders) - [为什么通用停机测试不可能](#undecidability-diagonalization) - [交错模拟与补语言](#recognizable-closure) ### 表达并检验逻辑主张 - [命题语法与真值](#propositional-semantics) - [逻辑等价与安全改写](#logical-equivalence) - [命题逻辑的范式](#propositional-normal-forms) - [逻辑后承与反模型](#logical-consequence) - [谓词、量词与作用域](#predicate-logic) ## 字符串、语言与规格 ### 01 / 从一个故事开始 想象门卫检查标签。选择扫描器前，先规定允许哪些标签，例如由 A、B 组成且以 B 结尾的序列。规格独立于检查设备描述规则。设备可以使用指示灯、程序或查表；不同实现仍能作出相同判断。类比也有限制：真实扫描器会机械故障，数学机器却严格遵守规则。我们研究规则是否描述了预期标签集合。 ### 02 / 理解原理 字母表是有限符号集合，字符串是由这些符号组成的有限序列。空串 ε 长度为零。语言是所有有限串的任意子集，不一定是人类语言，也不一定能用实用方法描述。判定问题可表示成语言成员资格：答案为是的输入属于语言。 规格说明输入范围和要求答案，算法提供步骤。实现只有对每个允许输入都符合规格才正确。一般计算还需说明是否要求终止：只要结束就答对，比总能给出答案弱。 ### 03 / 逐项读懂公式 ```text Σ* = ⋃ₖ≥₀ Σᵏ; L ⊆ Σ*; |ε| = 0 ``` Σ 是字母表，Σᵏ 是长度 k 的所有串。星号包含全部有限长度，包括零，所以 ε 总属于 Σ*。L 是其中选出的语言。竖线在此表示串长，不是集合大小。这些定义说明允许输入及肯定答案，并不保证每种 L 都有可判定成员资格的机器。 ### 04 / 先看一个完整例子 设 Σ={A,B}，L 为以 B 结尾的串。B、AB、BAB 属于它，ε、A、BAA 不属于。正确过程先拒绝空输入，再检查最后符号是否为 B。若表示方式允许，可以直接查看末字符；也可以从左到右扫描并记住最近字符，两者符合相同规格。只检查有没有 B 的过程在 BAA 上失败，这是具体反例。 ### 先认识这些词 - **字母表:** 允许符号构成的有限集合。 - **字符串:** 有限的有序符号序列。 - **规格:** 说明允许输入与所需输出的规则。 ### 一步步想清楚 **为什么将规则与扫描器分开？** 不同过程可符合相同规则，需要用统一目标判断。 **{x,y} 上有几个长度二的串？** 两个位置各两种选择，2×2=4：xx、xy、yx、yy。 **{ε} 是空集合吗？** 不是。它包含一个长度零的串。 ### 统计有限部分 在 Σ={x,y} 上列出长度不超过二且以 x 结尾的全部串。候选输入包括 ε，但必须严格检查结尾规则。 **先选择方法** 按长度划分，避免漏计与重复。 1. 长度零只有 ε，没有末尾 x，因此拒绝。 2. 长度一有 x、y，只有 x 以 x 结尾。 3. 长度二有 xx、xy、yx、yy，检查第二位保留 xx、yx。 **解释最终答案** 所选有限部分为 {x,xx,yx}，共三个串。 **检验推理** 正长度 n 时，固定末尾 x 后有 2^(n−1) 种。n=1、2 得 1+2=3。 ### 修复错误检查 规则为“二进制输入恰含两个 1”。候选测试在长度为二时接受。检查 10、101，并给出会停机的正确过程。 **先选择方法** 将候选条件与真实计数比较，再替换条件。 1. 10 长度二，候选接受；但只有一个 1，要求答案为否。 2. 101 长度三，候选拒绝；但有两个 1，要求答案为是。 3. 扫描有限输入，遇 1 加一。读完后仅在计数等于二时接受。 **解释最终答案** 仅看长度既会误接受也会误拒绝。计数过程在读完输入后停机。 **检验推理** 空串计数零被拒绝，11 计数二被接受。 ### Leon 的进一步思考 **先检查输入合法性** 字母表为 {x,y} 时，xz 不在输入范围。实现应说明报输入错误还是答否，不能悄悄改变数学语言。 **反例有决定作用** 一次不符就足以推翻对所有输入正确的主张。一千次成功测试也不能覆盖无限输入。 **注意这个边界:** 不要混淆 ε 与 ∅。ε 是一个串，∅ 没有任何串；{ε} 有一个成员。
检查自己的理解 所有二进制串的集合是一个字符串吗？ 不是。它是无限语言 {0,1}*。每个成员都有限，但成员数量无限。
## 正则表达式：语言的代数 ### 01 / 从一个故事开始 玩具制作有三种指令：选一种设计、将两块并排、把一块重复有限次。正则表达式也像字符串配方。选择给出替代项，连接拼起片段，重复允许数量变化。配方描述所有成品，不规定制作先后。重复可以为零次，容易遗漏。数学配方也不包含某些程序库的强大扩展，因此讨论正则语言时须明确基本运算。 ### 02 / 理解原理 正则表达式从符号、空语言、空串、并、连接和 Kleene 星递归构造。语义给每个表达式对应语言。并允许来自任一边的串；连接要求串可拆成左语言的片段与右语言的片段；星允许零个或多个成员连接。 括号决定分组。通常星优先于连接，连接优先于并。本课匹配指整个字符串的成员资格；子串搜索是另一任务，除非表达式允许任意前后文。表达式是规格，不是对回溯实现的承诺。 ### 03 / 逐项读懂公式 ```text L(R|S) = L(R) ∪ L(S) L(RS) = {uv : u ∈ L(R), v ∈ L(S)} L(R*) = ⋃ₖ≥₀ L(R)ᵏ ``` R、S 是表达式，L(R) 是其语言。表达式内竖线表示选择。uv 是串连接，上标 k 表示连接 k 块，不是对字符串求数字幂。L(R)⁰={ε}。先求小表达式，再按对应运算组合其语言。 ### 04 / 先看一个完整例子 R=(ab|c)*d 的重复块是 ab 或 c，末尾恰有一个 d。选 ab、c、ab 得 abcabd，匹配。零块得 d，也匹配。acd 不匹配，因为末尾 d 前的 ac 无法分成 ab 或 c：a 后缺少 b。dcc 不匹配，因为 d 必须在末尾。写出分块就能解释成员资格。 ### 先认识这些词 - **并:** 接受任一选择的字符串。 - **连接:** 把一个串接在另一个后面。 - **Kleene 星:** 将语言成员连接零次或多次。 ### 一步步想清楚 **零次重复为何重要？** 即使重复块非空，也会加入 ε。 **xyx 如何按 (xy|x)* 分块？** 选择 xy 后接 x，因此属于该语言。 **前缀匹配能证明整体匹配吗？** 不能，剩余每个符号也必须由表达式匹配。 ### 分解新模式 对 R=(xy|z)*x，判断 xyzzx、x、zxy 的成员资格，要求整个串匹配。 **先选择方法** 先分离必须的末尾 x，再拆重复前缀。 1. xyzzx 以 x 结尾，前缀 xyzz 可拆成 xy、z、z，均允许。 2. x 留下空前缀，星允许零个重复块。 3. zxy 以 y 结尾，无论前面怎样分块都不能提供末尾 x。 **解释最终答案** xyzzx、x 匹配，zxy 不匹配。 **检验推理** 若删除模式末尾 x，语言会改变，ε 将匹配。 ### 比较星的位置 在 {a,b} 上各找一串：属于 a*b* 不属于 (ab)*，以及相反。 **先选择方法** 比较块顺序：分组连续段与交替配对。 1. aab 是两个 a 后接一个 b，因此属于 a*b*。 2. 非空 (ab)* 交替 a、b 且长度为偶数。aab 长三，因此不属于。 3. abab 是两个 ab 块，但第一个 b 后又有 a，违反先全 a 后全 b 的结构。 **解释最终答案** aab 见证第一方向差异，abab 见证反方向。两语言互不包含。 **检验推理** 两者都接受 ε，因此共享空串不能证明等价。 ### Leon 的进一步思考 **表达式与实现** 表达式说明哪些串属于语言。回溯与同时状态模拟执行不同，却可以所有答案一致。 **星不等于加** 一次或多次可写 RR*。当 R 本身不能生成 ε 时，它与星的区别就是是否包含 ε。 **注意这个边界:** R* 总包含零次重复带来的 ε，即使 R 本身什么也不匹配。
检查自己的理解 a*b 与 (ab)* 有什么不同？ a*b 是任意数量 a 后接一个 b。(ab)* 重复完整 ab 块，也含 ε。aab 只属于前者。
## DFA 状态：概括已经读过的内容 ### 01 / 从一个故事开始 门口计数器只需两盏灯报告进入人数奇偶，不必保留每次到达时间。每来一人切换灯，当前灯概括最终奇偶问题所需全部信息。确定有限自动机也如此：状态代表已读前缀的信息摘要。设计应先命名每个状态含义。若任务要求无限制精确计数，类比就到头了，因为固定灯数不能记住任意多种总数。 ### 02 / 理解原理 DFA 有有限状态集、输入字母表、起点、接受状态集及完整转移函数。每次转移恰读一个符号，因此每个输入有唯一运行过程，读完全部输入后按最终状态判断接受。 围绕不变量设计状态：读完前缀后，当前状态保证什么？奇偶只需偶与奇；固定子串可记录最长有用后缀。定义必须包含每个状态与符号组合，包括拒绝汇点。先证初始不变量，再证每步保持，最后连接接受状态与规格。 ### 03 / 逐项读懂公式 ```text D = (Q, Σ, δ, q₀, F) δ : Q × Σ → Q w ∈ L(D) ⇔ δ*(q₀,w) ∈ F ``` Q 是有限状态集，q₀ 是起点，F 是接受子集。δ 给出读一个符号的后继，δ* 扩展到整串：从 q₀ 连续应用 δ，且 δ*(q,ε)=q。这里 δ 的星表示扩展转移，不是语言重复。必须读完所有符号后检查接受。 ### 04 / 先看一个完整例子 识别含奇数个 1 的二进制串。用 E、O 两状态，从 E 开始，只接受 O。读 0 不变，读 1 在 E、O 间切换。10110 的序列为 E,O,O,E,O,O，因此接受。ε 留在 E，因此拒绝。不变量为 E 表示已读前缀含偶数个 1，O 表示奇数。它能证明所有串，不只是例子。 ### 先认识这些词 - **状态:** 已处理前缀的有限摘要。 - **不变量:** 每次转移后保持的陈述。 - **接受状态:** 输入结束于此时接受的状态。 ### 一步步想清楚 **余数计数为何只需少量状态？** 问题不需要完整总数，只需要余数。 **模三余数二再读一个 1 会怎样？** 2+1=3 余零，转到零状态。 **接受前缀保证延长后也接受吗？** 不保证，额外符号可改变所概括性质。 ### 跟踪余数机 状态 0、1、2 表示 1 的个数模三。从 0 开始，只接受 0；读 0 不变，读 1 加一模三。跟踪 110101。 **先选择方法** 每读一符号记录状态，并以累计个数核对不变量。 1. 初始计数零、状态 0。前两个 1 得计数 1、2，状态 1、2。 2. 下一 0 保持状态 2，下一 1 让计数到三，状态回 0。 3. 倒数第二个 0 保持状态 0，最后 1 让计数到四，结束于状态 1。 **解释最终答案** 完整轨迹 0,1,2,2,0,0,1。四不能被三整除，因此拒绝。 **检验推理** 直接数到四个 1，4 mod 3=1，与末状态一致。 ### 设计末符号机器 在 {a,b} 上设计完整双状态 DFA，接受非空且以 b 结尾的串。 **先选择方法** 只记最近符号是否 b，把空前缀与拒绝状态归为一组。 1. 状态 N 表示空或末符号 a，B 表示末符号 b，从 N 开始。 2. 任一状态读 a 到 N，读 b 到 B，完整定义四种状态符号对。 3. 输入结束只接受 B。bab 的状态 N,B,N,B；ε 保持 N。 **解释最终答案** 该完整 DFA 接受 bab、拒绝 ε，符合末符号规则。 **检验推理** 在任何接受串后加 a 都转 N，因为所要求末字符已改变。 ### Leon 的进一步思考 **证明状态含义** 余数机初始计数零；0 保持计数，1 同时增加计数与余数。这两种情形证明所有转移，不只一次运行。 **表示是设计选择** 若问末符号是否 1，奇偶状态不足：10 与 1 奇偶相同，末符号不同。摘要必须匹配实际问题。 **注意这个边界:** 不能一到接受状态就接受，后续符号可能离开它，必须消费全部输入。
检查自己的理解 识别 1 的个数能被三整除的二进制串需要多少状态？ 三个，表示计数除以三的余数。读 1 推进余数，读 0 不变，仅余数零接受。
## 非确定性与 ε 转移 ### 01 / 从一个故事开始 想象一队人按给定颜色序列探索迷宫。到路口时，他们探索每条兼容分支。只要至少一人读完全部颜色并到达许可房间，任务就成功。失败分支不会取消成功分支。有些无色通道不消耗颜色即可经过，类似 ε 转移。这是推理模型，不是说电脑真有无限探索者；一个有限可达状态集合就能表示全部活跃分支。 ### 02 / 理解原理 NFA 对一个状态与符号可有零个、一个或多个后继。ε 转移改变状态但不读符号。接受要求存在一条有限路径，消费全部输入并停在接受状态。其他分支卡住、结束于非接受状态或在 ε 边循环，都不取消成功路径。 NFA 易于组合：并选择分支，连接把一机器终点连到下一机器，星允许反复通过并提供空输入选项。这解释正则表达式转自动机。非确定性改变描述便利性与大小，却不增加正则语言的范围。 ### 03 / 逐项读懂公式 ```text δ : Q × (Σ ∪ {ε}) → 𝒫(Q) 接受 w 当且仅当存在标签为 w 且终点在 F 的路径 ``` 𝒫(Q) 为 Q 的幂集，因此转移返回可能状态的集合。ε 不消费符号。路径标签把普通符号连接并忽略 ε。F 为接受状态集。“存在”是关键：一个成功运行就足够。缺失转移表示后继为空，不是等待后来的符号。 ### 04 / 先看一个完整例子 识别以 ab 结尾的 {a,b} 串。起点在两字母上自环，也允许读 a 到第二状态；第二状态读 b 到没有出边的终点。baab 上，一分支猜第一个 a 是后缀起点，却被下一个 a 卡住；另一分支等到第二个 a，再读末尾 b 接受。aba 上，一分支在 ab 后到终点却不能消费末 a，所以全串拒绝。 ### 先认识这些词 - **非确定性:** 一次转移可能有多个后继状态。 - **ε 转移:** 不消费输入符号的状态改变。 - **存在性接受:** 一条有限、完整、成功的运行就够。 ### 一步步想清楚 **为何可以忽略失败分支？** 接受要求至少一次成功，不要求每条分支成功。 **ε 会消费空格字符吗？** 不会。它什么也不消费，实际空格会是普通字母表符号。 **提前到终态就够了吗？** 只有还能成功消费全部剩余符号才行。 ### 字母前的免费分支 状态 s,p,f，起点 s，仅 f 接受。边为 s—ε→p、s—a→s、p—b→f，无其他边。判断 aab 与 ba。 **先选择方法** 每个符号前后维护包含所有免费 ε 移动的活跃状态。 1. 初始闭包 {s,p}。每个 a 沿 s 自环再用 ε 补回 p，读 aa 后仍为 {s,p}。 2. 末 b 将 p 移到 f，因此 aab 最后为 {f} 并接受。 3. 对 ba，b 先产生 {f}，f 没有 a 出边，读 a 后为 ∅，因此拒绝。 **解释最终答案** 接受 aab，拒绝 ba。在前缀后到终态并不够。 **检验推理** 成功串恰为 a*b：任意个 a 后接一个末 b。 ### 为什么交换 NFA 终态失败 NFA 状态 s,f，字母表 {a}，起点 s，终态 {f}。仅有 s—a→s 与 s—a→f。交换终态为 {s} 前后比较输入 a。 **先选择方法** 列出两条完整运行；补语言应反转整体答案，而非各路径独立结果。 1. 原机器输入 a 有终点 s、f 两条运行。终点 f 的路径成功，因此接受。 2. 交换终态后两条运行仍存在，现在终点 s 的路径成功。 3. 两机器均接受 a。真正补机器应因原机器接受而拒绝 a。 **解释最终答案** 这个 NFA 交换终态不能得到补语言。 **检验推理** 确定化后 a 对应唯一子集 {s,f}，反转该子集接受性才能正确反转答案。 ### Leon 的进一步思考 **同时模拟可能性** 每个前缀后记录可达状态集合。相同未读后缀下到同状态的两路径，未来选择相同，可合并。 **ε 环的闭包仍有限** 闭包搜索标记已访问状态。环 p→q→p 只各加入 p、q 一次，无需永远重复遍历。 **注意这个边界:** 不能直接交换 NFA 的接受与非接受状态来求补。存在性接受阻止该技巧，须先转完整 DFA。
检查自己的理解 一条分支接受，另一条在 ε 转移上永远循环，输入接受吗？ 接受。只需存在有限接受运行，其他分支不会取消它。
## 把 NFA 转为 DFA ### 01 / 从一个故事开始 控制室用点亮房间的集合代替迷宫探索队。每读一种颜色，就熄灭旧灯，点亮队员现在可能所在的所有房间。给定前缀后，显示屏只有一种配置，虽然探索路径很多。配置就是 DFA 状态。ε 通道要求额外点亮所有免费可达房间。少量房间也有指数多个子集，所以显示配置可能很多，即使实际运行只出现少部分。 ### 02 / 理解原理 子集构造为每个可达 NFA 状态集合建立一个 DFA 状态。先取起点 ε 闭包；读符号时从当前集合取所有该符号转移，再取 ε 闭包。集合与 NFA 接受集相交就接受。可达空子集应保留为拒绝汇点。 不变量为：每读完一个前缀，DFA 状态恰等于 NFA 在允许 ε 移动后所有可达状态。它证明两语言相同。m 个 NFA 状态最多有 2ᵐ 个子集，但通常只生成可达子集，不枚举所有子集。 ### 03 / 逐项读懂公式 ```text S₀ = E({q₀}) Δ(S,a) = E(⋃q∈S δ(q,a)) S 接受 ⇔ S ∩ F ≠ ∅ ``` E(S) 是含 S 本身及只沿 ε 边可达状态的闭包。Δ 属于新 DFA，δ 属于旧 NFA。并集收集每个可能普通 a 转移。F 是原接受集。最终条件表示至少一个活跃 NFA 状态接受，保留非确定性的存在含义。 ### 04 / 先看一个完整例子 NFA 有 p,q,r，从 p 开始，p 可经 ε 到 q，p 在 a 上自环，q 经 b 到 r，仅 r 接受。初始 DFA 状态 {p,q}。 读 a 时 p 到 p、q 无后继，闭包补回 q，仍为 {p,q}。读 b 仅 q 到 r，产生 {r}。再读任一字母变 ∅。因此 aab 接受，aaba 拒绝，构造直接显出语言 a*b。 ### 先认识这些词 - **子集状态:** 表示多个可能 NFA 状态的一个 DFA 状态。 - **ε 闭包:** 不消费符号可达的所有状态，包含原集合。 - **汇点:** 每条转移都回到自身的状态。 ### 一步步想清楚 **为何普通转移后还取闭包？** NFA 可在读下一符号前继续免费移动。 **四个状态有多少子集？** 每个状态选或不选，因此 2⁴=16。 **所有可能子集都必须建立吗？** 不必，可达子集构造省略所有输入都到不了的子集。 ### 构造四个可达子集 NFA 状态 0,1,2，起点 0，终态 2。边为 0—ε→1、1—x→1、1—y→2。字母表 {x,y}，缺失移动为空。构造可达 DFA。 **先选择方法** 从闭包开始，不断探索新子集直到没有新项。 1. 起点 A={0,1}。读 x 到 B={1}，读 y 到 C={2}。 2. B 读 x 自环、读 y 到 C。C 无普通移动，两符号都到 D=∅。 3. D 在两符号上自环。仅 C 含终态 2，因此仅 C 接受。A,B,C,D 四个子集可达。 **解释最终答案** DFA 有四个可达子集状态，识别 x*y。 **检验推理** 最多 2³=8 个子集。A、B 行为相同，之后可最小化合并为更小等价 DFA。 ### 跨环求闭包 ε 边为 p→q、q→r、r→q；唯一 a 边为 r→f，只有 f 接受。从 p 开始，求初闭包和读 a 后子集。 **先选择方法** 用已访问集合，有限探索免费移动环。 1. 零次移动先含 p，再由 p 加 q、由 q 加 r。 2. r 的 ε 边回到已有 q，因此停止，闭包为 {p,q,r}。 3. 读 a 时 p、q 无后继，r 贡献 f。f 无 ε 出边，后继子集 {f}。 **解释最终答案** 初子集 {p,q,r}；输入 a 最终到接受子集 {f}。 **检验推理** 若漏初闭包，p 无 a 转移，错误模拟就会拒绝 a。 ### Leon 的进一步思考 **闭包包含自身** 状态可以用零次 ε 移动留在原地。忘记零步选项会使有效起点消失。 **空子集有用途** 没有分支幸存后，后续符号无法复活分支。空子集在所有符号上自环，使 DFA 完整。 **注意这个边界:** 不能忘起点或每次符号后的 ε 闭包，否则可能丢失接受路径。
检查自己的理解 同时含接受与拒绝 NFA 状态的子集能接受吗？ 可以。只要含一个接受状态，至少一条 NFA 分支就成功了。
## 从自动机回到表达式 ### 01 / 从一个故事开始 移除交通图上的小车站时，所有进入该站、可能绕本地环若干次、再离开的路线，都须用新直达连接表示。旧直达路线仍作为另一选择。不断重复后只剩起终点，以及描述全部旅行的连接。状态消除用边上的正则表达式做这种压缩。结果可能比原图长很多，不同消除顺序也会给出外观不同但语言相同的表达式。 ### 02 / 理解原理 广义 NFA 用正则表达式标边。添加无入边的新起点与无出边的新终点，用 ε 接旧边界。缺边表示 ∅，平行边用并合并。移除 k 时，为每个幸存 i→j 加入经 k 的选择：进入、循环任意次、离开。 最后只剩新起终点，其边表达式表示原语言。结合表达式转 NFA 与子集构造，可证表达式、NFA、DFA 表达能力相同，但表示大小与执行成本未必相同。 ### 03 / 逐项读懂公式 ```text Rᵢⱼ ← Rᵢⱼ | Rᵢₖ(Rₖₖ)*Rₖⱼ ``` Rᵢⱼ 是当前 i 到 j 的边表达式。k 为待删状态。新选择依次连接进入路线、在 k 上零次或多次循环、离开路线。原直达路线仍保留。一步消除中所有边标签都取自消除前图，i、j 必须是幸存状态。 ### 04 / 先看一个完整例子 设起点 s、中间 k、终点 f，边为 s→k:a、k→k:b、k→f:c、s→f:d。删除 k 后 s→f 为 d|ab*c。abbbc 走 a 进入、三次 b 循环、c 离开。ac 用零次循环，d 用旧直达边。abcabc 不允许，因为到 f 后不能重启。若无直达边，其标签 ∅，结果简化为 ab*c。 ### 先认识这些词 - **广义边:** 以正则表达式标记的边。 - **消除:** 移除状态同时保留幸存端点间全部路线。 - **自环:** 从状态返回自身的路线。 ### 一步步想清楚 **为何保留旧边？** 有些接受路线从不经过被删状态。 **缺失自环贡献什么？** 其星贡献 ε，表示绕环零次。 **表达式更长就表示不同语言吗？** 不是，消除顺序可改变长度而不改接受串。 ### 删除有环中间状态 s,k,f 的标签为 s→f:u、s→k:v、k→k:w|x、k→f:y，无其他边。删除 k 并检验 vwxwy。 **先选择方法** 区分不经 k 与进入、循环、离开 k 的路线。 1. 不经 k 的路线贡献 u，必须保留。 2. 经 k 路线贡献 v(w|x)*y，每次环独立选 w 或 x。 3. vwxwy 分成入口 v、环 w,x,w、出口 y，顺序均符合。 **解释最终答案** 结果 u|v(w|x)*y，接受 vwxwy。 **检验推理** 零环路线 vy 也匹配，u 不进入 k 仍被接受。 ### 区分缺边与免费边 无 s→f 边。s→k:ε、k→f:ab，k 无自环。删除 k，再与 s→k 缺失的变体比较。 **先选择方法** 缺边代 ∅，存在的免费边代 ε。 1. 第一图代入 ∅|ε(∅)*ab，旧直达选择为空。 2. 因 ∅*={ε}，连接 ε、ε、ab 得 ab。 3. 变体入口为 ∅，因此 ∅|∅(∅)*ab=∅，根本无法进入 k。 **解释最终答案** 免费入口允许恰为 ab 的串，缺失入口不允许任何串。 **检验推理** 第一图及其表达式都不接受 ε，因为出口仍需 a、b 两符号。 ### Leon 的进一步思考 **一次更新只用一张旧图** 所有经 k 路线应使用消除前标签。同一步混入刚更新标签，可能意外引入不期望的重复结构。 **空语言消灭连接** 若无入口或出口，经该点路线为 ∅。相反，ε 入口或出口不消费符号，却仍允许路线。 **注意这个边界:** 不能删掉原 i→j 表达式，不经过 k 的路线也必须保留。
检查自己的理解 被删除状态没有自环会怎样？ 循环标签为 ∅，且 ∅*={ε}，因此新路线只是进入表达式接离开表达式。
## 匹配策略与重复工作 ### 01 / 从一个故事开始 图书管理员把一排相同卡片分成一张或两张的包。若末尾要求无法满足，她可能撤销选择，反复尝试面对相同剩余任务的不同分法。更有条理的方法记录已到达的不同情况并合并等价尝试。这说明短正则表达式在回溯引擎中也可能很慢，尽管有限状态匹配可行。数学语言与引擎搜索策略是两层，都影响性能判断。 ### 02 / 理解原理 成员问题问整个输入是否属于表达式语言。朴素递归或回溯匹配可能探索同一前缀的多种分解，重复等价子问题。Thompson 风格 NFA 模拟维护活跃状态集，逐符号更新并包含 ε 闭包。 大小 m 的表达式可构造状态与边数 O(m) 的 NFA，直接模拟长 n 输入需 O(mn) 时间、O(m) 工作空间。先确定化后，固定 DFA 的常数时间转移可使匹配 O(n)，但构造 DFA 可能需指数状态。这些界针对基本正则表达式，不包括反向引用等扩展。 ### 03 / 逐项读懂公式 ```text NFA 模拟：O(mn) 时间、O(m) 活跃状态空间 已预处理的固定 DFA：O(n) 匹配时间 ``` m 衡量 Thompson 风格 NFA 大小，包括转移；n 为输入长度。每个字符的 ε 可达与普通转移都避免重复访问已加入状态。DFA 界假定自动机已构造，查转移为常数时间。不是所有库引擎都采用这些策略，表达式也属输入时须计预处理成本。 ### 04 / 先看一个完整例子 对 (a|aa)*b 与 aaaaac，五个 a 可分成一张或两张块，例如 a,a,a,a,a 或 aa,a,aa。因缺末 b，所有选择最后都失败。回溯可能按许多分法重复发现失败。NFA 模拟合并同前缀后到同状态的分支，c 没有续路时拒绝。改为 aaaaab 则匹配。例子展示重复工作，而没有改变语言。 ### 先认识这些词 - **回溯:** 撤销选择并尝试其他路径。 - **活跃集合:** 当前输入前缀后所有可达状态。 - **预处理:** 匹配某个输入前进行的工作。 ### 一步步想清楚 **短模式为何也慢？** 执行可能重复探索最终同样失败的许多分法。 **什么信息允许合并尝试？** 相同自动机状态与输入位置表示相同剩余任务。 **DFA 构造总便宜吗？** 不是。子集构造可产生指数状态，即使后续匹配为线性。 ### 统计重复分解 对 (a|aa)*b 和输入 aaaaac，统计五个 a 分成长度一或二块的方式。不把它当作引擎指令总数。 **先选择方法** 设 F(n) 为分法数，按第一块长一还是二分类。 1. F(0)=1 表示空分法，F(1)=1 表示一个单块。 2. n≥2 时 F(n)=F(n−1)+F(n−2)，移去首块剩对应长度。因此 F(2)=2、F(3)=3。 3. 继续 F(4)=3+2=5，F(5)=5+3=8。每种分法最后仍遇 c 而非所需 b。 **解释最终答案** 八种分法都失败。这量化重复选择，不是通用运行时间。 **检验推理** 将 c 改为 b 会接受，但 a 块仍有八种分法。 ### 区分准备与匹配 假设已构造 DFA 每符号转移一次。三输入长 4、7、9。构造耗 30 个抽象工作单位，每转移一单位。求匹配成本与总成本。 **先选择方法** 先累加每输入扫描，再仅加一次准备成本。 1. 前两输入分别需四与七次转移，小计 11。 2. 加第三输入九次，匹配成本为 20。 3. 只加一次构造 30，三输入总成本 50。 **解释最终答案** 匹配成本 20，完整批次 50。线性扫描并未消除准备成本。 **检验推理** 若每输入都需新 DFA 且构造成本相同，准备为 90，总数 110。 ### Leon 的进一步思考 **统计状态，不统计想象的人** 成员判断无需保留同状态多个副本。路径数可增长而集合仍小；统计解析数是不同问题。 **合理分摊准备成本** 固定 DFA 多次复用可分摊构造成本。每请求换模式时忽略准备工作，会误导比较。 **注意这个边界:** 某回溯实现耗指数时间，并不证明正则匹配本身必然指数困难。
检查自己的理解 为什么同前缀后到同状态的两条 NFA 运行可合并？ 未来只依赖当前状态与未读后缀，不同历史不再提供成员判断所需信息。
## 正则语言的封闭性与判定过程 ### 01 / 从一个故事开始 一个面板同时记录两传感器状态。第一传感器三种模式，第二四种，组合最多十二对。策略可在两者都许可、任一许可或两者不同意时通过。这就是自动机积。接受状态对表达策略，转移结构不变。检查哪些状态对可达，就能判定是否可能发生分歧，为比较不同规格提供有限过程。 ### 02 / 理解原理 正则语言对并、交、补封闭。相同字母表上的完整 DFA 可构造积，每读一符号同时更新两个状态，再按所需布尔运算选择接受对。求补只需交换完整 DFA 的接受与非接受状态。 模拟可判定成员资格，从起点寻找接受状态可判定非空。等价归约为对称差是否为空：若没有可达状态对恰有一个分量接受，两机器就对所有串一致。表达式转 DFA 因此也能判定表达式等价，虽然转换可能指数增长。 ### 03 / 逐项读懂公式 ```text δ×((p,q),a) = (δ₁(p,a),δ₂(q,a)) L₁ = L₂ ⇔ (L₁ ∖ L₂) ∪ (L₂ ∖ L₁) = ∅ ``` p、q 是两个 DFA 的状态，δ₁、δ₂ 是各自转移，δ× 为积转移。L₁、L₂ 是语言。差集保留只在一侧的串，两差的并称对称差。要求共同字母表；求补或积前，必要时添加拒绝汇点使机器完整。 ### 04 / 先看一个完整例子 A 接受以 1 结尾的串，B 接受含奇数个 1 的串。积起点是（不以1结尾，偶）。输入 10 时 A 先接受后拒绝；B 读 1 到奇、读 0 不变。末状态恰有一侧接受，所以 10 证明语言不同。可达搜索可用前驱链接还原反例。一个反例足够，很多一致样本则不足。 ### 先认识这些词 - **积状态:** 记录每台机器一个状态的有序对。 - **对称差:** 恰属于两个语言之一的串。 - **可达性:** 是否有有限路径从起点到某状态。 ### 一步步想清楚 **一次分歧为何足够？** 等价要求每个输入一致，任一反例就推翻它。 **三状态与五状态机器的积大小界是多少？** 最多 3×5=15 对，部分可能不可达。 **完整 DFA 能交换终态求补吗？** 能。每输入恰有一个完整运行，反转末状态接受性就反转答案。 **为什么测试很多字符串仍弱于搜索乘积图？** 有限样例可能漏掉更长的反例。乘积图虽然节点有限，却覆盖任意字符串可能到达的状态对。 ### 求两个小规则的交 在 {0,1} 上，A 接受偶数长度，B 接受末尾 1。给出积的接受规则，检查 101、01。 **先选择方法** 独立跟踪长度奇偶与末符号，交要求两者都满足。 1. 状态为 (E,N),(E,Y),(O,N),(O,Y)，起点 (E,N)。每符号切奇偶，1 设置 Y，0 设置 N。 2. 101 长三且末 1，状态 (O,Y)，不满足偶长。 3. 01 长二且末 1，结束于唯一接受对 (E,Y)。 **解释最终答案** 交语言接受 01、拒绝 101，仅 (E,Y) 为终态。 **检验推理** ε 虽偶长却无末尾 1，起点正确拒绝。 ### 寻找语言反例 A 接受偶数个 1，B 接受末 0 串且拒绝 ε。在 {0,1} 上找最短分歧，允许 ε。 **先选择方法** 搜索边前先检查起点对，空串长度零。 1. 对 ε，A 见零个 1，零为偶数，所以接受。 2. B 因无末符号明确拒绝 ε，起点对已经分歧。 3. 不存在长度小于零的串，因此不可能有更短分歧。 **解释最终答案** ε 是最短反例，两语言在起点就不同。 **检验推理** 0 被两者接受，说明只看非空例子可能漏掉最简单证据。 ### 跟踪 aba 在两个自动机中的状态 比较“包含 ab”和“以 ab 结尾”。两机都从 0 开始，只接受状态 2。使用程序中的转移表。 **先选择方法** 每读一个字母记录状态对，读完整个单词后比较接受性。 1. 从 (0,0) 出发。读 a 后都到 1，得到 (1,1)。 2. 再读 b 得到 (2,2)，前缀 ab 被两者接受。 3. 最后读 a，得到 (2,1)，只有“包含 ab”接受。 **解释最终答案** aba 属于对称差，因此两个语言不等价。 **检验推理** 长度小于 3 且含 ab 的字符串只有 ab 本身，它也以 ab 结尾，因此不存在更短反例。 ### 找到区分两个 DFA 的最短单词 两位同学制作文本过滤器：一个接受任意位置含 ab 的单词，另一个只接受以 ab 结尾的单词。ab 和 aab 的测试都通过，于是他们以为两个过滤器等价。米娜不再猜测试字符串，而是同时运行两个自动机，搜索恰好只有一个接受的状态对。最终找到 aba，直接说明二者为何不同。 ```python from collections import deque from itertools import product def witness(a, accepting_a, b, accepting_b): alphabet = ("a", "b") start = (0, 0) parents = {start: None} queue = deque([start]) while queue: pair = queue.popleft() x, y = pair if (x in accepting_a) != (y in accepting_b): letters = [] while parents[pair] is not None: previous, letter = parents[pair] letters.append(letter) pair = previous return "".join(reversed(letters)) for letter in alphabet: nxt = (a[x][letter], b[y][letter]) if nxt not in parents: parents[nxt] = (pair, letter) queue.append(nxt) return None def accepts(table, word): state = 0 for letter in word: state = table[state][letter] return state == 2 contains = [{"a": 1, "b": 0}, {"a": 1, "b": 2}, {"a": 2, "b": 2}] ends = [{"a": 1, "b": 0}, {"a": 1, "b": 2}, {"a": 1, "b": 0}] word = witness(contains, {2}, ends, {2}) assert word == "aba" and witness(contains, {2}, contains, {2}) is None for size in range(len(word)): for letters in product("ab", repeat=size): test = "".join(letters) assert accepts(contains, test) == accepts(ends, test) print("shortest witness:", repr(word)) print("contains ab:", accepts(contains, word)) print("ends in ab:", accepts(ends, word)) ``` **在本地运行** ```sh python regular-decision-problems-shortest-dfa-counterexample.py ``` **预期输出** ```text shortest witness: 'aba' contains ab: True ends in ab: False ``` **按执行顺序理解** 1. 乘积状态 (x,y) 记录两个自动机读完同一前缀后的状态。 2. 状态对入队时标记；图中最多有 |Q_A|×|Q_B| 个状态对。 3. 恰好一个分量接受时，将乘积状态视为目标。这是对称差，而非交集。 4. 用父指针恢复字符串。BFS 保证首次找到的反例按符号数最短。 **逐步读懂代码** 两个语言不同，当且仅当对称差非空：L(A)≠L(B) 等价于存在 w，使 accept_A(w) 与 accept_B(w) 恰好一真一假。完整乘积搜索可以判定给定有限自动机的这一条件。若找不到可达的分歧状态对，任何单词都会到达判断一致的状态对。 状态数分别为 q_A、q_B，字母表大小为 s 时，时间为 O(s×q_A×q_B)，存储状态需要 O(q_A×q_B) 空间。自动机必须完整：每个状态对每个字母都有转移。缺失转移应先补到明确的拒绝汇点。 若初始状态就有分歧，返回空字符串也是合法反例。None 才表示不存在反例。这里的小规模穷举检查核实样例中没有更短反例；乘积状态的访问论证解释一般搜索为何终止。本方法比较 DFA，不能用于判定任意程序等价。 ### Leon 的进一步思考 **共同字母表重要** 补集相对于 Σ*。改变字母表会改变未见符号的处理，因此应在共同字母表上补全机器。 **广度优先找最短证据** 每边消费一个符号时，积图广度优先搜索可找最短分歧串。记录入边符号与父状态以还原。 **注意这个边界:** 不完整 DFA 求补前要加汇点。缺转移所拒绝的输入也须在补机器中接受。
检查自己的理解 有限搜索怎能证明无限多个串一致？ 每个串都在有限积图中产生路径。若无可达分歧状态，就不存在反例串。
## 证明有限记忆不够 ### 01 / 从一个故事开始 衣帽间管理员用固定卡片记录进入人数，稍后必须允许恰同数量离开。人数无上限时，两个不同总数迟早共用一张卡。此后相同退出序列会导致相同行为，尽管一者应该通过，另一者应失败。这不是某套卡片设计失败，而是反对所有固定有限卡片系统的论证。关键在无界的精确要求；人数有上限或只问固定模数余数，就改变了问题。 ### 02 / 理解原理 证明非正则，可说明任何有限状态摘要都保不住所需后缀区别。对 L={aⁿbⁿ:n≥0}，假设存在 m 状态 DFA。m+1 个前缀 ε,a,…,aᵐ 中必有 aⁱ、aʲ 到同状态。接同后缀 bⁱ 后两串行为相同，但 aⁱbⁱ 属于 L，aʲbⁱ 不属于，矛盾。 另一技巧利用封闭性：若假设语言正则，与已知正则语言运算后得到已知非正则语言，假设就错。这些论证只排除有限自动机，不表示语言不可判定。 ### 03 / 逐项读懂公式 ```text δ*(q₀,aⁱ) = δ*(q₀,aʲ), i < j ⇒ δ*(q₀,aⁱbⁱ) = δ*(q₀,aʲbⁱ) ``` m 为状态数，m+1 个前缀由抽屉原理迫使状态重复。i、j 是不同前缀长度，bⁱ 为共同区分后缀，δ* 为扩展转移。同状态的确定机器处理相同剩余输入必然一样。矛盾来自两完整串的成员资格，而不只是长度不同。 ### 04 / 先看一个完整例子 E 为任意顺序下 a、b 数相同的串。若 E 正则，与正则 a*b* 的交也应正则。该交恰为 {aⁿbⁿ:n≥0}，重复状态论证已证它非正则，矛盾，所以 E 也非正则。abba 在 E 却不在 a*b*；取交故意排除混合顺序，显出已知困难模式。 ### 先认识这些词 - **抽屉原理:** 对象多于类别时，至少两对象进入同类。 - **区分后缀:** 同一追加串使所需成员答案不同。 - **非正则:** 没有有限自动机能识别该语言。 ### 一步步想清楚 **为什么用 m+1 个前缀？** 只有 m 个状态，因此两个前缀必共享一个。 **为何恰接 bⁱ？** 它配平较短 a 前缀，却不能配平较长者。 **非正则是否表示没有算法能判定？** 不是。可用无界工作记忆的机器能对有限输入计数比较。 ### 走完必然碰撞论证 假设识别 {aⁿbⁿ:n≥0} 的 DFA 在 a²、a⁵ 后到同状态，解释为何矛盾。 **先选择方法** 找一个共同后缀，让一前缀必须接受，另一必须拒绝。 1. 选 b²，为较短前缀提供恰两个 b。 2. a²b² 数相同必须接受；a⁵b² 有五 a 两 b 必须拒绝。 3. 两运行处理后缀时状态相同，确定性迫使后续状态与最终答案相同，与要求矛盾。 **解释最终答案** 正确 DFA 中两前缀不能共状态。需要任意多区别，因此排除有限 DFA。 **检验推理** 改接 b⁵ 会交换哪个串配平，同样矛盾。 ### 有界版本是正则 设 L₃={aⁿbⁿ:0≤n≤3}，给正则表达式，并解释为何无限语言证明不能原样套用。 **先选择方法** 枚举有限 n 值，无需无界计数器。 1. n=0 得 ε，n=1 得 ab。 2. n=2 得 aabb，n=3 得 aaabbb，没有其他允许 n。 3. 取并 ε|ab|aabb|aaabbb，有限表达式正则地描述四串。 **解释最终答案** L₃ 正则。先前证明需要任意多个必须区分的前缀，这里固定上限消除了它。 **检验推理** a⁴b⁴ 虽数相等仍拒绝，因为 n=4 超过上限。 ### Leon 的进一步思考 **量词承担证明** 状态数 m 任意。证明某个三状态机失败，弱于从任意有限 m 出发推出矛盾。 **上限改变语言** 限制 n≤3 只剩 ε,ab,aabb,aaabbb。有限列表总可识别，尽管无界模式不能用有限记忆。 **注意这个边界:** 画不出 DFA 不是非正则证明，必须排除每个可能有限 DFA。
检查自己的理解 {aⁿbⁿ:0≤n≤20} 非正则吗？ 不是。它有限，可用 DFA 或显式表达式有限并识别。无界要求才驱动不可能性证明。
## 文法与递归结构 ### 01 / 从一个故事开始 嵌套收纳盒可选择空隔间，或在大盒里包一个小盒。指令可以引用自身，因此有限配方生成任意深度嵌套。上下文无关文法类似：有名称的未完成组件可替换为终结符与更多未完成组件。只有全部完成才得到成品。类比解释递归，却不规定实际执行顺序。不同替换次序可能描述同一结构、生成同一串。 ### 02 / 理解原理 CFG 包含非终结变量、终结符、产生式和起始变量。每条规则将一个非终结符替换为有限序列，也可替为 ε。“上下文无关”表示无论邻近符号是什么，都可应用规则。推导从起始变量开始，只有全为终结符的结果才属于语言。 文法可描述超出有限状态记忆的嵌套。正确性有两个方向：生成串都符合目标，目标串都能生成。上下文无关语言对并、连接、星封闭：先改名避免变量冲突，再加新起点选择、连接或重复。它们不像正则语言那样对任意交与补封闭。每个正则语言都上下文无关，反向不成立。 ### 03 / 逐项读懂公式 ```text G = (V, Σ, P, S) L(G) = {w ∈ Σ* : S ⇒* w} ``` V 是非终结符集，Σ 是与其不交的终结字母表，P 为产生式，S 为起点。⇒ 是一步重写，⇒* 为零步或多步。中间形式可混有变量，但不属于语言成员。w∈Σ* 要求最终只有终结符，包括可能的 ε。 ### 04 / 先看一个完整例子 用 S→[S]S|ε 生成平衡方括号。生成 [][]：先 S⇒[S]S，把内部 S 替 ε 得 []S，再展开余 S 为 [S]S，最后消去两个 S。生成 [[]] 则改为展开内部 S。任意非空平衡串的第一个 [ 都有匹配 ]，把串分成平衡内部及平衡后缀，恰对应两个 S。该分解支持按串长归纳证明。 ### 先认识这些词 - **非终结符:** 仍需重写的命名组件。 - **终结符:** 允许出现在完成串中的符号。 - **推导:** 从起始变量出发的一系列规则应用。 ### 一步步想清楚 **有限文法为何可生成无限多个串？** 递归规则可应用任意有限次数。 **aSb 已经是语言成员吗？** 只要 S 仍是非终结符就不是，必须完成剩余工作。 **生成几个例子就证明完备吗？** 不能，必须解释每个目标串如何生成。 ### 生成镜像串 文法 S→aSa|bSb|ε，字母表 {a,b}。完整推导 abba，并说明所有生成串共有性质。 **先选择方法** 匹配外层相同符号，递归中间，以 ε 结束。 1. abba 外符号为 a，因此 S⇒aSa。 2. 内部目标 bb，因此把 S 替 bSb，得 aSa⇒abSba。 3. 剩余 S 替 ε，得 abba，无变量。每次包裹添加两个相同端符号。 **解释最终答案** S⇒aSa⇒abSba⇒abba。每个生成串都是偶长度回文。 **检验推理** aba 虽回文却为奇长，文法不能生成；长度不变量解释原因。 ### 用新名称构造连接 G₁ 为 A→aA|ε，G₂ 为 B→bB|b。构造前者串一条接后者串一条的文法，再推导 aab。 **先选择方法** 保留不相交变量 A、B，用新起点将其连接。 1. 加 S→AB。A 生成零个或多个 a，B 生成一个或多个 b。 2. 两次 A 递归后用 ε：S⇒AB⇒aAB⇒aaAB⇒aaB。 3. 用 B→b 得 aab。两组件顺序固定，任何规则都不能将 a 放到 b 后。 **解释最终答案** 文法生成 a*b⁺，即任意 a 块后接非空 b 块，并可生成 aab。 **检验推理** A 立即消失时允许 b；B 无法消失，所以不含 ε。 ### Leon 的进一步思考 **可靠性与完备性不同** 只生成 ε 的文法对平衡括号是可靠却不完备的。它不生成坏串，却漏掉所有非空好串。 **组合前先改名** 两文法都可能用 S 表示不同内容。连接前先改名，否则规则可能发生意外交互。 **注意这个边界:** [S] 仍有非终结符，是中间形式，不是已生成终结串。
检查自己的理解 S→aS|b 生成什么语言？ 恰为 {aⁿb:n≥0}。每次递归加一个前导 a，最后规则添加 b 并结束。
## 解析树与歧义 ### 01 / 从一个故事开始 书面表达式像缺少分组标记的装配指令。先拼前两块或先拼后两块，可能从相同符号造出不同结构。解析树把结构写清：叶是可见串，内部节点记录文法如何组装。独立工作的不同先后顺序不一定改变结构。歧义关乎不同树，因此不能仅列两种任意规则应用顺序就断言有歧义。 ### 02 / 理解原理 解析树记录推导的层级结构。根为起始变量，内部节点按产生式展开，叶从左到右组成结果串。若某串有两棵不同解析树，等价地有两条不同最左推导，则文法有歧义。 E→E+E|E×E|n 没规定优先级和结合性，因此有歧义。分层文法让表达式用加法组合项，项用乘法组合因子，因子提供原子或括号。歧义属于特定文法，不能由一份有歧义文法断言语言没有无歧义文法。可靠求值或翻译前须先确定结构。 ### 03 / 逐项读懂公式 ```text G 有歧义 ⇔ 存在 w∈L(G)，且 w 至少有两棵不同解析树 ``` G 为文法，w 为终结串，存在量词表示一个见证就足够。不同树指产生式结构不同，不是书写或遍历顺序不同。最左推导总展开最左未完成变量，排除无关执行次序差异。这是歧义定义，不是能判定任意文法歧义的算法。 ### 04 / 先看一个完整例子 E→E+E|E×E|n 对 n+n×n 可有根为加或根为乘的树。三个 n 分别取 2、3、4，则 2+(3×4)=14，而 (2+3)×4=20。用 E→E+T|T，T→T×F|F，F→n|(E) 可让乘法先在项内形成，再由加法组合。括号仍能明确要求另一结构。 ### 先认识这些词 - **解析树:** 展示哪些规则构造该串的层级树。 - **优先级:** 决定哪个运算结合得更紧的规则。 - **结合性:** 同级重复运算如何分组。 ### 一步步想清楚 **两条任意推导为何不够？** 它们可能只在不同次序展开独立分支，仍是同一树。 **同一表达式如何有 17 与 27？** 5+4×3 若为 5+(4×3) 得 17，若为 (5+4)×3 得 27。 **加乘优先级能决定减法结合性吗？** 不能。重复减法还需独立分组规则。 **为什么一次切分内部相乘，不同切分之间相加？** 一次切分中，每棵左树可与每棵右树配对；不同切分下，一棵树的根划分唯一，因此集合互不重叠。 ### 两棵树产生不同结果 使用 E→E+E|E×E|n，其中 n 表示一个数字记号。三个数字记号依次显示数值 5、4、3。给出 5+4×3 的两种解析并求值。 **先选择方法** 保持叶顺序不变，选择不同根运算。 1. 根选 +，左叶 5，右子树 4×3。先乘得 12。 2. 根相加 5+12=17，该树为 5+(4×3)。 3. 改根为 ×，左子树 5+4=9，右叶 3，根值 9×3=27。 **解释最终答案** 两树给相同无括号文字，却得 17、27，证明文法有歧义。 **检验推理** 加显式括号可区分两个所求结构，消除这次歧义。 ### 展开顺序不是树歧义 文法仅 S→AB、A→a、B→b。比较先展开 A 与先展开 B。 **先选择方法** 写两推导，再比较父子结构。 1. 先 A 得 S⇒AB⇒aB⇒ab。 2. 先 B 得 S⇒AB⇒Ab⇒ab。 3. 两树均根 S，子为 A、B，A 下 a、B 下 b，没有产生式选择不同。 **解释最终答案** 两种调度描述同一解析树，不构成歧义；该文法无歧义。 **检验推理** 只有第一种始终最左展开，从而排除无关次序差异。 ### 用小规模结果算出五棵树 对 E→E+E | n，计算 T(4)，不要枚举所有推导顺序。 **先选择方法** 按根切分数树结构。不同节点展开顺序可能得到同一棵树，不能重复计数。 1. T(1)=1，T(2)=T(1)T(1)=1。 2. T(3)=T(1)T(2)+T(2)T(1)=2。 3. T(4)=T(1)T(3)+T(2)T(2)+T(3)T(1)=2+1+2。 **解释最终答案** 共有五棵语法树。程序打印五种不同的完全括号化形式。 **检验推理** 三个操作数的两棵树是 ((n+n)+n) 和 (n+(n+n))，可核对第一个非平凡情形。 ### 数清语法树，不要默认只有一种解析 计算器接受 n+n+n+n。米娜先合并第一对操作数，朋友却先合并最后一对。两种做法都符合 E→E+E | n。字符串合法，但结构并不唯一。米娜枚举根节点的所有切分，再组合左右子树，最终找到五棵树，也理解了解析器为什么需要结合性规则。 ```python from functools import lru_cache def count_trees(operands): if operands < 1: raise ValueError("at least one operand required") ways = [0] * (operands + 1) ways[1] = 1 for size in range(2, operands + 1): ways[size] = sum(ways[left] * ways[size - left] for left in range(1, size)) return ways[operands] @lru_cache(None) def trees(operands): if operands == 1: return ("n",) return tuple(f"({left}+{right})" for cut in range(1, operands) for left in trees(cut) for right in trees(operands - cut)) assert [count_trees(n) for n in range(1, 6)] == [1, 1, 2, 5, 14] assert len(set(trees(4))) == count_trees(4) print("four operands:", count_trees(4), "parse trees") for tree in trees(4): print(tree) ``` **在本地运行** ```sh python parse-trees-ambiguity-count-expression-trees.py ``` **预期输出** ```text four operands: 5 parse trees (n+(n+(n+n))) (n+((n+n)+n)) ((n+n)+(n+n)) ((n+(n+n))+n) (((n+n)+n)+n) ``` **按执行顺序理解** 1. 一个操作数对应一棵叶子树，基础值是一，不是零。 2. 根在 left 个操作数之后切分时，左右树数量相乘，每对左右树构成一棵树。 3. 对不同根切分求和；根的划分不同，不会得到同一棵有序树。 4. 只枚举四个操作数用于展示。计数与实际生成全部树，输出成本差别很大。 **逐步读懂代码** 设 T(m) 表示 m 个相同操作数词元用加号连接时的语法树数量。T(1)=1，T(m)=对 k=1 到 m-1 求和 T(k)×T(m-k)。k 表示左子树的叶子数量。m=4 时，三种根切分分别贡献 1×2、1×1、2×1，总数为 5。 计数器需要 O(m²) 次算术操作，并保存 O(m) 个整数。大计数需要大整数，因此这里没有声称任意大 m 下算术仍是常数成本。枚举所有树至少要花费与输出字符数相关的时间，增长快得多。 算出的数值相同，不表示文法无歧义。歧义指同一词元字符串具有多棵语法树。对这个简单语言，E→E+n | n 可以规定左结合。本例假定已经分词且只有加号，并未实现词法分析、其他运算符优先级或通用文法解析器。 ### Leon 的进一步思考 **同值可能掩盖歧义** 1+2+3 两树都算六，但仍不同。数值相等不能证明文法无歧义。 **修文法而非猜结构** 分表达式、项、因子可将优先级写入语法。求值器据树计算，无需事后添加可能矛盾的规则。 **注意这个边界:** 仅以不同次序展开独立分支并不构成歧义。应比较树或最左推导。
检查自己的理解 有歧义文法能生成正则语言吗？ 能。歧义关乎表示，不是表达类别。例如 S→A|B、A→a、B→a 对有限正则语言 {a} 给两种解析。
## 不改变语言的 Chomsky 范式 ### 01 / 从一个故事开始 设装配说明只能有两种形状：连接两个未完成组件，或安装一个完成零件。复杂指令拆成小阶段，可选组件和别名需谨慎处理，确保新说明仍生成相同成品。Chomsky 范式为文法规则提供这种形状。目的不是最短或最优雅，而是让解析容易推理。空成品例外单独保留，因为有可见叶的树无法表示无零件成品。 ### 02 / 理解原理 CNF 普通产生式只能 A→BC 或 A→a。若语言含 ε，新起点还可 S₀→ε，且新起点不可出现在任何右侧。转换通过为长规则中终结符引入变量、将长右侧拆成二元规则、为可空变量添加所有所需省略选择，以及按别名可达关系移除单位规则来保留语言。 顺序与记录很重要：可空变量可重复出现，只删 ε 规则而不添选择会丢串。长 n 的非空词的 CNF 树有 n 个终结生成节点、n−1 个二元节点。该受限结构支持可判定成员检查与动态规划。 ### 03 / 逐项读懂公式 ```text A→BC 或 A→a；可选 S₀→ε 含 n 个终结符的非空解析需 2n−1 次产生式应用 ``` A、B、C 为非终结符，a 为终结符，S₀ 为受保护起点。可选空规则是唯一 ε 例外。n 为非空串长。二叉结构有 n 个叶和 n−1 个分支节点，终结规则再对应 n 个叶应用。该计数只适用于 CNF，不适用于有单位链或可空环的任意文法。 ### 04 / 先看一个完整例子 从 S→aS|b 开始，引入 A→a，使混合规则变 S→AS。因 S 在右侧出现，加入新起点 S₀→S。去单位规则时复制 S 的非单位规则，得 S₀→AS|b、S→AS|b、A→a。 仍生成 aⁿb。对 aab：S₀⇒AS⇒aS⇒aAS⇒aaS⇒aab，共五次，与 2×3−1 一致。不同展开顺序计数仍一样，因为树节点数固定。 ### 先认识这些词 - **Chomsky 范式:** 规则限两个变量或一个终结符，另有受保护起点例外。 - **可空:** 变量能够推导 ε。 - **单位产生式:** 右侧仅一个变量的 A→B 规则。 ### 一步步想清楚 **为何引入终结符辅助变量？** 二元 CNF 规则须是两个变量，不能是 aB 这样的混合。 **CNF 生成四终结符要几步？** 四个终结规则加三个二元规则，共 2×4−1=7。 **ε 能用相同正长计数吗？** 不能。它无终结叶，使用独立起点例外。 ### 转换长度三规则 文法 S→aBC、B→b、C→c 只生成 abc。转换到 CNF 且不改变语言。 **先选择方法** 先分离长规则中的终结符，再把三个变量拆为二元步骤。 1. 加入 A→a，用 S→ABC 替代 S→aBC，生成符号不变。 2. 加入 X→BC，并将长规则改 S→AX。S 每步产生两个变量。 3. 保留 B→b、C→c。S→AX、X→BC、A→a、B→b、C→c 均符合形式。 **解释最终答案** CNF 文法仍恰生成 abc，每次解析用两个二元、三个终结产生式。 **检验推理** n=3 时 2n−1=5，与五次相符；没有其他规则可生成别的串。 ### 删除重复可空变量 文法 S→AA、A→a|ε。转为保语言 CNF，允许 S 作受保护起点，且 S 不在右侧出现。 **先选择方法** 移除空与单位规则前，枚举两个 A 独立保留或省略。 1. 保留两 A 得 S→AA，删一个得 S→A，两种删法得到同规则。 2. 都删得 S→ε，因为 S 受保护，允许该空规则。 3. 删除 A→ε，保留 A→a。把单位 S→A 替为 S→a。最终 S→AA|a|ε、A→a。 **解释最终答案** 两文法均恰生成 {ε,a,aa}，最终是带所述起点例外的 CNF。 **检验推理** 若删 A→ε 却不添 S→a、S→ε，就会丢掉三串中的两串。 ### Leon 的进一步思考 **先保留选择再删除** 变量可消失时，每个相关出现都能保留或省略。先删 ε 规则可能悄悄删掉短词。 **范式是工具** CNF 可能增加很多辅助变量。收益是可预测二叉解析结构，不一定文法更小或文字更短。 **注意这个边界:** 右侧长度不超过二并不就属于 CNF。A→B 是单位规则，A→aB 混合终结与非终结符，都需转换。
检查自己的理解 B→AA 中 A 可空，需要哪些更短选择？ 除 B→AA 外可能需 B→A、B→ε。随后删除不允许的空与单位规则，同时保留起点例外。
## CYK：从短片段构造长解析 ### 01 / 从一个故事开始 校对者先给单词贴标签，再处理两个词和更长片段。只有长片段可分成两个已理解且符合规则的短片段时，才给它标签。表格存结果避免重做。CYK 对 CNF 文法采用此计划，不把有希望的分界当成唯一分界，而会检查所有边界。表格直接回答成员资格，若保存成功选择，还能还原解析树。 ### 02 / 理解原理 使用左闭右开区间：T[i,j] 是生成 w[i:j] 的非终结符集合，边界为 0 到 n。用终结规则初始化长度一，再按长度 2 到 n 处理。对每个 i 检查自己的理解 为何不随意顺序填片段？ 格子依赖更短片段。递增长度确保所有子问题先完成。 ## 图灵机与配置 ### 01 / 从一个故事开始 想象细心书记员拿长方格纸、铅笔和小指令卡。卡片根据当前模式与笔下符号决定动作，一步可改符号、移动一格并换模式。不同于有限自动机，他可回看旧格并留记号。纸带提供可扩展记忆，指令仍有限。无限纸带是可用存储无固定上限的理想化，并非一步做无限操作。 ### 02 / 理解原理 图灵机由有限控制、可读写纸带、可移动读写头组成。带字母表含输入符号、空白及可能标记。配置记录状态、头位置与纸带内容，转移决定下一配置。有限次计算后，绝大多数格仍空白。 机器可停机接受、停机拒绝或永远继续。作为函数计算器时，要规定输出编码和头最终位置。单向或双向带、允许原地不动等标准约定改变描述，但不改变可计算函数范围。时间与模拟开销仍可能不同。 ### 03 / 逐项读懂公式 ```text δ(q,a) = (q′,b,d), d ∈ {L,R,S} C₀ ⊢ C₁ ⊢ C₂ ⊢ ⋯ ``` q 为当前状态，a 为头下符号，q′ 为新状态，b 为写入符号，d 为方向，S 表示原地。Cᵢ 为 i 步后完整配置，⊢ 为一次有效转移。停机状态无后续工作。一次只读当前格，不会同时查看整带。 ### 04 / 先看一个完整例子 机器扫描二进制串，将每个 0 改为 1，原 1 不变。scan 状态读 0 或 1 都写 1、右移并保持 scan；读空白进入停机且不改带。输入 010 从首位开始，非空带依次 110、110、111，再一次看到空白后停机。空输入立即停机。有限状态不存整词，纸带记录不断变化的输出。 ### 先认识这些词 - **配置:** 当前状态、头位置与带内容的整体。 - **带字母表:** 可写符号全集，包括空白与标记。 - **转移:** 一次读取、写入、移动与换状态的规则。 ### 一步步想清楚 **为何只有状态还不算配置？** 同状态可能处在不同格或符号上，下一步会不同。 **从位置 2 右移会怎样？** 写完当前格后，下一头位置为 3。 **无界纸带意味着每步无限工作吗？** 不是，每步只访问一个格并有限移动。 ### 跟踪翻转位机器 scan 中读0写1右移；读1写0右移；读空白写空白原地停机。101 位于 0–2，头从 0 开始。跟踪到停机。 **先选择方法** 每步记录纸带与头，控制状态不变不表示无事发生。 1. 位置0读1写0，头到1，带为001。 2. 位置1读0写1，头到2，带为011。 3. 位置2读1写0，头到空白位置3，带为010。第四转移看到空白，在此停机。 **解释最终答案** 输出010，四次转移后头在3。 **检验推理** 再翻转输出各位得到原101，独立验证变换。 ### 从配置求唯一后继 带位置0,1,2为a,b,空白。头在1，状态q。规则 δ(q,b)=(r,X,L)。求下一配置。 **先选择方法** 读指定格，分开处理写入、移动、控制更新。 1. 头位置1是b，因此规则适用；本步不读位置0的a。 2. 将位置1换X，带成a,X,空白，其他格不变。 3. 从1左移到0，状态q改r。新头下a在下一转移才被读取。 **解释最终答案** 下一配置为状态r、头0、纸带aX后接空白。 **检验推理** 带改变局部；左移和换状态都不会擦掉a。 ### Leon 的进一步思考 **说明输出约定** 若有效数字间留临时标记，只说输出在带上不完整。须指明输出格和是否擦标记。 **统计停机转移** 扫描器通常还需一步看到数据后的首空白。只数改变的格可能少算，即使某些写入没改符号。 **注意这个边界:** 缺失转移、拒绝和无限循环不等价。须说明约定，区分停机结果与发散。
检查自己的理解 标准图灵机能有无限多个状态吗？ 不能。控制描述有限，无界工作存储来自纸带。
## 用标记与不变量设计机器 ### 01 / 从一个故事开始 书记员检查两组物品是否配对：先标左组一件，走到右组标一件，再回去重复。标记让记忆跨行走保留。右组提前用完或结束时还有未配物品就失败。这适合比较需要无界记忆而控制模式有限的任务。好的设计要说明每趟保证什么，以及有限输入为什么不可能无限往返。 ### 02 / 理解原理 图灵机实现描述可先用阶段而非立即列全部转移。规定每阶段不变量、预期标记、成功与失败出口。对 aⁿbⁿ，先检查输入是一个 a 块后接 b 块，再反复标最左未标 a、找一未标 b、返回左边界。缺伙伴即拒绝；a、b 全标完才接受。 每成功轮未标 a 数严格下降，证明终止。每轮可扫描 O(n) 格，共 O(n) 轮，因此此简单单带实现有 O(n²) 上界，不是所有算法的普遍下界。 ### 03 / 逐项读懂公式 ```text r 轮后不变量：已标 r 个 a 与 r 个 b 每成功轮，未标 a 数减少一 ``` r 为已完成配对轮数。不变量假设带已通过 a*b* 形状检查，标记仍对应两个有序块。剩余 a 数为非负整数终止量。运行界中的 n 为总输入长。阶段描述还需说明边界检测与坏输入，才能扩成完整转移表。 ### 04 / 先看一个完整例子 对 aaabbb，形状检查后每轮带为 XaaYbb、XXaYYb、XXXYYY，最后无未标字母而接受。对 aabbb，两轮 XXYYb，剩 b 而拒绝。abab 有 a 出现在 b 块之后，先被形状检查拒绝。三例分别测试数量相等、数量不等、次序错误。只比数量会误接受某些混合顺序串。 ### 先认识这些词 - **标记:** 记录位置已被处理的带符号。 - **阶段:** 服务于明确目标的一组步骤。 - **终止度量:** 重复推进时严格下降的非负量。 ### 一步步想清楚 **配对前为何检查顺序？** 仅数量相等也会接受abab等混合串。 **完成一轮保证什么？** 恰好新增一个已标a和一个已标b。 **二次界是普遍下界吗？** 不是。它限制本重复扫描设计，不限制所有模型或算法。 ### 伙伴不足时拒绝 用X标a、Y标b，对aaaabb运行有序块配对算法，每轮标最左未标a和b。 **先选择方法** 先跟踪完整成功轮，再定位首次缺伙伴。 1. 形状a*b*合法。首轮配一a一b，得XaaaYb。 2. 第二轮得XXaaYY，还剩两个a，b却全标。 3. 第三轮选a得XXXaYY，但向右直到空白无未标b，明确失败并拒绝。 **解释最终答案** 拒绝aaaabb，因为四个a无法与两个b一一配对。 **检验推理** 直接计数4≠2核实结果，机器有限控制无需保存数字四。 ### 证明配对循环停机 输入为有限a块后接b块，总长n，每次扫描到带边界或明确失败便结束。证明不能完成无限多配对轮。 **先选择方法** 以未标a数作为下降非负整数。 1. 初始未标a数为u，0≤u≤n。 2. 每成功轮恰标一个旧未标a，度量u→u−1，且无规则恢复。 3. 至多初始u轮后计数零。缺b可更早拒绝；最终残余b检查也只是有限扫描。 **解释最终答案** 所有允许输入都终止。至多n轮、每轮O(n)，给此实现O(n²)上界。 **检验推理** u=0时无配对轮，最终扫描仍区分ε与非空b块。 ### Leon 的进一步思考 **区分失败类型** 顺序错立即拒绝，所选a无伙伴拒绝，结束残余b拒绝。各检查填补不同正确性缺口。 **下降计数还需要阶段有限** 未标a减少只能证明成功轮有限，还须每轮扫描能到边界或明确失败。停机论证要包含这点。 **注意这个边界:** 不能只证接受者正确而忘记终止或漏拒未配符号。判定器需要双向正确性与停机证明。
检查自己的理解 状态能记信息，为什么还需要标记？ 标记在纸带保存无界数量的局部事实，固定有限状态无法记任意多个访问位置。
## 模拟、通用性与 Church–Turing 论题 ### 01 / 从一个故事开始 通用播放器读取乐谱就能播放不同曲子，无需为每首重造硬件。通用图灵机同样读取机器编码及其输入，逐步解释。类比也显出限制：能跟乐谱不代表事先知道古怪乐谱会否要求无限重复。通用性是模拟任意编码程序的能力，不是无需执行便预测每个程序最终行为的能力。 ### 02 / 理解原理 通用图灵机 U 从有限编码 ⟨M,w⟩ 模拟 M 在 w 上运行，保留接受、拒绝或不终止结果。有限字母表、状态及转移表可编码为有限串，因此机器描述能作为数据。两种形式模型等价需双向模拟，单向仅证能力包含。 Church–Turing 论题把非形式的有效算法计算与图灵可计算联系起来，是关于“算法”的论题，不是仅靠定义 TM 就证明的定理。通用性与标准纸带变体等价是具体数学定理。可计算能力相同本身不保证速度、内存或实用性相同。 ### 03 / 逐项读懂公式 ```text U(⟨M,w⟩) 模拟 M(w) M(w) 接受／拒绝／发散 ⇒ U(⟨M,w⟩) 结果相同 ``` ⟨M,w⟩ 为机器有限描述与有限输入的可计算编码，必须能分开两部分。U 固定，M 遍历编码机器。发散表示从不停机。关系描述行为而非模拟步数。坏编码也需规定处理，常用立即拒绝。 ### 04 / 先看一个完整例子 M 在一元输入末尾添加一个1后停机。向 U 给 M 编码及111。U 存模拟状态和头位置，查编码规则、更新模拟带并重复直到停机，模拟输出1111。换成一直右移的机器，U 也一直运行。同一解释器处理两者，说明通用性并不提供停机测试。 ### 先认识这些词 - **编码:** 表示机器或输入的有限串。 - **通用机器:** 能模拟编码机器的单一解释器。 - **模拟开销:** 复现另一模型步骤所需额外工作。 ### 一步步想清楚 **机器描述为何能作输入数据？** 其有限规则可列出并用有限符号编码。 **模拟一个循环会让它停机吗？** 不会，忠实模拟保留不终止。 **为何需要双向模拟？** 单向只证模拟器能力至少包含被模拟模型。 ### 模拟简单加一器 M 向右扫描一元1，在首空白写一个额外1并停机。输入11，头在首符号。说明模拟输出与步骤。 **先选择方法** 保留模拟带、头和状态，一次应用一个编码规则。 1. 首步读位置0的1，保持并移到1。 2. 第二步读位置1的1，移到空白位置2。 3. 下一规则在位置2写1并停机，模拟带现为111。 **解释最终答案** 模拟输出111，表示一元三。按约定 M 用三次转移。 **检验推理** 通用解释器可能用超过三次自身转移实现这三步。 ### 跟踪明确模拟开销 教学解释器每模拟一步需自身6步，准备10步。被模拟程序7步停机。求解释器总工作，再讨论被模拟程序不停止的情形。 **先选择方法** 区分固定准备与逐步成本，再区分有限成本和保留发散。 1. 七模拟步耗7×6=42解释器步。 2. 加一次准备：42+10=52。这是题给成本模型，不是普遍界。 3. 若被模拟程序无限运行，逐步复现也需要无限解释器步。 **解释最终答案** 停机例耗52步；忠实模拟不停止例也不会停机。 **检验推理** 模拟步数零时只剩准备10，与10+6t一致。 ### Leon 的进一步思考 **行为与资源不同** 两模型可计算相同函数却用很不同步数。讨论模拟应同时说明保留结果与资源关系。 **坏编码也是输入** 通用解释器要识别机器描述边界，并按约定拒绝坏格式，否则形式输入行为不完整。 **注意这个边界:** 不能说论题证明所有可想象物理设备都与 TM 等价，也不能说模拟保证效率相同。
检查自己的理解 Python 能模拟 TM 就证明二者能力相同吗？ 不能。这只说明 Python 能模拟 TM，还需反向证明相关 Python 计算模型可由 TM 模拟。
## 识别器与判定器 ### 01 / 从一个故事开始 失物处找到匹配标签就能确认包已到，但没找到时可能无限搜。另一处承诺查完有限完整登记册，总回答是或否。前者类似识别，后者类似判定。久等前者并不能把沉默当可靠否定。区别是对全部输入的保证，不是已观察请求上是否友好或快。 ### 02 / 理解原理 语言识别器必须接受每个成员，绝不接受非成员；对非成员可拒绝或永远运行。判定器还要求每输入停机，因此每成员问题都得到正确是或否。每个可判定语言都可识别，但反向不成立。 对编码机器的接受问题，通用模拟识别肯定例：若被模拟机器接受，迟早会观察到；若拒绝可拒绝，若循环也可循环。有限测试不能证明程序为判定器，因为未测输入可能发散。证明既需全部允许计算终止，也需答案正确。 ### 03 / 逐项读懂公式 ```text L(M) = {w : M 接受 w} 判定器：每个 w∈Σ* 上 M 都停机 可判定语言 ⊊ 可识别语言 ``` L(M) 只记录接受串，拒绝与发散均不属于该语言。Σ* 是选定编码下有限输入宇宙。严格包含表示全部可判定语言可识别，但至少一可识别语言不可判定。分类问是否存在某种合适机器，不是某个坏实现是否碰巧停机。 ### 04 / 先看一个完整例子 程序依次试0,1,2,…，若找到满足输入谓词 P(x) 的整数就接受，假设每次 P 检查会停机。有见证就迟早遇到并接受，无见证则一直找，所以它识别见证存在性，却未自动判定。P 为 x²=49 时在7接受，P 为 x²=50 时在非负整数上一直搜，虽然该特殊家族可另设计有界判定。一个循环实现不能证明语言不可判定。 ### 先认识这些词 - **识别器:** 接受所有成员且不接受非成员，但可在非成员上循环。 - **判定器:** 对每输入给正确成员答案并停机。 - **见证:** 能建立肯定答案的有限对象。 ### 一步步想清楚 **识别器沉默可能意味着什么？** 可能尚未找到未来见证，也可能永远搜，沉默本身无法区分。 **为什么判定器都是识别器？** 正确接受已满足识别，还多保证否定例也停止。 **可判定语言也能有很差识别器吗？** 能。可判定性问某判定器是否存在，不保证每个实现好。 ### 在简单否定例上循环的识别器 输入n≥0，依次测试x=0,1,2,…，x²=n时接受，每次平方检查会停。比较16与18。 **先选择方法** 区分见证存在与无见证时终止。 1. n=16时测试0,1,4,9,16，x=4提供见证并接受。 2. n=18时4²=16、5²=25，后续非负平方继续增长，故无解。 3. 指定程序没有超过n后停止的规则，因此在18上永远试，尽管数学上能拒绝。 **解释最终答案** 该程序识别完全平方数但不判定；接受16，在18上发散。 **检验推理** 另一个程序可在x²>n时拒绝，所以循环例不证明平方语言不可判定。 ### 把特殊搜索变为判定器 修改平方搜索：整数n≥0，测试x从0到n，含端点；相等接受，循环结束否则拒绝。证明正确与终止。 **先选择方法** 证明有限范围包含每个可能非负平方根。 1. n=0只需x=0且成功。n≥1时x>n则x²≥x>n，不可能为解。 2. 循环检查n+1候选，每次会停，因此整体有限。 3. 相等提供真实见证；充分范围中无相等就不存在非负整数解，因此拒绝正确。 **解释最终答案** 有界过程判定平方数成员资格，更紧上界可提速但不改答案。 **检验推理** n=1时包含x=1，漏掉上端点会错误拒绝边界例。 ### Leon 的进一步思考 **证明要涵盖全部终止** 十条轨迹停只证明十例。覆盖每个允许输入的上界或下降度量才补全一般论证。 **限制可能使搜索有限** 若证明可计算有限上界足够，无界见证搜索可变判定器。上界须来自问题，而非任意超时。 **注意这个边界:** 不能由超时推非成员，也不能因某算法循环就推不可判定。
检查自己的理解 识别器可拒绝某些非成员、却在其他非成员上循环吗？ 可以。语言外两种行为都允许，唯独不能接受。
## 为什么通用停机测试不可能 ### 01 / 从一个故事开始 想象目录声称分类每个可能检查目录的程序，包括读取自己条目的程序。一个调皮程序可查看对自己的预测，再故意反着做。若目录总正确且总回答，自指就产生矛盾。问题不是太慢或内存少，而是完整过程能否存在。真实分析工具仍有用，因为可限制程序类型、允许未知，或只保证部分问题而非回答所有程序的一切。 ### 02 / 理解原理 假设全停机算法 H 能判定任意编码机器在任意输入是否停机。构造 D：输入机器描述x，问 H(x,x)；若答是就永远循环，若答否就停机。让 D 读取自己的描述，两答案都与行为矛盾，因此不存在全正确且全停机的 H。 停机语言仍可识别：模拟直到任何停机结果。接受问题也可识别却不可判定。相关对角语言为不接受自身描述的机器描述，它不可识别，因为任何候选识别器都会在自身描述上与定义冲突。形式证明要一致处理编码与坏输入。 ### 03 / 逐项读懂公式 ```text HALT = {⟨M,w⟩ : M 在 w 上停机} D(x)：若 H(x,x)=是 则循环，否则停机 ``` H 为假设判定器，因此每个合法对都必须返回。x 编码机器，同时也可作为该机器输入。D 是使用 H 的有限程序。代入 x=⟨D⟩ 强制矛盾。HALT 包含接受及拒绝两种停机，不同于只计接受计算的语言。 ### 04 / 先看一个完整例子 若 H 预测 D 在 ⟨D⟩ 上停机，D 见是后故意循环，预测错。若 H 预测不停机，D 见否后立即停止，仍错。两情况穷尽判定器布尔答案。允许第三答案“未知”避开矛盾，却不再判定原问题。限制固定步数的程序也可有界模拟，但这是另一输入类别。 ### 先认识这些词 - **不可判定:** 没有算法对每允许输入都停机并答对。 - **对角化:** 利用构造自身描述强制产生分歧。 - **全停机算法:** 保证在定义域每输入上停机的算法。 ### 一步步想清楚 **对 H 假设什么？** 它对每合法机器输入对都正确回答且总停机。 **预测是后 D 做什么？** 故意循环，反驳其会停的预测。 **未知能避开矛盾吗？** 可以，但 H 就不是覆盖全部输入的判定器。 ### 补全自指两种情况 假设 H 是全正确全停机判定器。D(x) 在 H(x,x)=是时循环，为否时停。分析 H(⟨D⟩,⟨D⟩)。 **先选择方法** 穷尽两种布尔答案，不猜实际是哪种。 1. 若 H 答是，预测 D 在自身描述停；但 D 的是分支永远循环。 2. 若 H 答否，预测 D 不停；但 D 的否分支立即停。 3. 因 H 全停机，必须返回两者之一，而两者都违反正确性，因此初假设失败。 **解释最终答案** 不存在适用于任意编码程序与输入的全正确全停机判定器 H。 **检验推理** 若 H 可不返回，第三步就不可用。证明针对完整判定器，不针对部分工具。 ### 有界问题可判定 给有限机器描述 M、输入 w、非负整数 B，判定 M 是否至多 B 次转移内停机。包括 B=0。 **先选择方法** 给定有限界允许完整模拟到该界，只回答有界问题。 1. 检查初始配置，若已是指定停机配置，即使 B=0 也答是。 2. 否则最多执行 B 次合法转移，每步后查停机，出现则答是。 3. 若检查配置都不停，则对“B内”答否。计数器限制模拟，所以过程自身停机。 **解释最终答案** 有界停机可判定。否表示界内没停，不表示永远不停。 **检验推理** 在 B+1 步停的机器被有界问题正确拒绝，却属于无界 HALT。 ### Leon 的进一步思考 **别混淆停机与接受** 停机拒绝也属于 HALT。因此 HALT 识别器在任一种模拟停机后都应接受，不仅模拟接受时。 **有用工具仍然可能** 检查器可对有下降整数计数器的受限循环语言证明终止，这不违反涵盖任意程序的定理。 **注意这个边界:** 定理不表示程序永远不能证明其他程序会停。它只排除适用于所有程序输入的完整、总正确判定器。
检查自己的理解 证明为什么要求 H 每输入都停止？ D 须收到 H 答案才选择相反行为。若 H 可循环或答未知，就没有完整判定过程。
## 交错模拟与补语言 ### 01 / 从一个故事开始 两位调查员分别寻找同一主张的真证书与假证书。若让第一位一直独占直到完成，第二位可能永无机会。改给交替时段，只要其中一位保证迟早找到相应证书，就能获得结论。这叫交错模拟。它不会凭空造证书，力量来自每个输入恰属于两个可搜索方面之一。 ### 02 / 理解原理 可判定语言对补、并、交封闭，因为判定器总结束。交换接受与拒绝即可补判定器。可识别语言对并、交封闭，却不保证对补封闭。并可公平模拟两个识别器，任一接受就接受；若顺序等第一台，可能卡住而错过第二台成功。交则等两台都接受，公平模拟可作为统一构造。 语言可判定当且仅当它与补都可识别。反向证明交错两识别器，必有一个最终接受，从而确定答案。因此可识别却不可判定语言的补不能也可识别。 ### 03 / 逐项读懂公式 ```text L 可判定 ⇔ L 与 Σ*∖L 都可识别 并识别器：R₁ 或 R₂ 接受就接受 交识别器：两者都接受后接受 ``` Σ* 固定输入宇宙，补含全部不在 L 的串。R₁、R₂ 各有独立模拟配置。公平模拟让每个未完成过程获得无限多机会，例如每次各一步。可保存已接受标志。非成员上组合识别器仍可能永远运行，这不违反识别定义。 ### 04 / 先看一个完整例子 Ryes 识别 L，Rno 识别其补。输入 z 上，Ryes 永远循环，Rno 在37步接受。先等 Ryes 的顺序策略永无答案。每台交替一步，至多74个模拟步就看到 Rno 接受，组合过程拒绝 z。若 z∈L，Ryes 保证接受，因此总停机。保证依赖互补语言，两项无关搜索可同时永远不结束。 ### 先认识这些词 - **交错模拟:** 公平分配模拟步，避免一过程永远等另一过程。 - **补语言:** 允许输入宇宙中不属于该语言的全部串。 - **接受标志:** 记录某模拟已接受的事实。 ### 一步步想清楚 **为什么不先跑完一识别器？** 它可能在该输入永不结束，阻止另一台找到见证。 **交识别器要记什么？** 各组件是否已接受，两个标志都真才接受。 **互补识别器为何给判定器？** 每输入恰属于一侧，该侧识别器保证最终接受。 ### 统计公平模拟步 Ryes 识别L，Rno识别补。w上Ryes循环，Rno自身第五步接受。按Ryes再Rno各一步交替，求组合何时回答。 **先选择方法** 给全局模拟步编号，跟踪各步归谁。 1. 全局1,3,5,7,9归Ryes，不终止其搜索。 2. 全局2,4,6,8,10是Rno第一至第五步，第10步它接受。 3. 补识别器接受证明w∉L，因此组合机器立即拒绝。 **解释最终答案** 判定器在10个组件模拟步后拒绝，不计调度额外工作。 **检验推理** 若先等Ryes，则即使证书仅需五步，也永远不会执行Rno。 ### 为什么补不能也可识别 假设L可识别却不可判定。反证假设其补有识别器C，不假设任一识别器对所有输入停机，推出矛盾。 **先选择方法** 用公平调度与成员互斥性组合两个部分成功过程。 1. 对同输入交替运行L的识别器R与补识别器C。 2. 输入属于L时R最终接受，否则C最终接受，二者都不能在错误侧接受。 3. R接受则接受，C接受则拒绝，因此每输入都获得正确且终止答案。 **解释最终答案** 这构造L判定器，与前提矛盾，因此补不可识别。 **检验推理** 可判定语言则无矛盾：两侧均有判定器，因此均有识别器。 ### Leon 的进一步思考 **公平是一项算法保证** 每个活跃过程轮流一步就足够。只说两者都试不完整，因为实现可能不给一方后续机会。 **拒绝并非补识别器已就绪** 识别器可能拒绝部分外部输入却在其他上循环。仅复用拒绝行为不能覆盖补的每个成员。 **注意这个边界:** 交换识别器停机标签不能求补，其无限计算仍无限，不会让所有原非接受输入变接受。
检查自己的理解 L 可识别且不可判定时，其补怎样？ 补不可识别，否则两侧识别器交错就能判定 L，与不可判定矛盾。
## 命题语法与真值 ### 01 / 从一个故事开始 实验室警报板组合门开、风扇开、温度超限等信号。连线说明怎样组合，当前开关值决定警报值。逻辑将两层区分为语法与语义。括号像接线，改变它可能改变结果。模型假设信号有明确真假，并不自动表示测量不确定或因果，因此逻辑蕴含不能当作传感器间物理机制。 ### 02 / 理解原理 命题公式由原子与否定、合取、析取等联结词组成。赋值给每原子布尔值，再按解析树递归算公式值。除非声明异或，析取是包含式。实质蕴含 P→Q 只在P真Q假时为假，P假时为真。 有至少一赋值使真称可满足，每赋值都真称有效，没有真赋值称不可满足。k个原子的完整真值表有2ᵏ行，给有限判定法，但赋值数指数增长，单行容易不代表整体便宜。 ### 03 / 逐项读懂公式 ```text P→Q ≡ ¬P∨Q F 可满足：∃α，α(F)=1 F 有效：∀α，α(F)=1 ``` P、Q为公式，F为待查公式，α为原子真值赋值，α(F)递归扩展到全公式。∃为存在，∀为每个，1表示真。蕴含等价式只定义真值行为，不表示P导致Q，也不要求Q与P相关。 ### 04 / 先看一个完整例子 设p为样本冷藏，q为封口完整，F=p→q。(假,假)、(假,真)、(真,真)都满足，只有(真,假)使假，所以可满足而非有效。再要求p，得p∧(p→q)，唯一满足为p=q=真。再要求¬q就无赋值而不可满足。推理排除配置，不是在说冷藏物理上确保封口。 ### 先认识这些词 - **真值赋值:** 为每原子命题选择真或假。 - **可满足:** 至少一个赋值下真。 - **有效公式:** 每个赋值下真。 ### 一步步想清楚 **三原子为何八行？** 各有两选择，2×2×2=8赋值。 **p→q何时假？** 恰在p真q假时。 **可满足公式还能某处假吗？** 能。可满足只需一真行，有效才要求全部真。 ### 分类受限制蕴含 原子p,q，分类F=(p→q)∧¬q为可满足、有效或不可满足，使用四赋值。 **先选择方法** 合取先强制¬q，再检查剩余行的蕴含。 1. q真时¬q假，因此p两选择都使F假。 2. q假p真时p→q假，因此F假。 3. q假p假时p→q真且¬q真，因此F真。 **解释最终答案** 仅(p,q)=(假,假)满足。F可满足但不有效。 **检验推理** 改写为(¬p∨q)∧¬q，在¬q下化为¬p∧¬q，核对结果。 ### 统计包含式或的模型 F=(p∨q)∧r，有三个独立布尔原子，或为包含式，统计满足赋值。 **先选择方法** 将被强制的r与允许的p,q对分开。 1. 合取要求r真，四个r假赋值全失败。 2. r真时p∨q接受(真,假)、(假,真)、(真,真)，不接受(假,假)。 3. 一个r选择配三个对，得1×3=3模型，总赋值2³=8。 **解释最终答案** F有三个满足赋值，可满足但不有效。 **检验推理** 若或改为异或，则去掉同时真对，模型数降二。 ### Leon 的进一步思考 **从内向外求值** 先算括号子公式，再算父联结词，可防止把长公式按自然语句意外分组。 **经典蕴含不是因果** 真蕴含只排除前提真结论假组合，不解释事件成因，也不给概率。 **注意这个边界:** “p only if q”应为p→q，不是q→p；only if给必要条件。
检查自己的理解 p∨¬p只是可满足还是有效？ 在经典二值语义下有效：p真或p假而¬p真。
## 逻辑等价与安全改写 ### 01 / 从一个故事开始 两警报电路外观不同，却可能在每种输入设置下都亮相同灯。一次测试只证明一次一致，等价要求全部一致。代数改写可不看外观而证明一致。替换法须匹配完整子电路，逻辑等价也作用于完整子公式。类比适于布尔行为，但转为有状态表达式的程序时，等价公式不保证求值成本或副作用相同。 ### 02 / 理解原理 F与G在每真值赋值下相同称逻辑等价。它允许在更大公式内用等价子公式替换而不改整体真值。常用双否定、De Morgan、分配、吸收、消蕴含等规则。真值表检查所有行可证明，一条差异行可推翻。 F↔G是在一个赋值下有真值的公式；F≡G是对全部赋值的元层断言。双条件有效当且仅当两侧等价。仅改排符号或给少量例子不足以证明语义关系。 ### 03 / 逐项读懂公式 ```text F ≡ G ⇔ ∀α, α(F)=α(G) ¬(F∧G) ≡ ¬F∨¬G F→G ≡ ¬G→¬F ``` α遍历涉及原子的全部赋值。≡陈述公式间关系，∧、∨、¬、→构造公式。最后一律为逆否：反转箭头并否定两侧，不能只反转。改写时要找完整匹配子公式，保留周围分组。 ### 04 / 先看一个完整例子 化简F=¬(p∨¬q)。用De Morgan得¬p∧¬¬q，再双否定得¬p∧q。p假q真时两式真，但单行不是证明，规则保证四行全部一致。比较p→q与q→p，p假q真时前真后假，立即推翻等价。正确反向等价式是¬q→¬p，仍排除p真q假。 ### 先认识这些词 - **等价:** 每个赋值下真值一致。 - **逆命题:** 将P→Q反转为Q→P。 - **逆否命题:** 与P→Q等价的¬Q→¬P。 ### 一步步想清楚 **一差异行为何确定不等价？** 等价要求每行，一次失败就推翻。 **¬(p∧q)怎样分配？** 否定两侧并将合取换析取，得¬p∨¬q。 **反转蕴含会保留它吗？** 逆否还须否定两侧，仅逆命题通常不同。 ### 化简嵌套否定 用等价律化简F=¬(p∧¬q)，并在p真q假时求两式值。 **先选择方法** 先将外否定推过合取，再删双否定。 1. De Morgan得¬p∨¬¬q，因为否定将∧换∨。 2. 双否定将¬¬q化为q，得¬p∨q。 3. p真q假时原内部p∧¬q真，F假；改写式假∨假也假。 **解释最终答案** F≡¬p∨q≡p→q。样本行一致，而规则证明全行等价。 **检验推理** p假时改写式无论q都真，符合原式否定假合取。 ### 推翻诱人的反转 比较F=p→q与G=q→p，给反赋值，再写F正确等价反向式。 **先选择方法** 寻找一侧前件假，另一侧真前件假结论的行。 1. 取p假q真，F因前件p假而真。 2. G因q真p假而假，因此两式此行不同。 3. 反转同时否定两侧得¬q→¬p，与F同样仅在p真q假时为假。 **解释最终答案** 逆命题不等价，逆否¬q→¬p等价。 **检验推理** p=q=真时两者碰巧都真，但该一致行不能修复反例。 ### Leon 的进一步思考 **子公式边界重要** ¬(p∨q)∧r中否定只覆盖p∨q。De Morgan改写不能改外层与r的合取。 **程序副作用需另行处理** 纯布尔等价不保证函数调用顺序或次数相同，逻辑假设原子已具有固定真值。 **注意这个边界:** p→q与q→p通常不同。逆否既反转也否定两侧。
检查自己的理解 某赋值下F↔G真就能推出F≡G吗？ 不能。等价要求每赋值下双条件都真，一行只证明局部一致。
## 命题逻辑的范式 ### 01 / 从一个故事开始 仓库检查员有一组必须全部通过的清单，每份清单允许若干替代条件。这个“每组至少一个、全部组都满足”的形状就是合取范式。换成统一形状方便算法处理，却可能重复很多内容。范式并不意味着唯一、最短或最容易读。 ### 02 / 理解原理 否定范式只用合取、析取，并把否定放在原子前。先消去蕴含与双条件，再用 De Morgan 律把否定向内推。合取范式是若干子句的合取，每个子句是文字的析取。把析取分配到合取上可得到它，但表达式可能指数增长。单个文字也可作为子句。 这里的命题 CNF 与文法的 Chomsky 范式是不同概念。SAT 转换有时引入新变量以避免膨胀；这通常保证可满足性对应，不能直接说新旧公式在同一组变量上等价。 ### 03 / 逐项读懂公式 ```text F∨(G∧H) ≡ (F∨G)∧(F∨H) CNF = C₁∧⋯∧Cₘ，每个 Cᵢ 是若干文字的析取 ``` F、G、H 可以是复合公式。Cᵢ 是第 i 个子句，m 是子句数。文字是 p 或 ¬p，不是带否定的任意复合式。分配方向决定得到合取范式还是析取范式。若出现空合取或空析取，须先声明约定。 ### 04 / 先看一个完整例子 把 p→(q∧r) 写成 ¬p∨(q∧r)，再分配得到 (¬p∨q)∧(¬p∨r)。p 假时两子句自动成立，p 真时必须 q、r 都真。式子 (p∧q)∨r 当前不是合取范式，但可改写为 (p∨r)∧(q∨r)；判断当前语法形状与判断能否转换是两回事。 ### 先认识这些词 - **文字:** 原子或单个原子的否定。 - **子句:** 文字的析取，例如 p∨¬q。 - **合取范式:** 子句的合取，每条子句都须成立。 ### 一步步想清楚 **p 是子句吗？** 是，单个文字是一文字子句。 **¬(p∨q) 是否是否定范式？** 不是，改为 ¬p∧¬q 将否定移到原子前。 **转换一定缩短公式吗？** 不一定，分配可能重复子公式并大幅增大长度。 ### 转换带替代条件的规则 用普通二值逻辑将 (p∧q)→r 转为合取范式，不引入新变量。 **先选择方法** 消去蕴含，再把否定向内推。 1. A→B 等于 ¬A∨B，故得到 ¬(p∧q)∨r。 2. De Morgan 将 ¬(p∧q) 改为 ¬p∨¬q。 3. 结合律得到一个子句 ¬p∨¬q∨r，已是合取范式。 **解释最终答案** 合取范式为 ¬p∨¬q∨r，仅禁止 p、q 真而 r 假。 **检验推理** 这恰是原规则真前提、假结论的情况。 ### 分配两组条件 将 (p∧q)∨(r∧s) 转为合取范式，数子句，并在 p 真、q 假、r 真、s 真时求值。 **先选择方法** 每次分配一个合取，保留全部配对。 1. 先得到 [p∨(r∧s)]∧[q∨(r∧s)]。 2. 分别分配得 (p∨r)∧(p∨s)∧(q∨r)∧(q∨s)。 3. 共有四条子句。给定赋值下因 r、s 都真，每条都真。 **解释最终答案** 四子句合取范式为真，与原式右边合取为真一致。 **检验推理** p=r=假时 p∨r 子句假，原式两合取也都假。 ### Leon 的进一步思考 **把合取范式读成清单** 一个真文字满足所在子句，不会自动满足所有子句。在 (p∨q)∧r 中令 p 真仍须满足 r。 **新变量改变比较方式** 若用新变量 z 代表 p∧q，须用子句约束两者关系。保可满足性问是否存在合适 z，不是每个 z 都与原式一致。 **注意这个边界:** 不要把合取范式与析取范式混淆。子句不一定恰有三个文字。
检查自己的理解 ¬(p∧q) 已是否定范式吗？ 不是，否定作用于复合式。改写 ¬p∨¬q 后是否定范式，也是一条子句组成的合取范式。
## 逻辑后承与反模型 ### 01 / 从一个故事开始 审查员问：只要所有前提都成立，结论就一定成立吗？一份所有前提真而结论假的记录，就足以推翻这种保证。这叫反模型。如果前提本来就相互矛盾，没有任何记录能同时满足它们，那么所有结论都会在形式上空泛成立。 ### 02 / 理解原理 Γ 在语义上蕴涵 F，指每个满足 Γ 中全部公式的赋值也满足 F。对有限前提，可以把它们与 ¬F 合取；若不可满足，推理有效。若可满足，该赋值就是反模型。有效性不保证现实中的前提为真；某次结论碰巧为真也不证明推理有效。 肯定前件与否定后件是有效规则。肯定后件、否定前件一般无效。后承有方向；等价则要求两个方向都成立。 ### 03 / 逐项读懂公式 ```text Γ ⊨ F ⇔ 不存在同时满足 Γ 中全部公式及 ¬F 的赋值 {P→Q, P} ⊨ Q ``` Γ 是公式集合，⊨ 表示语义后承。满足 Γ 要求其每个公式都真。第二式是肯定前件：P→Q 与 P 推出 Q。⊨ 是公式之间的元层关系，不是一个原子。前提有限时才直接写成有限合取。 ### 04 / 先看一个完整例子 设 p 为文件通过验证，q 为文件被接受。p→q 与 q 不能推出 p：p 假、q 真使两个前提真而结论假，文件或许通过另一条途径被接受。若把前提 q 改成 ¬q，则可推出 ¬p；因为 p 真会与规则一起迫使 q 真，与已知 ¬q 冲突。 ### 先认识这些词 - **前提:** 检查推理时暂时假定为真的陈述。 - **反模型:** 全部前提真而结论假的赋值。 - **后承:** 在前提的每个模型中都为真的结论。 ### 一步步想清楚 **前提现实中为假会令推理形式无效吗？** 不会，有效性考察所有前提成立时能否保真。 **怎样用可满足性检查后承？** 寻找前提与结论否定一起的满足赋值。 **为何一个反模型就够？** 后承要求前提的每个模型都成功。 ### 连接两条蕴含 经典命题逻辑中，p→q、q→r、p 是否推出 r？ **先选择方法** 假设所有前提真，逐步传播其必需后果。 1. 第三前提使 p 真。 2. p→q 真且 p 真，故 q 必真，否则蕴含失败。 3. q→r 真且 q 真，故 r 必真，不可能有反模型。 **解释最终答案** 能，通过两次肯定前件推出 r。 **检验推理** p=q=r=真满足前提，故并非不一致前提造成的空泛结果。 ### 检验否定前件 p→q 与 ¬p 能推出 ¬q 吗？若可行请构造反模型。 **先选择方法** 先使拟议结论假，再看前提是否仍成立。 1. 要使 ¬q 假，令 q 真。 2. 要满足 ¬p，令 p 假。 3. p 前件假使 p→q 真。两前提都成立，但 ¬q 失败。 **解释最终答案** 不能。p 假、q 真是反模型；规则没有说 p 是 q 的唯一途径。 **检验推理** 该赋值确实满足 p→q，因为没有真前件假结论。 ### 找出全部反模型 穷举两个布尔原子，检查 p→q 是否推出 p∨q。 ```python from itertools import product rows = [] for p, q in product([False, True], repeat=2): premise = (not p) or q conclusion = q or p if premise and not conclusion: rows.append((p, q)) print("Countermodels:", rows) assert rows == [(False, False)] ``` **在本地运行** ```sh python logical-consequence-entailment-countermodels.py ``` **预期输出** ```text Countermodels: [(False, False)] ``` **按执行顺序理解** 1. 枚举（假，假）、（假，真）、（真，假）、（真，真）。 2. 在（假，假）下蕴含真，而 p∨q 假。 3. 其他三行都不是反模型；保存的一个值对足以推翻后承。 **逐步读懂代码** product 生成 p 与 q 的全部四种组合。for 循环把每对值分别赋给两个变量。Python 的 not 表示否定，or 表示包含“两者都真”的析取，因此 (not p) or q 表示蕴含。 if 只保留前提真而结论假的行。append 把该值对加到列表，print 显示完成的列表，assert 检查预期结果。这个有限穷举只检验此推理；原子更多时所需行也更多。 ### Leon 的进一步思考 **利用结论指导寻找** 反驳 Γ⊨p∨q 时先令 p=q=假，这是结论失败的唯一方式，再检查前提能否仍真。 **区分一致性与有效性** 在把 p 与 ¬p 推出的结论当作有用知识前，先检验前提是否有模型。逻辑有效性本身不回答这个不同问题。 **注意这个边界:** 不要只检查结论为真的赋值。反模型必须令全部前提真、结论假。
检查自己的理解 p 与 ¬p 能推出 q 吗？ 能，形式语义上是空泛成立：没有赋值同时满足两个前提。这不代表这些前提一致或有用。
## 谓词、量词与作用域 ### 01 / 从一个故事开始 每位学徒都有导师，与有一位导师指导所有学徒，不是同一句话。第一句允许不同学徒选择不同导师，第二句要求同一人胜任。要判断真假，必须说明讨论哪些对象，以及指导关系具体有哪些。符号能帮助我们保留这些容易被日常语言隐藏的差别。 ### 02 / 理解原理 谓词逻辑让变量在明确的非空论域中取对象。∀ 表示每个对象，∃ 表示存在见证。“所有 A 都是 B”写为 ∀x(A(x)→B(x))；“有些 A 是 B”写为 ∃x(A(x)∧B(x))。不同量词的顺序决定后面的见证是否可依赖前面的对象。否定量词时交换 ∀ 与 ∃，并否定其内部公式。 量词有作用域，作用域外的同名变量不因此被约束。自由变量需要额外赋值。跨公式移动量词须检查该变量是否在另一部分自由出现；必要时先重命名约束变量，避免捕获。 ### 03 / 逐项读懂公式 ```text ∀x∃y M(x,y) 与 ∃y∀x M(x,y) ¬∀x F ≡ ∃x ¬F; ¬∃x F ≡ ∀x ¬F ``` M(x,y) 表示 y 指导 x。x、y 在同一指定论域内取值。∀x∃y 允许 y 随 x 改变；∃y∀x 要求同一个 y 对所有 x 有效。F 是量词的内部公式，可能含 x。否定规则不改变其他自由变量。括号明确量词覆盖范围。 ### 04 / 先看一个完整例子 论域为 Ada 与 Ben，且只有两条关系：Ada 指导 Ben，Ben 指导 Ada。每个人都有导师，所以 ∀x∃y M(x,y) 真；无人指导自己，所以不存在指导所有人的同一个导师，∃y∀x M(x,y) 假。 第一句的否定为 ∃x∀y¬M(x,y)，即有人完全没有导师。“并非每位学徒都获认证”是 ∃x(Apprentice(x)∧¬Certified(x))；仅写 ∃x¬Certified(x) 可能找到了非学徒。 ### 先认识这些词 - **论域:** 变量可以指向的非空对象集合。 - **见证:** 使存在陈述为真的对象。 - **作用域:** 受某个量词或联结词管辖的公式部分。 ### 一步步想清楚 **∀x∃y 的见证可不同吗？** 可以，每次选定 x 后，合适 y 可依赖它。 **怎样否定 ∃xP(x)？** 写为 ∀x¬P(x)，每个候选对象都不满足性质。 **所有 A 都是 B 为何用蕴含？** 只要求 A 对象通过 B 检查，非 A 对象不受此要求。 **能交换这两个量词而不改变命题吗？** 一般不能。给定关系让“全称—存在”为真、“存在—全称”为假，是二者等价这一主张的反模型。 ### 会改变的见证 论域 {1,2,3}，R(x,y) 表示 x≠y。求 ∀x∃yR(x,y) 与 ∃y∀xR(x,y) 的真假。 **先选择方法** 第一式给每个 x 找见证，第二式用全部 x 检验固定 y。 1. x=1 选 y=2；x=2 选 y=1；x=3 选 y=1。每个 x 都有不同伙伴。 2. 对任何固定 y，全称 x 都包括 x=y。 3. x=y 时 R 假，故没有一个 y 能通过全部三个 x 检查。 **解释最终答案** 第一式真，第二式假，交换不同种类量词会改变意义。 **检验推理** 不等有序对有六个，三个对角对缺失；每行有见证，每列有失败。 ### 否定全称类别规则 学生为 {A,B,C}，Pass(A) 真、Pass(B) 假、Pass(C) 真。翻译并判断“并非每位学生通过”。假设论域只有学生。 **先选择方法** 否定全称量词，再找具体失败学生。 1. 每位学生通过是 ∀xPass(x)，论域已将 x 限制为学生。 2. 否定得到 ¬∀xPass(x)≡∃x¬Pass(x)。 3. 选 x=B，Pass(B) 假，故 ¬Pass(B) 真，B 是所需见证。 **解释最终答案** 陈述为真，表示至少一人失败，不表示所有人都失败。 **检验推理** A、C 通过，故更强的 ∀x¬Pass(x) 为假。 ### 否定并检验量词命题 使用代码中的三名学生、两名导师。否定“每个学生都有导师”，再判断删除 (Bo,Noah) 后否定命题是否成立。 **先选择方法** 把否定依次推进各量词，再寻找具体见证。 1. ¬∀x∃yR(x,y) 变成 ∃x¬∃yR(x,y)。 2. ¬∃y 变成 ∀y¬，得到 ∃x∀y¬R(x,y)。 3. 删除后，R(Bo,Ivy)、R(Bo,Noah) 都为假，选择 x=Bo。 **解释最终答案** 删除后否定命题为真，Bo 是见证。 **检验推理** 删除前每个学生的见证列表非空，因此否定命题为假。 ### 在有限模型中寻找见证与反例 社团的每个学生都有导师。米娜听完，以为存在一位导师指导所有学生。一个小表就推翻了这个想法：Ana、Cy 跟 Ivy，Bo 跟 Noah。每个学生都有人指导，却没有一个导师覆盖三人。米娜用嵌套循环把两个量词的顺序具体展示出来。 ```python students = ["Ana", "Bo", "Cy"] mentors = ["Ivy", "Noah"] relation = {("Ana", "Ivy"), ("Bo", "Noah"), ("Cy", "Ivy")} def inspect(students, mentors, relation): witnesses = {x: [y for y in mentors if (x, y) in relation] for x in students} every_has_someone = all(witnesses[x] for x in students) shared = [y for y in mentors if all((x, y) in relation for x in students)] uncovered = [x for x in students if all((x, y) not in relation for y in mentors)] assert bool(uncovered) == (not every_has_someone) return witnesses, every_has_someone, shared, uncovered witnesses, every, shared, uncovered = inspect(students, mentors, relation) print("witnesses:", witnesses) print("every student has a mentor:", every) print("one mentor for everybody:", bool(shared)) assert every and not shared broken = relation - {("Bo", "Noah")} print("counterexample after removal:", inspect(students, mentors, broken)[3]) assert inspect([], mentors, relation)[1] is True assert inspect(students, [], relation)[1] is False ``` **在本地运行** ```sh python predicate-logic-finite-witness-search.py ``` **预期输出** ```text witnesses: {'Ana': ['Ivy'], 'Bo': ['Noah'], 'Cy': ['Ivy']} every student has a mentor: True one mentor for everybody: False counterexample after removal: ['Bo'] ``` **按执行顺序理解** 1. 为每位学生建立见证列表；内层存在量词可以为不同外层学生选择不同导师。 2. 寻找共同导师时反过来：先选一个导师，再要求他覆盖每位学生。 3. 若某学生对所有候选导师都不满足关系，他就是未被覆盖者；这会构造否定命题的见证，而不只是打印 False。 4. 检查空集合情形。没有学生时全称命题为真；有学生却没有导师时，原命题为假。 **逐步读懂代码** 设 S 为学生集合、M 为导师集合，R(x,y) 表示 y 指导 x。第一个命题是“对每个 x∈S，存在 y∈M，使 R(x,y)”；第二个是“存在 y∈M，对每个 x∈S 都有 R(x,y)”。共同见证能证明第二个，进而证明第一个；各自的见证只能证明第一个。 否定第一个命题得到：“存在 x∈S，使每个 y∈M 都不满足 R(x,y)”。删掉 Bo–Noah 后，Bo 就成为这个反例。|S| 名学生、|M| 名导师的直接检查需要 O(|S||M|) 次关系查询，这里假定集合查询平均 O(1)。 程序检查的是一个指定的有限解释。在一张表上成立，并不证明公式在所有解释中都有效，也不能解决任意一阶逻辑有效性。论域假设应写在题目中，不能遇到不想要的结果后再临时改变空集规则。 ### Leon 的进一步思考 **展开有限论域检验含义** 论域 {1,2} 上，∀xP(x) 等于 P(1)∧P(2)，∃xP(x) 等于 P(1)∨P(2)，将量词连到熟悉的命题运算。 **检查非空论域中的空类别** 若没有对象是龙，∀x(Dragon(x)→Blue(x)) 为真。它不表示有龙；存在性须另加 ∃xDragon(x)。 **注意这个边界:** 所有 A 都是 B 不是 ∀x(A(x)∧B(x))。后者要求论域每个对象同时是 A 与 B。
检查自己的理解 (∀x P(x))∧Q(x) 中 Q 的 x 被前面量词约束了吗？ 没有，Q(x) 在该量词括号之外。它的 x 是自由变量，需要赋值。
## 继续探索 - [MIT OpenCourseWare — Automata, Computability, and Complexity](https://ocw.mit.edu/courses/6-045j-automata-computability-and-complexity-spring-2011/) - [Boaz Barak — Universality and uncomputability](https://introtcs.org/public/lec_08_uncomputability.html) - [Berkeley AI textbook — First order logic](https://inst.eecs.berkeley.edu/~cs188/textbook/logic/first-order-logic.html) - [Boaz Barak — Automata and regular expressions](https://introtcs.org/public/lec_05_infinite.html) - [Cornell — Regular expressions and finite automata](https://www.cs.cornell.edu/courses/cs312/2007fa/recitations/rec26.html) - [Cornell CS 4120: Grammars and ambiguity](https://courses.cs.cornell.edu/courses/cs4120/2026sp/notes.html?id=grammars) --- Leon