数据结构与算法 / 系统课时
直接证明与反证法
直接证明与反证法
算法正确性常写成条件命题。例如对每个满足输入约定的 ,如果程序执行到结束,就应得到约定的结果。证明前应先确定对象的定义域、前提和目标,再选择推理方向。 MIT《计算机科学的数学》证明资料
学习目标
- 分清原命题、逆命题、否命题和逆否命题。
- 用直接证明、逆否和反证完成整数性质的证明。
- 区分逻辑穷举、反例和有限范围的程序测试。
条件命题的四种形式
| 形式 | 表达式 | 与原命题的关系 |
|---|---|---|
| 原命题 | 本身 | |
| 逆命题 | 一般不等价 | |
| 否命题 | 一般不等价 | |
| 逆否命题 | 逻辑等价 |
逆命题和否命题互为逆否,因此它们彼此等价。原条件命题的否定则是 。若原命题还带全称量词“对每个 ”,否定是“存在一个 使 成立而 不成立”。寻找反例时,要验证前提也确实成立。 MIT《计算机科学的数学》命题逻辑
直接证明
证明“对任意整数 ,若 是奇数,则 是奇数”。任取满足前提的 ,写成 ,其中 是整数。展开可得 。括号内仍是整数,按奇数定义,结论成立。这也覆盖负奇数,因为定义中的 可以为负。
逆否证明
证明“对任意整数 ,若 为偶数,则 为偶数”。其逆否命题是“若 不是偶数,则 不是偶数”。整数可以分为奇数或偶数,所以这正是刚证明的结论。单独交换前提和结论会得到另一个命题。比如“能被 4 整除就能被 2 整除”成立,反过来不成立, 就足以反驳逆命题。
反证法
证明条件命题 时,可同时假设 与 ,再找出与定义、已知事实或某个假设的明确冲突。若目标是单独的命题,例如“ 是无理数”,就假设它的否定。
假设 ,其中 是互质的正整数。平方得 ,由上一节的偶数结论可知 为偶数。令 ,代入得 ,所以 也为偶数。两者有公因子 2,与互质矛盾。因此 不能写成有理分数。 MIT《计算机科学的数学》证明方法

用 Python 核对逻辑形式
两个布尔变量只有四种组合。遍历四行可以完整验证表中的逻辑等价。整数命题的定义域无限,遍历一段整数可以发现反例,但覆盖不了所有合法整数。以下用 Python 3.11 或以上运行。
from itertools import product
def implies(p: bool, q: bool) -> bool:
return (not p) or q
rows = list(product((False, True), repeat=2))
print("contrapositive:", all(implies(p, q) == implies(not q, not p) for p, q in rows))
print("negation:", all((not implies(p, q)) == (p and not q) for p, q in rows))
print("converse differs:", [(p, q) for p, q in rows if implies(p, q) != implies(q, p)])
print("integer converse counterexample:", next(n for n in range(4, 10) if n % 2 == 0 and n % 4 != 0))contrapositive: True
negation: True
converse differs: [(False, True), (True, False)]
integer converse counterexample: 6本课练习
用直接证明写出两个偶数相加的结果。再证明“若整数平方为奇数,则该整数为奇数”,检查逆否命题是否对应“若整数为偶数,则其平方为偶数”。下一课会用归纳法把证明从起点扩展到所有更大规模。