反证法

下面列出一些比较有名的反证法

不同质量的两球下落速度一样

我们来用纯粹的逻辑，不使用任何物理定理（如牛顿定律），只用“整体”的概念和反证法来证明两个球的下落速度一样。

前提：

  • 真空环境: 没有空气阻力。
  • 相同起始条件: 两个球从相同高度静止释放。
  • 球的下落规律： 一个（单个）球的下落速度只取决于它自身的下落规则（这个假设是避免掉用物理定理）。
  • 整体性： 将两个球视为一个整体，这个整体的下落速度也只取决于自身的下落规则。

证明：

  1. **假设：**假设两个球 A 和 B，质量不同，单独下落时速度不同。我们假设 A 比 B 下落得快。

  2. **连接：**用一根轻质、无质量的绳子将 A 和 B 连接起来。现在 A 和 B 成为一个 整体 （我们称其为 AB）。

  3. 整体的下落： 由于 AB 是一个整体，所以AB的下落速度应该遵循AB的自身下落规则。

  4. 两种情况导致矛盾：

    • 情况一： 假设连接后下落速度处于A和B速度之间。A试图快速下落，但受到了绳子的牵制。B 本来慢，现在被 A 带动，也下落得快了一点。 那么，A的速度变慢了, B的速度变快了，这个连接改变了 A、B 自身的下落规则。 然而，绳子是 轻质，无质量 的，本身不应该提供任何下落驱动力或阻力。绳子只是把 A 和 B 绑在一起，成为一个系统（该系统遵循自身的下落规则）。 但是，如果绳子改变了A和B的下落规则，那么这个联合整体的行为则来源于了新的其他外力，而该外力却不存在. 因此，这本身就是一种矛盾。
    • 情况二： 假设连接以后，整体速度是A。那么B是被A拉下去的。相当于A自己下落，绳子拉着没有下落的B. 但由于绳子是 轻质、无质量 的，如果真的有这种情况，就相当于仅仅是A下落，而B静止不动。此时这个系统不应该被看成一个整体，而仍然是A单独下落。这与第3点整体的下落： 由于 AB 是一个整体，所以AB的下落速度应该遵循AB的自身下落规则。相抵触。B静止不动或者只有微弱的下落，绳子无法承受这个张力。所以这种情况不存在。假设整体速度是B也是一样的。

  5. 如果最初的假设是正确的（A 和 B 的速度不同，并且互相影响），那么连接后要么 A 下落变慢，B 下落变快，要么A拉着B， 或者B拖着A。然而这都需要一种力量来影响对方的下落. 轻质无质量的绳子不应该对球 A 和球 B 施加任何额外的力，导致 A 和 B 试图互相改变其下落速度与前提相悖。

  6. 结论： 因为假设 A 和 B 的速度不同会导致逻辑矛盾，因此最初的假设是错误的。A 和 B 的速度必须相同。这意味着，在真空环境中，两个质量不同的球在相同的起始条件下下落速度相同。

2\sqrt 2是无理数

无理数的定义:

  1. https://zh.wikipedia.org/wiki/無理數

2\sqrt{2} 是无理数的证明

人们发现了许多方法证明 2\sqrt{2} 是无理数。以下是反证法的证明。

常见的证明

  1. 假设 2\sqrt{2} 是有理数，即有整数 a0a_0、b0b_0，使得

    a0b0=2\frac{a_0}{b_0} = \sqrt{2}

  2. 将 2\sqrt{2} 重写成最简分数 ab\frac{a}{b}，即 aa 和 bb 互素，且

    (ab)2=2(\frac{a}{b})^2 = 2

  3. 所以

    a2b2=2\frac{a^2}{b^2} = 2

    即

    a2=2b2a^2 = 2b^2

  4. 因为 2b22b^2 必为偶数，故 a2a^2 亦是偶数。

  5. 故 aa 为偶数（奇数的平方不会是偶数）。

  6. 所以必有一整数 kk，使得

    a=2ka = 2k

  7. 将（6）的式子代入（3）：

    2b2=(2k)22b^2 = (2k)^2

  8. 化简得

    b2=2k2b^2 = 2k^2

  9. 因为 2k22k^2 是偶数，所以 b2b^2 是偶数，

    bb 亦是偶数。

  10. 所以 aa 和 bb 都是偶数，跟 ab\frac{a}{b} 是最简分数的假设矛盾。

  11. 因为导出矛盾，所以（1）的假设错误，2\sqrt{2} 不是有理数，即是无理数。

这个证明可推广至证明任何非完全平方数的正整数 nn，其算术平方根 n\sqrt{n} 为无理数。

其它题目

好的，我来列举一些类似反证法的应用，涵盖数学、逻辑、计算机科学等方面：

1. 数学领域:

  • 证明素数有无穷多个: 假设素数只有有限个，将它们全部相乘再加1，得到的新数要么是素数，要么能被比所有已知素数都大的素数整除，这与只有有限个素数的假设相矛盾。
  • 证明 3\sqrt{3} 是无理数: 证明方法与证明 2\sqrt{2} 类似，假设 3\sqrt{3} 是有理数，导出矛盾。
  • 欧几里得几何中平行公设的独立性证明: 试图通过假设平行公设不成立，推出与欧几里得其他公设矛盾的结果，从而证明它的必要性。虽然最终未能证明 Euclidean 几何的错误性，但为非欧几何的诞生奠定了基础。
  • 证明某个集合不可数: 比如证明实数集合不可数。先假设实数集合是可数的，然后构造一个不在假设的可数序列中的实数，导出矛盾。 （康托尔对角线法）
  • 鸽巢原理的证明: 尽管鸽巢原理本身很简单，但可以用反证法来正式证明。如果 n 个鸽子要入住 m 个鸽巢，且 n > m，假设每个鸽巢最多只有一只鸽子，那么总共最多只能容纳 m 只鸽子，与有 n 只鸽子矛盾。

2. 逻辑学:

  • 归谬法 (Reductio ad absurdum): 这是反证法的正式名称，在逻辑论证中经常使用。通过假设某个命题成立，然后推导出荒谬或自相矛盾的结论，从而证明该命题是错误的。
  • 证明逻辑规则的有效性: 假设某个逻辑规则无效，即存在一种情况下前提为真但结论为假，然后通过构造具体的例子来展示这种矛盾情况，证明该规则是不可靠的。

3. 计算机科学:

  • 证明算法的正确性: 有时可以通过假设算法不正确，然后找到一个输入使得算法产生错误的输出，从而证明算法在特定输入下的错误。
  • 证明某个问题是不可解的 (Undecidable): 例如，证明停机问题是不可解的。假设存在一个可以判断任何程序是否会停机的算法，然后构造一个利用该算法的程序，使得该程序在运行时与该算法的判断结果相反，从而导出矛盾。
  • 图论中的一些定理: 例如，证明一个图中存在欧拉回路的充要条件是所有顶点的度数都是偶数。可以反证法证明必要性：假设存在一个图，其中每个顶点的度数都是偶数，但是不存在欧拉回路。然后通过构造路径等方法，最终导出矛盾。

4. 其他领域:

  • 法律: 在法庭上，律师可能会使用类似反证法的策略来质疑对方的证词或证据。假设对方的说法成立，然后指出由此会产生的荒谬或不可能的结果。
  • 哲学论证: 许多哲学论证都依赖于反证法。哲学家可能会通过假设某个观点成立，然后指出由此会导致令人无法接受的伦理、形而上学或其他方面的后果，从而反驳该观点。

总结:

反证法是一种强大的论证工具，它通过展示假设的矛盾性来证明结论的正确性。它在很多领域都有广泛的应用，特别是在需要证明某个事物不存在、某个问题不可解，或某个假设不成立的情况下。关键在于找到一个从假设到矛盾的清晰的逻辑链条。

反证法(归谬吧)从数理逻辑上的正确性证明

出自离散数学第二版 P? 页面