来自 Wikibooks，开放的书籍，为开放的世界
逆否命题将结论和假设都否定。它在逻辑上等价于断言的原始命题。通常，证明逆否命题比证明原始命题更容易。本节将演示这一事实。
逆否命题的思想是证明命题“不存在这样的x ，使得P(x) 为假”。而不是“对于所有x ，P(x) 都为真”。
不要与反证法 混淆。如果我们要证明命题 P ⇒ Q {\displaystyle P\Rightarrow Q} P 为真，并证明其逻辑结论是Q 也为真。该命题的逆否命题为 ¬ Q ⇒ ¬ P {\displaystyle \lnot Q\Rightarrow \lnot P} Q 为假，并证明其逻辑结论是P 也为假。然而，在反证法中，我们假设P 为真，Q 为假，并得到一些不合逻辑的结论，例如“1=2”。
最基本的例子是重新做一个在上一节 中给出的证明。我们使用构造性方法证明了定理2.1.4 为真。现在我们可以使用逆否命题方法证明相同的结果。为了便于阅读，我将改变定理的措辞。
定理 2.2.1 （也称为定理 2.1.4）。如果A和B是有限集，且 | A | ≠ | B | {\displaystyle |A|\neq |B|} A ≠ B {\displaystyle A\neq B} 2.1.4 版本中的措辞可能更自然，但这展示了证明的步骤。我们假设有两个有限集 A 和 B ，并且它们元素数量不同。因此，设 n = | A | {\displaystyle n=|A|} m = | B | {\displaystyle m=|B|} A 和 B 中的元素进行编号，因此 A = { a 1 , a 2 , … , a n } {\displaystyle A=\{a_{1},a_{2},\ldots ,a_{n}\}} B = { b 1 , b 2 , … , b m } {\displaystyle B=\{b_{1},b_{2},\ldots ,b_{m}\}} n ≠ m {\displaystyle n\neq m} n < m {\displaystyle n<m} m < n {\displaystyle m<n} n < m {\displaystyle n<m} B − A {\displaystyle B-A} A 只有 n 个元素，我们可以最多从 B 中取出 n 个元素，剩下 B-A 中至少 m-n 个元素。这表明 B 中至少有一个元素不在 A 中，因此 B ≠ A {\displaystyle B\neq A}
我相信我们都知道如何进行算术，但数学家喜欢“严谨”。这意味着我们喜欢对我们使用的所有东西都有清晰的定义。
公理 7. 数字 0 和 1 存在。定义 2.2.2. 运算符 + 的定义使得 1+0=1 并且 { 1 , 1 + 1 , 1 + 1 + 1 , 1 + 1 + 1 + 1 , … } {\displaystyle \{1,1+1,1+1+1,1+1+1+1,\ldots \}} 1 , 2 , 3 , 4 , … {\displaystyle 1,2,3,4,\ldots } n + m = ( 1 + 1 + ⋯ ( n times ) ) + ( 1 + 1 + ⋯ ( m times ) ) = ( 1 + 1 + ⋯ ( n + m times ) ) {\displaystyle n+m=(1+1+\cdots (n{\mbox{ times}}))+(1+1+\cdots (m{\mbox{ times}}))=(1+1+\cdots (n+m{\mbox{ times}}))} 定义 2.2.3. 运算符 ⋅ {\displaystyle \cdot } 1 ⋅ 0 = 0 , {\displaystyle 1\cdot 0=0,} 1 ⋅ 1 = 1 {\displaystyle 1\cdot 1=1} n ⋅ 1 = 1 + 1 + ⋯ ( n times ) . {\displaystyle n\cdot 1=1+1+\cdots (n{\mbox{ times}}).} n ⋅ m = m + m + m + ⋯ ( n times ) . {\displaystyle n\cdot m=m+m+m+\cdots (n{\mbox{ times}}).} 以上定义只是形式上的。我们知道数字是什么以及它们如何运作。这只是一个数学定义。请注意，只有整数乘法被定义。现在我们需要一个额外的定义来证明以下定理。
定义 2.2.4. 如果一个整数是 2 的倍数，则称其为偶数 。也就是说，如果对于某个整数 k ，n = 2k ，则 'n' 为偶数。如果上述条件不成立，则称其为奇数 。数字是偶数还是奇数的性质称为其奇偶性 定理 2.2.5. 如果 x 和 y 是整数，使得 x + y {\displaystyle x+y} x ≠ y . {\displaystyle x\neq y.} 为了用逆否命题来证明这一点，我们假设 x = y {\displaystyle x=y} x + y {\displaystyle x+y} x = y {\displaystyle x=y} x + y = x + x {\displaystyle x+y=x+x} 2 ⋅ x {\displaystyle 2\cdot x} x + y {\displaystyle x+y}
逆否证法在证明双条件语句时非常有用。回想一下，双条件语句的形式为 P ⇔ Q {\displaystyle P\Leftrightarrow Q} P ⇒ Q {\displaystyle P\Rightarrow Q} Q ⇒ P . {\displaystyle Q\Rightarrow P.} P ⇒ Q {\displaystyle P\Rightarrow Q} ¬ P ⇒ ¬ Q . {\displaystyle \lnot P\Rightarrow \lnot Q.}
素数在数论中非常有趣，在算术中也很有趣。事实上，算术基本定理与素数有关。在这里我们不会给出证明，只给出定理的陈述。
定义 2.2.6. 一个素数 是一个正整数，除了 1 和它本身之外没有其他倍数。一个非素数被称为合数 。定理 2.2.7（算术基本定理）。 每个整数都有唯一的素数因式分解，不包括重新排序。该定理将在证明下一个定理时非常有用。
定理 2.2.8. 整数 n 是偶数当且仅当它的平方 n 2 = n ⋅ n {\displaystyle n^{2}=n\cdot n} 证明
首先我们做一个构造性证明。假设n 是一个偶数。那么根据偶数的定义， n = 2 ⋅ k {\displaystyle n=2\cdot k} k 。那么 n 2 = ( 2 k ) 2 = 2 k ⋅ 2 k = 2 ( k ⋅ 2 ⋅ k ) {\displaystyle n^{2}=(2k)^{2}=2k\cdot 2k=2(k\cdot 2\cdot k)} k ⋅ 2 ⋅ k {\displaystyle k\cdot 2\cdot k} n 2 {\displaystyle n^{2}}
为了证明“当”部分，我们使用逆否证法。假设n 不是偶数，或者n 是奇数。让 n = a 1 k 1 ⋅ a 2 k 2 ⋯ a m k m {\displaystyle n=a_{1}^{k_{1}}\cdot a_{2}^{k_{2}}\cdots a_{m}^{k_{m}}} n 的素数因式分解。那么对于任何i ， a i {\displaystyle a_{i}} n 2 = a 1 2 k 1 ⋯ a m 2 k m {\displaystyle n^{2}=a_{1}^{2k_{1}}\cdots a_{m}^{2k_{m}}} n 2 {\displaystyle n^{2}} 使用逆否证法证明以下内容整数n 是偶数当且仅当n+1 是奇数。
如果n 和m 具有相同的奇偶性，那么n+m 是偶数。 
