逻辑

逻辑是数学推理的基础！在《逻辑与集合》章节中，我们已经介绍了逻辑的基础知识。这里我们将深入探讨逻辑的更多内容。

回顾：逻辑基础

在《逻辑与集合》章节中，我们已经学习了：

• 命题和真值
• 逻辑联结词（与、或、非、蕴含、等价）
• 逻辑运算和逻辑等价
• 充分必要条件

谓词逻辑

什么是谓词逻辑？

谓词逻辑（Predicate Logic）是研究包含变量的命题的逻辑。

谓词

谓词（Predicate）是包含变量的命题，例如：

• $P(x)$："$x$ 是偶数"
• $Q(x, y)$："$x$ 大于 $y$"

量词

全称量词

全称量词（Universal Quantifier）$\forall$ 表示"对于所有"：

$\forall x P(x)$

读作："对于所有 $x$，$P(x)$ 为真"。

例子：$\forall x (x^2 \ge 0)$ 表示"对于所有 $x$，$x^2 \ge 0$"。

存在量词

存在量词（Existential Quantifier）$\exists$ 表示"存在"：

$\exists x P(x)$

读作："存在 $x$，使得 $P(x)$ 为真"。

例子：$\exists x (x^2 = 2)$ 表示"存在 $x$，使得 $x^2 = 2$"。

量词的否定

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

嵌套量词

可以嵌套使用多个量词：

$\forall x \exists y P(x, y)$

读作："对于所有 $x$，存在 $y$，使得 $P(x, y)$ 为真"。

注意：量词的顺序很重要！

• $\forall x \exists y P(x, y)$：对于每个 $x$，存在 $y$（$y$ 可能依赖于 $x$）
• $\exists y \forall x P(x, y)$：存在 $y$，对于所有 $x$（$y$ 不依赖于 $x$）

证明方法

直接证明

直接证明（Direct Proof）是直接使用定义和已知事实来证明结论。

步骤：

1. 假设前提为真
2. 使用逻辑推理
3. 得出结论

反证法

反证法（Proof by Contradiction）是通过假设结论为假，推出矛盾，从而证明结论为真。

步骤：

1. 假设结论为假
2. 使用逻辑推理
3. 推出矛盾
4. 因此结论为真

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

• 假设 $\sqrt{2}$ 是有理数，即 $\sqrt{2} = \frac{p}{q}$（$p, q$ 互质）
• 则 $2 = \frac{p^2}{q^2}$，即 $p^2 = 2q^2$
• 所以 $p^2$ 是偶数，因此 $p$ 是偶数
• 设 $p = 2k$，则 $4k^2 = 2q^2$，即 $q^2 = 2k^2$
• 所以 $q^2$ 是偶数，因此 $q$ 是偶数
• 这与 $p, q$ 互质矛盾
• 因此 $\sqrt{2}$ 是无理数

数学归纳法

数学归纳法（Mathematical Induction）是证明对所有自然数 $n$ 都成立的命题的方法。

步骤：

1. 基础步骤：证明 $P(1)$ 为真
2. 归纳步骤：假设 $P(k)$ 为真，证明 $P(k+1)$ 为真
3. 结论：因此对所有 $n$，$P(n)$ 为真

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

• 基础步骤：$n = 1$ 时，$1 = \frac{1 \times 2}{2} = 1$，成立
• 归纳步骤：假设 $1 + 2 + \cdots + k = \frac{k(k+1)}{2}$
  • 则 $1 + 2 + \cdots + k + (k+1) = \frac{k(k+1)}{2} + (k+1) = \frac{(k+1)(k+2)}{2}$
  • 因此 $P(k+1)$ 为真
• 结论：因此对所有 $n$，公式成立

强归纳法

强归纳法（Strong Induction）是数学归纳法的推广：

步骤：

1. 基础步骤：证明 $P(1)$ 为真
2. 归纳步骤：假设 $P(1), P(2), \ldots, P(k)$ 都为真，证明 $P(k+1)$ 为真
3. 结论：因此对所有 $n$，$P(n)$ 为真

构造性证明

构造性证明（Constructive Proof）是通过构造一个对象来证明存在性。

例子：证明存在无理数 $a, b$，使得 $a^b$ 是有理数

• 设 $a = \sqrt{2}$，$b = \sqrt{2}$
• 如果 $a^b = \sqrt{2}^{\sqrt{2}}$ 是有理数，则结论成立
• 如果 $a^b$ 是无理数，则设 $a = \sqrt{2}^{\sqrt{2}}$，$b = \sqrt{2}$
• 则 $a^b = (\sqrt{2}^{\sqrt{2}})^{\sqrt{2}} = \sqrt{2}^2 = 2$ 是有理数
• 因此结论成立

逻辑系统

命题逻辑系统

命题逻辑系统由以下组成：

• 公理（Axioms）：基本命题，不需要证明
• 推理规则（Inference Rules）：从已知命题推出新命题的规则
• 定理（Theorems）：从公理和推理规则推出的命题

完备性

如果所有真命题都可以从公理推出，则逻辑系统是完备的（Complete）。

一致性

如果逻辑系统不会推出矛盾，则系统是一致的（Consistent）。

逻辑的应用

计算机科学

• 💻 程序验证：验证程序的正确性
• 🔐 形式化方法：形式化规范和验证
• 🤖 人工智能：知识表示和推理

数学

• 📐 数学证明：证明数学定理
• 🔢 数理逻辑：研究数学的逻辑基础

常见错误

错误 1：量词顺序错误

要注意量词的顺序，$\forall x \exists y$ 和 $\exists y \forall x$ 是不同的。

错误 2：归纳法使用错误

要正确使用数学归纳法，注意基础步骤和归纳步骤。

错误 3：反证法使用错误

使用反证法时，要确保推出的矛盾是真正的矛盾。

小练习

1. 用谓词逻辑表示："所有学生都喜欢数学或物理"
2. 用反证法证明：如果 $n^2$ 是偶数，则 $n$ 是偶数
3. 用数学归纳法证明：$2^n > n^2$（$n \ge 5$）
4. 应用题：在程序验证中，如何用逻辑表示程序的性质？

---

💡 小贴士：逻辑是数学推理的基础。记住：全称量词 $\forall$ 表示"对于所有"，存在量词 $\exists$ 表示"存在"。掌握逻辑，你就能进行正确的推理和证明！