0.3

定义、定理和证明

定理和证明是数学的灵魂，而定义则是数学的精神。这三者是所有数学学科的核心，包括我们所研究的学科。

定义描述了我们使用的对象和概念。一个定义可能很简单，如本章前面给出的集合定义，也可能很复杂，如密码系统中的安全定义。精确性对任何数学定义都至关重要。在定义某个对象时，我们必须明确什么构成该对象，什么不构成。

在我们定义了各种对象和概念之后，我们通常会对它们做出数学陈述。通常，一个陈述表达某个对象具有某种性质。该陈述可能为真也可能为假；但像定义一样，它必须精确。不允许其含义有任何歧义。

证明是令人信服的逻辑论证，表明一个陈述是真实的。在数学中，论证必须是无懈可击的；也就是说，在绝对意义上是令人信服的。在日常生活中或法律中，证明的标准较低。谋杀审判要求“排除任何合理怀疑”的证据。证据的权重可能迫使陪审团接受嫌疑人的无罪或有罪。然而，证据在数学证明中不起任何作用。数学家要求排除任何怀疑的证明。

定理是已被证明为真的数学陈述。通常我们把这个词保留给特别感兴趣的陈述。偶尔我们也会证明一些陈述，它们之所以有趣，仅仅是因为它们有助于证明另一个更重要的陈述。这样的陈述称为引理。偶尔，一个定理或其证明可能使我们能够轻易地得出其他相关陈述是真实的结论。这些陈述称为定理的推论。

寻找证明

确定数学陈述真伪的唯一方法是数学证明。不幸的是，寻找证明并非总是容易的。它不能归结为一套简单的规则或过程。在本课程中，你将被要求提供各种陈述的证明。不要因此而绝望！尽管没有人有制作证明的秘诀，但有一些有用的通用策略可供使用。

首先，仔细阅读你想证明的陈述。你理解所有符号吗？用你自己的话重写该陈述。将其分解并分别考虑每个部分。

有时，多部分陈述的各个部分并不立即显而易见。一种经常出现的多部分陈述形式是“$P$ 当且仅当 $Q$”，通常写作“$P$ iff $Q$”，其中 $P$ 和 $Q$ 都是数学陈述。这种符号是两部分陈述的简写。第一部分是“$P$ 仅当 $Q$”，这意味着：如果 $P$ 为真，则 $Q$ 为真，写作 $P \Rightarrow Q$。第二部分是“$P$ 如果 $Q$”，这意味着：如果 $Q$ 为真，则 $P$ 为真，写作 $P \Leftarrow Q$。这两部分中的第一部分是原始陈述的正向，第二部分是反向。我们将“$P$ 当且仅当 $Q$”写作 $P \Longleftrightarrow Q$。要证明这种形式的陈述，你必须证明这两个方向。通常，其中一个方向比另一个更容易证明。

另一种多部分陈述形式是声明两个集合 $A$ 和 $B$ 相等。第一部分声明 $A$ 是 $B$ 的子集，第二部分声明 $B$ 是 $A$ 的子集。因此，证明 $A=B$ 的一种常见方法是证明 $A$ 的每个成员也是 $B$ 的成员，并且 $B$ 的每个成员也是 $A$ 的成员。

接下来，当你想要证明一个陈述或其一部分时，试着对它为何为真产生一种直观的、“直觉”感觉。通过例子进行实验特别有帮助。因此，如果陈述说某种类型的所有对象都具有某个特定性质，请选择几个该类型的对象，并观察它们确实具有该性质。之后，尝试找到一个不具有该性质的对象，称为反例。如果该陈述实际上是真的，你将无法找到反例。当你尝试寻找反例时遇到的困难可以帮助你理解该陈述为何为真。

示例 0.19

假设你想证明这样的陈述：对于每个图 $G$，图 $G$ 中所有节点的度数之和是一个偶数。

首先，选择几个图并观察这个陈述的作用。这里有两个例子。

和 $=2+2+2 =6$

和 $=2+3+4+3+2 =14$

接下来，尝试找一个反例；也就是说，一个度数之和为奇数的图。

每当添加一条边时，和就会增加 2。

你现在能开始明白这个陈述为什么是真的以及如何证明它了吗？

如果你在尝试证明一个陈述时仍然卡住，请尝试一些更容易的方法。尝试证明该陈述的一个特例。例如，如果你正在尝试证明某个性质对每个 $k>0$ 都成立，首先尝试证明它对 $k=1$ 成立。如果你成功了，就尝试 $k=2$，依此类推，直到你能理解更一般的情况。如果特例难以证明，请尝试不同的特例，或者可能是特例的特例。

最后，当你认为你已经找到了证明时，你必须正确地把它写出来。一个写得好的证明是一系列陈述，其中每个陈述都通过简单的推理从序列中的前一个陈述得出。仔细地写证明很重要，这既能让读者理解它，也能确保你自己确信它没有错误。

以下是一些编写证明的技巧。

• 要有耐心。寻找证明需要时间。如果你不能马上想出办法，不要担心。研究人员有时需要工作数周甚至数年才能找到一个证明。
• 回头再看。审视你想要证明的陈述，思考一会儿，放开，然后几分钟或几小时后回来。让你的无意识、直觉部分有机会发挥作用。
• 保持整洁。当你在建立对你试图证明的陈述的直觉时，使用简单、清晰的图画和/或文字。你正在努力培养你对该陈述的洞察力，而草率会阻碍洞察力。此外，当你为他人撰写解决方案时，整洁将有助于那个人理解它。
• 要简洁。简洁有助于你表达高层次的思想，而不会迷失在细节中。好的数学符号对于简洁地表达思想很有用。但请确保在撰写证明时包含足够的推理，以便读者能够轻松理解你想要表达的内容。

为了练习，让我们证明德摩根定律之一。

定理 0.20

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

首先，这个定理的含义清楚吗？如果你不理解符号 $\cup$ 或 $\cap$ 或上划线的含义，请回顾第 4 页的讨论。

为了证明这个定理，我们必须证明两个集合 $\overline{A \cup B}$ 和 $\bar{A} \cap \bar{B}$ 是相等的。回想一下，我们可以通过证明一个集合的每个成员也是另一个集合的成员，反之亦然，来证明两个集合相等。在查看下面的证明之前，请考虑几个例子，然后尝试自己证明它。

证明 该定理指出两个集合 $\overline{A \cup B}$ 和 $\bar{A} \cap \bar{B}$ 是相等的。我们通过证明一个集合的每个元素也是另一个集合的元素，反之亦然，来证明这个断言。

假设 $x$ 是 $\overline{A \cup B}$ 的一个元素。那么根据集合补集的定义，$x$ 不在 $A \cup B$ 中。因此，根据两个集合并集的定义，$x$ 不在 $A$ 中且 $x$ 不在 $B$ 中。换句话说，$x$ 在 $\bar{A}$ 中且 $x$ 在 $\bar{B}$ 中。因此，根据两个集合交集的定义，可知 $x$ 在 $\bar{A} \cap \bar{B}$ 中。

对于另一个方向，假设 $x$ 在 $\bar{A} \cap \bar{B}$ 中。那么 $x$ 既在 $\bar{A}$ 中又在 $\bar{B}$ 中。因此，$x$ 不在 $A$ 中且 $x$ 不在 $B$ 中，所以也不在这些集合的并集中。因此 $x$ 在这些集合并集的补集中；换句话说，$x$ 在 $\overline{A \cup B}$ 中，这完成了该定理的证明。

现在，让我们证明示例 0.19 中的陈述。

定理 0.21

对于每个图 $G$，图 $G$ 中所有节点的度数之和是一个偶数。

证明 图 $G$ 中的每条边都连接着两个节点。每条边对它所连接的每个节点的度数贡献 1。因此，每条边对所有节点的度数之和贡献 2。因此，如果 $G$ 包含 $e$ 条边，那么 $G$ 中所有节点的度数之和是 $2e$，这是一个偶数。

O. 4 "-"-"-"-"-"-"-"-"-"-"-"-"-"

证明类型

在数学证明中经常出现几种类型的论证。在这里，我们描述一些在计算理论中经常出现的类型。请注意，一个证明可能包含不止一种类型的论证，因为证明本身可能包含几个不同的子证明。

构造性证明

许多定理陈述了某种特定类型的对象存在。证明这种定理的一种方法是演示如何构造该对象。这种技术是构造性证明。

让我们使用构造性证明来证明以下定理。如果图中每个节点的度数都是 $k$，我们称该图为 k-正则图。

定理 0.22

对于每个大于 2 的偶数 $n$，存在一个具有 $n$ 个节点的 3-正则图。

证明 令 $n$ 为大于 2 的偶数。构造图 $G=(V, E)$ 如下，其中 $G$ 有 $n$ 个节点。$G$ 的节点集是 $V=\{0,1, \ldots, n-1\}$，$G$ 的边集是

$$\begin{aligned} E= & \{\{i, i+1\} \mid \text { for } 0 \leq i \leq n-2\} \cup\{\{n-1,0\}\} \\ & \cup\{\{i, i+n / 2\} \mid \text { for } 0 \leq i \leq n / 2-1\} . \end{aligned}$$

将该图的节点想象成按顺序排列在一个圆周上。在这种情况下，$E$ 的第一行描述的边连接圆周上的相邻对节点。$E$ 的第二行描述的边连接圆周上相对两侧的节点。这种心理图像清楚地表明 $G$ 中每个节点的度数都是 3。

反证法

在证明定理的一种常见论证形式中，我们假设定理是假的，然后证明这个假设会导致一个明显错误的结论，称为矛盾。我们经常在日常生活中使用这种推理，例如以下例子。

示例 0.23

杰克看到刚从外面进来的吉尔。他观察到她完全是干的，就知道没有下雨。他“证明”没有下雨的理由是，如果正在下雨（假设陈述是假的），吉尔就会湿透（明显错误的结论）。因此，一定没有下雨。

接下来，让我们用反证法证明 2 的平方根是一个无理数。一个数是有理数，如果它可以表示为分数 $\frac{m}{n}$，其中 $m$ 和 $n$ 是整数；换句话说，有理数是整数 $m$ 和 $n$ 的比率。例如，$\frac{2}{3}$ 显然是一个有理数。一个数是无理数，如果它不是有理数。

定理 0.24

$\sqrt{2}$ 是无理数。 证明 首先，为了以后获得矛盾，我们假设 $\sqrt{2}$ 是有理数。因此

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

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

我们方程两边乘以 $n$ 得到

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

我们对方程两边平方得到

$$2 n^{2}=m^{2} .$$

因为 $m^2$ 是整数 $n^2$ 的 2 倍，我们知道 $m^2$ 是偶数。因此，$m$ 也是偶数，因为奇数的平方总是奇数。所以我们可以写 $m=2k$ 对于某个整数 $k$。然后，用 $2k$ 替换 $m$，我们得到

$$\begin{aligned} 2 n^{2} & =(2 k)^{2} \\ & =4 k^{2} . \end{aligned}$$

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

$$n^{2}=2 k^{2} .$$

但这个结果表明 $n^2$ 是偶数，因此 $n$ 是偶数。这样我们就确定了 $m$ 和 $n$ 都是偶数。但是我们之前已经将 $m$ 和 $n$ 约简，使得它们不同时为偶数——这是一个矛盾。

归纳法证明

归纳法证明是一种高级方法，用于证明无限集合的所有元素都具有指定属性。例如，我们可以使用归纳法证明一个算术表达式对于变量的每个赋值都计算出所需的值，或者一个程序在所有步骤或所有输入下都能正确工作。

为了说明归纳法证明如何工作，让我们把无限集设为自然数 $\mathcal{N}=\{1,2,3, \ldots\}$，并假设该属性被称为 $\mathcal{P}$。我们的目标是证明 $\mathcal{P}(k)$ 对于每个自然数 $k$ 都是真的。换句话说，我们想证明 $\mathcal{P}(1)$ 是真的，以及 $\mathcal{P}(2)$、$\mathcal{P}(3)$、$\mathcal{P}(4)$ 等等。

每个归纳法证明都由两部分组成：基础和归纳步。每个部分本身都是一个独立的证明。基础证明 $\mathcal{P}(1)$ 是真的。归纳步证明对于每个 $i \geq 1$，如果 $\mathcal{P}(i)$ 是真的，那么 $\mathcal{P}(i+1)$ 也是真的。

当我们证明了这两个部分后，所需的结果就随之而来了——即 $\mathcal{P}(i)$ 对于每个 $i$ 都是真的。为什么呢？首先，我们知道 $\mathcal{P}(1)$ 是真的，因为基础本身就证明了它。其次，我们知道 $\mathcal{P}(2)$ 是真的，因为归纳步证明如果 $\mathcal{P}(1)$ 是真的那么 $\mathcal{P}(2)$ 也是真的，而我们已经知道 $\mathcal{P}(1)$ 是真的。第三，我们知道 $\mathcal{P}(3)$ 是真的，因为归纳步证明如果 $\mathcal{P}(2)$ 是真的那么 $\mathcal{P}(3)$ 也是真的，而我们已经知道 $\mathcal{P}(2)$ 是真的。这个过程会持续下去，对于所有自然数，证明 $\mathcal{P}(4)$ 是真的，$\mathcal{P}(5)$ 是真的，依此类推。

一旦你理解了前一段，你就可以很容易地理解相同思想的变体和推广。例如，基础不一定非要从 1 开始；它可以从任何值 $b$ 开始。在这种情况下，归纳证明表明 $\mathcal{P}(k)$ 对于每个至少为 $b$ 的 $k$ 都是真的。

在归纳步中，假设 $\mathcal{P}(i)$ 为真，这个假设被称为归纳假设。有时，拥有更强的归纳假设，即 $\mathcal{P}(j)$ 对每个 $j \leq i$ 都为真，是很有用的。归纳证明仍然有效，因为当我们想证明 $\mathcal{P}(i+1)$ 为真时，我们已经证明了 $\mathcal{P}(j)$ 对每个 $j \leq i$ 都为真。

归纳法证明的书写格式如下。 基础：证明 $\mathcal{P}(1)$ 为真。 ⋮

归纳步：对于每个 $i \geq 1$，假设 $\mathcal{P}(i)$ 为真，并利用此假设表明 $\mathcal{P}(i+1)$ 为真。 ⋮

现在，让我们用归纳法证明用于计算住房抵押贷款每月还款额的公式的正确性。在购买房屋时，许多人会借入部分购房所需的资金，并在一定年限内偿还这笔贷款。通常，此类还款条款规定，每月支付固定金额，以支付利息以及部分原始本金，以便在 30 年内还清总额。计算每月还款额的公式笼罩在神秘之中，但实际上非常简单。它影响着许多人的生活，所以你应该会觉得它很有趣。我们使用归纳法来证明它有效，这使其成为该技术的一个很好的例证。

首先，我们设置几个变量的名称和含义。设 $P$ 为本金，即原始贷款金额。设 $I>0$ 为贷款的年利率，其中 $I=0.06$ 表示 6% 的利率。设 $Y$ 为每月还款额。为方便起见，我们使用 $I$ 定义另一个变量 $M$，即月乘数。它是贷款因利息每月变化的比例。按照标准银行惯例，月利率是年利率的十二分之一，因此 $M=1+I/12$，并且利息按月支付（按月复利）。

每个月都会发生两件事。首先，由于月乘数的作用，贷款金额趋于增加。其次，由于每月还款额的作用，贷款金额趋于减少。设 $P_t$ 为第 $t$ 个月后未偿还的贷款金额。那么 $P_0=P$ 是原始贷款金额，$P_1=MP_0-Y$ 是一个月后的贷款金额，$P_2=MP_1-Y$ 是两个月后的贷款金额，依此类推。现在我们准备通过对 $t$ 的归纳法来陈述和证明一个定理，它给出了 $P_t$ 值的公式。

定理 0.25

对于每个 $t \geq 0$，

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

证明

基础：证明该公式对于 $t=0$ 成立。如果 $t=0$，那么该公式表明

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

我们可以通过观察 $M^0=1$ 来简化右侧。因此我们得到

$$P_{0}=P,$$

这成立，因为我们已将 $P_0$ 定义为 $P$。因此，我们已证明归纳的基础是真实的。

归纳步：对于每个 $k \geq 0$，假设该公式对于 $t=k$ 成立，并证明它对于 $t=k+1$ 成立。归纳假设表明

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

我们的目标是证明

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

我们通过以下步骤来完成。首先，根据 $P_k$ 定义 $P_{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$ 并重写 $Y$ 得到

$$\begin{aligned} 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 M^{k+1}-Y\left(\frac{M^{k+1}-1}{M-1}\right) \end{aligned}$$

因此，该公式对于 $t=k+1$ 是正确的，这证明了定理。

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

习题

0.1 检查以下集合的形式化描述，以便你了解它们包含哪些成员。用简短的非正式英语描述每个集合。 a. $\{1,3,5,7, \ldots\}$ b. $\{\ldots,-4,-2,0,2,4, \ldots\}$ c. $\{n \mid n=2 m$ 对于某个 $m$ 在 $\mathcal{N}$ 中 $\}$ d. $\{n \mid n=2 m$ 对于某个 $m$ 在 $\mathcal{N}$ 中，且 $n=3 k$ 对于某个 $k$ 在 $\mathcal{N}$ 中 $\}$ e. $\{w \mid w$ 是由 0 和 1 组成的字符串，且 $w$ 等于 $w$ 的反转 $\}$ f. $\{n \mid n$ 是一个整数，且 $n=n+1\}$ 0.2 写出以下集合的形式化描述。 a. 包含数字 1, 10 和 100 的集合 b. 包含所有大于 5 的整数的集合 c. 包含所有小于 5 的自然数的集合 d. 包含字符串 aba 的集合 e. 包含空字符串的集合 f. 包含任何内容的集合 0.3 设 $A$ 为集合 $\{\mathrm{x}, \mathrm{y}, \mathrm{z}\}$， $B$ 为集合 $\{\mathrm{x}, \mathrm{y}\}$。 a. $A$ 是 $B$ 的子集吗？ b. $B$ 是 $A$ 的子集吗？ c. $A \cup B$ 是什么？ d. $A \cap B$ 是什么？ e. $A \times B$ 是什么？ f. $B$ 的幂集是什么？ 0.4 如果 $A$ 有 $a$ 个元素，$B$ 有 $b$ 个元素，那么 $A \times B$ 中有多少个元素？解释你的答案。 0.5 如果 $C$ 是一个有 $c$ 个元素的集合，那么 $C$ 的幂集中有多少个元素？解释你的答案。 0.6 设 $X$ 为集合 \{1,2,3,4,5}， $Y$ 为集合 $\{6,7,8,9,10\}$。一元函数 $f: X \longrightarrow Y$ 和二元函数 $g: X \times Y \longrightarrow Y$ 描述在下表中。

$n$	$f(n)$
1	6
2	7
3	6
4	7
5	6

$g$	6	7	8	9	10
1	10	10	10	10	10
2	7	8	9	10	6
3	7	7	8	8	9
4	9	8	7	6	10
5	6	6	6	6	6

a. $f(2)$ 的值是多少？ b. $f$ 的值域和定义域是什么？ c. $g(2,10)$ 的值是多少？ d. $g$ 的值域和定义域是什么？ e. $g(4, f(4))$ 的值是多少？ 0.7 对于每个部分，给出一个满足条件的关​​系。 a. 自反且对称但不传递 b. 自反且传递但不对称 c. 对称且传递但不自反 0.8 考虑无向图 $G=(V, E)$，其中节点集 $V$ 是 $\{1,2,3,4\}$，边集 $E$ 是 $\{\{1,2\},\{2,3\},\{1,3\},\{2,4\},\{1,4\}\}$。画出图 $G$。每个节点的度数是多少？在你的图 $G$ 绘图中指出一条从节点 3 到节点 4 的路径。 0.9 写出以下图的形式化描述。

问题

0.10 证明每个包含两个或更多节点的图都包含两个度数相等的节点。 0.11 在以下证明中找出错误：所有马都是同一颜色。

主张：在任意 $h$ 匹马的集合中，所有马都是同一颜色。 证明：通过对 $h$ 的归纳法。 基础：对于 $h=1$。在只包含一匹马的任意集合中，所有马显然是同一颜色。

归纳步：对于 $k \geq 1$，假设该主张对于 $h=k$ 为真，并证明它对于 $h=k+1$ 为真。取任意一个包含 $k+1$ 匹马的集合 $H$。我们证明这个集合中的所有马都是同一颜色。从这个集合中移走一匹马，得到只包含 $k$ 匹马的集合 $H_1$。根据归纳假设，$H_1$ 中的所有马都是同一颜色。现在放回移走的马，再移走另一匹马，得到集合 $H_2$。根据同样的论证，$H_2$ 中的所有马都是同一颜色。因此，$H$ 中的所有马必须是同一颜色，证明完成。 0.12 设 $S(n)=1+2+\cdots+n$ 为前 $n$ 个自然数的和，设 $C(n)=1^{3}+2^{3}+\cdots+n^{3}$ 为前 $n$ 个立方数的和。通过对 $n$ 的归纳法证明以下等式，得出有趣的结论：对于每个 $n$， $C(n)=S^{2}(n)$。 a. $S(n)=\frac{1}{2} n(n+1)$。 b. $C(n)=\frac{1}{4}\left(n^{4}+2 n^{3}+n^{2}\right)=\frac{1}{4} n^{2}(n+1)^{2}$。 0.13 在以下证明 $2=1$ 的过程中找出错误。

考虑等式 $a=b$。两边乘以 $a$ 得到 $a^{2}=a b$。两边减去 $b^{2}$ 得到 $a^{2}-b^{2}=a b-b^{2}$。现在分解每一边，$(a+b)(a-b)= b(a-b)$，然后两边除以 $(a-b)$ 得到 $a+b=b$。最后，设 $a$ 和 $b$ 等于 1，这表明 $2=1$。

28 CHAPTER O / INTRODUCTION

${ }^{\mathrm{A}}$ 0.14 使用定理 0.25 推导一个公式，用于计算抵押贷款的每月还款额，以本金 $P$、利率 $I$ 和还款次数 $t$ 表示。假设在进行 $t$ 次还款后，贷款金额减少到 0。使用该公式计算为期 30 年、360 次月还款、初始贷款金额为 $100,000 美元、年利率为 5${ }^{\mathrm{A} \star}$0.15 拉姆齐定理。设$G$为一个图。$G$中的**团**是任意两个节点都由一条边连接的子图。**反团**，也称为**独立集**，是任意两个节点都没有由一条边连接的子图。证明每个有$n$个节点的图都包含一个至少有$\frac{1}{2} \log _{2} n$ 个节点的团或反团。

选定解答

0.14 我们令 $P_t=0$ 并解出 $Y$，得到公式：$Y=P M^{t}(M-1) /\left(M^{t}-1\right)$。对于 $P=\$ 100,000, I=0.05, t=360$，我们有 $M=1+(0.05) / 12$。我们使用计算器得出每月还款额 $Y \approx \$ 536.82$。 0.15 为两堆节点腾出空间：$A$ 和 $B$。然后，从整个图开始，重复将每个剩余节点 $x$ 添加到 $A$ 中，如果其度数大于剩余节点数量的一半，否则添加到 $B$ 中，并丢弃所有与 $x$ 不（是）连接的节点，如果它被添加到 $A(B)$ 中。继续直到没有节点剩余。在这些步骤中的每一步中，最多丢弃一半的节点，因此在过程终止之前至少会发生 $\log _{2} n$ 步。每一步都会向其中一堆添加一个节点，因此其中一堆最终将至少有 $\frac{1}{2} \log _{2} n$ 个节点。$A$ 堆包含一个团的节点，$B$ 堆包含一个反团的节点。

自动机与语言