章节具体问题

本页面将持续更新。

第一章

第一节课开始怎么有“预习”和“回顾”？

一些前置性的内容可以在 https://cloud.tsinghua.edu.cn/d/b400361d4427470aad1f/ 找到，这里的教材内容涵盖了对命题联结词与真值表的基本介绍。你只需要在开始正式学习前粗略浏览一遍即可。

当然，如果你对以上内容已有一定的了解（例如已经知道 $\vee, \wedge$ 等联结词的意义），则可以忽略这一部分，直接正常听课。

如何理解只有 $P$ 为真且 $Q$ 为假的情况下 $P \rightarrow Q$ 才为假？

下面是一个可能便于你理解的较为实际的例子。

许多政治家在竞选时都许诺：如果我当选了，那么我将会减税。

如果这个政治家当选了，选民将期望他能减税。如果这个政治家没有当选，那么选民就无法指望他能减税，尽管这个人也许有足够的影响力可令当权者减税。只有在该政治家当选但却没有减税的情况下，选民才能说政治家违背了竞选诺言。

第二章

$A^-$ 是什么意思？

假设命题公式 $A$ 依赖变元 $P_1, \cdots, P_n$，即 $A = A(P_1, \cdots, P_n)$，那么 $A^- = A(\neg P_1, \cdots, \neg P_n)$，即在原表达式中用 $\neg P_i$ 替换 $P_i$。

第三章

罗素公理系统没太学明白？

公理系统的相关内容具有较强的综合性，但除非进行专门的理论研究，在实际应用中往往只要求知晓，点到为止即可。罗素公理系统本身虽简单，相关证明过程却异常繁杂且没有通法，因此若初学时觉得困难，可直接略过。

3.2 练习的第 2 题怎么做？

见 https://cloud.tsinghua.edu.cn/f/a02502c9527844339ee4/。

第四章

第五章

第六章

6.8 练习的第 4 题为什么算下来结果不对？

需要注意 $6$ 和 $8$ 的最小公倍数是 $24$ 而不是 $48$，同理 $5, 6, 8$ 的最小公倍数是 $120$ 而不是 $240$。

第七章

7.10 练习的第 3 题怎么做？

解决这道题会用到的知识其实和本章内容没有太大的关联，可以仅将其当作一道有趣的思考题。以下会解决这道题的一般情况：对于正整数 $n$，求所有 $n$-排列的最长单调子序列长度的最小值。

问题的答案为 $\lceil\sqrt n\rceil$（$\sqrt n$ 上取整）。下面分两步证明之。

第一步： 构造最长单调子序列长度恰好为 $\lceil\sqrt n\rceil$ 的 $n$-排列，也即证明 $\lceil\sqrt n\rceil$ 这个值可以取到。

设 $r = \lfloor\sqrt n\rfloor$（注意这里是下取整）。下面的排列就是一个满足要求的 $n$-排列：

$$\underbrace{r, r-1, \cdots, 2, 1}_{r}, \underbrace{2r, 2r-1, \cdots, r+1}_{r}, \cdots, \underbrace{r^2, r^2-1, \cdots, r^2-r+1}_{r}, \underbrace{n, n-1, \cdots, r^2+1}_{(n-r^2)\;\rm rests}.$$

简单来说，序列的构造方式为每 $r$ 个数一组，组内的数按降序排列，但组与组之间呈现升序关系。容易验证，上面构造的排列的最长上升子序列长度和最长下降子序列长度分别为 $\lceil\sqrt n\rceil$ 和 $\lfloor\sqrt n\rfloor$。

以 $n = 10$ 为例，此时 $r = 3$，上面的排列即为 $3, 2, 1, 6, 5, 4, 9, 8, 7, 10$。

第二步： 证明找不到最长单调子序列长度小于 $\lceil\sqrt n\rceil$ 的 $n$-排列，也即证明 $\lceil\sqrt n\rceil$ 就是答案下界。

给定 $n$-排列 $p_1, p_2, \cdots, p_n$，对于 $1 \leq k \leq n$，定义 $i_k$ 表示从 $p_k$ 开始（即必须严格以 $p_k$ 为起点）的最长上升子序列长度，$d_k$ 表示从 $p_k$ 开始的最长下降子序列长度。

使用反证法。如果存在最长单调子序列长度小于 $\lceil\sqrt n\rceil$ 的 $n$-排列 $p_1, p_2, \cdots, p_n$，那么必然存在正整数 $r < \lceil \sqrt n \rceil$（也即 $r^2 < n$），使得对任意 $1 \leq k \leq n$，有 $1 \leq i_k, p_k \leq r$。这样，二元组 $(i_k, r_k)$ 一共只有最多 $r^2$ 种取值。但 $r^2 < n$，这表明 $n$ 个二元组中必然存在两个一样的二元组。我们不妨将其记作 $(i_s, d_s)$ 和 $(i_t, d_t)$，其中 $1 \leq s < t \leq n$。

• 如果 $p_s < p_t$，由于 $p_s$ 在 $p_t$ 的前面，因此从 $p_s$ 开始的最长上升子序列长度应至少为从 $p_t$ 开始的最长上升子序列长度再加 $1$，即 $i_s \geq i_t + 1 > i_t$。
• 如果 $p_s > p_t$，由于 $p_s$ 在 $p_t$ 的前面，因此从 $p_s$ 开始的最长下降子序列长度应至少为从 $p_t$ 开始的最长下降子序列长度再加 $1$，即 $d_s \geq d_t + 1 > d_t$。

由于上述两种情况的任意一种都与 $(i_s, d_s) = (i_t, d_t)$ 矛盾，因此假设不成立。这样便证明了结论。

第八章

第九章

评论