命题逻辑与证明方法

本章主线：命题与逻辑联结词 → 量词与逻辑等价 → 基本证明方法 → 算法正确性与不变量。

1 命题

能够明确判断真假的陈述句称为命题。

例如：

$2+3=5$ 是真命题；
$7$ 是偶数是假命题；
“请关闭窗口”不是命题；
“这个算法很优秀”通常不是严格命题，因为“优秀”的标准不明确。

命题通常用字母 $P,Q,R$ 表示。

命题只有两种真值：

真，记作 $T$ ；
假，记作 $F$ 。

2 否定

命题 $P$ 的否定记作 $\neg P$ ，表示“ $P$ 不成立”。

若 $P$ 为真，则 $\neg P$ 为假；若 $P$ 为假，则 $\neg P$ 为真。

例如，若 $P$ 表示“ $x$ 是偶数”，则 $\neg P$ 表示“ $x$ 不是偶数”。

注意，否定一个命题时，需要否定整个陈述，而不是只替换其中某个词。

例如，“所有顶点都被访问”的否定是“至少存在一个顶点未被访问”。

3 合取

命题 $P$ 与 $Q$ 的合取记作 $P\land Q$ ，表示“ $P$ 且 $Q$ ”。

只有当 $P,Q$ 都为真时， $P\land Q$ 才为真。

例如，“ $x>0$ 且 $x<10$ ”可以写成 $x>0\land x<10$ 。

在集合语言中：

x\in A\cap B\Longleftrightarrow x\in A\land x\in B.

4 析取

命题 $P$ 与 $Q$ 的析取记作 $P\lor Q$ ，表示“ $P$ 或 $Q$ ”。

数学中的“或”通常是包含性的：只要至少一个命题为真， $P\lor Q$ 就为真。

例如，“ $x\in A$ 或 $x\in B$ ”包括 $x$ 同时属于 $A,B$ 的情况。

在集合语言中：

x\in A\cup B\Longleftrightarrow x\in A\lor x\in B.

5 蕴含

命题“若 $P$ ，则 $Q$ ”记作 $P\Longrightarrow Q$ 。

其中：

$P$ 称为前件；
$Q$ 称为后件。

$P\Longrightarrow Q$ 只在 $P$ 为真而 $Q$ 为假时为假。

例如：

若一个整数能被 $4$ 整除，则它是偶数。

记作

4\mid n\Longrightarrow2\mid n.

这里“能被 $4$ 整除”是充分条件，“是偶数”是必要条件。

6 充分条件与必要条件

若 $P\Longrightarrow Q$ ，则：

$P$ 是 $Q$ 的充分条件；
$Q$ 是 $P$ 的必要条件。

“充分”表示只要满足 $P$ ，就足以推出 $Q$ 。

“必要”表示若想让 $P$ 成立， $Q$ 必须成立。

例如，若一个图是树，则它一定连通。

因此，“是树”是“连通”的充分条件，“连通”是“是树”的必要条件。

但连通图不一定是树，所以“连通”不是“是树”的充分条件。

7 逆命题、否命题与逆否命题

原命题为

P\Longrightarrow Q.

对应的三个命题为：

逆命题： $Q\Longrightarrow P$ ；
否命题： $\neg P\Longrightarrow\neg Q$ ；
逆否命题： $\neg Q\Longrightarrow\neg P$ 。

原命题与逆否命题等价。

逆命题与否命题等价。

但原命题通常不与逆命题等价。

例如原命题：

若 $n$ 能被 $4$ 整除，则 $n$ 是偶数。

逆命题：

若 $n$ 是偶数，则 $n$ 能被 $4$ 整除。

逆命题为假，因为 $n=2$ 是反例。

逆否命题：

若 $n$ 不是偶数，则 $n$ 不能被 $4$ 整除。

该命题与原命题等价。

8 充要条件

若 $P\Longrightarrow Q$ 且 $Q\Longrightarrow P$ ，则称 $P$ 与 $Q$ 互为充要条件，记作

P\Longleftrightarrow Q.

证明充要条件时，需要分别证明两个方向：

$P\Longrightarrow Q$ ；
$Q\Longrightarrow P$ 。

例如，整数 $n$ 是偶数，当且仅当存在整数 $k$ ，使得 $n=2k$ 。

9 量词

9.1 全称量词

“对所有”记作 $\forall$ 。

例如

\forall x\in\mathbb R,\quad x^2\ge0.

表示对任意实数 $x$ ，都有 $x^2\ge0$ 。

9.2 存在量词

“存在”记作 $\exists$ 。

例如

\exists x\in\mathbb Z,\quad x^2=4.

表示存在整数 $x$ ，满足 $x^2=4$ 。

10 含量词命题的否定

全称命题的否定是存在命题：

\neg(\forall x,\ P(x)) \Longleftrightarrow \exists x,\ \neg P(x).

存在命题的否定是全称命题：

\neg(\exists x,\ P(x)) \Longleftrightarrow \forall x,\ \neg P(x).

例如，“所有数组元素都为正数”的否定是“至少存在一个数组元素不是正数”。

“存在一个顶点未访问”的否定是“所有顶点都已访问”。

11 德摩根律

命题逻辑中的德摩根律为

\neg(P\land Q)\Longleftrightarrow\neg P\lor\neg Q,

\neg(P\lor Q)\Longleftrightarrow\neg P\land\neg Q.

例如，“不同时满足 $P,Q$ ”表示“至少一个不成立”。

集合中的德摩根律正是这一逻辑规律的集合形式。

12 直接证明

直接证明从已知条件出发，通过定义和已知结论推出目标结论。

例如证明：若 $a,b$ 都是偶数，则 $a+b$ 是偶数。

由偶数定义，存在整数 $m,n$ ，使得 $a=2m$ ， $b=2n$ 。

于是 $a+b=2(m+n)$ 。因为 $m+n\in\mathbb Z$ ，所以 $a+b$ 是偶数。

直接证明适合推导链条清晰的问题。

13 逆否证明

要证明 $P\Longrightarrow Q$ ，可以改为证明等价的逆否命题 $\neg Q\Longrightarrow\neg P$ 。

例如证明：若 $n^2$ 是偶数，则 $n$ 是偶数。

直接从 $n^2$ 是偶数出发不够方便，可以证明逆否命题：

若 $n$ 是奇数，则 $n^2$ 是奇数。

设 $n=2k+1$ ，则

n^2=(2k+1)^2=2(2k^2+2k)+1,

所以 $n^2$ 是奇数。

因此原命题成立。

14 反证法

反证法用于证明命题 $P$ 。

先假设 $\neg P$ 成立，再从这个假设推出矛盾，从而说明 $\neg P$ 不可能成立，因此 $P$ 成立。

例如证明 $\sqrt2$ 不是有理数。

假设 $\sqrt2=p/q$ ，其中 $p,q$ 互质。

平方后得 $p^2=2q^2$ ，所以 $p^2$ 是偶数，从而 $p$ 是偶数。

设 $p=2k$ ，代入得 $q^2=2k^2$ ，所以 $q$ 也是偶数。

这与 $p,q$ 互质矛盾，因此 $\sqrt2$ 不是有理数。

15 分类讨论

当问题可以按互斥情况完整划分时，可以分别证明每种情况。

例如证明任意整数 $n$ 的 $n(n+1)$ 都是偶数。

整数 $n$ 只有两种情况：

若 $n$ 是偶数，则 $n(n+1)$ 是偶数；
若 $n$ 是奇数，则 $n+1$ 是偶数，所以 $n(n+1)$ 是偶数。

两种情况覆盖所有整数，因此结论成立。

分类讨论需要满足：

各情况覆盖全部可能；
不遗漏情况；
各分支结论都成立。

16 数学归纳法

数学归纳法用于证明关于自然数 $n$ 的命题 $P(n)$ 。

基本步骤为：

证明基础情形 $P(n_0)$ 成立；
假设 $P(k)$ 成立；
在该假设下证明 $P(k+1)$ 成立。

若两步都完成，则 $P(n)$ 对所有 $n\ge n_0$ 成立。

例如证明

1+2+\cdots+n=\frac{n(n+1)}2.

基础情形 $n=1$ 时成立。

假设 $n=k$ 时成立，即

1+2+\cdots+k=\frac{k(k+1)}2.

则

\begin{aligned} 1+2+\cdots+k+(k+1) &=\frac{k(k+1)}2+(k+1)\\ &=\frac{(k+1)(k+2)}2. \end{aligned}

所以 $n=k+1$ 时也成立。

17 强归纳法

强归纳法在证明 $P(k+1)$ 时，可以假设 $P(n_0),P(n_0+1),\dots,P(k)$ 全部成立。

例如证明每个大于 $1$ 的整数都可以分解为质数乘积。

若 $n$ 是质数，则结论成立。

若 $n$ 不是质数，则 $n=ab$ ，其中 $1<a,b<n$ 。

根据归纳假设， $a,b$ 都可以分解为质数乘积，因此 $n$ 也可以。

强归纳法适合当前状态依赖多个更小状态的问题。

18 构造证明

构造证明通过直接给出满足条件的对象证明其存在。

例如证明任意偶数 $n$ 都可以写成两个整数之和。

可以直接构造

n=0+n.

在算法中，给出一个可行解、构造一条路径或构造一种排列，都属于构造思想。

19 反例

要否定全称命题 $\forall x,\ P(x)$ ，只需找到一个反例 $x_0$ ，使得 $P(x_0)$ 不成立。

例如命题“所有质数都是奇数”是假的，因为 $2$ 是质数但不是奇数。

反例只能否定命题，不能证明命题。

检查猜想时，应优先寻找：

最小规模；
边界情况；
空集或单元素情况；
极端值；
对称情况。

20 不变量

不变量是在算法执行过程中始终保持成立的性质。

证明算法正确性时，通常分为三步：

初始化后不变量成立；
每次操作都保持不变量；
算法结束时，不变量能够推出目标结论。

例如，二分查找可以维护不变量：

答案始终位于当前搜索区间内。

每次根据中点结果缩小区间，但不丢失答案。

并查集可以维护不变量：

两个元素属于同一个集合，当且仅当它们最终拥有相同根节点。

21 循环不变量

循环不变量是在每次循环开始或结束时都成立的命题。

例如插入排序处理到位置 $i$ 时，可以维护：

前 $i$ 个元素已经有序，并且它们仍然是原数组前 $i$ 个元素的一个排列。

证明循环正确性通常包括：

初始化：第一次循环前成立；
保持：一次循环后仍成立；
终止：循环结束时推出最终目标。

22 极小反例法

要证明某命题对所有对象成立，可以假设存在反例，并选择其中规模最小的反例。

然后利用其最小性，将它缩小、拆分或变换，构造出更小反例，从而产生矛盾。

极小反例法常用于：

图论证明；
贪心正确性；
递归结构；
整数分解问题。

其核心是利用“最小反例的所有更小结构都不是反例”。

23 交换论证

交换论证常用于证明贪心算法。

基本思路为：

取一个最优解；
若它不包含贪心选择，就交换其中部分结构；
证明交换后仍然可行，且答案不变差；
得到一个包含贪心选择的最优解。

这说明贪心选择至少存在于某个最优解中。

例如活动选择问题中，可以将最优解的第一个活动替换为结束最早的活动，而不会减少可选活动数量。

24 算法证明的基本结构

证明一个算法正确，通常需要分别说明：

24.1 可行性

算法产生的结果满足题目全部约束。

24.2 完备性

算法不会遗漏所有可能的正确答案。

24.3 最优性

若题目要求最优解，需要证明算法所得答案不劣于任何其他可行解。

24.4 终止性

算法能够在有限步内结束。

不同算法的证明重点不同：

搜索：完备性与不重复；
贪心：最优性；
动态规划：状态定义与转移完备性；
数据结构：操作前后的不变量；
图算法：路径、割、连通性等结构性质。

25 常见逻辑错误

25.1 证明了逆命题

已知需要证明 $P\Longrightarrow Q$ ，却只证明了 $Q\Longrightarrow P$ 。

25.2 把必要条件当充分条件

由“树一定连通”，错误推出“连通图一定是树”。

25.3 用若干例子代替证明

有限个例子只能支持猜想，不能证明全称命题。

25.4 漏掉边界情况

例如空图、单点图、长度为 $0$ 的路径、数组为空等。

25.5 循环论证

证明 $P$ 时使用了尚未证明的 $P$ 本身。

25.6 量词顺序混淆

下面两个命题不同：

\forall x,\ \exists y,\ P(x,y),

\exists y,\ \forall x,\ P(x,y).

前者允许不同的 $x$ 选择不同的 $y$ ；后者要求存在同一个 $y$ 对所有 $x$ 都有效。

26 与算法的联系

并查集

不变量是：父指针形成森林，每棵树对应一个等价类。

二分答案

需要证明判定函数具有单调性，并维护答案仍在搜索区间中的不变量。

Kruskal

常用交换论证或割性质证明贪心选边不会破坏最优性。

Dijkstra

在边权非负的前提下，维护已经确定的顶点，其最短距离不会再被后续路径改进。

动态规划

常用归纳法证明状态值等于对应子问题的最优答案。

拓扑排序

通过每次删除入度为 $0$ 的顶点，保持剩余图仍是 DAG。

28 与后续内容的联系

集合恒等式可以转化为命题逻辑等价；
等价关系、偏序关系、树与群等结构都需要通过定义和证明建立；
数学归纳法、循环不变量与交换论证分别支撑递归、迭代与贪心算法；
后续各数学分支中的证明，均默认使用本章的逻辑语言与证明规范。

29 本章思考题

判断下列句子是否为命题：
- $3+5=8$ ；
- 请输出答案；
- 存在最大的质数；
- 这个算法运行得很快。
写出命题“所有顶点都已访问”的否定。
写出命题“存在一个整数 $x$ ，使得 $x^2=2$ ”的否定。
设原命题为“若图是树，则图连通”，写出其逆命题、否命题和逆否命题。
说明原命题与逆否命题为什么等价。
证明：若 $n$ 是奇数，则 $n^2$ 是奇数。
使用逆否证明：若 $n^2$ 是偶数，则 $n$ 是偶数。
使用数学归纳法证明：
$1+3+5+\cdots+(2n-1)=n^2.$
找出命题“若 $ab$ 是偶数，则 $a,b$ 都是偶数”的反例。
说明二分查找中可以维护什么循环不变量。
说明为什么用若干测试样例不能证明算法一定正确。
尝试用交换论证说明：区间调度中优先选择结束时间最早的区间是合理的。

数学 > 数学语言与证明

#数学/数学语言与证明 #数学/证明

命题逻辑与证明方法

http://miqiu.space/posts/5efd66d4/

作者

Miqiu

发布于

2026年7月1日

许可协议

集合上一篇

关系下一篇