來自 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 是偶數。 
