逻辑

数理逻辑研究数学陈述的形式、推理规则以及证明与模型之间的关系。命题逻辑处理陈述之间的连接，一阶逻辑进一步使用变量、量词和关系描述对象。逻辑的作用是把“结论为什么跟随前提成立”说清楚。

命题与连接词

命题是具有确定真值的陈述。“2 是偶数”为真命题；“x 是偶数”在没有给定 $x$ 或量词时是含自由变量的谓词，不能直接作为确定真假的封闭命题。

常见连接词为否定 $\mathrm{\neg }P$、合取 $P\wedge Q$、析取 $P\vee Q$ 与蕴含 $P\Rightarrow Q$。普通逻辑中的析取允许两者同时为真。

P	Q	P∧Q	P∨Q	P⇒Q
真	真	真	真	真
真	假	假	真	假
假	真	假	真	真
假	假	假	假	真

蕴含只在“前提真、结论假”时为假。它表达真值之间的约束，并不自动表示因果关系；前提为假时蕴含为真，也不能由此断定结论本身为真。

必要条件、充分条件与逆否命题

若 $P\Rightarrow Q$，则 $P$ 是 $Q$ 的充分条件，$Q$ 是 $P$ 的必要条件。例如“整数能被 4 整除”足以推出“整数是偶数”，反向却不成立，6 就是反例。

集合包含关系解释蕴含：所有满足强条件的对象都满足弱条件，但弱条件可能包括额外对象。

蕴含与逆否命题等价： $$(P\Rightarrow Q)⟺(\mathrm{\neg }Q\Rightarrow \mathrm{\neg }P).$$ 它通常不等价于逆命题 $Q\Rightarrow P$。若两个方向都成立，才写作 $P\iff Q$，称为充要条件。

量词顺序不能随意交换

$\mathrm{\forall }$ 表示“对所有”，$\mathrm{\exists }$ 表示“存在”。例如在实数范围内， $$\mathrm{\forall }x\mathrm{\exists }y(y>x)$$ 为真，因为对每个 $x$ 可选择 $y=x+1$。交换后 $$\mathrm{\exists }y\mathrm{\forall }x(y>x)$$ 却为假，它要求找到一个比所有实数都大的固定实数。前者允许 $y$ 依赖 $x$，后者不允许。

这正是极限定义中“任给误差，存在足够小的邻域”的核心：邻域可以依赖误差，而不是预先选好同一个邻域应对一切误差。

怎样正确否定一句话

否定全称命题得到存在反例；否定存在命题得到全部不成立： $$\mathrm{\neg }(\mathrm{\forall }xP(x))\iff \mathrm{\exists }x\mathrm{\neg }P(x),\mathrm{\neg }(\mathrm{\exists }xP(x))\iff \mathrm{\forall }x\mathrm{\neg }P(x).$$ “所有整数都是偶数”的否定是“存在一个整数不是偶数”，不是“所有整数都不是偶数”。对于复合语句，德摩根律给出 $\mathrm{\neg }(P\wedge Q)\iff \mathrm{\neg }P\vee \mathrm{\neg }Q$。

证明与反例承担不同任务

全称命题不能靠检查有限个普通例子证明，却可以被一个满足前提、违反结论的反例推翻。例如“所有素数都是奇数”被 2 推翻。

直接证明从假设按有效规则推出结论；逆否证明转而证明等价的逆否命题；反证法假设所求结论的否定并导出矛盾。数学归纳法则需要同时给出初始情形和从 $n$ 到 $n+1$ 的一般推理，仅检查前几项并不构成归纳证明。

本条使用经典逻辑。形式证明保证结论跟随前提，但现实建模中前提是否符合实际，还需要定义、观测和验证。

延伸阅读

• Oscar Levin，《Discrete Mathematics: An Open Introduction》第 0、3 章：量词、逻辑与证明。
• 极限 · 组合数学 · 数学建模