第2章 思考能够写成规则吗
两个人争论一件事，常会遇到一种奇怪局面：他们说的每句话都像有道理，结论却彼此冲突。
有人说：“如果机器能通过考试，它就理解了课程。这台机器通过了考试，所以它理解了课程。”另一个人反驳：“它只是记住了题目。”争论中至少混着三个问题：第一句话是否成立，“通过考试”是否真的足以推出“理解课程”；这台机器是否确实通过了合格的考试；如果两个前提都接受，结论是否按规则推出。
逻辑首先把第三个问题单独取出来。它暂时不问前提是否符合现实，而问：假如前提都成立，结论能否必然成立？
这个看似克制的选择，为机械推理打开了一条道路。机器不需要理解考试、课程或机器是什么，只要符号形式相同，就能检查推理结构。
从句子含义中抽出骨架
看一个古老的例子：
所有人都会死。
苏格拉底是人。
所以，苏格拉底会死。把“人”“会死”和“苏格拉底”替换成其他词，只要关系保持不变，推理仍然有效：
所有 A 都是 B。
x 是 A。
所以，x 是 B。这就是形式化的第一步：忽略句子的部分具体含义，保留决定推理是否有效的结构。
形式化带来两种力量。
第一，同一规则可以用于不同内容。检查程序不必为苏格拉底、鲸鱼和三角形分别发明推理方法。
第二，每一步可以公开检查。结论不依赖说话者的威望或直觉，而依赖前提与规则。
代价也随之出现。自然语言中的“所有”“通常”“可能”“应该”和“因为”并不总能无损地塞进同一套符号。形式化不是把现实完整搬进公式，而是选择某些关系，暂时忽略其他关系。
命题：先把一句话看成真或假
在命题逻辑（propositional logic）中，一个命题是在给定解释下可以被赋予真或假的陈述。用字母表示完整命题：
P：设备正在通电。
Q：指示灯亮起。逻辑连接词把命题组合起来：
- \(\lnot P\)：并非 \(P\)；
- \(P\land Q\)：\(P\) 并且 \(Q\)；
- \(P\lor Q\)：\(P\) 或者 \(Q\)；
- \(P\rightarrow Q\)：如果 \(P\)，那么 \(Q\)。
其中，“或”通常采用包容含义：至少一个为真，也允许两个都真。这里的条件式称为材料蕴含；按它的真值定义，只有 \(P\) 为真而 \(Q\) 为假时，\(P\rightarrow Q\) 才是假。
| \(P\) | \(Q\) | \(P\land Q\) | \(P\lor Q\) | \(P\rightarrow Q\) |
|---|---|---|---|---|
| 真 | 真 | 真 | 真 | 真 |
| 真 | 假 | 假 | 真 | 假 |
| 假 | 真 | 假 | 真 | 真 |
| 假 | 假 | 假 | 假 | 真 |
最后两行常让初学者不习惯。日常语言中的“如果”可能暗示因果、时间或承诺，材料蕴含却只规定真值关系。如果设备根本没有通电，“如果设备通电，指示灯就亮”不会被一个不亮的灯直接推翻。
真值表的意义，在于把连接词变成有限、机械的操作。只要给出 \(P\) 和 \(Q\) 的真假，机器无需理解句子内容就能算出复合命题的真假。
推理规则：从什么可以走到什么
最常见的推理形式之一叫肯定前件（modus ponens）：
\[ \frac{P\rightarrow Q \qquad P}{Q} \]
横线上方是已接受的前提，下方是允许推出的结论。
例如：
如果温度低于零度，水管有冻结风险。
温度低于零度。
所以，水管有冻结风险。如果两个前提为真，结论就不能为假。这叫推理形式有效。
但有效不等于结论在现实中一定正确：
如果月亮由奶酪构成，夜晚会有奶酪味。
月亮由奶酪构成。
所以，夜晚会有奶酪味。推理形式仍然有效，问题在于前提是假的或没有根据。逻辑保证的是“真前提不会沿这条规则导出假结论”，不负责替我们观察月亮。
核心机制：把两类错误分开
逻辑错误可能来自推理步骤无效，也可能来自前提不真实、不完整或表达错误。一个规则系统即使每一步都正确，也可能因为输入知识错误而得到错误结论。
这个区分后来对 AI 极其重要。专家系统可能拥有可靠推理引擎，却装载了过时规则；语言模型可能给出正确形式，却引用了虚构事实；检索系统可能找错文档，后续计算再精确也无济于事。
布尔：让逻辑进入代数
19 世纪中叶，乔治·布尔试图用代数研究思维规律。他把逻辑类别和运算写成符号，使推理能够像代数式那样变换。1854 年出版的《思维规律研究》系统展开了这项工作。(Boole 1854年)
在现代布尔代数中，变量通常取两个值 \(0\) 和 \(1\)，可以对应假与真、断与通、低电平与高电平。逻辑“与”“或”“非”变成明确运算。
例如，只有安全门关闭 \(S=1\) 且启动按钮按下 \(B=1\) 时，机器才运行：
\[ R=S\land B \]
这条关系既能作为逻辑命题，也能成为电路设计条件。布尔本人面对的还是符号推理；几十年后，香农会把布尔代数与继电器开关连接起来，让逻辑形式直接进入电气机器。
形式逻辑在这里跨过了一个关键门槛：推理不只能够被讨论，还能够被计算。
命题内部还有结构
命题逻辑把“所有人都会死”看成一个整体字母，无法表示“所有”“人”和“会死”的内部关系。要处理这类结构，需要谓词逻辑。
可以把“苏格拉底是人”写成：
\[ Human(s) \]
“苏格拉底会死”写成：
\[ Mortal(s) \]
“所有人都会死”则写成：
\[ \forall x\,(Human(x)\rightarrow Mortal(x)) \]
\(\forall\) 表示“对于所有”。把一般规则与 \(Human(s)\) 结合，就能推出 \(Mortal(s)\)。
还可以用 \(\exists\) 表示“至少存在一个”：
\[ \exists x\,(Human(x)\land Scientist(x)) \]
这表示至少有一个对象同时是人和科学家。
戈特洛布·弗雷格在 1879 年的《概念文字》中建立了一套远比传统三段论更强的形式语言，能够表达量词、变量和嵌套关系。(Frege 1879年) 现代记号与他的原始书写不同，但关键思想延续下来：复杂推理可以在精确定义的符号语言中展开。
语法与语义
形式语言有两个层面。
语法（syntax）规定哪些符号串是合法表达式，以及如何根据规则变换。例如，括号必须匹配，\(\lnot\) 后面应接命题，推理规则只能应用于符合形式的前提。
语义（semantics）规定符号指向什么，以及在某种解释下何时为真。例如，\(Human(x)\) 中的 \(x\) 取哪些对象，“Human”包含哪些成员，都属于解释的一部分。
机器可以只按语法操作符号。一个证明检查器能够确认每一步是否符合规则，而不需要像人一样体验符号的含义。但若要让结论对应现实，我们仍需建立符号与世界之间的关系。
这会成为符号 AI 的中心困难之一：
写出推理规则往往不是最难的；难的是决定世界中的哪些对象、关系和例外应该进入符号系统。
“鸟会飞”看似简单。企鹅是鸟却不会飞；受伤的鸟暂时不能飞；玩具鸟不是生物；飞机名字里可能有“鸟”。日常常识通过大量背景知识处理这些例外，形式系统则要求我们把相关条件明确表示出来。
什么是形式系统
一个典型形式系统包含：
- 一组基本符号；
- 规定合法表达式的形成规则；
- 一组公理或初始表达式；
- 一组推理规则；
- 由公理经过有限规则步骤得到的定理。
证明于是变成一个有限符号序列。每一行要么是公理，要么能由前面的行按照规则得到。检查证明的人不需要猜作者灵感来自哪里，只需验证每一步是否合法。
技术深潜：可靠、完备和可判定不是一回事
讨论形式系统能力时，三个词必须分开。
可靠性（soundness）大意是：证明系统能推出的结论，在目标语义的所有相关解释中都成立。它防止证明规则越过语义所允许的范围。
完备性（completeness）大意是：目标语义中所有必然成立的结论，都能在证明系统中推出。它要求证明能力不遗漏语义后承关系。
可判定性（decidability）大意是：存在一个总会停机的机械过程，对任意合法输入都能正确回答目标问题，例如一个公式是否在所有解释中有效。
三个性质针对的问题不同。某种逻辑可能有可靠且完备的证明系统，却仍不存在对所有输入都能终止的判定算法；某个具体理论也可能因为表达能力更强而失去完备性。
还要区分两种“完备”。哥德尔的一阶逻辑完备性定理说明：对一阶逻辑而言，所有语义上有效的公式都能被形式证明。后来的不完备性定理则讨论包含足够算术能力的特定形式理论，说明其中会出现既不能证明也不能否定的句子。二者不矛盾，因为研究对象和“完备”的层次不同。
希尔伯特的梦想
19 世纪末到 20 世纪初，数学基础经历危机。集合论悖论让人怀疑，直觉上自然的推理是否会把数学带入矛盾。
大卫·希尔伯特等数学家推动一种形式化理想：把数学写进明确的公理和规则，证明系统不会导出矛盾，并用机械方法解决可判定的问题。如果每个数学命题都能按照规则证明或否定，争论就可以转化为符号检查。
这个愿景与后来的 AI 有一种深刻相似：两者都希望把高水平智力活动分解成明确表示和可执行步骤。
但形式化研究没有只带来胜利。它还发现，有些限制不是因为机器太慢，也不是因为程序员还不够聪明，而是来自问题本身。
哥德尔：系统中的真不都能在系统内证明
1931 年，库尔特·哥德尔发表不完备性定理。粗略地说，对于公理可由机械过程枚举、能够表达基本算术并满足相应一致性条件的形式理论，会存在理论内部无法判定的算术命题；满足进一步技术条件的一致理论，也不能在自身内部证明自己的整体一致性。(Gödel 1931年)
哥德尔的方法有一个令人惊讶的核心：让形式系统中的符号和证明编码为数字，于是系统能够间接谈论“关于自身证明”的陈述。由此可以构造与“本句在这个系统中不可证明”相近的算术句子；精确结论取决于理论采用的公理、可表达能力和一致性条件，不能只靠这句自然语言悖论代替证明。
不完备性定理并不表示“数学从此不能证明”，更不表示每道题都无答案。绝大多数日常计算和工程证明仍然可以进行。它指出的是：对足够强的一致形式系统，不能同时奢望它在自身范围内捕获全部算术真理。
丘奇与图灵：不存在解决所有输入的通用判定程序
另一个问题是希尔伯特的判定问题（Entscheidungsproblem）：能否找到一种机械过程，对任意一阶逻辑公式都在有限时间内判断它是否有效？
1936 年，阿隆佐·丘奇通过 lambda 演算，艾伦·图灵通过后来被称为图灵机的计算模型，分别给出了否定结果。(Church 1936年; Turing 1937年)
图灵的关键贡献不只是回答“不能”，还把“机械计算步骤”精确化。只要一个过程能被人按照固定规则逐步执行，它就可以由一个极简抽象机器描述。随后，图灵构造出某些没有通用算法能够判断的问题。
最著名的形式之一是停机问题：不存在一个程序，能够对任意程序及其输入都正确判断该程序最终是否停机。假设这样的判断器存在，就能构造一个专门反着做的程序：当判断器说它会停机时，它无限循环；当判断器说它不会停机时，它立即停止。把这个程序交给判断器分析自身，结论就产生矛盾。
这不是说我们永远无法判断任何程序是否停机。许多具体程序很容易分析。结论是不存在一个对所有可能程序和输入都正确、都终止的通用方法。
这些边界没有证明什么
哥德尔和图灵的结果常被搬进“机器能否思考”的争论，随后被解释成“形式系统有局限，所以人类心智一定超越机器”。这个推论并不自动成立。
首先，人类也会犯错、遗忘和无法解决问题。形式系统不能证明所有真理，不等于具体人类能证明这些真理。
其次，现实 AI 系统不必被限制在一套永不改变的公理中。它可以接收新数据、调用外部工具、修改程序或与人协作。这样做不会消除不可计算性，却会改变某个任务的实际能力。
再次，理论上的“不存在通用算法”与工程上的“对常见输入有很好方法”可以同时成立。数据库查询优化、程序验证和自动定理证明都面对最坏情况限制，却仍能解决大量有价值的问题。
核心判断
形式化边界告诉我们哪些目标不能被一套通用机械程序完全满足。它们不是关于所有机器、所有任务或人类优越性的简短口号。
逻辑给 AI 留下了什么
到 20 世纪 30 年代，逻辑学已经完成几件对 AI 至关重要的工作。
它提供了精确的符号语言，让对象、性质和关系能够被表示；它提供了推理规则，让结论可以按步骤生成和检查；它区分了语法、语义、证明和真；它还定义了机械计算的边界问题。
更微妙的遗产是：逻辑让研究者相信，至少一部分思考能够脱离人的直觉过程，变成可执行的形式操作。
然而，一页纸上的规则还不是一台机器。谁来保存符号？谁来选择下一条规则？“机械过程”究竟怎样由物理装置执行？怎样把连续的声音、图像和神经活动变成可处理的信息？系统能否根据反馈改变自己？
下一章将把逻辑接入计算、电路、信息和神经元模型。到那时，AI 的几块关键零件会第一次同时出现在技术视野中。
本章小结
- 逻辑从句子含义中抽出推理结构，检查“若前提为真，结论是否必然成立”。
- 命题逻辑把完整陈述视为真值单位，谓词逻辑进一步表示对象、性质、关系和量词。
- 有效推理不保证前提符合现实；规则正确与知识正确必须分别检查。
- 形式系统由符号、形成规则、公理和推理规则组成，证明可以变成机械检查的符号序列。
- 可靠性、完备性和可判定性描述不同性质，不能互换。
- 哥德尔不完备性与丘奇、图灵的不可判定结果揭示形式方法的原则边界，但不等于所有具体问题无解，也不直接证明人类心智超越一切机器。
思考问题
- 一个结论推理有效但前提错误，和前提正确但推理无效，哪一种更容易被发现？
- “鸟会飞”如果要写进规则系统，需要补充哪些例外和背景条件？
- 为什么一个不存在通用解法的问题，仍然可能拥有大量实用算法？
- 语言模型给出的推理步骤形式正确，是否足以说明答案正确？还需检查什么？
延伸阅读
- 布尔的原著展示了逻辑如何被放入代数框架。(Boole 1854年)
- 弗雷格《概念文字》适合了解现代量词逻辑诞生时的原始目标，尽管符号体系与今天不同。(Frege 1879年)
- 哥德尔、丘奇和图灵的论文技术门槛较高，建议先理解各自问题定义，再阅读证明细节。(Gödel 1931年; Church 1936年; Turing 1937年)