逻辑

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

英文名称：Mathematical logic。

English overview

Mathematical logic studies precise statements, their interpretation, and valid forms of inference. At an introductory level, propositional logic treats complete statements as units, while predicate logic makes variables and quantifiers explicit. The distinction matters because a sentence such as “there exists a bound for every input” can express different claims depending on the order of its quantifiers.

This article explains truth tables, implication, equivalence, negation, and common proof methods. A material implication is false only when its premise is true and its conclusion false; it does not by itself assert a causal connection. Universal claims are disproved by one counterexample but cannot generally be proved by checking a few cases. We work through parity proofs, quantifier negation, and an induction argument, making the domain of discourse and assumptions visible. We also distinguish semantic validity from a formal derivation: introductory truth-table reasoning addresses a limited language, while the wider subject includes proof theory, model theory, computability, and the foundations of mathematics. Historical notes place Boolean algebra and nineteenth-century symbolic logic within a longer development rather than attributing all reasoning to one inventor.

命题与连接词

命题是具有确定真值的陈述。“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$ 的一般推理，仅检查前几项并不构成归纳证明。

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

语句、变量和讨论范围

“今天下雨”在日期和地点确定后可以成为一个命题；“x 大于三”含有自由变量，在给定 x 或添加量词之前还没有确定真值。数学写作经常省略熟悉的讨论范围，但这种省略应当能从上下文恢复。例如“所有数都有平方根”在非负实数范围内与实数范围内意义不同，在复数范围内又有不同结论。先规定对象属于哪个集合，比急着列真值表更重要。

本条主要采用经典二值逻辑：在给定解释下，命题取真或假。它不意味着我们实际总能知道哪一个，也不意味着任何自然语言句子都能不经澄清地形式化。一个关于尚未解决数学问题的陈述，可能在经典框架中有确定真值，而人们暂时没有证明。真、可证、已知这几个词描述的层次不能混同。

条件命题为什么容易被读错

“若 p 则 q”写作 $p\Rightarrow q$。它排除的正是 p 真而 q 假的情形。当前件为假时，整个材料蕴含为真，并非声称我们发现了某种实际因果关系，而是说它没有违反所指定的条件约束。这个约定保证“所有满足 p 的对象都满足 q”与集合包含关系相配：找不到满足 p 却不满足 q 的对象，便没有反例。

“一个整数是四的倍数，则它是偶数”正确；“它是偶数，则它是四的倍数”是逆命题，整数二就是反例；“它不是四的倍数，则它不是偶数”是否命题，同样被二反驳；“它不是偶数，则它不是四的倍数”是逆否命题，与原命题等价。很多错误证明暗中把必要条件当成充分条件，恰好就是把原命题换成了未经证明的逆命题。

充分条件 p 保证 q，必要条件 q 是 p 成立时不可缺少的条件。若两个方向都成立，才写 $p\iff q$。例如对于整数 n，“n 为偶数”与“n 的平方为偶数”等价，需要分别证明两个方向，不能只算出偶数的平方仍为偶数就结束。

两种证明：直接构造与逆否

若 n 为偶数，按定义存在整数 k 使 $n=2k$，于是 $n^2=4k^2=2(2k^2)$，而括号内仍为整数，故平方为偶数。证明最后一句并非多余，因为“偶数”的定义要求某个整数的两倍，而不只是一个随意实数的两倍。

反向直接从 $n^2=2m$ 开始不容易看出 n 的形式，可以证明逆否命题：若 n 为奇数，写成 $n=2k+1$，则 $$n^2=4k^2+4k+1=2(2k^2+2k)+1,$$ 所以平方为奇数。逆否命题成立，原来的反向蕴含也成立。两个方向合并，完成等价证明。这里用到了整数不是偶数就是奇数的分类；如果把 n 换成任意实数，“奇偶”一词本身就不再按这个定义适用。

反证法则是假设要证结论的否定，从既有前提出发推出矛盾。例如假设存在最大的整数 N，那么 N+1 仍为整数并严格大于 N，与最大性矛盾，故最大整数不存在。这个证明既没有列举所有整数，也没有凭“似乎总能再加一”的直觉止步，而是把这种构造放入了明确的假设与矛盾结构中。

量词顺序：依赖关系写在符号里

在实数范围内，$\mathrm{\forall }x\mathrm{\exists }y(y>x)$ 为真，因为对每个给定 x 可以选择 y=x+1。这里的 y 允许依赖 x。交换顺序的 $\mathrm{\exists }y\mathrm{\forall }x(y>x)$ 为假，因为不可能先选一个固定实数 y，再让它超过所有实数：取 x=y 就破坏严格不等式。两个公式词语相似，数学要求却完全不同。

极限定义中“对每个误差容许量，都存在足够小的输入范围”也包含这种依赖。输入范围可以依赖所指定的误差和研究的函数，但不能依赖随后在这个范围内任意选取的点。如果把 $\delta$ 选成事后依赖 x 的量，就可能把一个真正的统一控制条件变成几乎没有内容的陈述。学习极限时先用普通语言说清谁先选、谁后选，会比机械背符号更可靠。

量词的否定按 $$\mathrm{\neg }(\mathrm{\forall }xP(x))\equiv \mathrm{\exists }x\mathrm{\neg }P(x),\mathrm{\neg }(\mathrm{\exists }xP(x))\equiv \mathrm{\forall }x\mathrm{\neg }P(x)$$ 转换。例如“每个学生都做对至少一道题”的否定，是“存在一个学生，一道题也没做对”，不是“每个学生都至少做错一道题”。设 P(s,q) 表示学生 s 做对题 q，原句为 $\mathrm{\forall }s\mathrm{\exists }qP(s,q)$，否定后为 $\mathrm{\exists }s\mathrm{\forall }q\mathrm{\neg }P(s,q)$。逐层取反可以避免自然语言中的歧义。

归纳法证明的到底是什么

证明对所有非负整数 n 都成立的命题，可以先证明 n=0 的基础步，再证明：对任意 k≥0，若第 k 项成立，则第 k+1 项成立。基础步启动链条，归纳步保证链条不会中断；二者缺一不可。它不是从几个数值“猜到规律”，而是利用自然数的归纳结构证明无限多项。

例如证明 $\sum _{j=1}^{n}j=n(n+1)/2$，n=0 时空和为零，等式成立。假设对 k 成立，那么 $$\sum _{j=1}^{k+1}j=\frac{k(k+1)}{2}+(k+1)=\frac{(k+1)(k+2)}{2}.$$ 于是归纳步完成。假设的只是某个任意 k 处的等式，用来证明下一步，并没有先假设所有 n 都成立，所以这不是循环论证。若命题只从 n=1 开始，也可以把基础步放在一；索引范围必须与实际命题一致。

计算机核查前一百万个数值，只证明了一百万个实例。它可以帮助发现反例、检查猜想或验证实现，却不能单独替代对全部自然数的证明。反过来，一个反例就足以否定全称命题，但反例只需落在所声明的对象范围内；拿复数例子反驳一个明确限定实数的定理没有作用。

空条件、存在性和唯一性

全称语句并不自动保证对象存在。“某个空集合的所有元素都满足条件”为真，因为没有元素能构成反例；同一空集合中“存在一个元素满足条件”则为假。这叫空真现象，谈的是在空子集上限制量词，并非随意改变一阶逻辑中通常采用的非空论域约定。若推理需要至少一个对象，必须另加存在性前提。

例如“所有满足方程的实数都为正”，若方程根本没有实数解，这句话仍不能被反例推翻，却不能据此推出“存在正实数解”。求方程时先证明候选解必须满足某条件，只完成必要性；还要实际构造解并代回，才能建立存在性。这个逻辑差别正是许多计算题中“筛选候选”与“确认答案”的区别。

存在唯一对象比存在对象更强。对实数方程 $x^2=4$，二是一个存在性见证，但负二也是解，因而不唯一；若将论域限制为非负实数，则存在且唯一。证明唯一性通常先任取两个满足条件的对象，再证明它们相等，而不能因为计算过程中只找到一个就断言没有别的。

推理规则也需要方向检查。从 $P$ 和 $P\Rightarrow Q$ 可以推出 $Q$，称为肯定前件；从 $\mathrm{\neg }Q$ 和同一个蕴含可推出 $\mathrm{\neg }P$。但已知 $Q$ 时不能倒推 $P$，例如“是四的倍数则为偶数”与“为偶数”不能推出四的倍数。这种错误称为肯定后件，与此前混淆必要充分条件是同一个逻辑问题。

形式证明与数学逻辑的更大范围

真值表可以判定有限个命题变量组成的公式是否在所有真假赋值下为真，这叫重言式。若在所有使前提为真的解释下结论也为真，就说推理在语义上有效；给出按照规定推理规则组织的有限公式序列，则是在某个系统中作形式推导。两者之间的联系是数学逻辑研究的对象，不能仅凭日常语感认定“显然可以推出”。

现代逻辑还研究带量词的语言、模型、形式系统的一致性与表达能力，以及哪些问题能够由算法判定。本条的二值真值表只是入门工具，不是整个数学逻辑。不同形式系统可能采用不同规则；讨论某个深层定理之前，应先说明使用的语言和系统，避免把针对特定系统的结果夸大成“所有数学都无法证明自己”。

历史背景与应用

逻辑研究有古代渊源，现代符号方法的形成则经历了长期发展。George Boole 在 1847 年的《The Mathematical Analysis of Logic》和 1854 年的《An Investigation of the Laws of Thought》中推进了逻辑的代数处理。University College Cork 的 Boole 纪念项目核对了两部著作的年份与逻辑研究背景。Boole 的贡献不等于“发现了人类推理”，今天的完整谓词逻辑体系也不能全部归于这两本书。

逻辑的用途包括整理定理假设、分析程序分支、写数据库查询以及验证软件性质。例如程序条件“输入合法且余额足够”与“输入合法或余额足够”只差一个连接词，却可能产生完全不同的可执行行为。数学证明同样需要检查每一步用到了什么前提，特别是除以一个量之前是否知道它非零，以及交换极限顺序之前是否满足额外条件。

一个量词否定的完整核验

考虑“存在一个最小正实数”。其形式是 $\mathrm{\exists }a>0\mathrm{\forall }x>0(a\le x)$。逐层否定得到 $\mathrm{\forall }a>0\mathrm{\exists }x>0(x<a)$，即每个正实数都有一个更小的正实数。对于任意给定的 a，选择 x=a/2，既保持正数条件，又满足严格小于，故否定命题成立。这里由“不大于”变成“严格大于”，并交换全称与存在量词；不能只改量词而保留原来的不等号。

编者评注（AI 辅助）

逻辑学习的收益不是把每一句话都改成符号，而是能及时追问：对象范围是什么，条件是否足够，所选常数能依赖谁，反例究竟反驳了哪一句话。建议把一份熟悉的计算题解改写成完整证明，标出每次使用的定义和前提。这样的练习能把形式规则连接到实际推理，也比单独背真值表更容易迁移到分析、代数和程序验证。

参考来源与延伸阅读

• Oscar Levin：命题逻辑，另见同书证明方法与量词章节。
• MacTutor：George Boole，用于著作年代与历史背景。
• Oscar Levin，《Discrete Mathematics: An Open Introduction》第 0、3 章：量词、逻辑与证明。
• 极限 · 组合数学 · 数学建模