Lecture 1: Propositional Logic & Proof Techniques（命题逻辑与证明技巧）

目录 · ← l1 · l3 →

Lecture 1: Propositional Logic & Proof Techniques（命题逻辑与证明技巧）

概述

上一讲我们已经在使用”若 $P$ 则 $Q$”这样的句式来写证明，但还没检查过这些句式本身是什么意思。本讲补上这一层地基：先把命题 (proposition) 与逻辑联结词 $\neg, \wedge, \vee, \Rightarrow, \iff$ 精确定义好（全部用真值表刻画），再讨论追溯每个定理”藏在哪个逻辑形式里”，最后处理数学语言中最容易出错的部分 —— 量词 (quantifier) 的辖域、嵌套顺序敏感性，以及否定的机械法则。本讲的三根支柱是：蕴涵 $P \Rightarrow Q$ 只在 $P$ 真 $Q$ 假时为假（因此前件为假时”空洞真”）、$P \Rightarrow Q \equiv \neg Q \Rightarrow \neg P$ 但 $P \Rightarrow Q \not\equiv Q \Rightarrow P$、$\neg$ 穿过 $\forall/\exists$ 时量词必须翻转。这些不是”语言游戏”：L02 的逆否证明、L03 的归纳法框架、乃至 L13 停机问题的否定式都直接建立在本讲的改写规则之上。

核心概念的直观解释

命题 (Proposition)

• 定义：命题是一个有确定真假的陈述句（”a statement which is either true or false”）。它的真假是客观的，不依赖说话人、不依赖语境、不依赖”程度”。
• 直观解释：判断一句话是不是命题，只问一个问题 —— “它有没有一个确定的是非答案？” 有就是命题（哪怕我们暂时不知道答案），没有就不是。这里是几个边界案例：

• 关键区分：$x^2 + 3x = 5$ 不是命题，但一旦用量词封口，它就变成命题：

  • $(\exists x \in \mathbb{R})(x^2+3x=5)$ —— 真。移项得 $x^2+3x-5=0$，判别式 $\Delta = 3^2 - 4\cdot 1\cdot(-5) = 9+20 = 29 > 0$，故有两个实根 $x = \dfrac{-3 \pm \sqrt{29}}{2} \approx 1.193$ 与 $-4.193$。
  • $(\exists x \in \mathbb{Z})(x^2+3x=5)$ —— 假。两个根都不是整数（$\sqrt{29}$ 是无理数），而整数里 $x^2+3x$ 恒为整数，$5$ 也是整数，但逐一检查 $x = -5,\dots,1$ 都得不到 $5$（$x=-1$ 给 $-2$，$x=1$ 给 $4$，$x=2$ 给 $10$）。
  • $(\forall x \in \mathbb{R})(x^2+3x=5)$ —— 假（取 $x = 0$ 得 $0 \neq 5$）。

  这三句话的谓词完全相同，只因量词与论域不同就产生不同的真值 —— 这解释了本讲第 2 节的动机：量词是让谓词变命题的装置，而论域是它的一部分。

• “这句话是假的”为什么不是命题？ 因为它自指 (self-reference)：如果它为真，则按它自己的话它是假的；如果它为假，则它是真的。两个方向都撞上矛盾，所以它没有一致的真值可分配。这类句子叫悖论 (paradox)，是形式化系统必须排除的对象（L13 会看到这背后是哥德尔式自指的力量）。
• “真实但未知”仍是命题：命题的定义只要求真值存在，不要求我们已知。例如”$\pi$ 的十进制展开中数字 $7$ 出现无穷多次”是命题（真值确定，虽然至今无人证明），而”$7$ 出现了很多次”不是命题（”很多”模糊）。

逻辑联结词：与 / 或 / 非

设 $P, Q$ 是代表命题的变量（例如 $P$ 表示”$3$ 是奇数”）。含变量的这类表达式叫命题形式 (propositional form)。

• 合取 (Conjunction)：$P \wedge Q$（”$P$ 且 $Q$”）—— 仅当 $P$ 与 $Q$ 都真时为真。
• 析取 (Disjunction)：$P \vee Q$（”$P$ 或 $Q$”）—— 只要 $P$ 与 $Q$ 至少一个为真就为真。注意这是包含式或 (inclusive or)：$P$ 和 $Q$ 都真时 $P \vee Q$ 也为真，与日常语言中”要汤还是沙拉”的排他式或不同。数学与计算机中的”或”一律是包含式的（C/Java 的 \|\|、Python 的 or 都是）。
• 否定 (Negation)：$\neg P$（”非 $P$”）—— $P$ 为假时为真。
• 真值表 (Truth table)：列出所有输入组合与对应输出。这和函数表完全一样，只是变量取布尔值。$n$ 个变量的真值表有 $2^n$ 行。
• 排中律 (law of the excluded middle)：对任何命题 $P$，要么 $P$ 真，要么 $\neg P$ 真，没有第三种可能。因此 $P \vee \neg P$ 恒真。
• 重言式 (tautology) 与矛盾式 (contradiction)：无论变量取何真值组合都为真的命题形式叫重言式（如 $P \vee \neg P$）；恒假的叫矛盾式（如 $P \wedge \neg P$）。注意 $P \wedge \neg P$ 永假不是因为 $P$ 特殊，而是因为在任何一行里 $P$ 与 $\neg P$ 必然一真一假，合取就必然有一个假。
• 具体示例：令 $P$ 表示”$3$ 是奇数”（T），$Q$ 表示”$4$ 是奇数”（F），$R$ 表示”$4+5=49$”（F）。则 $P \wedge R = \text{T} \wedge \text{F} = \mathbf{F}$；$P \vee R = \text{T} \vee \text{F} = \mathbf{T}$；$\neg Q = \neg \text{F} = \mathbf{T}$。

完整真值表（本讲第一个必背 ASCII 表）

  基本联结词真值表 (四个输入行 = 所有可能)
  =====================================================================
    P   Q  ||  P ∧ Q  |  P ∨ Q  |  P =⇒ Q  |  P ⇐⇒ Q  |  ¬P
  ==========++=========+=========+==========+==========+======
    T   T  ||    T    |    T    |    T     |    T     |   F
    T   F  ||    F    |    T    |    F     |    F     |   F
    F   T  ||    F    |    T    |    T     |    F     |   T
    F   F  ||    F    |    F    |    T     |    T     |   T
  =====================================================================
    ∧ : 全真才真 (AND, 交集思维)      ⇒ : 只有 T→F 那行为假 (最反直觉)
    ∨ : 有真就真 (OR, 并集思维)       ⇐⇒ : 两列同值才真 (等价 / 同真同假)
    ¬ : 取反                          ¬(P ∨ Q) 见下方德摩根定律
  =====================================================================
  读法速记:  ∧ 像乘法(0 吸收),  ∨ 像加法(1 吸收),  ¬ 是 1-x
          T=1, F=0 时:  P∧Q = P*Q,  P∨Q = P+Q-P*Q,  ¬P = 1-P

蕴涵 (Implication)：$P \Rightarrow Q$

• 定义：$P \Rightarrow Q$ 读作”$P$ 蕴涵 $Q$”“若 $P$ 则 $Q$”。”$P \Rightarrow Q$ 为假，当且仅当 $P$ 真而 $Q$ 假“，其余三行全为真。$P$ 叫前件 / 假设 (hypothesis / antecedent)，$Q$ 叫后件 / 结论 (conclusion / consequent)。
• 直观解释（”它是什么意思？”）：$P \Rightarrow Q$ 不是”断言 $P$ 成立”，而是一条”承诺”：”只要 $P$ 成立，$Q$ 就一定成立。”要”毁约”必须真的出现”$P$ 成立但 $Q$ 不成立”的情形；如果你从未让 $P$ 成立（前件为假），那这条承诺根本没有被触发，谈不上违约，于是它算”守住了”。
• 日常类比：
  • “如果你站在雨里，你就会淋湿。” 这句话唯一的假情形是”你站在雨里却没淋湿”。
  • “如果你通过了这门课，你会拿到证书。” 唯一的假情形是”通过了却没拿到证书”；如果你根本没通过，无论拿没拿到证书，这句话都不算假。
  • 反面类比（说明$P\Rightarrow Q$ 与因果无关）：”若 $1+1=3$，则月亮是奶酪做的”在数学上也是真的 —— 数学只看真值组合，不追究”因果机制”。
• 空洞真 (vacuously true)：当前件 $P$ 为假时，整个蕴涵为真，这种”白白为真”的情形叫空洞真。因此下列句子在数学上都是真命题（虽然说起来荒唐）：
  • “如果猪会飞，那么马会读书。”（前件假 ⇒ 真）
  • “如果 $14$ 是奇数，那么 $1+2=18$。”（$14$ 是偶数 ⇒ 前件假 ⇒ 真）
  • “如果 $4$ 是奇数，那么 $3$ 是奇数。”（$4$ 是奇数 $\Rightarrow$ $3$ 是奇数）—— 前件假，故为真。
• 具体示例：令 $P$ = “$3$ 是奇数”（T），$Q$ = “$4$ 是奇数”（F），$R$ = “$6$ 是偶数”（T）。则 $P \Rightarrow R$ 为 T（T 蕴涵 T）；$Q \Rightarrow P$ 为 T（空洞真，因为 $Q$ 假）；$R \Rightarrow P$ 为 T。又因为 $P \Rightarrow R$ 与 $R \Rightarrow P$ 都真，所以 $P \iff R$ 为 T。
• $(P \Rightarrow Q) \equiv (\neg P \vee Q)$：把真值表最后两列一比即可看出二者每一行都相同。这个等价式是化简/计算蕴涵的”工程手册”：把蕴涵翻译成”或”，就能直接用德摩根定律等工具处理。它的直观读法是：”要么前件不成立，要么后件成立 —— 反正不许出现’前件成立而后件不成立’。”
• 同一个蕴涵的六种说法（数学题里全都会出现，必须能互相翻译）：

最容易读错的是”仅当”：”$P$ only if $Q$” 不是 $Q \Rightarrow P$，而是 $P \Rightarrow Q$。记忆法：only if 直接修饰后件 $Q$，意思是”$Q$ 是唯一允许的出口”，即”$P$ 成立时 $Q$ 必须成立”，也就是 $P \Rightarrow Q$。同理”$P$ 是充分条件”（有 $P$ 就够）与”$Q$ 是必要条件”（没 $Q$ 就不行）都是 $P \Rightarrow Q$ 的换装说法。

双条件 (Biconditional)：$P \iff Q$

• 定义：$P \iff Q$ 表示”$P$ 当且仅当 $Q$”（”$P$ iff $Q$”），定义为 $(P \Rightarrow Q) \wedge (Q \Rightarrow P)$。它当且仅当 $P$ 与 $Q$ 真值相同时为真。
• 直观解释：$P \iff Q$ 是”两句同生共死”：要么同真，要么同假。它是数学中”等价 (equivalent)”的正式写法，也是”当一个定理可以双向使用”的标志。
• 具体示例：$P$ = “$3$ 是奇数”（T），$R$ = “$6$ 是偶数”（T），二者真值相同，故 $P \iff R$ 为 T。（注意 $3$ 与 $6$ 之间没有因果关系，$P \iff R$ 只说二者真值一致。）
• 一个必须记住的等式：$P \iff Q \;\equiv\; (P \Rightarrow Q) \wedge (Q \Rightarrow P) \;\equiv\; (\neg P \vee Q) \wedge (\neg Q \vee P)$。这就是 L00 中”证等价要双向各证一次”的逻辑根据。

命题的三种”变体”：逆否 / 逆 / 否

给定蕴涵 $P \Rightarrow Q$：

• 直观解释：逆否是”把箭头掉头、并同时给两端都加否定”，两个动作互相抵消了信息，所以意思不变（”没淋湿 ⇒ 没站在雨里”与原句同义）。逆命题只掉头不加否定，凭空多要了一个承诺（”淋湿了 ⇒ 一定站在雨里”，可你有可能是被泼的）。否命题只加否定不掉头，同样是”换了话题”。
• 具体例子：原句”若你通过了这门课，则你收到了证书。”
  • 逆否：”若你没有收到证书，则你没有通过这门课。”（同义，真值相同）
  • 逆命题：”若你收到了证书，则你通过了这门课。”（不等价：可能有人拿到了参与证书却未通过）
  • 否命题：”若你没有通过这门课，则你没有收到证书。”（也不等价）
• 具体示例（数字版）：原命题”若 $n$ 能被 $4$ 整除，则 $n$ 是偶数”（真）。
  • 逆否：”若 $n$ 是奇数，则 $n$ 不能被 $4$ 整除”（真，与原命题等价）。
  • 逆命题：”若 $n$ 是偶数，则 $n$ 能被 $4$ 整除”（假，反例 $n = 2$：$2$ 是偶数但 $4 \nmid 2$；$n=6, 10$ 同理）。
  • 否命题：”若 $n$ 不能被 $4$ 整除，则 $n$ 是奇数“（假，同样反例 $n = 2$：前件真而结论假）。

德摩根定律 (De Morgan’s Laws)

• 定义：$\neg(P \wedge Q) \equiv (\neg P \vee \neg Q)$，$\neg(P \vee Q) \equiv (\neg P \wedge \neg Q)$。
• 直观解释（”为什么是反直觉的？”）：否定”两个都成立”不需要两个都失败 —— 只要有一个失败就够了（于是 $\vee$）；否定”至少一个成立”则需要两个都失败（于是 $\wedge$）。注意连接词翻转：$\wedge$ 与 $\vee$ 互换。 忘记翻转是学生最经典的错误之一。
• 日常类比（有画面感的版本）：”我周末既交作业又打扫房间”这个承诺被打破，只需要满足”没交作业”或“没打扫房间”其中之一，不需要两件都没做。反过来，我说”我周末会交作业或者打扫房间”，要证明我食言，你必须同时确认”作业没交”且“房间没扫”。
• 旧金山类比：$U$ = 全体居民。$A$ = “戴眼镜的人”，$B$ = “戴帽子的人”。$\overline{A \cup B}$（既不戴眼镜也不戴帽子）$= \overline{A} \cap \overline{B}$（不戴眼镜的人 与 不戴帽子的人 的交）✓。而 $\overline{A \cap B}$（不是”两者都戴”的人）$= \overline{A} \cup \overline{B}$（不戴眼镜的，或 不戴帽子的）✓ —— 一个”只戴眼镜”的居民证明了这个集合远大于“两样都不戴”的人。

逻辑等价式家族（分配律、结合律、交换律……）

这些定律让命题形式可以像代数式一样”化简”。下表中的每一条都用穷举真值表验算通过（$P,Q,R$ 的全部 $8$ 种组合）：

• 具体示例（用定律化简）：验证 $\neg(P \Rightarrow Q) \equiv P \wedge \neg Q$。

第一步用”蕴涵转或”，第二步用德摩根（注意 $\vee$ 翻成 $\wedge$），第三步用双重否定。结论很重要：否定一个蕴涵不得到蕴涵，而得到一个合取 —— “若 $P$ 则 $Q$”的反面是”$P$ 成立并且 $Q$ 不成立”（即”存在一个反例”），不是“若 $P$ 则非 $Q$”。这是本讲最值钱的一条改写。

谓词 (Predicate / Propositional Formula)

• 定义：含自由变量的陈述，代入具体值后成为命题，例如”$n^2+n+41$ 是质数”是含变量 $n$ 的谓词。记作 $P(n)$、$P(x,y)$。
• 直观解释：谓词是”命题的模板”或”布尔值函数”：$P : U \to \{\text{T}, \text{F}\}$。$P(1)$ 就是”$43$ 是质数”（T），$P(40)$ 就是”$1681$ 是质数”（F，因为 $1681 = 41^2$）。谓词本身没有真值，只有”在某个输入上的真值”。

量词 (Quantifiers)

• 定义：全称量词 (universal quantifier) $(\forall x \in U)\,P(x)$ 表示”对论域 $U$ 中的每一个 $x$，$P(x)$ 都成立”；存在量词 (existential quantifier) $(\exists x \in U)\,P(x)$ 表示”论域 $U$ 中至少存在一个 $x$ 使 $P(x)$ 成立”。论域 (universe) $U$ 是变量允许取值的集合，是量词命题的一部分（换论域可以改变真值）。论域明确时省略：$\exists x\,(x \text{ lays eggs})$。
• 直观解释：量词是把谓词”批量封口”的装置，也是为什么”$x^2 + 3x = 5$”不是命题而”$(\exists x \in \mathbb{R})(x^2+3x=5)$”是命题 —— 后者有一个明确的论域，且被量词封死了自由变量。
• “some” 在数学里就等于 “at least one”：”有些哺乳动物会下蛋”正式化为 $(\exists x \in \text{mammals})(x \text{ lays eggs})$。数学的”存在”不暗示稀有或唯一：只说至少一个。
• 无限论域下的重要限制：在有限论域 $U = \{1,2,3,4\}$ 下，

也就是说 $\exists$ = 一大堆 $\vee$，$\forall$ = 一大堆 $\wedge$。但在无限论域（如 $\mathbb{N}$、$\mathbb{Z}$）里，你无法写下无穷长的合取/析取式，量词就成了不可消除的基本装置。这一条对应关系是后面量词否定律的根源。

• 具体示例（”有界”与”无界”的分水岭，强烈建议背下来）：

• 具体示例（$U=\{1,2,3,4\}$ 上 $P(x) :=$ “$x^2 > 10$” 的四联对比）：

  量化命题与其否定在 U = {1,2,3,4} 上的真值  (P(x) := "x² > 10")
  ==================================================================
    x   |  x²  |  P(x)     ||  说明
   -----+------+-----------++--------------------------------------
    1   |  1   |   F       ||  P(1) 假  -->  这就是 ∀x P(x) 的反例
    2   |  4   |   F       ||
    3   |  9   |   F       ||
    4   | 16   |   T       ||  P(4) 真  -->  这就是 ∀x ¬P(x) 的反例
  ==================================================================
    ∃x P(x)        = T        (因为 P(4) 真)
    ∀x P(x)        = F        (因为 P(1) 假)
    ¬(∀x P(x))     = T        <==>  ∃x ¬P(x) = T   (P(1) 假)   一致 ✓
    ∀x ¬P(x)       = F        (因为 P(4) 真)
    ¬(∃x P(x))     = F        <==>  ∀x ¬P(x) = F                一致 ✓
  ==================================================================
   两对量词否定律在这个例子上都对上了; 下面给出一般证明。

嵌套量词：顺序不能交换

• 现象：$(\forall x)(\exists y)P(x,y)$ 与 $(\exists y)(\forall x)P(x,y)$ 是不同的命题，前者一般不蕴含后者。

• 直观解释（”同一个人 vs 每次不同的人”）：考虑

  • (A) $(\forall t \in T)(\exists p \in P)\;(\text{$p$ 在时刻 $t$ 被刺})$：每次我坐地铁，都有人被刺（可以是每次不同的人）。
  • (B) $(\exists p \in P)(\forall t \in T)\;(\text{$p$ 在时刻 $t$ 被刺})$：存在某个人 Joe，每次我坐地铁，都是 Joe 被刺。

  (B) 蕴含 (A)（若 Joe 每次都被刺，当然每次”有人”被刺），但 (A) 不蕴含 (B)（可能是轮流被刺的不同人）。(B) 是强得多的断言。

• 另一个直观解释（”每个人都有母亲” vs “有一个人是所有人的母亲”）：
  • $(\forall x \in \text{people})(\exists y \in \text{people})(\text{$y$ 是 $x$ 的母亲})$ —— 真：每个人都各自有一个母亲（母亲随 $x$ 变化）。
  • $(\exists y \in \text{people})(\forall x \in \text{people})(\text{$y$ 是 $x$ 的母亲})$ —— 假（荒谬）：要求存在一个人是所有人的母亲。
• 具体示例（数学版）：$(\forall x \in \mathbb{Z})(\exists y \in \mathbb{Z})(x < y)$ 为真（对每个 $x$ 取 $y = x+1$，”见证 $y$ 依赖 $x$”）；而 $(\exists y \in \mathbb{Z})(\forall x \in \mathbb{Z})(x < y)$ 为假（它等价于”存在最大整数”，但不存在）。判据：若 $\exists$ 在内层，那么见证对象 $y$ 通常依赖于外层的 $x$；一旦把 $\exists$ 提到外层，$y$ 就必须”一次性对所有 $x$ 生效”，这是一个严苛得多的要求。
• 注意 $\exists\forall \Rightarrow \forall\exists$ 是单向的：$(\exists y)(\forall x)P(x,y) \Rightarrow (\forall x)(\exists y)P(x,y)$ 恒真（同一个 $y$ 通吃所有 $x$，当然对每个 $x$ 也存在这样的 $y$）；反过来不成立。上面”母亲”的例子就是这个单向箭头的最好注解：$\exists\forall$ 假而 $\forall\exists$ 真。

“至少 / 至多 / 恰好”三个数量的量化写法

• 至少三个不同的 $x$ 满足 $P$（论域 $\mathbb{Z}$）：

四个条件缺一不可：三个不等式保证互不相同，三个 $P(\cdot)$ 保证都满足。

• 至多三个不同的 $x$ 满足 $P$，写法一：

读作”存在三个候选者 $x,y,z$，使得任何满足 $P$ 的 $d$ 都必是其中之一”。（注意这里没要求 $x,y,z$ 互异：如果实际只有 $2$ 个解，我们可以让 $x = y$ 来”凑数”。）

• 至多三个，写法二（等价的”反证式”表达）：

读作”任取四个两两不同的数，它们不可能全都满足 $P$”。这个写法完全等价，但它把”至多”说成了”不存在四个互异解”，并且已经用上了本讲的改写技巧 $\neg(P \wedge Q \wedge R \wedge S) \equiv \neg P \vee \neg Q \vee \neg R \vee \neg S$（德摩根推广）。

• 恰好三个：把”至少三个”且“至多三个”两个式子用 $\wedge$ 连起来即可。这是”恰好 = 至少 + 至多”的标准套路，在 L14 计数中会反复出现。
• 具体示例：$U = \{1,2,3\}$，$P(x) :=$ “$x$ 是奇数”。$U$ 中奇数有 $1, 3$ 两个。故”至少三个互异奇数”为假（个数 $2 < 3$）；”至多三个”为真（个数 $2 \le 3$）；”恰好三个”为假。再把 $U$ 换成 $\{1,2,3,5\}$：奇数 $1,3,5$ 共三个，于是”至少三个”真、”至多三个”真、”恰好三个”真。

完整证明与推导（核心）

定理 1.1（德摩根定律，真值表证明）：对任意命题 $P, Q$，

证明策略：真值表证明 (proof by truth table)。命题形式的逻辑等价就是”真值表逐行相同”，而变量只有 $P,Q$ 两个，共 $2^2 = 4$ 种取值组合，穷举即可。为什么选这个策略？ 因为逻辑等价的定义本身就是”对所有真值指派，两边的值相同”，而这里真值指派只有有限多种。要小心的是：这种”穷举证明”只适用于变量个数有限的情形 —— 一旦出现量词（如 $\forall x$），论域可能无限，真值表就失效了（这正是量词否定律需要”逻辑论证 + 语义论证”而非真值表的原因）。

逐步推导（第一定律 $\neg(P\wedge Q) \equiv \neg P \vee \neg Q$）：

  定理 (第一德摩根律)  ¬(P ∧ Q) ≡ (¬P ∨ ¬Q)
  =======================================================================
   行 |  P  |  Q  |  P∧Q  | ¬(P∧Q)  ||  ¬P  |  ¬Q  | ¬P∨¬Q  | 两侧相同?
  ====+=====+=====+=======+=========++======+======+========+============
    1 |  T  |  T  |   T   |    F    ||  F   |  F   |   F    |    ✓
    2 |  T  |  F  |   F   |    T    ||  F   |  T   |   T    |    ✓
    3 |  F  |  T  |   F   |    T    ||  T   |  F   |   T    |    ✓
    4 |  F  |  F  |   F   |    T    ||  T   |  T   |   T    |    ✓
  =======================================================================
   第 5 列 (¬(P∧Q)) 与第 8 列 (¬P∨¬Q) 在全部 4 行都相同
   ==> 由逻辑等价的定义, 两式逻辑等价  ∎
  =======================================================================
  观察: P∧Q 只在第 1 行为真, 故 ¬(P∧Q) 只在第 1 行为假;
         ¬P∨¬Q 也只在第 1 行为假 (那时 ¬P=¬Q=F)。
        "唯一的假行"重合  ==> 等价。

逐步推导（第二定律 $\neg(P\vee Q) \equiv \neg P \wedge \neg Q$）：

  定理 (第二德摩根律)  ¬(P ∨ Q) ≡ (¬P ∧ ¬Q)
  =======================================================================
   行 |  P  |  Q  |  P∨Q  | ¬(P∨Q)  ||  ¬P  |  ¬Q  | ¬P∧¬Q  | 两侧相同?
  ====+=====+=====+=======+=========++======+======+========+============
    1 |  T  |  T  |   T   |    F    ||  F   |  F   |   F    |    ✓
    2 |  T  |  F  |   T   |    F    ||  F   |  T   |   F    |    ✓
    3 |  F  |  T  |   T   |    F    ||  T   |  F   |   F    |    ✓
    4 |  F  |  F  |   F   |    T    ||  T   |  T   |   T    |    ✓
  =======================================================================
   第 5 列与第 8 列在全部 4 行相同  ==>  逻辑等价  ∎
  观察: P∨Q 只在第 4 行为假, 故 ¬(P∨Q) 只在第 4 行为真;
         ¬P∧¬Q 也只在第 4 行为真。 两边"唯一的真行"重合。

（推广版，三个变量）：$\neg(P \wedge Q \wedge R) \equiv \neg P \vee \neg Q \vee \neg R$。证明只需把 $Q \wedge R$ 当作一个整体先用一次第一定律，再用结合律与一次第一定律：

【证明机制解说】：德摩根定律的”机制”是一个双重翻转：$\neg$ 进入括号时，(i) 把 $\wedge$ 与 $\vee$ 互换，(ii) 给每个原子命题分别加 $\neg$。为什么必然互换？因为”全部成立”的失效条件是”有任一失败”（$\wedge \to \vee$），而”存在成立”的失效条件是”全部失败”（$\vee \to \wedge$）。记忆口诀：否定进门，与或换位，逐个加非。 后面的量词否定律是这同一条口诀的”量词版”：把 $\forall$ 看成广义 $\wedge$、$\exists$ 看成广义 $\vee$，则 $\neg\forall$ 变成 $\exists\neg$，$\neg\exists$ 变成 $\forall\neg$ —— 形式完全相同。

定理 1.2（量词否定律）：设 $P(x)$ 是论域 $U$ 上的谓词，则

证明策略：语义论证 (semantic argument)，必要时对有限论域再用真值表/逻辑等价做穷举验证。理由是：真值表证明要求变量取值有限，而 $U$ 可能是无限的（$\mathbb{Z}$、$\mathbb{N}$），所以必须给出一般论证。一般论证的骨架是双重否定 + 排中律：命题”$\neg(\forall x)P(x)$”为真 $\iff$ “$(\forall x)P(x)$”为假 $\iff$ 不是所有 $x$ 都满足 $P$ $\iff$ 至少有一个 $x$ 不满足 $\iff$ $(\exists x)\neg P(x)$。

逐步推导（以第一式为例，走”双向因此等价”）：

1. 方向 $\Rightarrow$：假设 $\neg\bigl(\forall x \in U\bigr)P(x)$ 为真，即”并非所有 $x$ 都满足 $P$”。（依据：排中律）对任意给定的 $x$，$P(x)$ 要么真要么假；既然”所有 $x$ 都满足 $P$”是假的，那么不可能每个 $x$ 都满足 $P$。因此至少存在某个 $x$ 使 $P(x)$ 为假，即 $\neg P(x)$ 为真。所以 $\bigl(\exists x \in U\bigr)\neg P(x)$ 为真。
2. 方向 $\Leftarrow$：假设 $\bigl(\exists x \in U\bigr)\neg P(x)$ 为真，取定这样一个 $x_0$，则 $P(x_0)$ 为假。（依据：全称量词的定义）若 $(\forall x)P(x)$ 为真，则特别地 $P(x_0)$ 应为真，与上一步矛盾。故 $\neg\bigl(\forall x)P(x)$ 为真。
3. 两个方向都成立，故二者逻辑等价。第二式同法（对偶地交换 $\forall/\exists$ 与”真/假”的角色）。$\blacksquare$

有限论域上的穷举验证（把 $U = \{1,2,3,4\}$、$P(x) :=$ “$x^2>10$” 代入）：

第四行与第三行相同、第六行与第五行相同 —— 定律在具体例子上完全对上 ✓。

逐步推导（”$\neg$ 往内推”的机械过程，多重量词）：设 $P(x,y)$ 是二元谓词，要把 $\neg(\forall x)(\exists y)P(x,y)$ 的否定推到底：

注意量词在每一步都”翻转”：$\forall \to \exists$、$\exists \to \forall$。这个”逐个吃进去”的策略把复杂否定拆成小步 —— 每次只处理最外层的一个量词。

具体示例（”所有质数都是奇数”的否定，本讲必考类型）：

• 原命题：$(\forall p \in \text{Primes})(p \text{ 是奇数})$。形式化：$(\forall p)\bigl(\text{Prime}(p) \Rightarrow \text{Odd}(p)\bigr)$。
• 否定（机械推）：

关键一步用的是定理 1.1 附近的改写 $\neg(P \Rightarrow Q) \equiv P \wedge \neg Q$ —— 否定穿过蕴涵不会留下蕴涵。

• 自然语言读法：”存在一个质数，它不是奇数”（即”存在偶质数”）。
• 真值：由于 $p = 2$ 是质数且为偶数，这个否定命题是真的，所以原命题”所有质数都是奇数”是假的。反例只有 $2$ 一个（$2$ 是唯一的偶质数）。
• 对照最常见的错误写法：$(\forall p)(\text{Prime}(p) \Rightarrow \neg\,\text{Odd}(p))$，读作”所有质数都是偶数”—— 这不是原命题的否定（原命题假而它也是假，二者不对立）。错误根源：忘记”否定蕴涵得到合取”。

另一个例子（”每个偶数 $n$ 都使 $n^2+n+41$ 为质数”的否定）：

• 原命题：$(\forall n \in \mathbb{Z})\bigl(\text{Even}(n) \Rightarrow \text{Prime}(n^2+n+41)\bigr)$。
• 否定：$(\exists n \in \mathbb{Z})\bigl(\text{Even}(n) \wedge \neg\,\text{Prime}(n^2+n+41)\bigr)$，即”存在一个偶数 $n$ 使 $n^2+n+41$ 是合数”。
• 真值：真，取 $n = 40$（偶数）：$40^2+40+41 = 1681 = 41^2$ 是合数。故原命题为假。这正是 L00 那个”证据陷阱”的正式化写法 —— 它的否定就是”存在反例”。

定理 1.3（逆否律 / Contrapositive）：对任意命题 $P, Q$，$(P \Rightarrow Q) \equiv (\neg Q \Rightarrow \neg P)$。

证明策略：真值表证明（也可用逻辑等价链）。这里两种都展示，因为真值表给出”确信”，等价链给出”为什么”。

逐步推导（真值表）：

  定理 (逆否律)  (P ⇒ Q) ≡ (¬Q ⇒ ¬P)   附: 顺带看逆命题/否命题为何不等价
  ==================================================================================
   行 |  P  |  Q  | P⇒Q | Q⇒P | ¬P⇒¬Q | ¬Q⇒¬P || P⇐⇒Q | 备注
  ====+=====+=====+=====+=====+=======+=======++======+==============================
    1 |  T  |  T  |  T  |  T  |   T   |   T   ||   T  | 都真
    2 |  T  |  F  |  F  |  T  |   T   |   F   ||   F  | 唯一"原命题为假"的行
    3 |  F  |  T  |  T  |  F  |   F   |   T   ||   F  | 原命题空洞真; 逆命题假
    4 |  F  |  F  |  T  |  T  |   T   |   T   ||   T  | 都空洞真
  ==================================================================================
   第 4 列 (P⇒Q)  与第 7 列 (¬Q⇒¬P) 逐行相同      ==> 逻辑等价 ✓
   第 4 列 (P⇒Q)  与第 5 列 (Q⇒P)   第2,3行不同  ==> 不等价 ✗
   第 4 列 (P⇒Q)  与第 6 列 (¬P⇒¬Q) 第2,3行不同  ==> 不等价 ✗
  ==================================================================================
   记忆: 逆否 = "掉头 + 双否定", 两个动作相互抵消 ==> 等价
         逆   = "只掉头"                        ==> 换了个命题
         否   = "只否定"                        ==> 也换了个命题
  ==================================================================================

逐步推导（逻辑等价链，只用已证定律）：

四步的依据依次是：蕴涵转或；$\vee$ 交换律；双重否定 $\neg(\neg Q)\equiv Q$；蕴涵转或（反向读）。整条链条每一步都是等价，所以可以正向、反向随便读 —— 这就是”逆否证明合法”的严格理由。

【证明机制解说】：逆否律的深层含义是：$P \Rightarrow Q$ 其实是一个关于”禁止某个组合”的声明：它禁止”$P$ 真 $Q$ 假”。$\neg Q \Rightarrow \neg P$ 禁止的组合是”$\neg Q$ 真 $\neg P$ 假”，即”$Q$ 假 $P$ 真” —— 同一条禁令的两种说法。所以二者当然等价。反观逆命题 $Q \Rightarrow P$，它禁止的是”$Q$ 真 $P$ 假”，这是另一条禁令；否命题 $\neg P \Rightarrow \neg Q$ 禁止”$P$ 假 $Q$ 真”，这又是第三条。一个蕴涵只对应一条禁令，逆否是它的同义改写，而逆/否是别的禁令，因此可能一真一假。真值表第 2、3 行就是这两种情况的”活标本”：第 2 行 $P$ 真 $Q$ 假使原命题假而逆命题真；第 3 行 $P$ 假 $Q$ 真使原命题真而逆命题假。

反例（条件不可省：把”逆否等价”误用成”逆等价”）：设 $P(n)$ = “$4 \mid n$”，$Q(n)$ = “$2 \mid n$”。

• 原命题 $(\forall n \in \mathbb{Z}^+)(P(n) \Rightarrow Q(n))$：若 $4 \mid n$ 则 $2 \mid n$ —— 真（$n = 4k = 2(2k)$，而 $2k \in \mathbb{Z}$；这就是 L00 定理 0.1 的推论 0.2）。
• 逆否命题 $(\forall n)(\neg Q(n) \Rightarrow \neg P(n))$：若 $n$ 是奇数则 $4 \nmid n$ —— 真（奇数不可能被 $4$ 整除），与原命题等价 ✓。
• 逆命题 $(\forall n)(Q(n) \Rightarrow P(n))$：若 $n$ 是偶数则 $4 \mid n$ —— 假，反例 $n = 2$（$2$ 是偶数，$4 \nmid 2$）。$n = 6, 10$ 同样是反例。
• 否命题 $(\forall n)(\neg P(n) \Rightarrow \neg Q(n))$：若 $4 \nmid n$ 则 $n$ 是奇数 —— 假，同一批反例 $n = 2, 6, 10$。

为什么这个反例值得记住：它证明”$P \Rightarrow Q$ 为真”完全不蕴含 “$Q \Rightarrow P$ 为真”。所以当你证完一个定理，你不能顺手把结论当条件用。反过来，只有当你打算用逆否证明时，你才有资格把 $P \Rightarrow Q$ 替换成 $\neg Q \Rightarrow \neg P$ —— 因为那是被真值表逐行验证过的等价，而不是”想当然掉头”。

与经典问题的联系

（1）逻辑等价改写的工业价值：形式验证与 SAT 求解器

定理 1.1 的德摩根定律、$\neg(P\Rightarrow Q) \equiv P \wedge \neg Q$、量词否定律，是自动定理证明与 SAT/SMT 求解器的”编译规则”。任何硬件电路规范都要先被翻译成布尔公式，再用否定范式 (NNF, negation normal form) 或 合取范式 (CNF) 化简；把 $\neg$ 推到原子命题上的过程，用的就是本讲的改写规则（沿途把 $\wedge/\vee$ 互换、把 $\forall/\exists$ 翻转）。工业界验证 CPU 流水线、缓存一致性协议、甚至密码协议实现时，前端做的第一件事就是把规范否定掉，然后交给 SAT 求解器搜索一个满足赋值的”反例”（counterexample）—— 这正好就是本讲”否定一个全称命题 = 断言存在反例”的机械化版本。本讲和 L00 强调的”一个反例推翻全称命题”在这里变成了一个可执行的算法。

（2）$P \Rightarrow Q \equiv \neg P \vee Q$：把蕴涵变成算术

取 $\text{T}=1, \text{F}=0$，则 $\wedge$ 变成乘法、$\neg P$ 变成 $1-P$，于是

这个从布尔到整数的翻译（把”与”当乘法、”非”当 $1-x$）是 代数正规形 (ANF, algebraic normal form) 与 布尔多项式 的起点。密码学里把 S 盒（S-box）表示成 $\mathbb{F}_2$ 上的多项式，靠的就是这个”布尔 = 模 $2$ 算术”的视角。而一旦进入模 $2$ 的世界，你就已经站在 L04 模运算的门口了：$P \vee Q$ 在 $\mathbb{F}_2$ 上写成 $P + Q + PQ$，$P \oplus Q$（异或）写成 $P+Q$。

（3）真值表 + 穷举：所有”穷举验证”的原型

定理 1.1 的证明方式是”$2^2 = 4$ 行全部检查”。这个思路的规模化就是模型检验 (model checking)：状态空间有限时（例如一个 $32$ 位寄存器的取值空间虽大但有限），系统地枚举所有状态以验证性质。L14 的计数工具正是用来估计状态空间大小的 —— 若变量个数是 $n$，真值表有 $2^n$ 行；这解释了为什么”暴力穷举逻辑”在 $n$ 大时会爆炸（组合爆炸），也解释了为什么我们需要更聪明的证明技巧（L02 的逆否、反证，L03 的归纳，L04 以后的数论结构）。“有限可以穷举、无限必须推理”是本讲与 L00 共享的主旋律。

（4）量词与数据库/程序规范

程序的后置条件通常是量词命题，例如”对每一个输入 $x$，输出 $y$ 都满足 $y^2 \le x < (y+1)^2$”。当测试发现”程序不满足规范”时，规范的否定给出了失败的形状：$(\exists x)\,\neg(\cdots)$，即”存在某个输入使输出不满足条件” —— 这个 $x$ 就是调试时你要找的最小反例 (minimal counterexample)。把”测试失败”翻译成规范的否定式，是写正确测试用例的第一步。同时注意：量词顺序在规范里是承重的。”对每个请求，存在一个服务器处理它”（$O(1)$ 负载均衡的目标形态）与”存在一个服务器处理所有请求”是完全不同的保证 —— 后者是灾难，前者是正常。这个区分在 L20 讲哈希与负载均衡（balls-in-bins）时会被反复使用。

（5）逆否与”证明不存在”

逆否律给了我们一种把”不存在”命题改写成”存在”命题的入口（或反过来）。L00 提到证明”某物不存在”很难；L02 会系统利用 $\neg Q \Rightarrow \neg P$ 来绕开这种困难：想证”$n$ 是奇数 $\Rightarrow$ $d$ 是奇数”，改证”$d$ 是偶数 $\Rightarrow$ $n$ 是偶数”，后者是构造性的（把倍数显式写出来）。而 L13 的停机问题本质上是在证明”不存在能判定停机的程序”，其反证结构的最后一步就是本讲这个改写：把”对所有程序 $P$ 都有……”的否定翻译成”存在一个程序 $P$ 使……不成立”。

与其他讲次的关联

• L00（Direct Proofs，直接证明）：L00 的每一条定理陈述都用到了本讲的蕴涵。L00 反复强调的”原命题与逆命题不等价”在本讲被真值表逐行坐实：表中第 2、3 行给出 $P \Rightarrow Q$ 与 $Q \Rightarrow P$ 真值不同的两行。同时 L00 定理 0.4 的集合等式 $A \cup (B\cap C) = (A\cup B) \cap (A\cup C)$ 正是本讲逻辑分配律 $P \vee (Q\wedge R) \equiv (P\vee Q) \wedge (P\vee R)$ 的集合版本，而集合差恒等式 $A\setminus(B\cup C) = (A\setminus B)\cap(A\setminus C)$ 就是德摩根第二定律。
• L02（Proof Techniques II，逆否 / 反证 / 分情形 / 鸽笼）：本讲的逆否律是 L02 整个”逆否证明”技巧的许可证。L02 的第一个例子”若 $n$ 是奇数且 $d \mid n$，则 $d$ 是奇数”就是改成逆否”若 $d$ 是偶数则 $n$ 是偶数”来证的。L02 的反证法还要用到本讲的排中律（”若命题不假则必真”）与 $\neg(P \Rightarrow Q) \equiv P \wedge \neg Q$（反证时假设的是”前提成立且结论不成立”）。没有本讲的改写规则，L02 的全部技巧都无法表述。
• L03（Induction，归纳法）：归纳法的证明模板是 $(\forall n \in \mathbb{N})P(n)$，其”归纳步骤”本身是一个蕴涵 $P(n) \Rightarrow P(n+1)$。要理解”为什么只需证基础情形与归纳步骤就能覆盖无限多个 $n$”，必须先接受全称量词与蕴涵的组合语义。此外 L03 的一个常见失分点是”漏掉基础情形”，其逻辑本质就是：只有 $\forall n\,(P(n)\Rightarrow P(n+1))$ 而没有 $P(0)$，整个命题不成立（”$P(0)$ 是链条的第一环”）。
• L04（Modular Arithmetic，模运算）：本讲把 $\text{T}/\text{F}$ 映射到 $1/0$，并用 $P \vee Q = P + Q - PQ$ 说明”布尔运算在算术里长什么样”。L04 会把算术限制到模 $m$ 的世界，其中最重要的特例是模 $2$（$\mathbb{F}_2$）：此时 $P \vee Q \equiv P + Q + PQ$、$P \oplus Q \equiv P + Q \pmod 2$ —— 逻辑与模运算是同一件事的两种语言。L00 中”数字和 $\bmod 9$”的定理也会在此获得统一表述。
• L05–L06（Euclid/FLT/CRT → RSA）：RSA 的安全性论述大量依赖量词命题，例如”不存在（除非 $a \equiv 0 \pmod p$）使 $ax \equiv 0 \pmod p$ 的 $x$”。写这类命题的否定式（”假设存在这样的 $x$，导出矛盾”）就是在用本讲的量词否定律，其技术形态是 L02 的反证法。
• L13（Computability，可计算性与停机问题）：停机问题的陈述”$(\forall P, x)$，判定器 $H$ 都输出正确答案”被否定后变成”$(\exists P, x)$ 使 $H$ 给出错误答案”，然后通过对角线构造造出那个反例。这个”否定全称命题 → 寻找反例 → 构造反例”的三步，就是本讲量词否定律的最深刻应用。
• L20（Expectations & Linearity，期望与线性性）：L20 中用期望线性性分析 balls-in-bins 负载均衡时，关键论证是”对每个球，都存在很多箱可选”（$\forall$ 球 $\exists$ 空箱）与”存在一个球落在某个箱”的区分 —— 这类规范的正确表述完全依赖本讲对量词顺序的敏感度训练。

关键要点

1. 命题五联表必须默写：$\wedge$ 全真才真、$\vee$ 有真就真、$\neg$ 取反、$\Rightarrow$ 只在 T→F 时为假、$\iff$ 同值才真。记住：$\Rightarrow$ 的四行中有三行是真的，”假”只留给”前件真后件假”这一种情形。前件为假时整个蕴涵空洞真 (vacuously true) —— 这不是数学家的怪癖，而是”承诺未被触发即未违约”的语义必然。
2. 两个”翻译键”必须刻进肌肉记忆：$P \Rightarrow Q \equiv \neg P \vee Q$（把蕴涵变成或），$\neg(P \Rightarrow Q) \equiv P \wedge \neg Q$（否定蕴涵得到合取，即”存在反例”）。前者用于化简，后者用于反证与量词否定。绝不把 $\neg(P\Rightarrow Q)$ 写成 $P \Rightarrow \neg Q$。
3. 三种变体的地位完全不同：逆否 $\neg Q \Rightarrow \neg P$ 与原命题等价（放心把证明改成逆否来写）；逆 $Q \Rightarrow P$ 与否 $\neg P \Rightarrow \neg Q$ 与原命题不等价（各自是另一个命题，可能一真一假）。数值记忆：原命题”$4 \mid n \Rightarrow 2 \mid n$”真，而逆命题”$2 \mid n \Rightarrow 4 \mid n$”假（$n=2$）。
4. 德摩根口诀：否定进门，与或换位，逐个加非。 $\neg(P\wedge Q)\equiv\neg P\vee\neg Q$，$\neg(P\vee Q)\equiv\neg P\wedge\neg Q$。同一口诀的量词版：$\neg\forall x\,P(x)\equiv\exists x\,\neg P(x)$、$\neg\exists x\,P(x)\equiv\forall x\,\neg P(x)$ —— 量词必须翻转，而”$\neg(\forall x)(P(x)\Rightarrow Q(x))$”的正确否定是”$(\exists x)(P(x)\wedge\neg Q(x))$”（一个反例：前提真、结论假）。
5. 量词顺序是承重的：$(\forall x)(\exists y)$ 一般不能换成 $(\exists y)(\forall x)$。前者允许”见证 $y$ 依赖 $x$”（每个人各自有母亲 —— 真），后者要求”一个 $y$ 通吃所有 $x$”（一个人是所有人的母亲 —— 假）。反向的单向箭头 $(\exists y)(\forall x) \Rightarrow (\forall x)(\exists y)$ 恒成立。

常见误区与注意事项

1. 把”或”当排他式。 数学与编程里的 $\vee$ 是包含式：$P$ 和 $Q$ 都真时 $P \vee Q$ 仍为真。若真要表达”二者恰有其一”，必须写 $(P \vee Q) \wedge \neg(P \wedge Q)$（即异或 $P \oplus Q$）。
2. 把”$P$ only if $Q$”读成 $Q \Rightarrow P$。 正确翻译是 $P \Rightarrow Q$。同理”$P$ 是 $Q$ 的充分条件”与”$Q$ 是 $P$ 的必要条件”都是 $P \Rightarrow Q$；只有”$P$ 是 $Q$ 的必要条件”才是 $Q \Rightarrow P$。
3. 否定蕴涵时留下蕴涵。 把”所有质数都是奇数”的否定写成”所有质数都是偶数”（即 $(\forall p)(\text{Prime}(p)\Rightarrow\neg\text{Odd}(p))$），这是错的；正确否定是 $(\exists p)(\text{Prime}(p)\wedge\neg\text{Odd}(p))$，读作”存在一个非奇数的质数”，由 $p=2$ 使其为真。
4. 否定量词时不翻转，或只翻一部分。 $\neg(\forall x)(\exists y)P(x,y)$ 的正确形式是 $(\exists x)(\forall y)\neg P(x,y)$ —— 每一个量词都翻转，且 $\neg$ 推到最内层。只写 $(\exists x)(\exists y)\neg P(x,y)$ 或漏翻内层都是错的。
5. 混淆逆命题与逆否命题。 这是 CS70 最普遍的失分点。逆否要”掉头 且 两端都加否定”，逆命题”只掉头”。真值表上逆否与原命题逐行相同、逆命题在第 2、3 行不同 —— 背下这两行的位置比背口诀更可靠。
6. 在无限论域上滥用真值表证明。 “用真值表证明量词否定律”严格来说只对有限论域有效（把 $\forall$ 展开成有限个 $\wedge$）。要证一般情形必须给出本讲定理 1.2 那样的语义论证（用排中律与量词定义）。真值表证明的适用范围是有限变量，不是”任何逻辑命题”。
7. 忘记论域 (universe) 是量词命题的一部分。 $(\forall x)(x^2 \ge x)$ 在 $\mathbb{Z}$ 上为真，但在 $\mathbb{R}$ 上为假（取 $x = 0.5$：$0.25 < 0.5$）。论域变了，真值就变了 —— 写命题时论域必须明确（或由上下文无歧义地确定）。

思考题（带答案）

Q1.（计算 / 真值表） 令 $P$ 表示”$3$ 是奇数”（T），$Q$ 表示”$4$ 是奇数”（F），$R$ 表示”$4+5=49$”（F）。求下列各式的真值，并说明用到的规则：(a) $P \wedge R$；(b) $P \vee R$；(c) $\neg Q$；(d) $Q \Rightarrow P$；(e) $\neg(P \Rightarrow R)$；(f) $(P \vee Q) \wedge \neg(P \wedge Q)$。

Q2.（量词与否定） (a) 把”存在一个整数 $k$ 既不是偶数也不是奇数”用符号写出，并判断真假（论域 $\mathbb{Z}$）。(b) 写出”所有质数都是奇数”的否定，用符号与自然语言两种形式，并给出反例。(c) 判断 $(\forall x \in \mathbb{Z})(\exists y \in \mathbb{Z})(y > x)$ 与 $(\exists y \in \mathbb{Z})(\forall x \in \mathbb{Z})(y > x)$ 的真假，说明二者为何不同。

Q3.（证明与反例） (a) 用逻辑等价链证明 $\neg(P \iff Q) \equiv (P \wedge \neg Q) \vee (\neg P \wedge Q)$。(b) 设 $P(n)$ = “$4 \mid n$”，$Q(n)$ = “$2 \mid n$”，对 $n = 2$ 与 $n = 4$ 分别列出原命题、逆命题、否命题、逆否命题的真值，并指出哪些与原命题一致（$n$ 为整数）。(c) 为什么”用真值表证明量词否定律”严格来说不够？给出一个论域使该做法失效。