命题与公理系统

本篇先回答两个问题：一句话怎样才算清楚的数学陈述，以及怎样根据明确的假设推出结论。这些概念会贯穿后面的直接证明、逆否证明和归纳法。证明的基本组织方式可以对照 MIT 的证明讲义阅读[1][1] T. Leighton and R. Rubinfeld, “What Is a Proof?,” 2006. MIT 6.042/18.062J lecture notes, September 7, 2006. https://web.mit.edu/neboat/Public/6.042/proofs.pdf。

以下采用经典逻辑，并约定 $\mathbb N=\{0,1,2,\ldots\}$。这里的“真或假”以已经说明的论域和解释为前提，不表示我们总能找到判定真假的算法。

从句子到命题

定义命题与论域

命题是含义明确、在给定解释下具有真值的陈述。论域规定变量允许取哪些对象。真值是否确定，与我们是否已经知道或证明这个真值，是不同的问题。

“所有素数都是偶数”是假命题，反例是 $3$；它仍然是命题。“请找一个素数”是命令，没有相应的真假判断。“这个证明很漂亮”缺少明确的评价标准，不能直接作为这里讨论的数学命题。

有些句子的问题在于条件没说全。例如，“三角形内角和是 $180^\circ$”需要说明讨论的是欧氏平面几何。更换几何背景后，不能直接沿用结论。写证明之前，应先确认句子里的对象、运算和背景都已经确定。

定义谓词与自由变量

含有尚未赋值的自由变量的公式，可以看作谓词。令 $P(x)$ 表示 $x>2$，其中 $x\in\mathbb Z$。它的真假依赖于 $x$：$P(3)$ 为真，$P(1)$ 为假。给变量赋值，或者用量词把所有自由变量绑定起来，才能得到不再依赖这些变量取值的句子。

例如，$x^2=2$ 本身没有交代 $x$。写成“存在实数 $x$ 使得 $x^2=2$”后，得到一个真命题；把“实数”换成“有理数”，就得到假命题。同一段符号，论域不同，所说的事情也不同。

注真值确定不等于已经知道答案

“我们还不会证明”不意味着一个陈述不是命题。反过来，知道某个命题在预期的数学结构里为真，也不能直接断言它在任意指定的公理系统中都可证。判断一个证明建立了什么结论时，要始终留意所选的假设。

用逻辑联结词组织陈述

设 $P,Q$ 都是命题。否定 $\neg P$ 表示 $P$ 不成立；合取 $P\land Q$ 要求两者都成立；析取 $P\lor Q$ 要求至少一个成立，允许两者同时成立。数学中的“或”默认是这种包容性的“或”。

条件命题 $P\to Q$ 读作“若 $P$，则 $Q$”。它排除的情况只有一种：前提成立而结论不成立。双条件 $P\leftrightarrow Q$ 则要求两个方向都成立，读作“$P$ 当且仅当 $Q$”。

$P$	$Q$	$P\to Q$	$P\leftrightarrow Q$
真	真	真	真
真	假	假	假
假	真	真	假
假	假	真	真

例为什么假前提不会构成反例

考虑“对每个整数 $n$，若 $4$ 整除 $n$，则 $n$ 是偶数”。当 $n=6$ 时，前提不成立，这个取值并不反驳原命题。要反驳它，必须找到一个能被 $4$ 整除却不是偶数的整数。条件命题约束的是满足前提的对象。

命题“若 $P$，则 $Q$”为真，也不表示两者之间一定有因果关系。它描述的是逻辑条件。把它改成“若 $Q$，则 $P$”通常会改变真值；具体比较见逆命题、否命题与逆否命题。

量词决定要证明什么

全称与存在

全称量词 $\forall$ 表示“对所有对象”，存在量词 $\exists$ 表示“至少存在一个对象”。若论域是 $D$，常用写法是

$$\forall x\in D,\ P(x),$$

以及

$$\exists x\in D,\ P(x).$$

证明全称命题时，应取任意一个符合条件的对象，并让论证不依赖于它的特殊性。检查几个例子通常只能帮助形成猜想。否定全称命题只需一个反例；证明存在命题则可以给出一个满足条件的见证，见证不要求唯一。

量词顺序与依赖关系

例每个数都有更大的数，与存在最大的数

下面两个句子只交换了量词顺序，却说了不同的事情：

$$\forall x\in\mathbb Z,\ \exists y\in\mathbb Z,\ y>x,$$$$\exists y\in\mathbb Z,\ \forall x\in\mathbb Z,\ y>x.$$

第一句为真。给定任意整数 $x$ 后，可以选择 $y=x+1$；这个 $y$ 允许依赖于 $x$。第二句为假，因为它要求先固定一个 $y$，再让它大于所有整数。随后取 $x=y$，要求就变成 $y>y$，无法成立。

读带多个量词的命题时，可以按从左到右的顺序问：“现在谁已经给定了？接下来选择的对象可以依赖谁？”这是后面理解极限定义、算法保证和函数性质时反复用到的习惯。

否定带量词的命题

全称命题不成立，意味着至少有一个对象不满足条件；存在命题不成立，意味着每个对象都不满足条件。因此

$$\neg\bigl(\forall x\in D,\ P(x)\bigr) \iff \exists x\in D,\ \neg P(x),$$ $$\neg\bigl(\exists x\in D,\ P(x)\bigr) \iff \forall x\in D,\ \neg P(x).$$

例如，“每个整数都有更大的整数”的否定是“存在一个整数，没有整数比它大”。把前面的公式逐层取反，得到

$$\exists x\in\mathbb Z,\ \forall y\in\mathbb Z,\ y\le x.$$

注空论域与空真

如果量词被限制在空集合 $D=\varnothing$ 上，那么“每个 $x\in D$ 都满足 $P(x)$”为真，因为没有反例；“存在 $x\in D$ 满足 $P(x)$”为假，因为没有见证。这里说的是空集合上的受限量词，通常的一阶逻辑仍约定模型的整个论域非空。

公理、定义与推理规则各做什么

形式语言规定哪些符号和表达式合法；公理是选作出发点的句子；推理规则规定怎样由已接受的句子得到下一句。将非逻辑公理组成集合 $T$，并固定背景逻辑后，就可以讨论从 $T$ 能推出什么。

在实际写作中，还会遇到几种名称：

• 定义引入术语或记号，例如“整数 $n$ 是偶数”表示存在整数 $k$ 使 $n=2k$。通常它是对既有语言的明确缩写，不是从几个例子猜出的规律。
• 定理是已经给出证明的结论。证明需要说明使用的假设和背景理论。
• 引理也是定理，只是主要用来帮助证明其他结果。
• 推论也是已证明的结果，通常可以较直接地从前面的定理得到。

这些名称说明结论在叙述中的角色，不代表不同等级的“正确”。同一个陈述可以在一种公理化中作为公理，在另一种公理化中作为定理。

例定义对象也需要检查条件

若要定义实数函数 $f(x)=1/x$，定义域不能包含 $0$。若说“令 $r$ 是满足 $r^2=2$ 的那个实数”，又没有指定符号，就不能得到唯一的 $r$。要定义通常的平方根，应要求 $r\ge 0$，并证明或引用相应的存在性和唯一性。定义可以自由选择记号，但不能省略让对象有意义的条件。

例分离一条推理规则与一条命题

肯定前件规则（modus ponens）允许我们由 $P$ 和 $P\to Q$ 推出 $Q$：

$$\frac{P\qquad P\to Q}{Q}.$$

上方是两条前提，下方是结论。仅有 $P\to Q$ 还不够推出 $Q$，因为我们可能根本没有证明 $P$。

证明把规则放进一段短推导

假设已有 $P\to Q$、$Q\to R$ 和 $P$。由第一条条件命题及 $P$，用肯定前件得到 $Q$；再由 $Q\to R$ 和 $Q$ 得到 $R$。每一步都能指出使用了哪条前提和哪条规则。

幂运算的推导同样需要说明论域。取 $a>0$ 为实数，$m,n\in\mathbb Z$，从而所有整数次幂都有定义。如果已经证明指数律和整数加法交换律，就可以写出

$$\begin{aligned} a^m a^n &= a^{m+n}\\ &=a^{n+m}\\ &=a^n a^m. \end{aligned}$$

这段推导展示的是怎样调用已有结果。它没有从零证明指数律，也不能用来偷偷假设自己尚未建立的结论。

公理究竟支持了什么

真假讨论一个陈述在给定解释下是否成立，可证性讨论能否根据指定公理和规则把它推导出来。记号 $T\vdash\varphi$ 表示从假设集合 $T$ 出发存在对 $\varphi$ 的推导。写证明时，应交代足够的背景，使每一步都有依据。

例如，只有假设 $P$ 时，无法决定一个无关陈述 $Q$ 的真假。$P$ 成立，可以同时伴随 $Q$ 成立，也可以同时伴随 $Q$ 不成立。因此，在某个选定例子中成立的事实，不会自动成为已有假设的推论。

现阶段先练习区分假设、定义、推理步骤与结论。掌握这些习惯后，再到形式逻辑与自然演绎系统学习模型、一致性、独立性和两种完备性。

练习：把条件与理由写完整

下面的题目对应本篇的关键区别。先独立作答，再展开解析；不需要使用后面章节的复杂证明技巧。

练习句子、赋值与论域

在 $x\in\mathbb R$ 的背景下，比较 $x^2\ge 0$、$\forall x\in\mathbb R,\ x^2\ge 0$ 和 $\exists x\in\mathbb R,\ x^2=-1$。哪些是闭句？真假如何？如果第一句直接被写进证明，作者还应说明什么？

查看解析

解

第一式有自由变量 $x$，是开放公式；虽然它对每个实数赋值都成立，写作时仍应说明 $x$ 已经任意选定，或写出全称量词。第二式是一个真闭句。第三式是一个假闭句，因为实数的平方非负。这里“不是闭句”和“为假”是两种不同情况。

练习交换量词

在 $\mathbb N$ 中，判断下面两个句子，并写出第一句的否定：

$$\forall n\in\mathbb N,\ \exists m\in\mathbb N,\ m>n,$$$$\exists m\in\mathbb N,\ \forall n\in\mathbb N,\ m>n.$$

查看解析

解

第一句为真，给定 $n$ 后取 $m=n+1$。第二句为假，对任何候选 $m$ 都可以取 $n=m$。第一句的否定是

$$\exists n\in\mathbb N,\ \forall m\in\mathbb N,\ m\le n.$$

否定既交换量词，也否定最内层的不等式，不能只把 $>$ 换成 $\le$。

练习结论成立，前提就成立吗

设 $P$ 表示“$n$ 能被 $4$ 整除”，$Q$ 表示“$n$ 是偶数”。有人从 $P\to Q$ 和 $Q$ 推出 $P$。给出一个整数反例，并解释它为什么不是肯定前件规则。

查看解析

解

取 $n=6$。此时 $Q$ 为真、$P$ 为假，而 $P\to Q$ 仍为真。因此两条前提可以同时成立，结论却为假。肯定前件需要的是 $P$ 与 $P\to Q$，这里提供的却是 $Q$ 与 $P\to Q$。

练习用模型检查公理是否多余

在经典命题逻辑中，取 $T=\{P\lor Q,\neg P\}$。证明 $T\vdash Q$，再判断将 $Q$ 加入 $T$ 是否增加了可推导的结论。如果删掉 $\neg P$，还能够推出 $Q$ 吗？

查看解析

解

$P\lor Q$ 表示至少一个成立，而 $\neg P$ 排除了 $P$，所以得到 $Q$。形式上可以按析取的两个分支证明：在 $P$ 分支，由 $P$ 与 $\neg P$ 得到矛盾，再由矛盾推出 $Q$；在 $Q$ 分支，结论已经给定。

既然 $Q$ 已经有从 $T$ 出发的证明，把它再列成公理不会增加可推导的结论，因为每次使用新公理都可以换成原来的证明。若删掉 $\neg P$，赋值 $P=\mathrm T,Q=\mathrm F$ 满足剩下的公理，却不满足 $Q$，因此不能再推出 $Q$。

接下来怎么读

读到这里，应当能够先写出论域和量词，再区分一个句子的含义、真假、证据与可推导性。接下来用逆命题、否命题与逆否命题练习改写条件命题，再到直接证明把定义、假设和规则组织成完整论证。

参考文献

1. [1] T. Leighton and R. Rubinfeld, “What Is a Proof?,” 2006. MIT 6.042/18.062J lecture notes, September 7, 2006. https://web.mit.edu/neboat/Public/6.042/proofs.pdf ↩