逻辑与证明方法——数学推理的规则

兔狲教授的提示：数学不仅仅是计算，更是严谨的推理。逻辑提供了推理的规则，证明方法提供了推理的工具。学习逻辑，就是学习如何清晰地、无歧义地思考。

词条1：命题逻辑基础

官方解释

命题：可以判断真假的陈述句。 逻辑联结词：

1. 否定：$\mathrm{\neg }P$（非P）
2. 合取：$P\wedge Q$（P且Q）
3. 析取：$P\vee Q$（P或Q）
4. 蕴含：$P\to Q$（如果P则Q）
5. 等价：$P\leftrightarrow Q$（P当且仅当Q）

真值表：列出命题在所有可能赋值下的真假值。

兔狲老师解释

逻辑就像'思维的游戏规则'。

小小猪打了个比喻：想象你在玩一个推理游戏：

• P：天在下雨
• Q：地上是湿的

那么：

• $P\wedge Q$：天在下雨且地上是湿的
• $P\to Q$：如果天在下雨，那么地上是湿的
• $\mathrm{\neg }P$：天没有下雨

游戏规则就是真值表，告诉我们这些组合什么时候为真。

重要概念：

• 重言式：总是为真的命题（如 $P\vee \mathrm{\neg }P$）
• 矛盾式：总是为假的命题（如 $P\wedge \mathrm{\neg }P$）
• 可满足式：至少有一种赋值使其为真

思考题1：动手题

问题：构造以下命题的真值表：

1. $P\to (Q\to P)$
2. $(P\to Q)\leftrightarrow (\mathrm{\neg }Q\to \mathrm{\neg }P)$
3. $(P\wedge Q)\vee (\mathrm{\neg }P\wedge \mathrm{\neg }Q)$

思考题2：动脑题

问题：为什么"如果P则Q"在P为假时总是为真？

思考方向：

• 从日常语言理解蕴含
• 从逻辑一致性要求理解
• 思考'空真'的概念

---

词条2：谓词逻辑与量词

官方解释

谓词：包含变量的陈述，如 $P(x)$：x是质数。 量词：

1. 全称量词：$\mathrm{\forall }xP(x)$（对所有x，P(x)成立）
2. 存在量词：$\mathrm{\exists }xP(x)$（存在x使得P(x)成立）

量词的否定：

• $\mathrm{\neg }\mathrm{\forall }xP(x)\equiv \mathrm{\exists }x\mathrm{\neg }P(x)$
• $\mathrm{\neg }\mathrm{\exists }xP(x)\equiv \mathrm{\forall }x\mathrm{\neg }P(x)$

兔狲老师解释

谓词逻辑让我们谈论'所有'和'有些'。

小海豹举了个例子：设 $P(x)$：x是偶数

• $\mathrm{\forall }x\in \mathbb{N}P(x)$：所有自然数都是偶数（假）
• $\mathrm{\exists }x\in \mathbb{N}P(x)$：存在自然数是偶数（真）
• $\mathrm{\forall }x\in \mathbb{N}\mathrm{\neg }P(x)$：所有自然数都不是偶数（假）
• $\mathrm{\exists }x\in \mathbb{N}\mathrm{\neg }P(x)$：存在自然数不是偶数（真）

嵌套量词：多个量词组合，如 $\mathrm{\forall }x\mathrm{\exists }yP(x,y)$

重要技巧：

• 量词顺序很重要：$\mathrm{\forall }x\mathrm{\exists }y$ 和 $\mathrm{\exists }y\mathrm{\forall }x$ 不同
• 翻译自然语言为逻辑公式
• 否定带量词的命题

思考题1：动手题

问题：将以下陈述翻译为谓词逻辑：

1. 每个自然数都有后继
2. 存在最大的自然数
3. 对于任意两个不同的自然数，一个比另一个大

问题：否定以下命题：

1. $\mathrm{\forall }x\mathrm{\exists }y(x<y)$
2. $\mathrm{\exists }x\mathrm{\forall }y(x\le y)$

思考题2：动脑题

问题：为什么 "$\mathrm{\forall }x\mathrm{\exists }yP(x,y)$" 和 "$\mathrm{\exists }y\mathrm{\forall }xP(x,y)$" 不等价？

思考方向：

• 从具体例子理解
• 思考量词的"作用域"
• 在日常语言中找例子

---

词条3：直接证明与反证法

官方解释

直接证明：从已知条件出发，通过逻辑推理直接得到结论。 反证法（归谬法）：假设结论不成立，推导出矛盾，从而证明结论成立。

反证法的逻辑形式： 要证明P，假设 $\mathrm{\neg }P$，推导出矛盾（如 $Q\wedge \mathrm{\neg }Q$），从而P成立。

兔狲老师解释

证明就像'搭建逻辑桥梁'。

兔狲教授打了个比喻：直接证明是'正面进攻'，反证法是'迂回包抄'。

例子：$\sqrt{2}$ 是无理数

假设 $\sqrt{2}$ 是有理数，即 $\sqrt{2}=a/b$（a,b互质）

则 $2=a^2/b^2\Rightarrow a^2=2b^2\Rightarrow$ a是偶数

设 $a=2c$，则 $4c^2=2b^2\Rightarrow b^2=2c^2\Rightarrow$ b是偶数

与a,b互质矛盾！所以 $\sqrt{2}$ 是无理数。

证明技巧：

• 明确已知条件和要证明的结论
• 选择合适的证明方法
• 检查每一步的逻辑严密性

思考题1：动手题

问题：用直接证明证明：如果n是偶数，则 $n^2$ 是偶数。 问题：用反证法证明：如果 $a^2$ 是偶数，则a是偶数。

思考题2：动脑题

问题：反证法为什么有效？它的逻辑基础是什么？

思考方向：

• 矛盾在逻辑中意味着什么？
• 为什么从矛盾可以推出任何结论？
• 反证法有哪些局限性？

---

词条4：数学归纳法

官方解释

数学归纳法：证明对所有自然数n，命题P(n)成立的方法。

步骤：

1. 基础步骤：证明P(1)成立
2. 归纳步骤：假设P(k)成立，证明P(k+1)成立
3. 结论：对所有 $n\in \mathbb{N}$，P(n)成立

强归纳法：假设P(1), P(2), ..., P(k)成立，证明P(k+1)成立。

兔狲老师解释

归纳法就像'多米诺骨牌'。

小小猪打了个比喻：想象一排无限长的多米诺骨牌：

1. 推倒第一块（基础步骤）
2. 确保如果第k块倒了，第k+1块也会倒（归纳步骤）
3. 那么所有骨牌都会倒！

例子：证明 $1+2+\cdots +n={\displaystyle \frac{n(n+1)}{2}}$

1. 基础：n=1时，左边=1，右边 $=1\times 2/2=1$，成立

2. 归纳：假设对k成立，即 $1+\cdots +k={\displaystyle \frac{k(k+1)}{2}}$

   则

   $$1+\cdots +k+(k+1)=\frac{k(k+1)}{2}+(k+1)=(k+1)(\frac{k}{2}+1)=\frac{(k+1)(k+2)}{2}$$

   即对k+1成立

3. 结论：对所有n成立

思考题1：动手题

问题：用数学归纳法证明：

1. $1^2+2^2+\cdots +n^2={\displaystyle \frac{n(n+1)(2n+1)}{6}}$
2. $2^n>n$ 对所有 $n\ge 1$ 成立

思考题2：动脑题

问题：数学归纳法为什么有效？它基于自然数的什么性质？

思考方向：

• 归纳法与皮亚诺公理的关系
• 为什么归纳假设是合理的？
• 归纳法能证明什么类型的命题？

---

词条5：构造性证明与存在性证明

官方解释

构造性证明：通过具体构造来证明存在性。 非构造性证明：证明存在性但不给出具体构造。

鸽巢原理：如果n+1只鸽子飞进n个鸽巢，至少有一个鸽巢有至少2只鸽子。

兔狲老师解释

有些证明'展示'，有些证明'指出'。

小海豹举了个例子：证明：存在两个无理数a,b，使得 $a^b$ 是有理数。

构造性证明：取 $a=\sqrt{2}$，$b=\sqrt{2}$

考虑 $(\sqrt{2}{)}^{\sqrt{2}}$：

• 如果是有理数，得证

• 如果是无理数，取 $a=(\sqrt{2}{)}^{\sqrt{2}}$，$b=\sqrt{2}$

  则 $a^b=((\sqrt{2}{)}^{\sqrt{2}}{)}^{\sqrt{2}}=(\sqrt{2}{)}^2=2$，是有理数

这个证明是非构造性的，因为我们不知道 $(\sqrt{2}{)}^{\sqrt{2}}$ 是否是有理数，但两种情况总有一种成立。

证明风格：

• 算法思维：构造性证明
• 逻辑思维：非构造性证明
• 组合思维：鸽巢原理等

思考题1：动手题

问题：用鸽巢原理证明：

1. 在13个人中，至少有2人生日在同一个月
2. 从1到2n中任选n+1个数，必有两个数互质

问题：给出构造性证明：存在无限多个质数。

思考题2：动脑题

问题：构造性证明和非构造性证明各有什么哲学意义？

思考方向：

• 数学对象的存在意味着什么？
• "知道存在"和"具体找到"有什么区别？
• 这对数学实践有什么影响？

---

总结：证明的艺术

兔狲教授总结道：证明是数学的核心。学习证明方法，就是学习：

1. 严谨性：每一步都有逻辑依据
2. 创造性：选择巧妙的证明策略
3. 清晰性：让他人理解你的推理

不同的证明方法适用于不同的问题：

• 直接证明：结构清晰的问题
• 反证法：否定更容易处理的问题
• 归纳法：与自然数有关的问题
• 构造性证明：需要具体算法的问题

掌握这些方法，你就能面对各种数学挑战。

小小猪的体会：原来证明不是死记硬背，而是有策略的游戏！

小海豹的反思：逻辑训练让我的思考更清晰，不仅对数学，对日常生活也有帮助。

下一章预告：我们将学习函数与关系，这是连接代数、分析和几何的重要桥梁。