高中數學擴充套件

補充章節 — 素數和模算術 — 邏輯

矩陣 — 進一步模算術 — 數學規劃 — 馬爾可夫鏈

"我們透過邏輯證明，但透過直覺發現。"

介紹

在過去五百年的時間裡，數學家們一直沉迷於證明。他們想要證明一切，在這個過程中證明了他們不能證明一切（參見此處）。本章將介紹數學的公理化方法，以及幾種型別的證明。

直接證明

直接證明相對簡單 - 透過邏輯地應用先前的知識，我們直接證明所需的內容。

示例 1

證明任意兩個偶數的和 $x$ 和 $y$ 也是偶數。

解 1

我們知道，由於 $x$ 和 $y$ 是偶數，它們必須有 2 作為因子。然後，我們可以寫出以下內容

令

x=2a

,

y=2b

，對於某些整數

a,b

然後

{\begin{matrix}x+y&=&2a+2b\\&=&2(a+b)\end{matrix}}

根據整數的分配律

數字 $2(a+b)$ 明顯有因子 2，這意味著它是偶數。因此， $x+y$ 是偶數。

示例 2

證明以下關於非零整數 $a,b,c$ 的陳述

如果 $a$ 整除 $b$ 且 $b$ 整除 $c$ ，那麼 $a$ 整除 $c$ 。

解答 2

如果一個整數 $x$ 整除另一個整數 $y$ ，那麼我們可以寫成 $y=qx$ ，其中 $q$ 是一個非零整數。因此假設 $b=qa$ 且 $c=rb$ ，其中 $q$ 和 $r$ 是非零整數，那麼

{\begin{matrix}c&=&rb\\&=&r(qa)\\&=&(rq)a\end{matrix}}

根據整數乘法的結合律。

但由於 $q$ 和 $r$ 是整數，它們的乘積 $qr$ 也必須是整數。因此， $c$ 是某個整數乘以 $a$ 的乘積，所以我們得到 $a$ 整除 $c$ 。

數學歸納法

演繹推理是指得出必然成立的結論的過程。例如，如果我們知道

所有烏鴉都是黑色的鳥，並且
對於每一個作用，都有一個大小相等、方向相反的反作用

那麼我們可以得出結論

這隻鳥是烏鴉，所以它是黑色的。
當用球杆擊打檯球時，它會移動。

歸納法與演繹法相反。為了歸納，我們觀察事物在特定情況下的行為，並據此得出事物在一般情況下的行為結論。

假設我們想要證明一個命題（我們稱之為 $S$ ，為了方便表示）對於所有自然數都成立。這就是歸納法證明是如何運作的

首先，我們證明 $S$ 對於自然數 1 成立。這通常被稱為 *基本情況* 或 *基本情況*。
然後，我們證明 $S$ 對於自然數 $n+1$ 成立，只要它對於自然數 $n$ 成立。
根據數學歸納法， $S$ 對於所有自然數都成立。

為了理解最後一步是如何運作的，請注意以下內容

$S$ 對於 1 成立（由於步驟 1）
$S$ 對於 2 成立，因為它對於 1 成立（由於步驟 2）
$S$ 對於 3 成立，因為它對於 2 成立（由於之前）
$S$ 對於 4 成立，因為它對於 3 成立（由於之前）
$S$ 對於 5 成立，因為它對於 4 成立（由於之前）
等等...

示例 1 證明恆等式

1+2+\dots +n={\frac {n(n+1)}{2}}

對所有正整數成立。

解首先，我們證明它對1成立。

1={\frac {(1+1)1}{2}}={\frac {2}{2}}=1

假設該恆等式對某個自然數*k*成立。

1+2+3+...+k={\frac {1}{2}}(k+1)k

這個假設被稱為歸納假設。我們假設它是真的，並試圖證明，

1+2+3+...+k+(k+1)={\frac {1}{2}}(k+2)(k+1)

也是真的。

我們繼續

{\begin{matrix}1+2+3+...+k&&=&{\frac {1}{2}}(k+1)k\\\\1+2+3+...+k&+(k+1)&=&{\frac {1}{2}}(k+1)k+(k+1)\\\\&&=&(k+1)({\frac {k}{2}}+1)\\\\&&=&{\frac {1}{2}}(k+1)(k+2)\end{matrix}}

這就是我們要證明的。由於恆等式對3成立，它也對4成立，由於它對4成立，它也對5、6、7等等成立。

數學歸納法有兩種型別：強歸納法和弱歸納法。在弱歸納法中，假設恆等式對某個值k成立，並證明它對k+1成立。在強歸納法中，恆等式必須對任何小於或等於k的值成立，然後證明它對k+1成立。

例2 證明對於n≥4，n!>2ⁿ。

解當n=4時，該結論成立。因為4!>2⁴，即24>16。現在假設它對n=k，k≥4成立，即

k!>2^k

那麼有

(k+1)k!>(k+1)2^k>2^k+1

(k+1)!>2^k+1

我們已經證明，如果對n=k成立，那麼它也對n=k+1成立。由於它對n=4成立，因此它對n=5、6、7、8等等所有n成立。

例3 證明

1^{3}+2^{3}+...+n^{3}={\frac {(n+1)^{2}n^{2}}{4}}

解假設它對n=k成立，即

1^{3}+2^{3}+...+k^{3}={\frac {(k+1)^{2}k^{2}}{4}}

那麼有

{\begin{matrix}1^{3}+2^{3}+...+k^{3}+(k+1)^{3}&=&{\frac {(k+1)^{2}k^{2}}{4}}+(k+1)^{3}\\&=&(k+1)^{2}({\frac {k^{2}}{4}}+(k+1))\\&=&{\frac {1}{4}}(k+1)^{2}(k^{2}+4k+4)\\&=&{\frac {1}{4}}(k+1)^{2}(k+2)^{2}\end{matrix}}

我們已經證明了，如果對於 n = k 成立，那麼對於 n = k + 1 也成立。現在對於 n = 1 成立（很明顯）。因此它對於所有整數都成立。

練習

1. 證明 $1^{2}+2^{2}+...+n^{2}={\frac {n(2n^{2}+3n+1)}{6}}$

2. 證明對於 n ≥ 1，

(1+{\sqrt {5}})^{n}=x_{n}+y_{n}{\sqrt {5}}

其中 x_n 和 y_n 是整數。

3. 注意到

\sum _{i=1}^{n}[i^{k}-(i-1)^{k}]=n^{k}

證明存在一個顯式公式，

\sum _{i=1}^{n}i^{m}

對於所有整數 m。例如，

$1^{3}+2^{3}+...+n^{3}={\frac {n^{2}(n+1)^{2}}{4}}$

4. 三角形所有內角的和為 $180^{\circ }$ ；矩形所有角的和為 $360^{\circ }$ 。證明具有 n 條邊的多邊形所有角的和為 $(n-2)\cdot 180^{\circ }$ .

反證法

"當你排除了所有不可能，剩下的，無論多麼不可能，都一定是真相。" - 阿瑟·柯南·道爾

反證法的思想是

首先，我們假設我們要證明的結論的相反為真。
然後，我們證明這個假設的邏輯結果包含矛盾。
最後，我們得出結論，這個假設一定是錯誤的。

√2 是無理數

例如，我們將證明 ${\sqrt {2}}$ 不是一個有理數。回顧一下，有理數是可以表示為 p/q 的數，其中 p 和 q 是整數，且 q 不等於 0（見“數字分類”部分這裡）。

首先，假設 ${\sqrt {2}}$ 是有理數

{\sqrt {2}}={\frac {a}{b}}

其中a 和b 是互質的（即沒有公因子的整數，最大公因數為 1）。如果a 和b 不是互質的，我們去掉所有的公因子。換句話說，a/b 是最簡形式。現在，繼續

{\begin{matrix}{\sqrt {2}}&=&a/b\\2&=&a^{2}/b^{2}\\2b^{2}&=&a^{2}\end{matrix}}

我們現在發現a² 是某個整數乘以 2。因此，a² 必須能被二整除。如果a² 是偶數，那麼a 也必須是偶數，因為奇數的平方是奇數。因此我們可以寫a = 2c，其中c 是另一個整數。

{\begin{matrix}2b^{2}&=&a^{2}\\2b^{2}&=&(2c)^{2}\\2b^{2}&=&4c^{2}\\b^{2}&=&2c^{2}\end{matrix}}

我們發現b² 也是一個整數乘以二。由此可見，b 必須是偶數。我們得到矛盾了！a 和b 都是偶數。換句話說，它們都有公因子 2。但是我們之前已經說過a/b 是最簡形式，沒有公因子。既然產生了這種矛盾，我們必須得出結論，我們的初始假設是錯誤的。因此，√2 是無理數。

逆否命題

有些命題形式為如果 xxx 那麼 yyy 很難證明。有時考慮該命題的逆否命題 很有用。在我解釋逆否命題是什麼之前，讓我們看一個例子

"如果x² 是奇數，那麼x 也是奇數"

比

"如果x 是偶數，那麼x² 也是偶數"

更難證明，儘管它們表達的意思相同。因此，我們不是直接證明第一個命題，而是證明第二個命題。

如果A 和B 是兩個命題，並且我們想要證明

如果A 為真，那麼B 為真

我們可以證明等價命題

如果B 為假，那麼A 為假

來代替。這種技巧稱為逆否證法。

為了說明這兩個命題為什麼等價，我們證明下面的布林代數表示式為真（見邏輯）

p\Rightarrow q\equiv q'\Rightarrow p'\!

（留給讀者完成）。

練習

1. 證明不存在 11,111,1111,11111...... 的完全平方數。

2. 證明存在無窮多個k，使得 4k + 3 是素數。（提示：考慮 N = p₁p₂...p_m + 3）

閱讀高等數學

這是一些幫助閱讀其他高等數學文獻的基本資訊。... 待擴充套件

量詞

有時我們需要包含一些粗略數量描述的命題，例如，“對於所有奇數整數 x，x² 也是奇數”。單詞所有是數量的描述。單詞“一些”也用於描述數量。

兩個特殊符號用於描述“所有”和“一些”的數量

\forall

表示“對於所有”或“對於任何”

\exists

表示“存在一些”或“存在”

示例 1
命題

對於所有偶數整數x，x² 也是偶數。

可以用符號表示為

(\forall x)(x{\mbox{ is even}}\Rightarrow x^{2}{\mbox{ is even}})

示例 2
命題

存在一些奇數整數x，使得 x² 是偶數。

可以用符號表示為

(\exists x)(x{\mbox{ is odd}}\Rightarrow x^{2}{\mbox{ is even}})

這個命題是假的。

示例 3
考慮關於 (z = x'y' + xy) 的命題

對於任何 x 的值，都存在 y 的值，使得 z = 1。

可以用符號表示為

(\forall x)(\exists y)(z=1)

這個命題是正確的。注意量詞的順序很重要。雖然上面的陳述是正確的，但陳述

(\exists y)(\forall x)(z=1)

是錯誤的。它斷言存在一個對於所有 x 都有效的 y 值，使得 z=1。第一個陳述只斷言對於每個 x 都存在一個 y，但不同的 x 值可能具有不同的 y 值。

否定

否定只是一個表示相反的詞，例如，“所有名叫布蘭妮的人都能唱歌”的否定是“有些名叫布蘭妮的人不會唱歌”。這意味著要反駁所有名叫布蘭妮的人都能唱歌，我們只需要找到一個不會唱歌的布蘭妮。用符號表示

令p表示一個名叫布蘭妮的人

[(\forall p)(p{\mbox{ can sing}})]'=(\exists p)(p{\mbox{ cannot sing}})

類似地，要反駁

(\forall x)(x{\mbox{ is odd}}\Rightarrow x^{2}{\mbox{ is even}})

我們只需要找到一個不滿足條件的奇數。3 是奇數，但 3×3 = 9 也是奇數，因此命題是錯誤的，並且

(\exists x)(x{\mbox{ is odd}}\Rightarrow x^{2}{\mbox{ is odd}})

是正確的。

總之，要獲得包含量詞的命題的否定，您需要用其相反的量詞替換量詞（例如，用 $\exists$ 替換 $\forall$ ）並將量化命題（例如“x 是偶數”）用其否定替換（例如“x 是奇數”）。

示例 1

(\forall x)(\exists y)(x(x+1)(x+2)(x+3)+1=y^{2})

是一個正確的陳述。它的否定是

(\exists x)(\forall y)(x(x+1)(x+2)(x+3)+1\neq y^{2})

公理和推理

如果今天的數學家要在一個詞中描述 20 世紀數學的最大成就，那麼這個詞將是抽象。顧名思義，抽象是一個非常抽象的概念（參見抽象）。

在本章中，我們將討論我們熟悉的一些數系本質。例如，實數和有理數。我們研究最基本的性質，這些性質在某種意義上定義了這些數系。

我們從研究一些被告知是正確的更模糊的結果開始

0 乘以任何數都等於 0
負數乘以負數等於正數

大多數人只是接受它們是正確的（它們確實是），但上面的兩個結果是我們在實數等數系中認為是正確的簡單推論！

為了理解這一點，我們引入了公理化數學（具有簡單假設的數學）的概念。公理是對數系的一個我們假設為真的陳述。每個數系都有幾個公理，從這些公理中我們可以得出結論（推論）。

讓我們考慮實數，它有公理。令a、b和c是實數

對於從實數中取的a、b和c

A1: a+b也是實數（閉包）

A2: 存在 0，使得對於所有a都有 0 + a = a（零的存在 - 一個恆等式）

A3: 對於每個a，都存在b（寫成 -a），使得 a + b = 0（加法逆元的)

A4: (a + b) + c = a + (b + c)（加法的結合律）

A5: a + b = b + a（加法的交換律）

對於從實數中取的a、b和c，不包括零

M1: ab也是實數（閉包）

M2： 存在一個元素 1，使得對於所有 a，1a = a（存在單位元 - 稱為恆等式）

M3： 對於每個 a，存在一個 b，使得 ab = 1

M4： (ab)c = a(bc)（乘法的結合律）

M5： ab = ba（乘法的交換律）

D1： a(b + c) = ab + ac（分配律）

這些是我們假設在這個系統中為真的最小值。這些是最小值，因為在這個數系中所有其他為真的東西都可以從這些公理推匯出來！

讓我們考慮以下為真的恆等式

(x + y)z = xz + yz

它沒有包含在公理中，但我們可以使用公理來證明它。我們繼續

{\begin{matrix}(x+y)z&=&z(x+y)\ {\mbox{by M5}}\\&=&zx+zy\ {\mbox{by D1}}\\&=&xz+yz\ {\mbox{by M5}}\\\end{matrix}}

在我們繼續之前，你應該已經注意到，實數並不是唯一滿足這些公理的數！例如，有理數也滿足所有公理。這就導致了域的抽象概念。簡單來說，域是一個滿足所有這些公理的數系。讓我們更仔細地定義一個域

如果一個數系 F 支援 + 和 × 操作，並且滿足以下條件，則它是一個域

對於從 F 中取出的 a、b 和 c

A1： a + b 也在 F 中（封閉性）

A2: 存在 0，使得對於所有a都有 0 + a = a（零的存在 - 一個恆等式）

A3: 對於每個a，都存在b（寫成 -a），使得 a + b = 0（加法逆元的)

A4: (a + b) + c = a + (b + c)（加法的結合律）

A5: a + b = b + a（加法的交換律）

對於從 F 中取出的 a、b 和 c，並且去掉了零（有時寫為 F^*）

M1： ab 在 F 中（封閉性）

M2： 存在一個元素 1，使得對於所有 a，1a = a（存在單位元 - 稱為恆等式）

M3： 對於每個 a，存在一個 b，使得 ab = 1（逆元）

M4： (ab)c = a(bc)（乘法的結合律）

M5： ab = ba（乘法的交換律）

D1： a(b + c) = ab + ac（分配律）

現在，對於M3，我們不令 b 為零，因為 1/0 沒有意義。但是對於 M 公理，我們已經排除了零。

對於感興趣的學生，在一個操作和一個集合上封閉性、恆等式、具有逆元和結合律的要求被稱為群。如果 F 是一個加法群，並且 F^* 是一個乘法群，再加上分配律要求，那麼 F 就是一個域。以上公理只是完整地陳述了這一事實。

請注意，自然數不是域，因為一般來說M3不滿足，即不是每個自然數都具有一個也是自然數的逆元。

還要注意，(-a) 表示 a 的加法逆元，它並不表示 (-a) = (-1)(a)，雖然我們可以證明它們是等價的。

示例 1

僅使用公理證明 0 = -0，其中 -0 是 0 的加法逆元。

解 1

0 = 0 + (-0) 根據A3：存在逆元

0 = (-0) 根據A2：0 + a = a

示例 2

令 F 為一個域，a 為 F 的一個元素。僅使用公理證明 0a = 0 對於所有 a 均成立。

解

0 = 0a + (-0a) 根據A3存在逆元

0 = (0 + 0)a + (-0a) 根據示例 1

0 = (0a + 0a) + (-0a) 根據乘法的分配律和交換律

0 = 0a + (0a + (-0a)) 根據加法的結合律

0 = 0a + 0 根據A3

0 = 0a 根據A2。

示例 3

證明 (-a) = (-1)a。

解 3

(-a) = (-a) + 0

(-a) = (-a) + 0a 根據示例 2

(-a) = (-a) + (1 + (-1))a

(-a) = (-a) + (1a + (-1)a)

(-a) = (-a) + (a + (-1)a)

(-a) = ((-a) + a) + (-1)a

(-a) = 0 + (-1)a

(-a) = (-1)a

人們可能會想，為什麼我們需要證明這些顯而易見的事情（從小學開始就顯而易見）。但這裡不是要證明它們是真的，而是要練習推理，如何以邏輯的方式將論據結合起來以證明一個觀點。這是數學中一項重要的技能。

練習

1. 描述一個 1 = 0 的域

2. 僅使用公理證明，如果 u + v = u + w，則 v = w（從兩邊減去 u 不被接受為解）

3. 證明，如果 xy = 0，則 x = 0 或 y = 0

4. 在 F_- 中，+ 操作被定義為兩個數的差，× 操作被定義為兩個數的商。例如 1 + 2 = -1，5 + 3 = 2 以及 9×3 = 3，5×2; = 2.5。 F_- 是一個域嗎？

5. 解釋為什麼 Z₆（模 6 的模運算）不是一個域。

習題集

1. 證明

{\frac {1}{\sqrt {1}}}+{\frac {1}{\sqrt {2}}}+...+{\frac {1}{\sqrt {n}}}\geq {\sqrt {n}}

對於 $n\geq 1$

2. 用歸納法證明 $2n^{3}-3n^{2}+n+31\geq 0$

3. 用歸納法證明

{n \choose 0}+{n \choose 1}+{n \choose 2}+...+{n \choose n}=2^{n}

其中

{n \choose m}={\frac {n!}{m!(n-m)!}}

和

n!=n\cdot (n-1)\cdot (n-2)\cdot ...\cdot 2\cdot 1

並且根據定義 0! = 1。

4. 用歸納法證明 ${n \choose 0}+2{n \choose 1}+2^{2}{n \choose 2}+...+2^{n}{n \choose n}=3^{n}$

5. 證明如果 x 和 y 是整數，n 是奇數，那麼 ${\frac {x^{n}+y^{n}}{x+y}}$ 是一個整數。

6. 證明 (n~m) = n!/((n-m)!m!) 是一個整數。其中 n! = n(n-1)(n-2)...1。例如 3! = 3×2×1 = 6，(5~3) = (5!/3!)/2! = 10。

許多其他章節中的問題都需要你證明一些東西。請務必嘗試本章中討論的技術。

反饋

你覺得怎麼樣？ 太容易還是太難？資訊太多還是不夠？我們怎樣才能改進？請在討論標籤中留言告訴我們。更好的方法是自己編輯並改進它。