原命题与逆命题等价，因此原命题为真可推出逆命题为真
原命题与逆否命题等价，逆命题与否命题等价。原命题为真时逆命题可真可假，必须独立判断。
CS70 · 第 1 讲
从真值表与命题翻译起步，训练逆命题/否命题/逆否命题、量词等价、集合的原像与像运算；结合鸽巢原理等基础组合推理，建立严谨的证明写作规范。
一个命题（proposition）是一个具有确定真值（真 \(T\) 或假 \(F\)）的陈述句。给定命题变元 \(P, Q, R, \ldots\)，我们通过逻辑联结词构造复合命题：否定（negation）\(\neg P\) 当且仅当 \(P\) 为假时为真；合取（conjunction）\(P \wedge Q\) 当且仅当二者同时为真时为真；析取（disjunction）\(P \vee Q\) 当二者至少一个为真时为真（包含性或）；蕴含（implication）\(P \to Q\) 当 \(P\) 真且 \(Q\) 假时为假，其余情况为真；双条件（biconditional）\(P \leftrightarrow Q\) 当二者真值相同时为真。
真值表（truth table）列出命题变元所有可能的真值指派及对应的复合命题真值。两个命题 \(\phi\) 与 \(\psi\) 逻辑等价（记作 \(\phi \equiv \psi\)），当且仅当在每一行指派下真值相同。真值表在有限变元下给出判定等价性的充分必要条件。
常用的逻辑等价式包括分配律 \(P \wedge (Q \vee R) \equiv (P \wedge Q) \vee (P \wedge R)\) 与 \(P \vee (Q \wedge R) \equiv (P \vee Q) \wedge (P \vee R)\)、德摩根律 \(\neg(P \wedge Q) \equiv \neg P \vee \neg Q\) 与 \(\neg(P \vee Q) \equiv \neg P \wedge \neg Q\)、以及蕴含重言式 \(P \to Q \equiv \neg P \vee Q\)。这些等价式既是验证工具，也是化简与推导的基础。
验证 \((P \to Q) \vee (P \to R) \equiv P \to (Q \vee R)\)。
列出 \(2^3 = 8\) 行真值指派：
\[ \begin{array}{ccc|cccc} P & Q & R & P \to Q & P \to R & (P \to Q) \vee (P \to R) & Q \vee R & P \to (Q \vee R) \\ \hline T & T & T & T & T & T & T & T \\ T & T & F & T & F & T & T & T \\ T & F & T & F & T & T & T & T \\ T & F & F & F & F & F & F & F \\ F & T & T & T & T & T & T & T \\ F & T & F & T & T & T & T & T \\ F & F & T & T & T & T & T & T \\ F & F & F & T & T & T & F & T \\ \end{array} \]
第六列与第八列在所有行中真值相同，因此两命题等价。
观察：当 \(P\) 为真时，左边退化为 \(Q \vee R\)，右边也是 \(Q \vee R\)；当 \(P\) 为假时，两边均为真。按主联结元分类讨论，在手工验证时能减少计算量。
蕴含 \(P \to Q\) 是数学论证的核心。围绕它衍生出四种命题形式：原命题 \(P \to Q\)、逆命题（converse）\(Q \to P\)、否命题（inverse）\(\neg P \to \neg Q\)、逆否命题（contrapositive）\(\neg Q \to \neg P\)。
关键等价关系：原命题与逆否命题逻辑等价（\(P \to Q \equiv \neg Q \to \neg P\)）；逆命题与否命题逻辑等价（\(Q \to P \equiv \neg P \to \neg Q\)）。原命题与逆命题之间没有必然的真值关系——原命题为真时，逆命题可真可假。
判断蕴含式真假的标准方法：寻找一个反例（counterexample），即一个使前件真而后件假的实例。若存在反例则命题为假；若不存在则为真，此时需要给出一般性论证。
原命题："若整数 \(n\) 能被 15 整除，则 \(n\) 能被 5 整除。"
原命题 \((\forall n \in \mathbb{Z})(15 \mid n \to 5 \mid n)\)：真。若 \(n = 15k\)，则 \(n = 5(3k)\)，故 \(5 \mid n\)。
逆命题 \((\forall n \in \mathbb{Z})(5 \mid n \to 15 \mid n)\)：假。反例 \(n = 5\) 能被 5 整除但不能被 15 整除。
否命题 \((\forall n \in \mathbb{Z})(15 \nmid n \to 5 \nmid n)\)：假。反例 \(n = 10\) 不能被 15 整除但能被 5 整除。
逆否命题 \((\forall n \in \mathbb{Z})(5 \nmid n \to 15 \nmid n)\)：真。与原命题等价，亦可用直接论证：若 \(5 \nmid n\)，则 \(n\) 不是 5 的倍数，从而也不可能是 15 的倍数。
全称量词 \(\forall\)（"对所有"）与存在量词 \(\exists\)（"存在"）用于量化命题函数 \(P(x)\) 在某个论域（universe）上的真假。
量词对逻辑联结词的分配律：\(\forall x\, (P(x) \wedge Q(x)) \equiv (\forall x\, P(x)) \wedge (\forall x\, Q(x))\)（全称对合取可分配）；\(\exists x\, (P(x) \vee Q(x)) \equiv (\exists x\, P(x)) \vee (\exists x\, Q(x))\)（存在对析取可分配）。
但以下两式一般不成立：\(\forall x\, (P(x) \vee Q(x)) \not\equiv (\forall x\, P(x)) \vee (\forall x\, Q(x))\)；\(\exists x\, (P(x) \wedge Q(x)) \not\equiv (\exists x\, P(x)) \wedge (\exists x\, Q(x))\)。
量词顺序至关重要。\(\forall x \exists y\, P(x, y)\)（对每个 \(x\) 都存在对应的 \(y\)）与 \(\exists y \forall x\, P(x, y)\)（存在一个 \(y\) 对所有 \(x\) 成立）含义不同，前者通常弱于后者。
量词的否定规则（德摩根律的量词形式）：\(\neg(\forall x\, P(x)) \equiv \exists x\, \neg P(x)\)；\(\neg(\exists x\, P(x)) \equiv \forall x\, \neg P(x)\)。
取论域为整数集 \(\mathbb{Z}\)，令 \(P(x, y)\) 表示 \(x + y = 0\)。
\(\forall x \exists y\, P(x, y)\)：真。对任意 \(x\)，取 \(y = -x\) 即可。
\(\exists y \forall x\, P(x, y)\)：假。不存在一个固定的 \(y\) 使得对所有 \(x\) 都有 \(x + y = 0\)。
因此 \(\forall x \exists y\, P(x, y) \not\equiv \exists y \forall x\, P(x, y)\)。量词顺序决定了"依赖性"：\(\forall x \exists y\) 允许 \(y\) 依赖于 \(x\)，而 \(\exists y \forall x\) 要求 \(y\) 独立于 \(x\)。
设函数 \(f: X \to Y\)。对于子集 \(A \subseteq X\) 和 \(B \subseteq Y\)，定义像 \(f(A) = \{y \in Y \mid \exists x \in A,\, f(x) = y\}\) 与原像 \(f^{-1}(B) = \{x \in X \mid f(x) \in B\}\)。
原像完全保持集合运算：\(f^{-1}(A \cup B) = f^{-1}(A) \cup f^{-1}(B)\)、\(f^{-1}(A \cap B) = f^{-1}(A) \cap f^{-1}(B)\)、\(f^{-1}(A \setminus B) = f^{-1}(A) \setminus f^{-1}(B)\)。
证明策略：利用 \(X = Y \iff X \subseteq Y \wedge Y \subseteq X\) 以及 \(X \subseteq Y \iff (\forall z)(z \in X \to z \in Y)\)。对原像，从 \(x \in f^{-1}(\cdot)\) 出发，由定义转化为 \(f(x) \in \cdot\)，再逐层拆解。
像仅保持并运算 \(f(A \cup B) = f(A) \cup f(B)\)。对交与差，一般只有单向包含：\(f(A \cap B) \subseteq f(A) \cap f(B)\)、\(f(A \setminus B) \supseteq f(A) \setminus f(B)\)。等号不成立的根源是函数可能将 \(A\) 和 \(B\) 中不同元素映射到同一个像，造成"碰撞"。
设 \(f: \mathbb{R} \to \mathbb{R}\)，\(f(x) = x^2\)。取 \(A = [1, 4]\)，\(B = [-4, -1]\)。
\(A \cap B = \varnothing\)，故 \(f(A \cap B) = \varnothing\)。
\(f(A) = [1, 16]\)，\(f(B) = [1, 16]\)，故 \(f(A) \cap f(B) = [1, 16]\)。
因此 \(f(A \cap B) = \varnothing \subsetneq [1, 16] = f(A) \cap f(B)\)，等号不成立。原因是 \(f(2) = f(-2) = 4\)，即 \(A\) 中的 2 与 \(B\) 中的 \(-2\) 碰撞到同一像。
数学证明要求从已知前提出发，经由有效推理规则达到结论。本节介绍三种基本技术：
直接证明（direct proof）：假设前提 \(P\) 为真，通过定义、已知定理和逻辑推导直接得出结论 \(Q\)。结构为 \(P \implies \cdots \implies Q\)。
逆否证明（proof by contraposition）：要证 \(P \to Q\)，改为证其逆否命题 \(\neg Q \to \neg P\)。由于 \(P \to Q \equiv \neg Q \to \neg P\)，两者等价。适用场景：当 \(\neg Q\) 比 \(P\) 提供更丰富的可用信息时。
反证法（proof by contradiction）：要证命题 \(S\)，假设 \(\neg S\) 为真，推导出矛盾（某命题 \(R\) 与 \(\neg R\) 同时成立）。由此断定 \(S\) 为真。
关于整数的常用引理：\(n\) 为奇数当且仅当存在 \(k \in \mathbb{Z}\) 使 \(n = 2k + 1\)；为偶数当且仅当存在 \(k \in \mathbb{Z}\) 使 \(n = 2k\)。奇偶性分析是反证法与逆否证明的常见入口。
命题：若 \(n^3\) 是偶数，则 \(n\) 是偶数（\(n \in \mathbb{Z}\)）。
用逆否证明。逆否命题：若 \(n\) 是奇数，则 \(n^3\) 是奇数。
设 \(n = 2k + 1\)，其中 \(k \in \mathbb{Z}\)。则 \[ n^3 = (2k + 1)^3 = 8k^3 + 12k^2 + 6k + 1 = 2(4k^3 + 6k^2 + 3k) + 1. \] 令 \(m = 4k^3 + 6k^2 + 3k \in \mathbb{Z}\)，则 \(n^3 = 2m + 1\) 为奇数。
逆否命题得证，故原命题成立。
鸽巢原理（Pigeonhole Principle）是组合数学中最基本的存在性工具。
基本形式：若 \(n\) 个物品放入 \(m\) 个容器，且 \(n > m\)，则至少有一个容器包含多于一个物品。
一般形式：若 \(n\) 个物品放入 \(m\) 个容器，则至少一个容器包含至少 \(\lceil n/m \rceil\) 个物品。
鸽巢原理的证明通常采用反证法：假设每个容器至多一个物品，则总物品数不超过 \(m\)，与 \(n > m\) 矛盾。
应用的关键是正确识别"物品"与"容器"，并注意容器实际可用数量的约束——某些容器可能因条件互斥而无法同时被占用。
命题：在边长为 1 的正方形内任取 5 个点，必有两点之间的距离不超过 \(\sqrt{2}/2\)。
将正方形分成 4 个边长为 \(1/2\) 的小正方形（4 个容器）。5 个点（5 个物品）放入 4 个小正方形，由鸽巢原理，至少有一个小正方形包含至少 2 个点。
边长为 \(1/2\) 的正方形中，任意两点最远距离为其对角线长度 \(\sqrt{(1/2)^2 + (1/2)^2} = \sqrt{2}/2\)。因此这两点距离不超过 \(\sqrt{2}/2\)。
原命题与逆否命题等价，逆命题与否命题等价。原命题为真时逆命题可真可假，必须独立判断。
量词顺序决定依赖性。\(\forall x \exists y\) 允许 \(y\) 依赖于 \(x\)，而 \(\exists y \forall x\) 要求同一个 \(y\) 对所有 \(x\) 成立，后者一般强于前者。
原像完全保持并/交/补运算，但像仅保持并运算；对交与差一般只有单向包含，等号不成立的根源是不同元素可映射到同一像。
逆否证明直接证 \(\neg Q \to \neg P\)，不需要导出矛盾；反证法假设结论假（并保持前提真），推导出任何矛盾即可。两者逻辑结构不同。
某些容器可能因条件互斥而无法同时被占用（如朋友数中 0 和 \(n-1\) 不能共存），实际可用容器数可能少于表面取值个数。
问题：设 \(P(x)\) 与 \(Q(x)\) 为命题函数。下列哪个逻辑等价式是正确的？
问题：设函数 \(f: X \to Y\)，\(A, B \subseteq Y\)。下列哪个命题对所有函数 \(f\) 都成立？
问题：命题"对所有自然数 \(n\)，若 \(n^2\) 是奇数，则 \(n\) 是奇数"的逆否命题是：
问题：下列哪个情境不能直接由鸽巢原理得出？
discussion/dis00a.pdf · 1 · confidence: high · Determine whether the following equivalences hold, by writing out truth tables. (a) P ∧ (Q ∨ P) ≡ P ∧ Q; (b) (P ∨ Q) ∧ R ≡ (P ∧ R) ∨ (Q ∧ R); (c) (P ∧ Q) ∨ R ≡ (P ∨ R) ∧ (Q ∨ R)discussion/dis00a.pdf · 2 · confidence: high · The inverse of an implication P =⇒ Q is ¬P =⇒ ¬Q. ... The contrapositive of an implication P =⇒ Q is ¬Q =⇒ ¬P.discussion/dis00a.pdf · 2-4 · confidence: high · (a) ∀x (P(x) ∧ Q(x)) ≡ ∀x P(x) ∧ ∀x Q(x) 正确；(b) ∀x (P(x) ∨ Q(x)) ≡ ∀x P(x) ∨ ∀x Q(x) 错误；(c) ∃x (P(x) ∨ Q(x)) ≡ ∃x P(x) ∨ ∃x Q(x) 正确；(d) ∃x (P(x) ∧ Q(x)) ≡ ∃x P(x) ∧ ∃x Q(x) 错误discussion/dis00b.pdf · 1 · confidence: high · Prove that if n² is odd, then n must also be odd. ... We will proceed by a proof by contraposition; the contrapositive is "if n is even, then n² is also even".discussion/dis00b.pdf · 1 · confidence: high · Prove that if there are n ≥ 2 people at a party, then at least 2 of them have the same number of friends at the party. ... containers 0, n − 1 or both must be empty since these two containers cannot be occupied at the same time. This means that we are assigning n people to at most n − 1 containersdiscussion/dis00b.pdf · 2 · confidence: high · f⁻¹(A ∪ B) = f⁻¹(A) ∪ f⁻¹(B). Suppose x ∈ f⁻¹(A∪B) which means that f(x) ∈ A∪B. Then either f(x) ∈ A, in which case x ∈ f⁻¹(A), or f(x) ∈ B, in which case x ∈ f⁻¹(B)homework/hw00.pdf · 3-4 · confidence: high · (a) f⁻¹(A ∩ B) = f⁻¹(A) ∩ f⁻¹(B); (b) f⁻¹(A \ B) = f⁻¹(A) \ f⁻¹(B); (c) f(A ∩ B) ⊆ f(A) ∩ f(B), and give an example where equality does not hold; (d) f(A \ B) ⊇ f(A) \ f(B), and give an example where equality does not holdhomework/hw00.pdf · 3 · confidence: high · (a) ∃x∃yQ(x,y) =⇒ ∃y∃xQ(x,y) True; (b) ∀x∃yQ(x,y) =⇒ ∃y∀xQ(x,y) False; (c) ∃x∀yQ(x,y) =⇒ ∀y∃xQ(x,y) True; (d) ∃x∃yQ(x,y) =⇒ ∀y∃xQ(x,y) False