0_绪论0.3.ZH解释

这段话用了一个非常生动的比喻来介绍数学这门学科的三个最核心的组成部分：定义、定理和证明。这三者是构建整个数学大厦的基石，尤其是在理论计算机科学（我们这门学科）中，它们的作用更是至关重要。

1. 心脏和灵魂——定理与证明：
   • 定理 (Theorem)：是数学中的真理，是一些被证明为绝对正确的陈述。它们是数学知识的精华和成果，就像一个人的思想结晶。
   • 证明 (Proof)：是连接假设与定理之间的桥梁，是确认一个陈述为真的逻辑过程。它赋予定理生命和可信度。没有证明的定理只能算是猜想。
   • 将它们比作“心脏和灵魂”，是因为它们是数学活动中最具创造性和实质性的部分。数学家的主要工作就是发现和证明新的定理。它们驱动着数学的发展，是数学知识体系的核心内容。
2. 精神——定义：
   • 定义 (Definition)：是数学交流的语言基础。它精确地描述了我们要研究的对象、概念和使用的符号。
   • 将它比作“精神”，是因为定义决定了我们思考和讨论的边界与内涵。没有清晰的定义，定理和证明就无从谈起，如同一个人没有精神，就只是一具空壳。所有的数学推理都始于定义。
3. 核心地位：
   • 最后一句强调，这三者不仅仅是在纯粹数学中重要，在我们正在学习的理论计算机科学这个学科里，它们同样是核心。理论计算机科学本质上是数学的一个分支，它使用同样严谨的定义-定理-证明的框架来研究计算的本质、能力和效率。

这段话深入阐述了“定义”的性质和要求，核心在于强调其“精确性”。

1. 定义的作用：定义的核心功能是“描述”。它告诉我们一个术语、一个符号或一个概念到底是什么。这些被描述的东西，文中称之为“对象”和“概念”。
   • 对象 (Objects)：通常指具体的数学实体，比如数字、集合、函数、图等。
   • 概念 (Notions)：通常指一些性质或关系，比如“相等”、“子集”、“可计算”等。
2. 定义的复杂性：定义的难度和篇幅不是固定的。
   • 简单的定义：例如，一个集合 (Set) 被非形式地定义为“一些对象的聚集”。这个定义虽然简单，但在入门阶段够用了。
   • 复杂的定义：例如，在密码学中定义一个密码系统是“安全的”。这个定义会非常复杂，可能需要好几页纸。它需要精确描述攻击者拥有什么能力（例如，能看到加密后的文本），攻击者的目标是什么（例如，想猜出原始信息），以及在什么条件下我们认为系统是安全的（例如，攻击者猜对的概率可以忽略不计）。这个定义必须能抵抗各种已知的和未知的攻击方法，所以必然复杂。
3. 定义的核心要求——精度 (Precision)：
   • 这是对所有数学定义的根本要求。精确性意味着定义必须是无歧义的。
   • 对于任何一个东西，根据定义，我们必须能够毫不含糊地判断出它“是”还是“不是”所定义的那个对象。不允许有“可能
   • “我们必须清楚什么构成了这个对象，什么不构成”：这句话是精确性的同义反复。一个好的定义就像一个完美的过滤器或一个边界清晰的围栏，可以准确地筛出符合条件的对象，并排除所有不符合的。

这段话依次解释了陈述、证明和定理（以及引理、推论）这三个概念，并着重对比了数学证明与日常生活中证明的根本区别。

第一部分：数学陈述 (Mathematical Statement)

1. 产生时机：在有了清晰的定义之后，我们就可以开始讨论这些定义的对象了。
2. 内容：陈述通常是关于某个对象是否具有某种属性的判断句。例如，“数字7是素数”就是一个陈述。
3. 真伪性：一个陈述有真假之分。它可以是真的，也可以是假的。例如，“7是素数”是真的，而“6是素数”是假的。
4. 要求：和定义一样，陈述也必须是精确的、无歧义的。我们必须清楚地知道这个陈述在说什么。例如，“这个三角形是‘漂亮的’”不是一个好的数学陈述，因为“漂亮”没有精确的数学定义。

第二部分：证明 (Proof)

1. 定义：证明是一个逻辑论证过程，它的唯一目的是令人信服地展示一个陈述是真的。
2. 数学证明的“高标准”：
   • 无懈可击 (Incontrovertible)：这是数学证明的最高标准。意思是证明过程中的每一步推理都必须是逻辑上完美的，不接受任何形式的反驳。
   • 绝对意义上令人信服：它不依赖于个人信念、经验或权威，只依赖于公认的公理和逻辑规则。任何一个理解相关定义和逻辑的人，都必然会接受证明的结论。
3. 与日常/法律证明的对比：
   • 标准不同：日常生活中或法庭上的“证明”标准要低得多。法庭要求“排除一切合理怀疑”，这意味着允许存在“不合理”的怀疑，不是100%的确定。
   • 证据 (Evidence) 的作用：法庭证明依赖于证据（人证、物证）。证据的分量（persuasiveness）是关键，目的是说服陪审团。但在数学中，“证据”没有地位。
   • 举例的局限性：你不能通过举100个例子（证据）来证明一个陈述对所有情况都成立。例如，你不能通过计算 $1+3=4$, $3+5=8$, $5+7=12$ 都是偶数，就证明了“任意两个奇数之和是偶数”。你需要的是一个普适的逻辑论证。
   • 数学要求“毫无疑问”：数学证明追求的是绝对的、永恒的真理。一个陈述一旦被证明，它在数学体系内就是永远正确的。

第三部分：定理 (Theorem)、引理 (Lemma)、推论 (Corollary)

1. 定理 (Theorem)：一个已经被证明为真的数学陈述。这个头衔通常授予那些比较“重要”或“有特殊兴趣”的陈述。例如，勾股定理。
2. 引理 (Lemma)：可以理解为“辅助定理”或“小定理”。它也是被证明为真的陈述，但它的主要价值在于作为证明另一个更重要定理的垫脚石。它本身可能不是那么令人关注。
3. 推论 (Corollary)：一个可以从某个定理或其证明中“顺便”或“很容易”推导出来的真陈述。它像是定理的直接产物或附属品。

这段话是关于如何开始寻找证明的入门指导。它首先点明了证明的必要性和难度，然后给出了第一个，也是最重要的一步：彻底理解你要证明的陈述。

第一部分：引言

1. 证明的唯一性：再次强调，数学证明是判断一个数学陈述真假的唯一途径。没有其他捷径。
2. 寻找证明的难度：作者坦诚，想出一个证明是困难的，它不像解一元二次方程那样有固定的公式（“简单的规则或过程”）。它是一项创造性的活动。
3. 给学生打气：预见到学生可能会因为被要求做证明题而感到“绝望”，作者给予了鼓励。虽然没有万能的“秘诀”，但确实存在一些行之有效的“通用策略”，可以帮助我们入手。

第二部分：第一条策略——深入理解陈述

这是所有证明工作的起点，包含三个具体的动作：

1. 仔细阅读 (Read carefully)：不要一目十行。每个词、每个符号都可能包含关键信息。
2. 理解符号 (Understand all notation)：数学是符号的语言。如果你不认识某个符号，比如 $\forall$ (任意), $\exists$ (存在), $\in$ (属于), $\subseteq$ (是...的子集)，就必须先查清楚它的确切含义。
3. 用自己的话改写 (Rephrase in your own words)：这是一个非常有效的检验你是否真正理解了陈述的方法。如果你能用更通俗、更直白的语言把陈述的意思复述出来，而没有丢失任何精度，说明你理解了。这个过程也能帮你更好地建立直觉。
4. 分解陈述 (Break it down)：复杂的陈述通常由几个部分组成。把它们拆开，逐个分析。比如，一个陈述可能是“如果 A 成立，并且 B 成立，那么 C 成立”。你可以先分别思考 A 是什么，B 是什么，C 是什么。

这段话介绍了两种特殊但非常常见的多部分陈述的证明策略，这两种策略都是将一个复杂的证明任务分解为两个独立的、更简单的子任务。

第一种：当且仅当 (if and only if, iff)

1. 陈述形式：“$P$ 当且仅当 $Q$”，符号记为 $P \Longleftrightarrow Q$。
2. 含义拆解：“当且仅当”是一个双向的蕴含关系，它是两个独立陈述的合并。
   • 第一部分 (“仅当”部分 / 正向)： “$P$ 仅当 $Q$”。这句话的逻辑含义是 “如果 $P$ 成立，那么 $Q$ 必然成立”。这写作 $P \Rightarrow Q$。可以理解为“要让 $P$ 发生，一个必要条件是 $Q$ 必须发生”。
   • 第二部分 (“如果”部分 / 反向)： “$P$ 如果 $Q$”。这句话的逻辑含义是 “如果 $Q$ 成立，那么 $P$ 必然成立”。这写作 $P \Leftarrow Q$ (或者更常见的 $Q \Rightarrow P$)。可以理解为“只要 $Q$ 发生了，就足以让 $P$ 发生”。
3. 证明策略：要证明 $P \Longleftrightarrow Q$，你必须完成两个独立的证明：
   • 证明1 (正向)：假设 $P$ 为真，然后通过逻辑推导证明 $Q$ 也为真。
   • 证明2 (反向)：假设 $Q$ 为真，然后通过逻辑推导证明 $P$ 也为真。
4. 难易度：作者提醒，这两个方向的证明难度往往是不一样的，一个可能很简单，另一个可能需要复杂的技巧。

第二种：集合相等 (Set Equality)

1. 陈述形式：集合 $A$ = 集合 $B$。
2. 定义拆解：根据集合相等的定义，两个集合相等意味着它们包含完全相同的元素。这个定义可以被拆解为两个互为子集的关系。
   • 第一部分：$A$ 是 $B$ 的子集（$A \subseteq B$）。这意味着 $A$ 中的每一个元素都必须在 $B$ 中。
   • 第二部分：$B$ 是 $A$ 的子集（$B \subseteq A$）。这意味着 $B$ 中的每一个元素都必须在 $A$ 中。
3. 证明策略：要证明 $A=B$，你也必须完成两个独立的证明：
   • 证明1：任取一个元素 $x \in A$，证明 $x$ 也必然属于 $B$。这就证明了 $A \subseteq B$。
   • 证明2：任取一个元素 $y \in B$，证明 $y$ 也必然属于 $A$。这就证明了 $B \subseteq A$。

这段话介绍了证明过程中的第二条重要策略：通过具体的例子和反例来建立直觉。这是一种从具体到抽象的探索方法。

1. 目标：建立直觉
   • 在进行严格的逻辑推导之前，最好能对“为什么这个陈述是对的”有一个感性的认识或“直觉”。这种直觉能极大地指导你寻找证明的方向。
2. 方法一：实验例子 (Experiment with examples)
   • 操作：如果一个陈述宣称“所有 A 都有 B 属性”，那么你就去找几个具体的 A 的例子。
   • 验证：检查你找的这几个例子，看看它们是不是真的都有 B 属性。
   • 作用：
   • 如果例子验证通过，会增强你对该陈述为真的信心。
   • 观察例子满足属性的过程，可能会揭示出一般性的规律，为你提供证明的思路。
3. 方法二：寻找反例 (Search for a counterexample)
   • 操作：主动地、有意识地去寻找一个不满足陈述的例子。即，找一个属于 A 类型，但却不具备 B 属性的对象。这个对象就叫做反例。
   • 作用：
   • 如果找到了反例：恭喜你，你已经证明了原陈述是假的。任务结束。
   • 如果找不到反例：这才是这个方法最精妙的地方。当你努力尝试构造一个反例却屡次失败时，观察“失败的原因”本身，往往能让你深刻理解为什么陈述必须为真。那些阻碍你构造反例的“困难”或“障碍”，往往就是证明的核心所在。

这个例子是上一节“通过例子和反例建立直觉”策略的实战演练。这个定理在图论中被称为“握手引理”。

第一步：理解陈述

• 陈述：“对于每个图 $G$，图 $G$ 中所有节点的度数之和是一个偶数。”
• 关键词定义：
• 图 (Graph): 由节点（或顶点）和连接节点的边组成的数学对象。
• 节点 (Node/Vertex): 图中的点。
• 度 (Degree): 一个节点的度是指连接到该节点的边的数量。
• 度数之和 (Sum of degrees): 图中所有节点的度加起来的总和。
• 偶数 (Even number): 可以被2整除的整数。
• 用自己的话改写：随便画一个图，不管它长什么样，把每个点的度数出来，再把这些数加起来，得到的总和一定是偶数。

第二步：实验例子

• 作者给的例子1（三角形）：
• 这是一个有3个节点和3条边的图。
• 我们来数每个节点的度：
• 左上角节点：连接了2条边，度为2。
• 右上角节点：连接了2条边，度为2。
• 下方节点：连接了2条边，度为2。
• 度数之和 = $2 + 2 + 2 = 6$。
• 6是一个偶数。陈述在此例中成立。

• 作者给的例子2（一个更复杂的图）：
• 这是一个有5个节点的图。
• 我们来数每个节点的度 (从左到右)：
• 第一个节点：度为2。
• 第二个节点：度为3。
• 第三个节点：度为4。
• 第四个节点：度为3。
• 第五个节点：度为2。
• 度数之和 = $2 + 3 + 4 + 3 + 2 = 14$。
• 14是一个偶数。陈述在此例中也成立。

第三步：寻找反例并分析失败原因

• 目标：构造一个图，使其度数之和为奇数。
• 作者的图示分析：图片展示了一个从无到有构造图的过程。
• 初始状态：只有一些孤立的节点，没有边。此时，每个节点的度都是0，度数之和为0（一个偶数）。
• 添加第一条边：选择任意两个节点，用一条边连接它们。这条边会使这两个节点的度各增加1。因此，总的度数之和增加了 $1+1=2$。原来的和是0，现在的和是2（仍然是偶数）。
• 添加第二条边：再选两个节点（可以是新的，也可以是已经用过的），用一条边连接。同样，这条新边会使其两端节点的度各增加1，总的度数之和又增加了2。
• 观察到的规律：“每次添加边时，和都会增加 2。”
• 分析失败原因：
• 我们从一个偶数（0）开始。
• 每一步操作（添加一条边）都是在当前的总和上加上另一个偶数（2）。
• 一个偶数加上一个偶数，结果永远是偶数。
• 因此，无论我们添加多少条边，构造出多么复杂的图，最终的度数之和永远不可能是奇数。我们永远无法构造出反例。

第四步：获得证明思路

• 从寻找反例的失败中，我们提炼出了证明的核心思想：

1. 考虑图中每一条边。
2. 每一条边都有两个端点，它会分别给这两个端点的度贡献1。
3. 因此，每一条边对整个图的度数之和的总贡献是2。
4. 如果一个图有 $e$ 条边，那么所有边贡献的总和就是 $2 \times e$。
5. 所以，图的度数之和就等于 $2e$，这显然是一个偶数。

• 最终问题：“你现在能开始明白为什么陈述为真以及如何证明它了吗？”
• 答案是：是的。通过观察添加边的过程，我们发现了度数之和与边数之间的关系，从而找到了证明的方法。

这段话提供了更多关于证明的实用建议，分为两部分：卡住时该怎么办，以及找到思路后如何写下来，最后是一些通用的“软技能”。

第一部分：如果仍然困难——简化问题

1. 策略：证明特例 (Prove a special case)
   • 当你面对一个普适性的陈述（例如，对所有整数 $k>0$ 都成立）感到无从下手时，不要硬磕。
   • 把它简化，先证明最简单的一个特例。例如，证明当 $k=1$ 时成立。
   • 如果 $k=1$ 成功了，再试试 $k=2$。
   • 这个过程的目的不是通过穷举来证明，而是通过解决这些简化的版本，来观察其中的模式、规律和证明技巧，从而获得解决一般情况的灵感。
   • 如果一个特例还是很困难，可以再简化，比如对这个特例再增加一些限制条件，做一个“特例的特例”。

第二部分：找到证明后——正确书写

1. 什么是好的证明：一个写得好的证明，是一个陈述的序列。这个序列像一个逻辑链条，环环相扣。
   • 序列中的每个陈述：都必须由它前面的陈述，通过“简单推理”（比如代数运算、定义的直接应用、已知的定理等）得到。
   • 不能有跳跃：推理步骤不能太大，要保证读者能跟上你的思路。
2. 仔细书写的重要性：
   • 为了读者：让别人（比如老师、合作者）能看懂、理解并检验你的证明。
   • 为了自己：书写的过程也是一个自我审查的过程。当你强迫自己把每一步逻辑都清晰地写下来时，很容易发现之前思考时忽略的逻辑漏洞或错误。

第三部分：通用的技巧（软技能）

1. 耐心 (Patience)：证明是智力马拉松，不是百米冲刺。思路卡壳是常态，不要因此焦虑或放弃。伟大的数学家也需要花费大量时间来解决问题。
2. 回头再看 (Come back to it)：当你陷入僵局时，暂时放下问题，去做点别的事情。散步、听音乐、睡觉等。这被称为“酝酿效应”(incubation effect)。你的潜意识可能会在你没有主动思考的时候继续处理信息，当你再回来看这个问题时，可能会有全新的视角或灵感（“直觉”）。
3. 整洁 (Be neat)：无论是在草稿纸上探索思路，还是在最终书写证明时，保持整洁都非常重要。
   • 探索阶段：清晰的图和文字能帮助你发现洞察力，而杂乱的草稿只会让你的思维更加混乱。
   • 书写阶段：整洁的证明能让读者专注于逻辑本身，而不是费力地辨认你的字迹和混乱的版面。
4. 简洁 (Be concise)：
   • 简洁的好处：用最少的文字和符号清晰地表达思想，有助于抓住证明的高层次脉络，不至于陷入琐碎的细节中。
   • 数学符号的作用：数学符号本身就是一种追求简洁和精确的语言。
   • 度的把握：简洁不等于省略。你必须保证包含了足够的推理步骤，让读者能够“轻松理解”。在简洁和清晰之间需要找到一个平衡。

这段内容是对前面所学证明策略的一次完整实践。它证明了德摩根定律，一个集合论中的基本定理。

第一部分：准备工作

1. 陈述定理：定理0.20

：对于任何两个集合 $A$ 和 $B, \overline{A \cup B}=\bar{A} \cap \bar{B}$。

1. 检查理解：作者首先引导读者自我检查。
   • 含义清楚吗? 你知道这个陈述在说什么吗？
   • 符号理解? 你是否理解 $\cup$ (并集), $\cap$ (交集), 和上划线 (补集) 的定义？如果不理解，就无法进行证明。
2. 规划证明策略：
   • 核心任务：证明两个集合，即 $\overline{A \cup B}$ 和 $\bar{A} \cap \bar{B}$，是相等的。
   • 套用策略：作者明确指出，要使用前面讲过的“证明集合相等”的标准策略，即分别证明它们互为子集。
   • 方向1: 证明 $\overline{A \cup B} \subseteq \bar{A} \cap \bar{B}$。
   • 方向2: 证明 $\bar{A} \cap \bar{B} \subseteq \overline{A \cup B}$。
3. 鼓励读者尝试：在给出标准证明之前，作者鼓励读者先自己动手尝试，比如用文氏图或具体的集合例子来建立直觉。

第二部分：形式化证明

这部分严格地执行了上面规划的策略。

方向1：证明 $\overline{A \cup B} \subseteq \bar{A} \cap \bar{B}$

1. [假设]：从要证明的子集关系 ($A \subseteq B$) 的“左边”任取一个元素。

假设 $x$ 是 $\overline{A \cup B}$ 的一个元素。

1. [展开定义]：将这个假设按照定义一步步展开。

那么根据集合补集的定义，$x$ 不在 $A \cup B$ 中。

1. [继续展开定义]：

因此，根据两个集合的并集的定义，$x$ 不在 $A$ 中，也不在 $B$ 中。

• 这一步是关键逻辑：一个元素不在并集里，意味着它既不属于第一个集合，也不属于第二个集合。

1. [重新应用定义]：将上面的结论用补集的定义重新包装。

换句话说，$x$ 在 $\bar{A}$ 中，并且 $x$ 在 $\bar{B}$ 中。

1. [得出结论]：根据交集定义，得出最终结论。

因此，两个集合交集的定义表明 $x$ 在 $\bar{A} \cap \bar{B}$ 中。

• 小结：我们从“$x$ 在左边的集合里”出发，通过一系列严格的定义转换，最终证明了“$x$ 也在右边的集合里”。这就完成了第一个方向的证明。

方向2：证明 $\bar{A} \cap \bar{B} \subseteq \overline{A \cup B}$

这个方向的逻辑与方向1正好相反。

1. [假设]：从“右边”的集合任取一个元素。

对于另一个方向，假设 $x$ 在 $\bar{A} \cap \bar{B}$ 中。

1. [展开定义]：

那么 $x$ 既在 $\bar{A}$ 中，也在 $\bar{B}$ 中。

1. [继续展开定义]：

因此，$x$ 既不在 $A$ 中，也不在 $B$ 中，

1. [应用定义]：

因此不在这些两个集合的并集中。

1. [得出结论]：

因此 $x$ 在这些集合的并集的补集中；换句话说，$x$ 在 $\overline{A \cup B}$ 中，这完成了定理的证明。

• 小结：我们从“$x$ 在右边的集合里”出发，通过反向的逻辑步骤，证明了“$x$ 也在左边的集合里”。

最终结论

因为我们已经证明了两个方向的子集关系都成立，所以根据集合相等的定义，这两个集合是相等的。定理得证。

这段给出了在 示例 0.19 中通过探索得到的“握手引理”的正式证明。这个证明非常简洁，其核心思想是改变计数的视角。

1. 证明策略：双重计数 (Double Counting)

• 我们想计算的是“所有节点的度数之和”。
• 通常的思路是：遍历每个节点，数出它的度，然后相加。
• 这个证明的巧妙之处在于，它不从节点的角度计数，而是从边的角度来计数。它在思考：每一条边对最终的总和贡献了多少？

2. 证明步骤的分解

• [陈述1] 图 $G$ 中的每条边都连接到两个节点。
• 这是边的基本定义。一条边就是一个节点对 {u, v}。
• （注：这里暂时不考虑多重图和自环的复杂情况，但在标准简单图中，这是成立的。即使有自环，如果定义一个自环对度贡献2，结论依然成立。）
• [陈述2] 每条边对它所连接的每个节点的度数贡献 1。
• 这是度的定义。一个节点的度就是与它相连的边的数目。所以，每多一条边连接到这个节点，它的度就加1。
• [推论1] 因此，每条边对所有节点的度数之和贡献 2。
• 这是本证明最核心的洞察。一条边，比如连接节点A和节点B，它让A的度加1，也让B的度加1。所以在计算“所有节点的度数之和”时，这条边的贡献被计算了两次，总贡献是 $1+1=2$。
• [推论2] 因此，如果 $G$ 包含 $e$ 条边，那么图 $G$ 中所有节点的度数之和是 $2e$。
• 既然每一条边都贡献2，那么 $e$ 条边的总贡献自然就是 $e$ 个2相加，即 $2e$。
• 这建立了一个 beautiful 的等式：$\sum_{v \in V} \text{deg}(v) = 2|E|$ (其中 $V$ 是节点集，$E$ 是边集)。
• [最终结论] $2e$ 是一个偶数。
• 因为 $e$ (边的数量) 是一个整数，所以 $2e$ 必然是一个偶数。
• 定理得证。

这是一个过渡段落，起到了承上启下和引导的作用。

1. 主题预告：本段明确告诉读者，接下来要介绍几种在数学证明中反复出现的、模式化的论证类型（types of argument）。
2. 范围限定：作者特别指出，将重点描述那些在“计算理论”中常用的证明类型。这表明接下来的内容是为本课程量身定做的，具有很强的针对性。
3. 重要提醒：一个复杂的证明往往不是由单一类型的论证构成的，它可能是一个“混合体”。比如，一个大的证明主体可能是归纳法，但在其归纳步骤的子证明中，可能又用到了反证法。这个提醒很重要，它让读者在分析和构造证明时保持思路的灵活性。

这段话介绍了第一种证明类型：构造性证明 (Proof by Construction)。

1. 适用场景：当一个定理的陈述是“存在一个具备...性质的对象”时，构造性证明是一个非常直接和有力的工具。这类定理被称为“存在性定理”。
2. 核心方法：证明方法非常直观——“just build it!”。你不需要间接地论证它存在，而是直接给出一个明确的“蓝图”或“食谱”，演示如何一步步地把这个满足条件的对象给构造出来。
3. 证明的完成：一旦你成功构造出了这个对象，并且证明了你构造出的这个对象确实满足定理所要求的所有属性，那么这个定理就得证了。因为你已经找到了一个例子，它的“存在性”就不言而喻了。
4. 引入新定义：为了引出接下来的例子，这里给出了一个图论中的定义。
   • k-正则图 (k-regular graph)：如果一个图中，所有节点的度数都相等，且都等于 $k$，那么这个图就叫做一个 k-正则图。例如，一个三角形是 2-正则的，一个正方形也是 2-正则的。

这是一个典型的构造性证明。

第一步：理解定理陈述

• 条件：$n$ 是一个偶数，并且 $n > 2$。所以 $n$ 可以是 4, 6, 8, ...
• 结论：存在一个图，这个图有 $n$ 个节点，并且是 3-正则的（即每个节点的度都等于3）。

第二步：给出构造方法

这是构造性证明的核心。作者给出了一个明确的图的“蓝图”。

1. 构造节点集 V：
   • $V = \{0, 1, \ldots, n-1\}$。这是一个非常标准的构造，就是给 $n$ 个节点从 0 到 $n-1$ 编号。
2. 构造边集 E：
   • 这个是关键。边集 $E$ 被定义为两个子集的并集。
   • 第一部分 (圆环边)：
   • \{\{i, i+1\} | for 0 <= i <= n-2\}：这表示节点 $i$ 和它的下一个节点 $i+1$ 之间有一条边，从 0 到 $n-2$。这会产生边 {0,1}, {1,2}, ..., {n-2, n-1}。
   • \{\{n-1, 0\}\}：这条边把最后的节点 $n-1$ 和最开始的节点 0 连接起来，形成一个闭环。
   • 综合起来：这部分构造了一个包含 $n$ 个节点的简单圆环。此时，每个节点的度都正好是2。
   • 第二部分 (对角线边)：
   • \{\{i, i+n/2\} | for 0 <= i <= n/2 - 1\}：这表示节点 $i$ 和它“对面”的节点 $i+n/2$ 之间有一条边。
   • 为什么是 $i+n/2$？因为节点排成一个圆环，与节点 $i$ 相对的正好是编号差 $n/2$ 的那个节点。
   • 为什么 $i$ 只到 $n/2 - 1$？因为如果 $i$ 继续增加，例如到了 $n/2$，那么它要连接的节点是 $n/2 + n/2 = n$。但节点编号是 $0, ..., n-1$，所以这里的计算是模 $n$ 的。更重要的是，连接 {i, i+n/2} 和连接 {i+n/2, i} 是同一条边。所以我们只需要从一侧连接到另一侧，即 $i$ 从 0 遍历到 $n/2 - 1$，就可以把所有对面的节点都连接起来，不多也不少。
   • 这部分构造了 n/2 条“对角线”，把圆环上相对的节点两两配对连接。

第三步：证明构造出的对象满足属性

• 属性要求：每个节点的度都是3。
• 证明：
• 对于任意一个节点 $i$：
• 从第一部分 (圆环边) 的构造中，我们知道节点 $i$ 与节点 $i-1$ (模n) 和 $i+1$ (模n) 相连。这贡献了2个度。
• 从第二部分 (对角线边) 的构造中，我们知道节点 $i$ 与节点 $i+n/2$ (模n) 相连。这贡献了1个度。
• 总度数：$2 + 1 = 3$。
• 这个论证对所有节点 $i$ 都成立。因此，构造出的图中每个节点的度都是3，即它是一个 3-正则图。
• 证明完成：我们成功地为任意一个大于2的偶数 $n$ 构造出了一个 $n$ 节点的 3-正则图。定理得证。

这段话介绍了第二种重要的证明类型：反证法 (Proof by Contradiction)，在拉丁语中称为 reductio ad absurdum (归谬法)。

1. 核心思想：这是一种间接证明方法。我们不直接证明一个陈述 $P$ 是真的，而是反过来，先假设 $P$ 是假的（即非 $P$ 是真的）。
2. 推理过程：从“$P$ 是假的”这个假设出发，进行一系列严格的逻辑推导。
3. 目标结果：通过推导，最终得出了一个“矛盾” (contradiction)。
4. 什么是矛盾：一个矛盾是指一个显然为假的结果。常见的矛盾形式有：
   • 推导出了 $Q$ 并且 非 $Q$ 同时成立（例如，一个数既是偶数又是奇数）。
   • 推导出了一个与已知公理、定义或已证明的定理相违背的结论（例如，推导出 $1=0$）。
   • 推导出了一个与我们的初始假设相矛盾的结论。
5. 结论：既然一个真实的假设（非 $P$）通过有效的逻辑推导，居然得到了一个假的结果（矛盾），那么问题只能出在源头上——即我们最初的假设“$P$ 是假的”这个陈述本身是错误的。因此，唯一的可能性就是 $P$ 必须是真的。
6. 与日常生活的联系：作者指出，这种推理方式非常普遍，我们每天都在使用它，只是没有意识到它的逻辑结构。

这个例子将上一节介绍的抽象的反证法逻辑，应用到了一个非常日常和直观的情景中，以帮助读者理解其思维模式。

1. 杰克想证明的陈述是什么？

• 陈述 P：“外面没有下雨”。

2. 杰克是如何运用反证法的？

• 第一步：假设陈述 P 为假
• P 的反面 (非P) 是：“外面正在下雨”。
• 杰克在脑海中假设：“如果外面正在下雨......”

• 第二步：从假设进行推理
• 杰克有一个背景知识（常识公理）：“如果一个人在雨里走，他/她就会变湿”。
• 基于这个背景知识和他的假设（外面在下雨），他推导出一个必然的结果：“吉尔（刚从外面进来）就会是湿的”。

• 第三步：将推理结果与现实观察对比，发现矛盾
• 推理得出的结果：“吉尔是湿的”。
• 杰克的实际观察：“吉尔完全是干的”。
• “是湿的”和“是干的”这两个陈述不可能同时为真，这就是一个矛盾。作者称这个观察结果（吉尔是干的）为“显然是假的结果”，这是站在“外面正在下雨”的假设角度来说的。在那个假设的世界里，“吉尔是干的”这个事实是不应该发生的，是“假”的。

• 第四步：得出结论
• 既然“外面正在下雨”这个假设导致了一个与事实不符的矛盾，那么这个假设本身一定是错误的。
• 因此，它的反面——“外面没有下雨”——必然是真的。

这是数学史上一个非常经典和优美的反证法应用，证明了 $\sqrt{2}$ 无法被写成两个整数的分数。

预备定义

• 有理数 (Rational number): 可以表示为分数 $\frac{m}{n}$ 的数，其中 $m$ 是整数，$n$ 是非零整数。“有理”来自于 ratio，即比值。
• 无理数 (Irrational number): 不是有理数的实数。

证明的整体思路

1. 想证明的陈述 P：$\sqrt{2}$ 是无理数。
2. 反证法第一步 (假设非P)：假设 $\sqrt{2}$ 不是无理数，那它就必须是有理数。
3. 推理：从“$\sqrt{2}$ 是有理数”这个假设出发，进行一系列代数变形和逻辑推导。
4. 寻找矛盾：推导的目标是得出一个自相矛盾的结论。

证明步骤详解

1. [假设] 假设 $\sqrt{2}$ 是一个有理数。根据定义，我们可以把它写成一个分数：

$\sqrt{2} = \frac{m}{n}$

其中 $m, n$ 是整数 ($n \neq 0$)。

1. [关键预处理：化为最简分数]

如果 $m$ 和 $n$ 都可以被大于 1 的同一个整数整除，则将它们都除以这个最大的整数。这样做不会改变分数的值。现在，$m$ 和 $n$ 中至少有一个必须是奇数。

• 这一步至关重要，它为后面制造矛盾埋下了伏笔。任何分数都可以被化简到“最简形式”，即分子和分母没有公因数（除了1）。
• 如果 $m$ 和 $n$ 都是偶数，它们就有一个公因数2，就不是最简的。所以，对于最简分数 $\frac{m}{n}$， $m$ 和 $n$ 不可能同时是偶数。这意味着，两者中至少有一个是奇数。这个结论是后面产生矛盾的关键。

1. [代数变形1：去分母]

$n \sqrt{2} = m$

1. [代数变形2：去根号]

$2 n^2 = m^2$

• 这个等式是后续所有推理的基础。

1. [第一轮推论：关于 m 的性质]

因为 $m^2$ 是整数 $n^2$ 的 2 倍，我们知道 $m^2$ 是偶数。

因此，$m$ 也是偶数，因为奇数的平方总是奇数。

• 这是一个重要的引理：如果一个整数的平方是偶数，那么这个整数本身也是偶数。证明在之前的例子中已经提过（用反证法：如果 $m$ 是奇数，$m^2$ 必然是奇数）。
• 我们得出了第一个重要结论：m 是偶数。

1. [利用 m 的性质继续变形]

所以我们可以写 $m=2k$，其中 $k$ 是某个整数。

• 这是偶数的定义。

然后，用 $2k$ 代替 $m$，我们得到

$2n^2 = (2k)^2 = 4k^2$

• 代入 $2n^2=m^2$ 这个等式。

1. [代数变形3：化简]

将方程两边除以 2，我们得到

$n^2 = 2k^2$

1. [第二轮推论：关于 n 的性质]

但这个结果表明 $n^2$ 是偶数，因此 $n$ 是偶数。

• 和第5步完全一样的逻辑。因为 $n^2$ 是整数 $k^2$ 的2倍，所以 $n^2$ 是偶数，从而 $n$ 也必须是偶数。
• 我们得出了第二个重要结论：n 是偶数。

1. [引爆矛盾]

因此我们已经确定 $m$ 和 $n$ 都是偶数。

但我们之前已经将 $m$ 和 $n$ 约分，使得它们不同时是偶数——这是一个矛盾。

• 在第5步，我们推导出 m 是偶数。
• 在第8步，我们推导出 n 是偶数。
• 所以，$m$ 和 $n$ 同时是偶数。
• 但这直接违背了我们在第2步设下的前提：“$m$ 和 $n$ 被化简到最简，它们不可能同时是偶数”。
• 同一个陈述“m和n不可能同时是偶数”和它的否定“m和n都是偶数”同时成立了。这就是一个彻头彻尾的逻辑矛盾。

1. [最终结论]
   • 这个矛盾的根源在哪里？我们所有的代数和逻辑推导都是正确的。那么问题只能出在最初的那个假设上。
   • “$\sqrt{2}$ 是一个有理数”这个假设导致了逻辑体系的崩溃。因此，这个假设必须是假的。
   • 结论：$\sqrt{2}$ 只能是无理数。证明完毕。

这段话介绍了第三种，也是在计算机科学中极为重要的一种证明类型：数学归纳法 (Proof by Induction)。

1. 适用场景

• 核心用途：用于证明一个陈述对于一个无限、有序、且具有起始点的集合中的所有元素都成立。
• 典型集合：最常见的应用场景是证明某个属性 $\mathcal{P}$ 对所有自然数 $k=1, 2, 3, \ldots$ 都成立。
• 计算机科学中的应用：
• 证明算法正确性：例如，证明一个循环在每一次迭代后都保持某个“循环不变式” (loop invariant)。
• 证明数据结构性质：例如，证明一棵树在任意次插入操作后，仍然保持其平衡属性。
• 证明公式：例如，证明某个关于 $n$ 的求和公式对所有 $n$ 都成立。

2. 证明结构：两步法

数学归纳法的证明结构非常固定，必须包含以下两个独立的部分：

• 第一部分：基础 (Base Case / Basis Step)
• 目标：证明这个陈述在无限集的“起点”处成立。
• 操作：对于自然数集，就是要证明 $\mathcal{P}(1)$ 是真的。直接将 $k=1$ 代入陈述，验证其真伪。
• 作用：它像是多米诺骨牌的第一张牌，我们必须先手动把它推倒。

• 第二部分：归纳步骤 (Inductive Step)
• 目标：证明一个“传递”的规律：如果陈述在某一点成立，那么它在紧接着的下一点也必然成立。
• 操作：

1. 归纳假设 (Inductive Hypothesis)：假设对于某个任意的 $i \geq 1$，$\mathcal{P}(i)$ 是真的。我们并不知道 $i$ 是多少，只是假设它成立。
2. 归纳证明：利用这个假设，通过逻辑推导，证明 $\mathcal{P}(i+1)$ 也必须是真的。
   • 核心：证明的是一个蕴含关系：$\forall i \ge 1, (\mathcal{P}(i) \Rightarrow \mathcal{P}(i+1))$。
   • 作用：它证明了“如果前一张牌倒了，那么后一张牌也一定会跟着倒”这个连锁反应的机制是存在的。

3. 为什么这样就够了？——多米诺骨牌效应

作者用一段话解释了为什么完成了这两步，就足以证明陈述对所有自然数都成立。这个逻辑链条就像推倒多米诺骨牌：

1. 我们通过 基础 证明了 $\mathcal{P}(1)$ 为真。（第一张牌被推倒了。）
2. 我们通过 归纳步骤 证明了 $\mathcal{P}(1) \Rightarrow \mathcal{P}(2)$。因为已经知道 $\mathcal{P}(1)$ 为真，所以 $\mathcal{P}(2)$ 必然为真。（第一张牌倒了，所以第二张也倒了。）
3. 我们通过 归纳步骤 证明了 $\mathcal{P}(2) \Rightarrow \mathcal{P}(3)$。因为刚刚推导出 $\mathcal{P}(2)$ 为真，所以 $\mathcal{P}(3)$ 必然为真。（第二张牌倒了，所以第三张也倒了。）
4. ...这个过程可以无限地延续下去，覆盖所有的自然数。$\mathcal{P}(i) \Rightarrow \mathcal{P}(i+1) \Rightarrow \mathcal{P}(i+2) \ldots$

这段话介绍了数学归纳法的两种常见变体，并给出了标准的书写格式。

第一种变体：改变起始点

• 标准归纳法：从 $k=1$ 开始，证明对所有自然数 $k \ge 1$ 成立。
• 变体：基础可以从任何整数 $b$ 开始。
• 操作：
• 基础：证明 $\mathcal{P}(b)$ 为真。
• 归纳步骤：证明对于所有 $i \ge b$，如果 $\mathcal{P}(i)$ 为真，则 $\mathcal{P}(i+1)$ 也为真。
• 结论：这种证明表明 $\mathcal{P}(k)$ 对于所有 $k \ge b$ 的整数都为真。
• 直观理解：多米诺骨牌不一定从第一张开始推，我们可以从第 $b$ 张开始推，那么从第 $b$ 张往后的所有牌都会倒下。

第二种变体：强归纳法 (Strong Induction)

• 标准归纳法 (弱归纳法)：
• 在归纳步骤中，我们只假设 $\mathcal{P}(i)$ 成立，来证明 $\mathcal{P}(i+1)$。
• 归纳假设：$\mathcal{P}(i)$ is true.
• 多米诺骨牌比喻：我们只关心“前一张牌” ($i$) 是否倒下。

• 强归纳法：
• 在归纳步骤中，我们假设从起点到 $i$ 的所有命题都成立，来证明 $\mathcal{P}(i+1)$。
• 更强的归纳假设：$\mathcal{P}(1), \mathcal{P}(2), \ldots, \mathcal{P}(i)$ all are true. (或者说，for all $j$ where $b \le j \le i$, $\mathcal{P}(j)$ is true)。
• 为什么仍然有效：作者解释说，这个证明依然有效，因为在多米诺骨牌的逻辑链中，当我们试图推倒第 $i+1$ 张牌时，它前面的第1, 2, ..., i 张牌实际上都已经倒下了。所以，假设它们全都倒下了，是完全合理的。我们只是把一个更强的、但同样为真的事实作为我们的假设。
• 多米诺骨牌比喻：要推倒第 $i+1$ 张牌，我们不仅可以利用第 $i$ 张牌的力量，我们可以利用前面所有已经倒下的牌（1到i）的合力。
• 何时使用：当证明 $\mathcal{P}(i+1)$ 时，仅靠 $\mathcal{P}(i)$ 的信息不足，还需要用到 $\mathcal{P}(i-1)$ 或更早的信息时，强归纳法就非常有用。常见于涉及递归深度大于1的问题（如斐波那契数列）的证明。

归纳法证明的标准格式

作者给出了一个清晰、简洁的写作模板，这在答题或写论文时非常重要。

1. 明确标出“基础”部分：
   • 写出 基础: 或 Base Case:。
   • 清晰地证明 $\mathcal{P}(1)$ (或 $\mathcal{P}(b)$) 成立。
2. 明确标出“归纳步骤”部分：
   • 写出 归纳步骤: 或 Inductive Step:。
   • 明确写出你的归纳假设。例如：“假设对于某个 $i \ge 1$，$\mathcal{P}(i)$ 成立。”
   • 明确写出你要证明的目标。例如：“我们要证明 $\mathcal{P}(i+1)$ 成立。”
   • 给出从归纳假设到证明目标的完整推导过程。
3. 使用省略号(...)：这里的省略号表示证明的具体内容需要填充进去。

这是一个引子，为接下来的定理和证明设置了背景和定义。它将一个抽象的数学工具（归纳法）应用到一个非常现实的金融问题上。

1. 问题背景

• 场景：房屋抵押贷款。
• 过程：借一笔钱（本金），然后每月支付固定的金额（月付款），持续多年（例如30年），直到还清。
• 月付款的构成：每次还款，一部分是用来支付这个月产生的利息，剩下的一部分才是用来减少本金。
• 目标：作者提到计算这个“月付款”的公式看起来很神秘，而他将要用归纳法来证明一个与之相关的公式是正确的。这展示了数学在日常生活中的应用。

2. 变量定义

这是进行任何数学建模的第一步，必须极其清晰。

• $P$: 本金 (Principal)。是你最初借的钱的总额。例如，$P = \$500,000$。
• $I$: 年利率 (Annual Interest Rate)。以小数形式表示。例如，年利率 6% 意味着 $I = 0.06$。
• $Y$: 月付款 (Monthly Payment)。每个月你固定支付的金额。例如，$Y = \$2,997.75$。
• $M$: 月乘数 (Monthly Multiplier)。这是每个月你的欠款因为利息而增长的倍数。
• 计算方法：银行通常按月计算利息（按月复利），月利率 = 年利率 / 12。
• 如果月利率是 $I/12$，那么一个月后，你的欠款会变成原来的 $1 + I/12$ 倍。
• 所以，$M = 1 + I/12$。
• 例子：如果年利率是 6% ($I=0.06$)，那么月利率是 $0.06 / 12 = 0.005$。月乘数 $M = 1 + 0.005 = 1.005$。这意味着你每个月的欠款都会乘以 1.005。

3. 建立递推关系

这一步是归纳法应用的关键，它描述了问题状态是如何从一步演变到下一步的。

• $P_t$: 第 $t$ 个月结束时（还完款后）剩余的欠款。
• $P_0$: 第0个月结束时，也就是刚借钱时，欠款就是本金 $P$。
• $P_1$: 第1个月的演变过程：

1. 月初，欠款是 $P_0$。
2. 一个月过去，利息产生，欠款增长为 $M \times P_0$。
3. 月末，你还了一笔钱 $Y$。
4. 最终欠款 $P_1 = M P_0 - Y$。
   • $P_2$: 第2个月的演变过程：
5. 月初，欠款是 $P_1$。
6. 一个月过去，利息产生，欠款增长为 $M \times P_1$。
7. 月末，你还了钱 $Y$。
8. 最终欠款 $P_2 = M P_1 - Y$。
   • 通用递推关系: $P_{t+1} = M P_t - Y$。这个关系描述了贷款余额的动态变化，是归纳步骤的基础。

4. 预告

• 作者明确指出，他将要陈述并证明一个关于 $P_t$ 的“封闭公式”(closed-form formula)。
• 递推关系 $P_t = M P_{t-1} - Y$ 告诉我们如何从上一步计算下一步，但如果我们想直接知道第360个月（30年）的欠款 $P_{360}$，就需要一步步算360次，非常麻烦。
• 而一个封闭公式可以直接把 $t=360$ 代入，一次性算出结果。接下来的定理就是给出这个封闭公式，并用归纳法来证明它与递推关系是等价的。

这是定理的陈述，它给出了第 $t$ 个月后剩余贷款 $P_t$ 的一个封闭公式。

• 公式含义：这个公式允许我们不通过一步步的递推，直接计算出任意时刻 $t$ 的剩余贷款。
• 公式结构分析：
• $P M^t$: 这一项代表的是原始本金 $P$ 在没有任何还款的情况下，经过 $t$ 个月复利增长后会变成多少。这是纯粹的利息增长部分。
• $Y\left(\frac{M^{t}-1}{M-1}\right)$: 这一项代表的是你每月支付的月付款 $Y$ 所产生的“总价值”。
• $\frac{M^{t}-1}{M-1}$: 这是一个标准的等比数列求和公式的结果，即 $1 + M + M^2 + \dots + M^{t-1}$。
• 所以 $Y\left(\frac{M^{t}-1}{M-1}\right) = Y(1 + M + M^2 + \dots + M^{t-1})$。
• 这一项的金融学含义是：你每次支付的 $Y$，如果都存入一个同样按月利率 $M-1$ 复利的账户，到第 $t$ 个月时，它们总共会值多少钱。你第 $t$ 次还的 $Y$ 还没利息，价值是 $Y$；第 $t-1$ 次还的 $Y$ 增值了1个月，价值是 $YM$；...；你第1次还的 $Y$ 增值了 $t-1$ 个月，价值是 $YM^{t-1}$。总价值就是这个求和。
• 整体含义：第t个月的欠款 = (本金按复利计算的总额) - (你所有还款按复利计算的总价值)。这在逻辑上是非常合理的。

这是对定理 0.25 的完整归纳法证明。

第一部分：基础 (Base Case)

• 目标：证明 公式在起点 $t=0$ 时成立。
• 操作：将 $t=0$ 代入定理中的公式。

$P_0 = P M^0 - Y\left(\frac{M^0 - 1}{M-1}\right)$

• 化简：
• 任何非零数的0次方都等于1，所以 $M^0 = 1$。
• 代入后，右边的第二项变为 $Y\left(\frac{1 - 1}{M-1}\right) = Y\left(\frac{0}{M-1}\right) = 0$。
• 所以，公式变为 $P_0 = P \times 1 - 0$，即 $P_0 = P$。
• 验证：这个结果 $P_0 = P$ 与我们在问题背景中初始定义的“第0个月的欠款是本金 P”是完全一致的。
• 结论：基础成立。多米诺骨牌的第一张牌 ($t=0$) 确实是“倒下的”。

第二部分：归纳步骤 (Inductive Step)

• 目标：证明连锁反应机制：如果公式在第 $k$ 个月成立，那么它在第 $k+1$ 个月也一定成立。
• 1. 归纳假设 (Inductive Hypothesis)：
• 我们假设对于某个任意的 $k \ge 0$，公式是对的。即：

$P_{k}=P M^{k}-Y\left(\frac{M^{k}-1}{M-1}\right)$

• 2. 证明目标 (Goal to Prove)：
• 我们需要利用上面的假设，去证明 公式对 $t=k+1$ 也成立。即要证明：

$P_{k+1}=P M^{k+1}-Y\left(\frac{M^{k+1}-1}{M-1}\right) .$$

• 3. 推导过程：
• 出发点：我们从贷款余额的递推定义出发，这是连接第 $k$ 个月和第 $k+1$ 个月的桥梁。

$P_{k+1} = P_k M - Y$

• 关键一步：使用归纳假设。将归纳假设中 $P_k$ 的表达式，完整地代入上面的递推关系式中。

$P_{k+1} = \left[ P M^k - Y\left(\frac{M^k - 1}{M-1}\right) \right] M - Y$

• 代数化简：现在我们的目标就是把这个复杂的表达式，通过纯粹的代数运算，化简成我们想证明的目标形式。
• 第一步：把 M 乘进去

$P_{k+1} = (P M^k)M - \left(Y\left(\frac{M^k - 1}{M-1}\right)\right)M - Y$

$= P M^{k+1} - Y\left(\frac{(M^k - 1)M}{M-1}\right) - Y$

$= P M^{k+1} - Y\left(\frac{M^{k+1} - M}{M-1}\right) - Y$

• 第二步：合并 Y 项。为了合并，需要把单独的 $Y$ 也变成一个分母是 $M-1$ 的分数。

$Y = Y \times 1 = Y \left(\frac{M-1}{M-1}\right)$

所以，

$P_{k+1} = P M^{k+1} - Y\left(\frac{M^{k+1} - M}{M-1}\right) - Y\left(\frac{M-1}{M-1}\right)$

• 第三步：合并分数。

$P_{k+1} = P M^{k+1} - Y \left[ \left(\frac{M^{k+1} - M}{M-1}\right) + \left(\frac{M-1}{M-1}\right) \right]$ (注意提了负号，所以是加法)

$= P M^{k+1} - Y \left( \frac{(M^{k+1} - M) + (M - 1)}{M-1} \right)$

$= P M^{k+1} - Y \left( \frac{M^{k+1} - M + M - 1}{M-1} \right)$

$= P M^{k+1} - Y \left( \frac{M^{k+1} - 1}{M-1} \right)$

• 达成目标：我们化简得到的结果，与我们的“证明目标” $P_{k+1}$ 的表达式完全一样。
• 结论：归纳步骤完成。我们证明了 $\mathcal{P}(k) \Rightarrow \mathcal{P}(k+1)$。

最终结论

因为基础和归纳步骤都已成功证明，所以根据数学归纳法原理，该公式对于所有 $t \ge 0$ 都成立。

[问题 0.14 的提示]

问题 0.14 要求你使用上述公式计算实际的抵押贷款付款。

• 这里的公式是用来计算 $P_t$ 的。要计算月付款 $Y$，你需要设定一个还款目标。例如，30年（360个月）后还清贷款。
• 这意味着 $P_{360} = 0$。
• 所以，你将 $t=360$ 和 $P_{360}=0$ 代入定理 0.25 的公式：

$0 = P M^{360} - Y\left(\frac{M^{360}-1}{M-1}\right)$

• 这是一个关于 $Y$ 的一元一次方程。你可以通过移项和除法，从中解出 $Y$ 的值。

$Y\left(\frac{M^{360}-1}{M-1}\right) = P M^{360}$

$Y = P M^{360} \left/ \left(\frac{M^{360}-1}{M-1}\right) \right. = P \frac{M^{360}(M-1)}{M^{360}-1}$

• 把 $M=1+I/12$ 代回去，就得到了标准的月付款计算公式。

这道题的目的是考察对集合描述方式的理解，以及在形式化语言和自然语言之间进行转换的能力。

• 形式描述 (Formal description): 使用数学符号和规则来精确定义的描述，如 {n | P(n)} 的形式。
• 非正式英语描述 (Informal English description): 使用日常语言来描述集合的性质，让人能直观理解。
• a. $\{1,3,5,7, \ldots\}$: 这是通过列举部分元素并使用省略号来暗示规律。你需要识别出这个规律。这是所有正奇数组成的集合。
• b. $\{\ldots,-4,-2,0,2,4, \ldots\}$: 同样是列举法，省略号在两边表示向两个方向无限延伸。这是所有偶数（包括正、负、零）组成的集合。
• c. $\{n \mid n=2 m$ 对于某个自然数 $m\}$: 这是集合构建表示法。| 左边是集合元素的形式 ($n$)，右边是元素必须满足的条件。条件是 $n$ 能被写成一个自然数 $m$ 的两倍。这正是所有正偶数的定义。注意，如果课本定义自然数从0开始，那么这里就是所有非负偶数。如果从1开始，就是所有正偶数。
• d. $\{n \mid n=2 m \ldots \text{并且} n=3 k \ldots\}$: 元素 $n$ 必须同时满足两个条件：它是一个正偶数（能被2整除），并且它是一个正的3的倍数（能被3整除）。一个数同时是2和3的倍数，意味着它是6的倍数。所以这是所有正的6的倍数组成的集合。
• e. $\{w \mid w \text{ 是一个...字符串...并且 } w \text{ 等于 } w \text{ 的反向}\}$: 这里的元素是字符串。条件是字符串 $w$ 和它的反向（把字符串倒过来写）是相同的。这种字符串有一个专门的名字，叫做“回文串” (palindrome)。所以这是所有由0和1组成的回文串的集合（例如 0, 11, 010, 1001）。
• f. $\{n \mid n \text{ 是一个整数，并且 } n=n+1\}$: 条件是 $n=n+1$。这是一个在整数范围内永远无法满足的方程。没有任何整数会等于它自己加一。因此，没有任何元素满足这个条件。这是一个空集 ($\emptyset$ or {})。

这道题是上一题的反向操作，考察将自然语言描述的集合转换为形式化数学语言的能力。

• a. 包含数字 1、10 和 100 的集合: 元素数量有限且确定，最适合用列举法。形式描述为 $\{1, 10, 100\}$。
• b. 包含所有大于 5 的整数的集合: 元素无限，适合用集合构建表示法。形式描述为 $\{n \mid n \in \mathbb{Z} \text{ and } n > 5\}$，其中 $\mathbb{Z}$ 代表整数集。也可以写成 $\{6, 7, 8, \ldots\}$。
• c. 包含所有小于 5 的自然数的集合: 同样用集合构建法。形式描述为 $\{n \mid n \in \mathbb{N} \text{ and } n < 5\}$，其中 $\mathbb{N}$ 代表自然数集。假设自然数从0开始，这个集合就是 $\{0, 1, 2, 3, 4\}$。如果从1开始，就是 $\{1, 2, 3, 4\}$。用列举法写出来更清晰。
• d. 包含字符串 aba 的集合: 只有一个元素的集合。形式描述为 {"aba"}。注意元素是字符串 aba，而不是字符 a, b, a。
• e. 包含空字符串的集合: 空字符串通常用 $\epsilon$ 或 $\lambda$ 表示。这是一个只包含一个元素——空字符串——的集合。形式描述为 {\epsilon}。
• f. 完全不包含任何内容的集合: 这是空集。形式描述为 {} 或 $\emptyset$。

这道题考察对基本集合运算和关系的理解。

• a. $A$ 是 $B$ 的子集吗？: 判断 $A$ 的所有元素是否都在 $B$ 中。元素 'z' 在 $A$ 中，但不在 $B$ 中。所以，不是。
• b. $B$ 是 $A$ 的子集吗？: 判断 $B$ 的所有元素是否都在 $A$ 中。$B$ 的元素 'x' 和 'y' 都在 $A$ 中。所以，是。
• c. $A \cup B$ 是什么？: 并集，包含所有在 $A$ 或在 $B$ 中的元素，不重复。结果是 $\{\mathrm{x}, \mathrm{y}, \mathrm{z}\}$，也就是 $A$ 本身。
• d. $A \cap B$ 是什么？: 交集，包含所有同时在 $A$ 和 $B$ 中的元素。结果是 $\{\mathrm{x}, \mathrm{y}\}$，也就是 $B$ 本身。
• e. $A \times B$ 是什么？: 笛卡尔积，是由一个来自 $A$ 的元素和一个来自 $B$ 的元素组成的所有可能的有序对。

结果是：$\{(\mathrm{x}, \mathrm{x}), (\mathrm{x}, \mathrm{y}), (\mathrm{y}, \mathrm{x}), (\mathrm{y}, \mathrm{y}), (\mathrm{z}, \mathrm{x}), (\mathrm{z}, \mathrm{y})\}$。

• f. $B$ 的幂集是什么？: 幂集 (Power Set) 是原集合的所有子集组成的集合。$B = \{\mathrm{x}, \mathrm{y}\}$ 有两个元素，所以它的幂集有 $2^2=4$ 个元素（子集）。

结果是：$\{\emptyset, \{\mathrm{x}\}, \{\mathrm{y}\}, \{\mathrm{x}, \mathrm{y}\}\}$。

这两题考察组合计数和对集合运算规模的理解。

• 0.4: $A \times B$ 是所有有序对 $(x,y)$ 的集合，其中 $x \in A, y \in B$。对于 $A$ 中的每一个元素（有 $a$ 种选择），$B$ 中都有 $b$ 个元素可以与之配对。根据乘法原理，总的配对数量是 $a \times b$。
• 0.5: $C$ 的幂集是 $C$ 的所有子集的集合。对于 $C$ 中的每一个元素，在构造一个子集时，我们都有两种选择：要么“包含”这个元素，要么“不包含”。$C$ 有 $c$ 个元素，每个元素都有2种独立的选择。根据乘法原理，总共可以构造出 $2 \times 2 \times \dots \times 2$ ($c$次) = $2^c$ 个不同的子集。

这道题考察对函数及其相关概念（定义域、值域、函数求值、函数复合）的理解，以及从表格中读取信息的能力。

• a. $f(2)$: 查找 $f$ 的表格，找到 $n=2$ 的那一行，对应的 $f(n)$ 的值是 7。
• b. $f$ 的值域和定义域:
• 定义域 (Domain) 是函数输入的集合，题目已给出 $f: X \longrightarrow Y$，所以定义域是 $X = \{1,2,3,4,5\}$。
• 值域 (Range) 是函数所有可能的输出值组成的集合。查看 $f(n)$ 那一列，出现过的值有 6 和 7。所以值域是 $\{6, 7\}$。
• c. $g(2,10)$: 查找 $g$ 的表格，找到行号为 2，列号为 10 的那个单元格，其值是 6。
• d. $g$ 的值域和定义域:
• 定义域是 $g: X \times Y \longrightarrow Y$ 的输入集合 $X \times Y$。
• 值域是 $g$ 的表格中出现的所有值的集合。表格中出现了 6, 7, 8, 9, 10。所以值域是 $\{6,7,8,9,10\}$，即 $Y$ 本身。
• e. $g(4, f(4))$: 这是一个函数复合求值。

1. 先计算内部的 $f(4)$。查 $f$ 表，当 $n=4$ 时，$f(4)=7$。
2. 问题变为计算 $g(4, 7)$。
3. 查 $g$ 表，找到行号为 4，列号为 7 的单元格，其值是 8。

这道题考察对关系的三个核心属性（自反性、对称性、传递性）的深刻理解。你需要构造具体的例子。设关系 $R$ 定义在集合 $S$上。

• 自反 (Reflexive): 对所有 $x \in S$，$(x,x) \in R$。
• 对称 (Symmetric): 如果 $(x,y) \in R$，那么 $(y,x) \in R$。
• 传递 (Transitive): 如果 $(x,y) \in R$ 并且 $(y,z) \in R$，那么 $(x,z) \in R$。
• a. 自反和对称但不传递:
• 思路: 需要破坏传递性。即找到 $(x,y)$ 和 $(y,z)$，但不让 $(x,z)$ 存在。
• 例子: 在集合 $S=\{a,b,c\}$ 上。
• 自反: 必须包含 {(a,a), (b,b), (c,c)}。
• 对称: 添加 (a,b) 就必须添加 (b,a)。添加 (b,c) 就必须添加 (c,b)。
• 不传递: 我们有 (a,b) 和 (b,c)，但我们不加入 (a,c)。
• 最终关系: R = {(a,a), (b,b), (c,c), (a,b), (b,a), (b,c), (c,b)}。这个关系中，(a,b) 和 (b,c) 都在，但 (a,c) 不在，所以不传递。
• b. 自反和传递但不对称:
• 思路: 破坏对称性。即有 (x,y) 但没有 (y,x)。
• 例子: 在整数集上的 "小于等于" 关系 ($\le$)。
• 自反: 对任意整数 $x$, $x \le x$ 成立。
• 传递: 如果 $x \le y$ 并且 $y \le z$，那么 $x \le z$ 成立。
• 不对称: 如果 $x < y$ (例如 $3 \le 5$)，那么 $y \le x$ ($5 \le 3$) 不成立。
• c. 对称和传递但不自反:
• 思路: 破坏自反性。即至少有一个元素 $x$ 使得 (x,x) 不在关系中。
• 例子: 在集合 $S=\{a,b,c\}$ 上。
• 不自反: (a,a) 不在关系中。
• 对称和传递: 最简单的例子是空关系 $R=\{\}$。它是对称和传递的（因为找不到反例），但不是自反的。
• 另一个例子：$R = \{(b,b), (c,c), (b,c), (c,b)\}$。(a,a) 不在其中，所以不自反。(b,c)在, (c,b)也在, 对称。传递性也满足。

这道题考察图的基本表示和概念。

• 绘制图 G:

1. 先画出4个点，并标上数字 1, 2, 3, 4。
2. 根据边集 $E$ 逐条连线：
   • 连接 1 和 2。
   • 连接 2 和 3。
   • 连接 1 和 3。（现在 1,2,3 构成一个三角形）
   • 连接 2 和 4。
   • 连接 1 和 4。（现在 1,2,4 也构成一个三角形）
   • 最终的图形看起来像一个信封，或者一个底边是 {3,4} 的三菱锥的俯视图。
   • 每个节点的度数:
   • 数一下每个节点连接了多少条边。
   • deg(1): 连接了 2, 3, 4。度数是 3。
   • deg(2): 连接了 1, 3, 4。度数是 3。
   • deg(3): 连接了 1, 2。度数是 2。
   • deg(4): 连接了 1, 2。度数是 2。
   • 验证: 度数之和 = $3+3+2+2 = 10$。边数是 5。$10 = 2 \times 5$。符合握手引理。
   • 标示路径: 路径是从一个节点到另一个节点的边的序列。从 3 到 4 的路径有很多。
   • 路径1: $3 \rightarrow 2 \rightarrow 4$。边序列是 {3,2}, {2,4}。
   • 路径2: $3 \rightarrow 1 \rightarrow 4$。边序列是 {3,1}, {1,4}。
   • 你只需要在画出的图上，用不同颜色或加粗的方式，描出其中一条路径即可。

这道题是上一题的反向操作，考察从图形中提取形式化描述的能力。一个图的形式描述是 $G=(V, E)$。

• 1. 确定节点集 V:
• 图片中有6个节点。我们可以给它们命名，比如用它们在图片上的标签：$V = \{1, 2, 3, 4, 5, 6\}$。
• 2. 确定边集 E:
• 仔细观察图中的每一条边，把它们用节点对的形式写下来。为了不遗漏，可以按节点顺序来。
• 从节点 1 出发的边: {1,2}, {1,5}。
• 从节点 2 出发的边: {2,1} (已记录), {2,3}, {2,5}。
• 从节点 3 出发的边: {3,2} (已记录), {3,4}。
• 从节点 4 出发的边: {4,3} (已记录), {4,5}, {4,6}。
• 从节点 5 出发的边: {5,1}, {5,2}, {5,4} (都已记录)。
• 从节点 6 出发的边: {6,4} (已记录)。
• 3. 整合边集 E:
• $E = \{\{1,2\}, \{1,5\}, \{2,3\}, \{2,5\}, \{3,4\}, \{4,5\}, \{4,6\}\}$。
• 最终形式描述:
• $G = (V, E)$
• $V = \{1, 2, 3, 4, 5, 6\}$
• $E = \{\{1,2\}, \{1,5\}, \{2,3\}, \{2,5\}, \{3,4\}, \{4,5\}, \{4,6\}\}$