离散数学中的反证法

证明的记号是所有数学的关键。当我们想绝对确定地说某个性质对所有情况或所有数字都成立时，我们不仅仅是因为它听起来很好或听起来令人信服，而是因为我们能够做到这一点。在数学领域，各种类型的证明会反复出现。反证法就是其中一种。在本节中，我们将通过一个例子，借助反证法来证明这个陈述。

有时，使用直接论证/直接方法来证明一个猜想为真，是不可能的，或者会非常困难。例如：假设我们要证明“2的平方根是无理数”。可能存在无数个有理数可以包含2的平方根，但我们无法直接检验或排除它们。相反，我们会假设2的平方根是有理数，这将导致矛盾。还有一种强大的工具叫做“反证法”，它通过间接论证来证明一个猜想为真。

反证法需要遵循一些步骤，描述如下：

第一步：在第一步中，我们将假设结论的反面，描述如下：

1. 为了证明“素数有无穷多个”这个陈述，我们将假设素数是一个有限集合，大小为n。
2. 对于陈述“如果一个三角形是不等边三角形，则它的任意两条角都不相等”，我们将假设该三角形的最小的2个角相等。

第二步：只要假设与我们的前提相反，我们就开始使用假设来推导出新的结果。我们需要为以上两个例子建立一些东西，描述如下：

1. 对于第一个例子，我们将证明存在一个素数，它不在最初的n个素数组合中。
2. 对于第二个例子，我们将证明该三角形不能是또한。

第三步：这是最后一步。在这里，我们将得出结论，我们的假设是错误的，而其反面是正确的，这意味着我们最初的结论是正确的。

现在我们将理解这种方法是如何行得通的。为了理解这一点，我们将注意到我们正在直接证明我们原始陈述的逆否命题。（这意味着我们证明的是“非Y，则非X”）。因为逆否命题在逻辑上总是等价的，所以原始命题自然也成立。

请注意，通过矛盾，我们被迫拒绝我们的假设。这是因为我们基于该假设的其他步骤都是合理且合乎逻辑的。我们唯一可能犯的错误就是假设本身。通过间接证明，可以确定相反的结论与前提不一致。这时，原始结论就必须是真的。

反证法的定义

如果我们想通过矛盾来证明任何陈述或某事，那么我们将假设该陈述不成立，然后，我们将证明该陈述的后果是不可能的。这些后果被用来与我们刚刚假设的相矛盾，或者很多时候，与我们已知为真的事物相矛盾。有时，两者都是真实的，这就称为矛盾。

为了理解矛盾，我们将举一个简单的例子，其中我们将考虑“波特和他停车罚单”。我们知道，如果波特无法支付停车罚单，那么议会就会给他发一封糟糕的信。还有一件事是波特没有收到任何糟糕的信。这时有两种情况：要么他支付了停车罚单，要么他没有。根据我们最初的信息，我们知道如果波特没有支付，他就会收到一封糟糕的信。因此，他必须支付他的罚单，因为他没有收到糟糕的信。

如果我们想通过反证法正式证明上述例子“波特支付了他的罚单”，那么我们将假设他没有支付罚单，然后我们将推断议会必须给他寄一封糟糕的信。然而，我们知道波特本周的过去特别愉快，并且没有任何糟糕的信件。这是一个矛盾，因此我们可以说我们的假设是错误的。这个例子的答案非常明显，但我们花了很多精力来证明它。有时在某些情况下确实需要很长时间，但在更复杂的例子中，反证法在精确说明我们的假设以及在哪里找到我们的矛盾方面非常有用。

反证法的例子

例1：在这个例子中，我们必须证明一个无理数乘以一个非零数的乘积仍然是无理数，并且要使用反证法。

解：这里，我们将使用反证法来证明一个无理数乘以一个非零数的乘积是一个无理数。

因此，通过反证法，我们证明了给定的陈述。

例2：假设有两个陈述，p和q。

这里陈述p是“x = a/b”，其中a和b用来表示互质数。陈述q是“2整除a和b”。

在这种情况下，我们将认为陈述p为真。我们也必须证明陈述q也为真。因此，我们得出了一个矛盾，因为陈述q意味着陈述p的否定为真。