数据结构与算法 / 系统课时

直接证明与反证法

直接证明与反证法

算法正确性常写成条件命题。例如对每个满足输入约定的 xx,如果程序执行到结束,就应得到约定的结果。证明前应先确定对象的定义域、前提和目标,再选择推理方向。 MIT《计算机科学的数学》证明资料

学习目标

  • 分清原命题、逆命题、否命题和逆否命题。
  • 用直接证明、逆否和反证完成整数性质的证明。
  • 区分逻辑穷举、反例和有限范围的程序测试。

条件命题的四种形式

形式 表达式 与原命题的关系
原命题 P⇒QP⇒Q 本身
逆命题 Q⇒PQ⇒P 一般不等价
否命题 ¬P⇒¬Q\neg P⇒\neg Q 一般不等价
逆否命题 ¬Q⇒¬P\neg Q⇒\neg P 逻辑等价

逆命题和否命题互为逆否,因此它们彼此等价。原条件命题的否定则是 P∧¬QP\land\neg Q。若原命题还带全称量词“对每个 xx”,否定是“存在一个 xx 使 P(x)P(x) 成立而 Q(x)Q(x) 不成立”。寻找反例时,要验证前提也确实成立。 MIT《计算机科学的数学》命题逻辑

直接证明

证明“对任意整数 nn,若 nn 是奇数,则 n2n^2 是奇数”。任取满足前提的 nn,写成 n=2k+1n=2k+1,其中 kk 是整数。展开可得 n2=2(2k2+2k)+1n^2=2(2k^2+2k)+1。括号内仍是整数,按奇数定义,结论成立。这也覆盖负奇数,因为定义中的 kk 可以为负。

逆否证明

证明“对任意整数 nn,若 n2n^2 为偶数,则 nn 为偶数”。其逆否命题是“若 nn 不是偶数,则 n2n^2 不是偶数”。整数可以分为奇数或偶数,所以这正是刚证明的结论。单独交换前提和结论会得到另一个命题。比如“能被 4 整除就能被 2 整除”成立,反过来不成立,n=6n=6 就足以反驳逆命题。

反证法

证明条件命题 P⇒QP⇒Q 时,可同时假设 PP 与 ¬Q\neg Q,再找出与定义、已知事实或某个假设的明确冲突。若目标是单独的命题,例如“2\sqrt 2 是无理数”,就假设它的否定。

假设 2=a/b\sqrt 2=a/b,其中 a,ba,b 是互质的正整数。平方得 a2=2b2a^2=2b^2,由上一节的偶数结论可知 aa 为偶数。令 a=2ca=2c,代入得 b2=2c2b^2=2c^2,所以 bb 也为偶数。两者有公因子 2,与互质矛盾。因此 2\sqrt 2 不能写成有理分数。 MIT《计算机科学的数学》证明方法

证明方法选择流程图

用 Python 核对逻辑形式

两个布尔变量只有四种组合。遍历四行可以完整验证表中的逻辑等价。整数命题的定义域无限,遍历一段整数可以发现反例,但覆盖不了所有合法整数。以下用 Python 3.11 或以上运行。

python
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))
text
contrapositive: True
negation: True
converse differs: [(False, True), (True, False)]
integer converse counterexample: 6

本课练习

用直接证明写出两个偶数相加的结果。再证明“若整数平方为奇数,则该整数为奇数”,检查逆否命题是否对应“若整数为偶数,则其平方为偶数”。下一课会用归纳法把证明从起点扩展到所有更大规模。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

直接证明与反证法

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通