高中数学扩展

补充章节 — 素数和模算术 — 逻辑

矩阵 — 进一步模算术 — 数学规划 — 马尔可夫链

"我们通过逻辑证明，但通过直觉发现。"

介绍

在过去五百年的时间里，数学家们一直沉迷于证明。他们想要证明一切，在这个过程中证明了他们不能证明一切（参见此处）。本章将介绍数学的公理化方法，以及几种类型的证明。

直接证明

直接证明相对简单 - 通过逻辑地应用先前的知识，我们直接证明所需的内容。

示例 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。

许多其他章节中的问题都需要你证明一些东西。请务必尝试本章中讨论的技术。

反馈

你觉得怎么样？ 太容易还是太难？信息太多还是不够？我们怎样才能改进？请在讨论标签中留言告诉我们。更好的方法是自己编辑并改进它。