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

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

词条1：命题逻辑基础

官方解释

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

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

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

兔狲老师解释

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

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

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

那么：

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

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

重要概念：

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

思考题1：动手题

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

1. P \to (Q \to P)
2. (P \to Q) \leftrightarrow (\neg Q \to \neg P)
3. (P \land Q) \lor (\neg P \land \neg Q)

思考题2：动脑题

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

思考方向：

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

词条2：谓词逻辑与量词

官方解释

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

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

量词的否定：

• \neg \forall x\, P(x) \equiv \exists x\, \neg P(x)
• \neg \exists x\, P(x) \equiv \forall x\, \neg P(x)

兔狲老师解释

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

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

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

嵌套量词：多个量词组合，如 \forall x\, \exists y\, P(x,y)

重要技巧：

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

思考题1：动手题

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

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

问题：否定以下命题：

1. \forall x\, \exists y\, (x < y)
2. \exists x\, \forall y\, (x \le y)

思考题2：动脑题

问题：为什么 "\forall x\, \exists y\, P(x,y)" 和 "\exists y\, \forall x\, P(x,y)" 不等价？

思考方向：

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

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

官方解释

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

反证法的逻辑形式：
要证明P，假设 \neg P，推导出矛盾（如 Q \land \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 = \dfrac{n(n+1)}{2}

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

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

   则

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

   即对k+1成立

3. 结论：对所有n成立

思考题1：动手题

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

1. 1^2+2^2+\cdots+n^2 = \dfrac{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. 清晰性：让他人理解你的推理

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

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

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

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

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

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