离散数学及其应用-逻辑和证明-证明的方法和策略
- 怀旧特辑
- 2025-09-26 14:41:05
- 7622
1.8. 证明的方法和策略
本章将研究关于证明的艺术和科学方面的一些问题。我们将提供如何寻找一个定理的证明的一些忠告。我们还将描述一些窍门，包括如何通过反向思维和通过改编现有证明来发现证明。
穷举证明法和分情形证明法
为了证明如下的条件语句
(p1∨p2∨⋯∨pn)→q(p_1 \lor p_2 \lor \dots \lor p_n) \to q(p1∨p2∨⋯∨pn)→q
可以使用永真式
[(p1∨p2∨⋯∨pn)→q]↔[(p1→q)∧(p2→q)∧⋯∧(pn→q)][(p_1 \lor p_2 \lor \dots \lor p_n) \to q] \harr [(p_1 \to q) \land (p_2 \to q) \land \dots \land (p_n \to q) ][(p1∨p2∨⋯∨pn)→q]↔[(p1→q)∧(p2→q)∧⋯∧(pn→q)]
如果pnp_npn为假，则(pn→q)(p_n \to q)(pn→q)为真。
来证明由命题p1, p2, …,pnp_1, \: p_2 , \: \dots , p_np1,p2,…,pn 的析取式组成前提的原条件语句。这种论证称为分情形证明法（proof by cases）。
穷举证明法
有些定理可以通过校验相对少量的例子来证明。这样的证明叫做穷举证明法（exhaustive proof, proof by exhaustion）。因为这些证明是要穷尽所有可能性的。
证明如果nnn是一个满足n≤4n \le 4n≤4的正整数时，则有(n+1)3≥3n(n+1)^3 \ge 3^n(n+1)3≥3n。
采用穷举证明法。我们只需检验当n=1,2,3,4n = 1,2,3,4n=1,2,3,4时，不等式(n+1)3≥3n(n+1)^3 \ge 3^n(n+1)3≥3n成立。
分情形证明法 分情形证明一定要覆盖定理中出现的所有可能情况。
存在性证明
存在性证明
许多定理是断言特定类型对象的存在性。这种类型的定理是形如∃xP(x)\exist x P(x)∃xP(x)的命题，其中PPP是谓词。∃xP(x)\exist x P(x)∃xP(x)这类命题的证明称为存在性证明（existence proof）。
有时可以通过找出一个使得P(a)P(a)P(a)为真的元素aaa（称为一个物证）来给出∃xP(x)\exist x P(x)∃xP(x)的存在性证明。这样的存在性证明是构造性的（constructive）。也可以给出一种非构造性的（nonconstractive）存在性证明，即不是找出使P(a)P(a)P(a)为真的元素aaa，而是以某种其他方式来证明∃xP(x)\exist x P(x)∃xP(x)为真。
证明存在无理数xxx和yyy使得xyx^yxy是有理数。
2\sqrt{2}2是无理数。考虑数22\sqrt{2}^{\sqrt{2}}22。如果它是有理数，那就存在两个无理数xxx和yyy且xyx^yxy是有理数。
如果22\sqrt{2}^{\sqrt{2}}22是无理数，那么令x=22x = \sqrt{2}^{\sqrt{2}}x=22且y=2y=\sqrt{2}y=2，
因此xy=(22)2=22⋅2=22=2x^y=(\sqrt{2}^{\sqrt{2}})^{\sqrt{2}}=\sqrt{2}^{\sqrt{2} \cdot \sqrt{2}}=\sqrt{2}^2 = 2xy=(22)2=22⋅2=22=2
唯一性证明
某些定理断言具有特定性质的元素唯一存在。换句话说，这些定理断言恰好只有一个元素具有这个性质。
唯一性证明（uniqueness proof）的两个部分如下：
存在性：证明存在某个元素xxx具有期望的性质。
唯一性：证明如果y≠xy \neq xy=x，则yyy不具有期望的性质。
评注证明存在唯一元素xxx使得P(x)P(x)P(x)为真等同于证明语句
∃x(P(x)∧∀y(y≠x→¬P(y)))\exist x (P(x) \land \forall y(y \neq x \to \lnot P(y)) )∃x(P(x)∧∀y(y=x→¬P(y)))
证明策略
正向推理（forward reasoning）
无论选择什么证明方法，都需要为证明找一个起点。条件语句的直接证明就从前提开始。利用这些前提以及公理和已知定理，用导向结论的一系列步骤来构造证明。这类推理称为正向推理。
反向推理（backward reasoning）
要反向推理证明命题qqq，我们就寻找一个命题ppp并可证明其具有性质p→qp \to qp→q。（注意，寻找一个命题rrr并能证明其具有q→rq \to rq→r不会有所帮助，因为从q→rq \to rq→r和rrr得出qqq为真是一种窃取论题的错误推理）
