CS 70 HW01

2024年春季，Seshia和Sinclair编写的作业01

1. 逻辑等价性

请判断以下逻辑等价是否正确，并解释你的答案。

(a) $\forall x (P(x) \land Q(x)) \equiv \forall x P(x) \land \forall x Q(x)$

答案：正确。
- 解释：假设左边是正确的，则对于任意 $x$， $P(x)$ 和 $Q(x)$ 都成立。因此，$\forall x P(x)$ 和 $\forall x Q(x)$ 也成立。所以右边是正确的。反之亦然，两边是等价的。

(b) $\forall x (P(x) \lor Q(x)) \equiv \forall x P(x) \lor \forall x Q(x)$

答案：错误。
- 解释：假设（即 $x$ 可以取值的集合）是 $\{1,2\}$，并且定义 $P(1)$ 为真，$Q(1)$ 为假，$P(2)$ 为假，$Q(2)$ 为真。此时左边的表达式为真，但右边的表达式为假。因此两者不等价。

(c) $\exists x (P(x) \lor Q(x)) \equiv \exists x P(x) \lor \exists x Q(x)$

答案：正确。
- 解释：假设左边为真，说明存在某个 $x$，使得 $P(x)$ 或 $Q(x)$ 成立。因此，右边也为真。反之亦然，两边是等价的。

(d) $\exists x (P(x) \land Q(x)) \equiv \exists x P(x) \land \exists x Q(x)$

答案：错误。
- 解释：假设是自然数集合 $N$，$P(x) = (x = 1)$，$Q(x) = (x = 2)$。此时右边为真，因为存在 $x = 1$ 使得 $P(x)$ 为真，存在 $x = 2$ 使得 $Q(x)$ 为真，但没有 $x$ 使得 $P(x)$ 和 $Q(x)$ 同时为真，因此左边为假。

2. 证明或反驳

对于以下陈述，证明其为真或通过找到反例来反驳。

(a) 对于所有 $n \in N$，如果 $n$ 是奇数，则 $n^2 + 4n$ 是奇数。

答案：正确。
- 证明：设 $n = 2k + 1$（奇数的定义），则有： $ n^2 + 4n = (2k+1)^2 + 4(2k+1) = 4k^2 + 12k + 5 = 2(2k^2 + 6k + 2) + 1 $ 因此 $n^2 + 4n$ 是奇数。

(b) 对于所有 $a,b \in R$，如果 $a + b \leq 15$，那么 $a \leq 11$ 或 $b \leq 4$。

答案：正确。
- 证明：使用反证法，假设 $a > 11$ 且 $b > 4$。则 $a + b > 15$，这与条件 $a + b \leq 15$ 矛盾，因此命题成立。

(c) 对于所有 $r \in R$，如果 $r^2$ 是无理数，那么 $r$ 是无理数。

答案：正确。
- 证明：使用反证法，假设 $r$ 是有理数，则 $r = \frac{a}{b}$，其中 $a$ 和 $b$ 是整数且 $b \neq 0$。则 $r^2 = \frac{a^2}{b^2}$，也是有理数。矛盾，因此 $r^2$ 是无理数时，$r$ 必然是无理数。

(d) 对于所有 $n \in Z^+$，有 $5n^3 > n!$。

答案：错误。
- 反例：取 $n = 7$，此时 $5 \cdot 7^3 = 1715$，但 $7! = 5040$，显然 $5n^3 < n!$，所以命题是错误的。

(e) 非零有理数与无理数的乘积是无理数。

答案：正确。
- 证明：使用反证法，假设有理数 $a$ 与无理数 $b$ 的乘积 $ab = c$ 是有理数。则 $b = \frac{c}{a}$，其中 $a$ 和 $c$ 都是有理数，因此 $b$ 是有理数，这与 $b$ 是无理数矛盾。

3. 双素数

(a) 设 $p > 3$ 是素数，证明 $p$ 的形式为 $3k + 1$ 或 $3k - 1$，其中 $k$ 是整数。

证明： 任何整数都可以写成 $3k$，$3k + 1$ 或 $3k + 2$ 的形式。对于 $p > 3$，如果 $p = 3k$，则 $p$ 可以被3整除，因此 $p$ 不是素数。因此，$p$ 必须是 $3k + 1$ 或 $3k - 1$ 的形式。

(b) 使用 (a) 部分证明 5 是唯一参与两对双素数的素数。

证明： 对于任何素数 $m > 5$，根据 (a) 的证明，$m$ 要么是 $3k + 1$，要么是 $3k - 1$ 形式。
- 情况1：如果 $m = 3k + 1$，则 $m + 2 = 3k + 3$，可以被3整除，不是素数。
- 情况2：如果 $m = 3k - 1$，则 $m - 2 = 3k - 3$，也可以被3整除，不是素数。
因此，5 是唯一参与两对双素数（3和5，5和7）的素数。

4. 机场问题

证明：假设有 $2n + 1$ 个机场，每个机场之间的距离都不同。每个机场有一架飞机飞向最近的机场。证明必然存在一个机场没有飞机飞向它。

证明： 使用数学归纳法：
- 基例： 当 $n = 1$ 时，有3个机场，设A、B、C是其中任意两个最近的机场，它们的飞机飞向彼此。因此，剩下的一个机场没有飞机飞向它。
- 归纳假设： 假设当有 $2k + 1$ 个机场时，存在一个机场没有飞机飞向它。
- 归纳步骤： 当有 $2k + 3$ 个机场时，移除最近的两座机场，它们的飞机飞向彼此，剩下的机场数量变为 $2k + 1$。根据归纳假设，剩下的机场中有一个没有飞机飞向它。添加回移除的机场后，该机场依然没有飞机飞向它。因此，对于任意 $n$，命题成立。

5. 一个硬币游戏

你的朋友 Stanley Ford 提议你和他玩一个游戏。你们每个人从一堆 $ n $ 枚硬币开始。每一轮，你选择一个至少有两枚硬币的堆，并将其分成两个堆，每个堆至少有一枚硬币。你本轮的得分是这两个堆大小的乘积（例如，如果你把一堆 5 枚硬币分成一堆 3 枚和一堆 2 枚，则得分为 $ 3 = 6 $）。你不断地进行轮次，直到所有堆都只有一枚硬币为止。Stan 也进行同样的游戏，最后谁的总得分高谁获胜。

证明：不管你如何分割堆，你的总得分始终为 $ $。

解答：

证明：

我们使用 数学归纳法 对 $ n $ 进行证明。

基础情况：

当 $ n = 1 $ 时，你开始时只有一枚硬币，因此游戏立即结束。此时你的总得分为零——确实，$ = 0 $。

归纳假设：

假设对于 $ i $ 枚硬币（其中 $ 1 i n $），无论你采用什么策略，你的总得分都会是 $ $。

归纳步骤：

现在假设你有 $ n+1 $ 枚硬币。第一步，你必须将这堆硬币分成两堆，设这两堆的大小分别为 $ s_1 $ 和 $ s_2 $，因此 $ s_1 + s_2 = n+1 $，且 $ s_1, s_2 $。你的总得分由以下几个部分组成：

你在第一次分割时的得分是 $ s_1 s_2 $；
根据归纳假设，来自堆 $ s_1 $ 的未来分割的得分是 $ $；
来自堆 $ s_2 $ 的未来分割的得分是 $ $。

因此，总得分为： $ s_1s_2 + + $

化简得： $ = = $

由于 $ s_1 + s_2 = n+1 $，因此总得分为：$ $

这正是我们需要证明的结果。因此，归纳证明完成。

解释：

这道题通过数学归纳法证明了，不管你如何选择分割硬币堆，你的最终得分始终是 $ $。这个结果表明，你和你的对手 Stanley Ford 将始终得到相同的得分，因此这个游戏的最终结果实际上是平局。

6. 网格归纳

题目描述：

Pacman在一个无限的二维网格上行走。他从某个位置$(i, j)$开始（在第一象限），并受到限制只能待在第一象限。每秒，他可以进行以下操作（如果可能的话）：

向下走一步，至$(i, j-1)$。
向左走一步，至$(i-1, j)$。

问题：证明无论他如何走，都会在有限时间内到达$(0,0)$。

解决方案：

这个问题看起来比较复杂，因为我们需要对两个变量$i$和$j$进行归纳。然而，如果我们从一些小点（比如$(2,1)$）开始尝试，看看他可以采取的不同路径，可能会发现一些规律。

我们注意到，从位置$(i,j)$到达$(0,0)$总是需要$i+j$秒，无论采取什么路径。这意味着他在有限时间内到达$(0,0)$，因为$i+j$是一个有限的数字。

我们可以通过对$i+j$进行归纳（而不是分别对$i$和$j$进行归纳），来证明这个命题。

证明步骤：

基础案例：如果$i+j=0$，那么$i=j=0$。这意味着Pacman已经在$(0,0)$的位置，因此到达$(0,0)$需要0步。
归纳假设：假设当Pacman从位置$(i,j)$开始时，$i+j=n$，他将在有限时间内到达$(0,0)$。
归纳步骤：现在考虑$i+j=n+1$的情况。
- 如果Pacman的第一步移动到$(i-1,j)$，那么新的坐标和为$i-1+j=(i+j)-1=n$，根据归纳假设，他将需要有限的时间到达$(0,0)$。
- 如果Pacman的第一步移动到$(i,j-1)$，那么新的坐标和为$i+(j-1)=(i+j)-1=n$，同样根据归纳假设，他也将在有限时间内到达$(0,0)$。
- 因此，无论他选择哪条路径，我们都可以得出结论：Pacman将需要有限时间到达$(0,0)$，证明了对于$n+1$的情况成立。