CH1 逻辑与证明

1 命题逻辑

命题

1. 定义：命题是一个陈述语句，它或者为真或者为假，但不能不真不假。

2. 构造命题

   • 命题变元：$p, q, r, s$
   • 如果一个命题是真命题，它的真值为真，用 T 表示；如果它是假命题，它的真值为假，用 F 表示。

3. 复合命题

   • 非命题（否定命题）：$\neg p$
   • 合取命题：$p\wedge q$
   • 析取命题：$p \vee q$

   • 异或命题 ：$p \oplus q$，p 和 q 中至少有一个为真，但不同时为真

     在自然语言中，“或”字有两种不同的含义：

     • 兼或：$p \vee q$
     • 异或：$p \oplus q$

   • 蕴含命题 ：$p \to q$，当且仅当 p 真 q 假时，命题为假
   • 双向蕴含命题：$p \leftrightarrow q$， 当 p 和 q 有同样的真值时，命题为真，否则为假
   • 逆命题，逆否命题，反命题：$q\to p, \neg q \to \neg p, \neg p \to \neg q$
4. 复合命题的真值表
5. 等价命题：两个命题等价，当他们总是有相同的真值。

逻辑运算的优先级

2 命题逻辑的应用

1. 语句翻译
2. 系统规范说明
3. 逻辑谜题
4. 逻辑电路

3 命题等价式

重言式，矛盾式，可能式

• 永真式（重言式）：一个真值永远为真的复合命题，如 $p \vee \neg p$
• 矛盾式：一个真值永远为假的复合命题，如 $p \wedge \neg p$
• 可能式：既不是永真式，也不是矛盾式的复合命题，如 $\neg p$

逻辑等价式

1. 在所有情况下都有相同真值的两个复合命题 $p, q$，那么它们是逻辑等价的。

2. 常见的逻辑等价式

   • 结合律：$(p \wedge q) \wedge r \equiv p \wedge (q \wedge r)$ $(p \vee q) \vee r \equiv p \vee (q \vee r)$
   • 分配律：$p \vee (q \wedge r) \equiv (p \vee q) \wedge (p \vee r)$ $p \wedge (q \vee r) \equiv (p \wedge q) \vee (p \wedge r)$
   • 德摩根律：$\neg (p \vee q) \equiv \neg p \wedge \neg q$ $\neg (p \wedge q) \equiv \neg p \vee \neg q$
   • 吸收律：$p \vee (p \wedge q) \equiv p$ $p \wedge (p \vee q) \equiv p$

3. 条件命题的逻辑等价式

   • $\mathbf{p \to q \equiv \neg p \vee q}$
   • $\mathbf{p \to q \equiv \neg q \to \neg p}$
   • $p \vee q \equiv \neg p \to q$
   • $p \wedge q \equiv \neg ( p \to \neg q )$
   • $\neg (p \to q) \equiv p \wedge \neg q$
   • $(p \to q) \wedge (p \to r) \equiv p \to (q \wedge r)$
   • $(p \to r) \wedge (q \to r) \equiv (p \vee q) \to r$
   • $(p \to q) \vee (p \to r) \equiv p \to (q \vee r)$
   • $(p \to r) \vee (q \to r) \equiv (p \wedge q) \to r$

4. 双条件命题的逻辑等价式

   • $p \leftrightarrow q \equiv (p \to q) \wedge (q \to p)$
   • $p \leftrightarrow q \equiv \neg q \to \neg p$
   • $p \leftrightarrow q \equiv (p \wedge q) \vee (\neg p \wedge \neg q)$
   • $\neg (p \leftrightarrow q) \equiv p \leftrightarrow \neg q$

可满足性

一个复合命题称为可满足的，如果存在一个对其变元的真值赋值其为真。当不存在这样的赋值时，即复合命题对所有变元的真值赋值都是假，则复合命题称为不可满足的。

范式

范式是命题公式的规范形式，分为析取范式和合取范式。

1. 析取范式：命题公示 $A$ 等价写为 $A_1 \vee A_2 \ldots \vee A_n$，其中 $A_i(i=1, 2, \ldots, n)$是命题变元或其否定形式的合取式。

   合取范式：命题公示 $A$ 等价写为 $A_1 \wedge A_2 \ldots \wedge A_n$，其中 $A_i(i=1, 2, \ldots, n)$是命题变元或其否定形式的析取式。

2. 范式存在定理：任一命题公式都存在着与之等值的析取范式和合取范式，但析取范式和合取范式可能不是唯一的。

3. 极小项： n 个命题变元 $p_1, p_2, \ldots p_n$ 的合取式，其中每个命题变元必出现且仅出现一次（本身或者否定形式）。用 $m_i$ 表示第 i 个极小项，其中 i 是该极小项成真赋值的十进制表示。

   极大项：n 个命题变元 $p_1, p_2, \ldots p_n$ 的析取式，其中每个命题变元必出现且仅出现一次（本身或者否定形式）。用 $M_i$ 表示第 i 个极大项，其中 i 是该极大项成假赋值的十进制表示。

4. 主析取范式：若 一 个 命 题 公 式 的 析 取 范 式 为 $A_1 \vee A_2 \ldots \vee A_n$，其中 $A_i(i=1,2,\ldots,n)$ 是极小项，则称该公式为 A 的主析取范式。

   主合取范式：若 一 个 命 题 公 式 的 合 取 范 式 为 $A_1 \wedge A_2 \ldots \wedge A_n$，其中 $A_i(i=1,2,\ldots,n)$ 是极大项，则称该公式为 A 的主合取范式。

求含命题变项 $p_1, p_2, \ldots, p_n$ 的公式 A 的主析取范式/主合取范式的步骤：

1. 求 A 的析取范式/合取范式，由简单合取/析取式构成
2. 将简单合取/析取式展开
3. 消去重复出现的极小项/极大项
4. 将极小项/极大项按下标从小到大排列

4 谓词和量词

谓词逻辑

谓词逻辑包含以下新特征：

• 变量：$x, y, z$
• 谓词：$P(x), M(x)$
• 量词

命题函数

命题函数将变为命题（具有真值），当它的每个变量被由其域中的元素替换或者被量词约束。

量词

1. 量词

   • 全称量词：$\forall x P(x)$
   • 存在量词：$\exists x P(x)$
   • 唯一性量词：$\exists !xP(x)$ 或 $\exists_1 x P(x)$，存在一个唯一的 $x$ 使得 $P(x)$ 为真
2. 受限域的量词：$\forall_{x<0}(x^2>0)$
3. 量词的优先级：量词 $\exists$ 和 $\forall$ 的优先级高于所有的逻辑运算符.

4. 量化表达的否定

   • $\neg \forall x J(x) \equiv \exists x \neg J(x)$
   • $\neg \exists x J(x) \equiv \forall x \neg J(x)$

5 嵌套量词

1. 常见的四种嵌套量词：

   • $\forall x \forall y P(x, y)$
   • $\forall x \exists y P(x, y)$
   • $\exists x \forall y P(x, y)$
   • $\exists x \exists y P(x, y)$
2. 嵌套量词的顺序
3. 嵌套量词的否定

例：$\neg \exists w \forall a \exists f (P(w, f) \wedge Q(f, a)) \equiv \forall w \exists a \forall f (\neg P(w, f) \vee \neg Q(f, a))$

6 推理规则

论证

1. 有效论证
2. 命题逻辑中的论证：命题逻辑中的论证是一系列命题，除最终命题之外的所有命题都称为前提，最后的陈述是结论

命题逻辑的推理规则

1. 假言推理：$(p \wedge (p \to q)) \to q$
2. 取拒式：$(\neg q \wedge (p \to q)) \to \neg p$
3. 假言三段论：$((p\to q) \wedge (q \to r)) \to (p \to r)$
4. 析取三段论：$(\neg p \wedge (p \vee q)) \to q$
5. 附加律：$p \to (p \vee q)$
6. 化简律：$(p \wedge q) \to q$
7. 合取律：$((p) \wedge (q)) \to (p \wedge q)$
8. 消解律：$((p \vee q) \wedge (\neg p \vee r)) \to (q \vee r)$
9. 构造性二难推理：$((p \to q) \wedge (r \to s) \wedge (p \vee r)) \to (q \vee s)$
10. 破坏性二难推理：$((p \to q) \wedge (r \to s) \wedge (\neg q \vee \neg s)) \to (\neg p \vee \neg r)$

使用推理规则建立论证

使用推理规则建立论证，其中前提为 $A_1, A_2, \ldots , A_k$，结论为$B$，常用的构造证明的方法包括：

直接证明法

由前提 $A_1, A_2, \ldots , A_k$ 出发， 应用推理规则，推出 $B$

附加前提证明法

假设推理的形式结构为 $(A_1 \wedge A_2 \wedge \ldots \wedge A_k) \to (A \to B)$，证明的结论也为蕴含式，那么可以将结论中的前提 $A$ 也作为推理的前提，使结论为 $B$，即把推理的形式改写为：

$$ (A_1 \wedge A_2 \wedge \ldots \wedge A_k \wedge A) \to B $$

归谬法

假设推理的形式结构为 $(A_1 \wedge A_2 \wedge \ldots \wedge A_k) \to (A \to B)$，那么可以将结论的 $B$ 的否定作为推理的前提，推出矛盾，则说明推理正确。

量化命题的推理规则

1. 全称实例：从给定前提 $\forall x P(x)$ 得出 $P(c)$ 为真的推理规则，其中 $c$ 是论域里的一个特定成员。

$$ \forall xP(x) \to P(c) $$

2. 全称引入：对论域里所有元素 $c$ 都有 $P(c)$ 为真的前提，推出 $\forall x P(x)$ 为真。

$$ P(c), 任意c \to \forall x P(x) $$

3. 存在实例：如果我们知道 $\exists x P(x)$ 为真，得出在论域中存在一个元素 $c$ 使得 $P(c)$ 为真。

$$ \exists x P(x) \to P(c),对某个元素 $$

4. 存在引入：已知一个特定 $c$ 使得 $P(c)$ 为真，得出结论 $\exists x P(x)$ 为真。

$$ P(c),对某个元素 \to \exists x P(x) $$

7 证明导论

证明条件语句 $p \to q$：

平凡证明：如果已知 $q$ 为真，那么 $p \to q$ 也为真

空证明：如果已知 $p$ 为假，那么 $p \to q$ 为真

直接证明法

1. 假设 $p$ 为真
2. 用推理规则构造
3. 表明 $q$ 也必须为真

间接证明法

反证法

假设 $\neg q$ 为真，然后证明 $\neg p$ 为真。如果我们证明了 $\neg q \to \neg p$，那么相当于我们证明了 $p \to q$。

#### 归谬证明法

为了证明 $p$ 为真, 先假设 $\neg p$ 为真。证明对于某个命题 $r$，$\neg p \to (r \wedge \neg r)$ 为真，就能证明 $p$ 为真。

条件语句的归谬证明：

为了证明 $p \to q$ 为真，先假定 $p$ 和 $\neg q$ 都为真，然后证明出 $\neg p$ 也为真，导出矛盾 $p \wedge \neg p$。

为了证明 $p \to q$ 为真，先假定 $p$ 和 $\neg q$ 都为真，然后证明出 $q$ 也为真，导出矛盾 $q \wedge \neg q$。

等价证明法

为了证明 $p \leftrightarrow q$，需要同时证明 $p \to q$ 和 $q \to p$ 都为真。

证明方法和策略

分情形证明法

为了证明条件语句 $(p_1 \vee p _2 \vee \ldots \vee p_n) \to q$，可以用永真式作为推理规则：

$$ [(p_1 \vee p _2 \vee \ldots \vee p_n) \to q] \to [(p_1\to q) \wedge (p_2 \to q) \wedge \ldots \wedge(p_n \to q)] $$

然后，分别证明每个条件语句 $p_i \to q$ 为真即可。

存在性证明

为了证明形如 $\exists x P(x)$ 的命题，存在性证明将：

1. 找到一个显式值 $c$，使得 $P(c)$ 为真
2. 那么 $\exists x P(x)$ 为真

反例：

为了证明 $\neg \forall x P(x)$ 为真（或 $\forall x P(x)$ 为假），找到一个元素 $c$ 使得 $\neg P(c)$ 为真（或者 $P(c)$ 为假）。

唯一性证明

证明 $\exists! xP(x)$ 包括两部分：

• 存在性：证明某个元素 $x$ 具有期望的性质
• 唯一性：证明如果 $y \neq x$，则 $x$ 不具有期望的性质

全称性证明

为了证明 $\forall x P(x)$，全称性证明假设 $x$ 是论域 $U$ 中的任意元素，证明 $P(x)$ 为真。使用量化命题的推理规则之全称引入，那么就能证明 $\forall x P(x)$。