第14章:形式系统——给推理一个地基
在你能证明一件事之前,你得先说清楚"证明"是什么意思。
上卷的十三章是一次旅行。我们从熵出发,穿过符号系统的废墟,绕过向量空间的陷阱,在复杂度理论的边界上停了很久。整个过程,我们一直在谈"推理"——但从未真正定义它。
这是故意的。直觉需要先行,定义跟在后面。
但现在是时候付账了。下卷要做的事情只有一件:把推理这件事说清楚。不是用比喻,不是用历史,而是用精确的语言,把推理的结构挖出来,放在灯光下。
这需要一个起点。这个起点叫做形式系统。
14.0 公理印章游戏:什么叫“合法推出”?
先不要急着谈“真”。我们先玩一个更冷酷的游戏:公理印章游戏。
桌面上有三样东西:一叠空白纸、一盒印章、一张规则表。印章上刻着一些固定公式,比如
游戏开始时,纸上什么都没有。你只能做两种动作:
- 盖公理印章:把某个公理模板实例化,写到纸上。
- 按规则走一步:从纸上已经出现的公式,按照推断规则写出一个新公式。
除此之外,什么都不许做。你不能说“这显然对”,不能说“我凭直觉觉得应该如此”,不能拿现实世界来帮忙。这个游戏里的“证明”,就是一串合法盖章记录;这个游戏里的“定理”,就是某张纸最后一行出现的公式。
这个游戏的形式化骨架
- 状态空间:所有有限公式序列
。 - 合法移动:写下一个公理实例,或者对已经写下的公式应用一条推断规则。
- 转移规则:从序列
变成 ,其中 必须由公理或规则合法产生。 - 获胜条件:目标公式
出现在序列末尾,即 。 - 失败模式:你觉得
显然为真,但规则不允许你写出它。形式系统不关心你的感受。
这个游戏的重点是:合法性先于真理。形式系统首先规定哪些符号串能写、哪些步骤能走;至于这些符号是否真的描述了世界,那是后面“语义”才要处理的问题。
这就是形式化的第一刀。它把推理从自然语言里切出来,放进一个你可以检查的游戏里。赢了游戏,不代表你掌握真理;它只证明了一件事:在这套规则下,你确实走到了那里。
形式系统不是一台真理机器。它是一张棋盘、一盒棋子、一本规则书。你能走到某个格子,只说明这步棋合法——不说明宇宙欠你一个掌声。把“合法推出”和“真实成立”分开,是下卷的第一课。
14.0.5 用代码玩这个游戏
这个游戏小到可以真的跑起来。下面的程序会按照规则表检查证明行——盖一个公理实例,或者对前面两行应用假言推理——然后尝试一系列非法移动,让你亲眼看检查器把它们拒绝掉。打印出来的每一条判定,都是检查器实际计算出的结果。
#!/usr/bin/env python3
"""
axiom_stamp_game.py -- the Axiom-Stamp Game of Chapter 14, run for real.
Book reference: The Reasoning Kingdom, Volume 2, Chapter 14, Section 14.0
"The Axiom-Stamp Game: What Does 'Legally Derived' Mean?"
The table holds blank paper, a box of stamps, and a rule sheet. A proof is
nothing but a string of legal stamp records. This program plays the game:
* it CHECKS proof lines the way the rule sheet demands (stamp an axiom
instance, or apply modus ponens to two earlier lines), and
* it lets you try illegal moves, so you can watch them get rejected.
The system is Lukasiewicz's three axiom schemas plus modus ponens over the
atoms {P, Q} -- the same toy formal system Chapter 15's companion script
mirror_sentence_game.py runs its proof search on.
Honest scope: the checker only recognizes the three schemas by shape; it
does not prove anything about the system. That is the point of the game:
legality comes first, truth has no stamp.
Style: formulas are immutable tuples, every function is pure, no classes.
Run: python3 axiom_stamp_game.py
"""
# ---------------------------------------------------------------------------
# Formulas: "P" / "Q", ("not", F), ("->", F, G)
# ---------------------------------------------------------------------------
def show(f):
"""Canonical parenthesized string of a formula."""
if isinstance(f, str):
return f
if f[0] == "not":
return "¬" + show(f[1])
return "(" + show(f[1]) + "→" + show(f[2]) + ")"
def is_axiom(f):
"""Is f an instance of one of the three axiom schemas?
A1: X -> (Y -> X)
A2: (X -> (Y -> Z)) -> ((X -> Y) -> (X -> Z))
A3: (not X -> not Y) -> (Y -> X)
"""
if not (isinstance(f, tuple) and f[0] == "→"):
return False
# A1: X -> (Y -> X)
if isinstance(f[2], tuple) and f[2][0] == "→" and f[2][2] == f[1]:
return True
# A3: (not X -> not Y) -> (Y -> X)
if isinstance(f[1], tuple) and f[1][0] == "→" \
and isinstance(f[2], tuple) and f[2][0] == "→":
nx, ny = f[1][1], f[1][2]
if isinstance(nx, tuple) and nx[0] == "not" \
and isinstance(ny, tuple) and ny[0] == "not" \
and f[2][1] == ny[1] and f[2][2] == nx[1]:
return True
# A2: (X -> (Y -> Z)) -> ((X -> Y) -> (X -> Z))
x, yz = f[1][1], f[1][2]
xy, xz = f[2][1], f[2][2]
if isinstance(yz, tuple) and yz[0] == "→" \
and isinstance(xy, tuple) and xy[0] == "→" and xy[1] == x \
and isinstance(xz, tuple) and xz[0] == "→" and xz[1] == x \
and xy[2] == yz[1] and xz[2] == yz[2]:
return True
return False
# ---------------------------------------------------------------------------
# The proof checker: the rule sheet, enforced line by line
# ---------------------------------------------------------------------------
def check_proof(lines):
"""Check a claimed proof.
lines: list of (formula, justification), where justification is
None -> "I stamped an axiom" (checked against the schemas)
(i, j) -> "modus ponens on lines i, j" (1-based; line j must be
line_i -> formula)
anything else -> no such move exists on the rule sheet.
Returns a list of (formula, verdict, note) per line.
"""
formulas = {}
verdicts = []
for k, (f, why) in enumerate(lines, start=1):
if why is None:
ok = is_axiom(f)
note = "stamped axiom" if ok else "rejected: not an axiom instance"
elif isinstance(why, tuple) and len(why) == 2:
i, j = why
a = formulas.get(i)
b = formulas.get(j)
ok = (
b is not None
and isinstance(b, tuple)
and b[0] == "→"
and b[1] == a
)
note = f"MP from lines {i},{j}" if ok else "rejected: illegal MP"
else:
ok = False
note = "rejected: the rule sheet has no such move"
formulas[k] = f
verdicts.append((f, ok, note))
return verdicts
# A legal five-line proof of P -> P (the stamp record, line by line).
P = "P"
LEGAL_PROOF = [
(("→", P, ("→", P, P)), None), # 1 A1
(("→", P, ("→", ("→", P, P), P)), None), # 2 A1
(
(
"→",
("→", P, ("→", ("→", P, P), P)),
("→", ("→", P, ("→", P, P)), ("→", P, P)),
),
None, # 3 A2
),
(("→", ("→", P, ("→", P, P)), ("→", P, P)), (2, 3)), # 4 MP
(("→", P, P), (1, 4)), # 5 MP
]
def demo():
print("=" * 70)
print(" THE AXIOM-STAMP GAME -- the rule sheet, enforced for real")
print(" The Reasoning Kingdom, Volume 2, Chapter 14 (Sec. 14.0)")
print("=" * 70)
print("\nA legal proof of P -> P, checked line by line:")
print(" line formula verdict")
for k, (f, ok, note) in enumerate(check_proof(LEGAL_PROOF), start=1):
print(f" {k:>4} {show(f):<40} {note}")
assert all(ok for _, ok, _ in check_proof(LEGAL_PROOF))
print("\nNow the illegal moves -- watch the rule sheet refuse:")
attempts = [
(("→", "P", "Q"), None, "I stamp P -> Q"),
(("→", "P", "P"), (1, 1), "MP of line 1 with itself"),
(("→", "P", "P"), "it is obviously true", "the real world says so"),
(("P",), None, "P is true, so stamp it"),
]
for f, why, story in attempts:
(_, ok, note) = check_proof([(f, why)])[0]
verdict = "ACCEPTED" if ok else "REJECTED"
print(f" [{verdict:>8}] {story:35} -> {note}")
assert not ok
print("\nThe point of the game: legality comes before truth.")
print(" The checker never asked whether P -> Q is true. It asked only")
print(" whether the rule sheet lets you write it. It does not.")
print(" Formal systems do not care about your feelings -- they care")
print(" about which moves are legal.")
print("=" * 70)
if __name__ == "__main__":
demo()14.1 语言的歧义性问题
考虑这句话:"如果天下雨,地就湿。天下雨了。所以地湿了。"
这个推理看起来完全正确。但问题是:它为什么正确?
你可能会说:因为这符合常识。但常识不是数学。或者你会说:因为逻辑强迫如此。但"逻辑强迫如此"是什么意思?如果我们要严肃对待这个问题,就必须找到某种不依赖"常识"和"显然"的解释。
自然语言是有歧义的。"或"在一个语境下可以表示"至少一个",在另一个语境下可以表示"恰好一个"。"如果……那么……"在日常用法里变化剧烈——"如果你考上了,我就请你吃饭"和"如果这个算法正确,那么它的运行时间是
形式化的目的不是让语言变得难看,而是消除歧义。我们需要一套符号,每个符号只有一个含义,由定义给出,不依赖语境,不依赖常识。
"常识不是数学"——这句话说得很好。但别以为形式化就是把常识翻译成符号。形式化是在强迫你承认:你那些"显然"里藏着多少从没想清楚的东西。符号只是逼你原形毕露的工具,不是答案本身。就这样。
14.2 命题:推理的原材料
最小的推理单元是命题——一个可以被断言为真或假的陈述。"今天下雨"是命题。"下雨"不是,因为它没有断言任何事情。"这句话是假的"看起来是命题,但它触发了自指悖论——我们先把它放在一边,第15章会正面处理它。
命题用大写字母
| 符号 | 读法 | 含义 |
|---|---|---|
| 非 | ||
| 两者都成立 | ||
| 至少一个成立 | ||
| 若 | ||
| 两者同真同假 |
这些符号的含义来自精确的规则,不是约定俗成的。
逻辑连接词不是在描述因果,而是在约束推断的合法性。
14.3 形式系统:给推理划定游戏规则
有了命题的语言,下一步是说清楚哪些推断是合法的。这就是形式系统的工作。
一个形式系统
语言
公理
推断规则
前提在横线上,结论在横线下。这不是在描述什么是"真"的,而是在规定哪些推断步骤是允许的。
证明:把公理和推断规则连接起来的有限序列。一个证明是一列命题
当我们说
⊢ 和 ⊨:两个长得像、含义却截然不同的符号
这两个核心符号在下卷其余部分会不断出现;混淆它们会让一切变得难以理解:
(单横线,turnstile):句法可证性。 意思是"存在一个形式证明,按照规则从公理出发一步步推出 "。这纯粹是符号操作的结果——和"真或假"无关。 (双横线):语义真值。 意思是" 在所有可能的解释下都为真"(重言式)。这是关于意义的陈述。
类比:
可靠性(Soundness):
完备性(Completeness):
这两个方向都不是自动成立的;两者都需要证明。
14.4 证明是句法对象
这里有一个关键的哲学立场值得停下来想一想。
在形式系统里,证明是一个句法对象——一个可以被机械检查的符号串序列。验证一个证明不需要理解它在"说什么",你只需要检查每一步是否合法地应用了某条推断规则。
这意味着什么?它意味着一台机器——它不懂数学,不知道"真"是什么意思,只会匹配符号——可以验证任何形式证明的正确性。现代定理证明器(Lean、Coq、Isabelle)正是这样工作的:你写证明,机器检查符号。
注意这种非对称性。验证一个证明是机械的,可以在多项式时间内完成——只需一步步检查每条推断规则是否被合法应用。发现一个证明则是另一回事:没有通用算法能保证在任何情况下都找到证明(第15章会说明这是不可能的)。这种非对称性贯穿整个可计算性理论,也是"NP"谜题的根源之一。
这不是数学的终结,而是数学的一个深刻特性:数学真理可以被机械验证。不依赖权威,不信任直觉——我们只需要检查符号串。
当然,想出证明的过程——找到正确的推断路径——不是机械的,也许永远不会是。但验证是机械的,这一点已经足够深刻。
这里容易飘。"机器可以验证证明"不等于"机器理解证明"。验证是对符号串做模式匹配,和"理解"没有任何关系。如果你要把"可机械验证"当作数学的荣耀来庆祝,先弄清楚你庆祝的究竟是什么。被验证的是形式,不是意义。
14.5 上下文:假设的簿记
现实的推理很少从零开始。通常我们说:"假设
比如
上下文看起来像一个簿记工具,但它的行为决定了整个逻辑系统的性格。关于上下文有三条基本规则,它们通常默默运行在后台,所以大多数人从未注意到它们的存在:
弱化:如果在假设
收缩:同一个假设可以被使用任意多次。如果你知道
交换:假设的顺序无关紧要。
在经典逻辑里,这三条规则被当作理所当然——资源无限,顺序无关。但第16章会拿走收缩规则,而这一改动会从根本上改变整个逻辑的性格:每个假设恰好只能用一次,推理变成资源管理。
弱化、收缩、交换:它们听起来无聊,但第16章会把它们摧毁
这三条结构规则是经典逻辑的隐藏地基。绝大多数逻辑教材从不明说它们,因为它们"显然成立":
- 弱化:多余的前提不碍事。知道"天下雨"和"钱包在家",可以推出"地湿了"——即使钱包完全没用。
- 收缩:同一前提可以被无限复用。知道"我有五块钱",可以把这条知识用任意多次。
- 交换:前提的顺序无关紧要。
为什么要把它们列出来?因为第16章的线性逻辑会去掉收缩——突然之间,"五块钱只能用一次",推理变成资源管理。这三条规则存在,正是为了在第16章去掉其中一条时,让对比变得锋利。
大多数人学了十年逻辑,从未意识到自己一直在默默使用这三条规则。这不是额外知识;这是你推理脚下的地基。你连地基是什么都不知道,就在上面盖楼——还说不清你盖的东西为什么站得住。名字的缺席,不等于它们不存在。
因为它们并不是"逻辑本身",而是关于逻辑的元选择——选择它们,你得到经典逻辑;拒绝其中某一条,你得到不同的逻辑系统。大多数数学课完全不提这三条规则,因为在经典语境下它们从不被违反。但正是这种"不言而喻"掩盖了逻辑的可选择性。形式系统能做的事情之一,就是让这些隐藏的选择变得可见。
14.6 语义:符号背后的含义
形式系统在句法层面操作符号。但我们通常希望这些符号"有含义"——对应某个真实世界或数学结构。
给命题赋予含义叫做赋值:把每个命题变元映射到真或假。在给定赋值下,复合命题的真值由连接词的规则递归决定——
如果一个命题在每种赋值下都为真,就称它为重言式,记作
现在有两个层面需要区分:
:在句法层面, 有一个形式证明 :在语义层面, 是重言式
这两个层面之间的关系是形式逻辑的核心问题:
可靠性:若
完备性:若
命题逻辑的标准形式系统同时满足两者。一阶谓词逻辑也是如此——哥德尔在 1930 年证明了这一点;那是他带来的最后一个好消息。一年后,他带来了完全不同的东西。
14.7 系统越强,代价越大
不同的形式系统有不同的表达能力。从弱到强,大致是:
命题逻辑:只处理命题和连接词——无法谈论"所有"和"存在"。足够简单,可以被机械判定——存在一个算法,对任意命题,在有限步内判定它是否为重言式。
一阶谓词逻辑:加入量词
皮亚诺算术(PA):在一阶逻辑上加入算术公理,强到可以表达初等数论几乎所有的陈述。哥德尔的噩耗正是在这个层级到来。
集合论(ZFC):现代数学的共同语言——几乎所有数学对象都可以在其中编码和研究。
这个层级有一个规律:系统越强,表达能力越大,自我验证的能力越弱。命题逻辑简单到可以穷举检查自身;皮亚诺算术强到连自身的一致性都无法证明。力量有代价。这个代价,正是下一章要结清的账单。
直觉上:一个足够强的系统能谈论自己,而一旦能谈论自己,它就能构造关于自身的悖论性陈述。弱的系统无法表达"我自己的命题",所以它永远不会遇到这个问题。这就像语言——表达能力越丰富,越容易出现自指悖论;简单的形式语言之所以安全,恰恰是因为它不能指涉自身。哥德尔发现的不是数学的缺陷,而是表达能力的内在代价。
14.8 实战:写出第一个形式证明
在继续之前,停下来做一件事:写一个真实的形式证明序列。不是"理解它在说什么"——而是真的写出来,标明每一行从哪里来。
这会让接下来的一切都不同。
我们采用一个极简的命题逻辑系统,只有两条公理(Łukasiewicz 的简化版本,用来练习足够了):
公理模式 L1:
公理模式 L2:
唯一的推断规则:假言推理——从
公理模式的意思是:用任意命题变元替换
目标:证明
它看起来显然——但在这个系统里,它不是公理;它必须从公理推导出来。
下面是一个脚手架。试着填出每一行的来源(一个公理实例,还是对哪两行应用 MP):
| 行号 | 命题 | 来源 |
|---|---|---|
| 1 | L1,其中 | |
| 2 | ? | |
| 3 | ?(对第 1、2 行应用 MP) | |
| 4 | ? | |
| 5 | ?(对第 3、4 行应用 MP) |
第2行是 L2 的一个实例——找出
填完之后,你就完成了一个完整的形式证明:五行,每行都有清楚的来源,不依赖任何直觉——只靠符号操作。
这个证明的意义不在于结论
回到本章开头的公理印章游戏:你刚刚用自己的手盖了五枚印章。真正值得记住的不是最后的
但也正因为如此,一个更尖锐的问题浮现出来:如果每一步合法移动都被规则表提前固定,那么规则表本身可靠吗?它能盖出假的东西吗?它会漏掉真的东西吗?这就是下一章要面对的两堵墙。
悬而未决
形式化能捕捉所有推理吗? 数学家在日常工作中大量依赖非形式直觉——某个构造"应该"能行,某个证明"显然"可以推广。这些直觉能被形式化吗?还是说,形式系统本质上会遗漏推理中某种不可言说的维度?
公理的选择是客观的吗? 不同的公理集会给出不同的数学宇宙。选择公理——ZFC 中最有争议的公理——并非"显然"正确;数学家为它争论了一个世纪。形式化让争论变得更清楚,但没有解决它。
这台机器可靠吗?完备吗? 我们建造了形式系统,描述了它的语言、公理和推断规则,并把句法与语义分开。但有一个问题我们还没有正面回答:它证明的东西都是真的吗?它能证明所有为真的东西吗?一个答案会令人欣慰,另一个则会令人震惊。第15章正面处理这两个问题。
思考题
★ 热身
以下符号串中,哪些是合法的命题公式,哪些不是?不需要理由——只需判断。
(提示:合法的命题公式由命题变元、连接词和括号按照语法规则组装而成。连接词是一元或二元运算符,不能单独出现在末尾。)
★★ 推导
以下三个断言中,哪些成立?用自然语言清楚解释,并指出每个断言依赖本章的哪个概念(推断规则、弱化、收缩,还是演绎定理)。
- 若
,则 。 - 若
且 ,则 。 - 若
,则 。
第三条叫做演绎定理。它说的是:在假设
★★★ 挑战
演绎定理是关于形式系统的元定理,不是系统内部的公理或推断规则。用本章引入的语言(
进一步:演绎定理本身能在某个形式系统内被证明吗?还是必须在系统之外,用数学归纳法对证明长度做归纳来建立?这个答案与第15章"一个系统无法证明自身的一致性"有什么关系?不需要解决——只需用本章的语言把问题精确陈述出来。
