3.命题逻辑

1.命题与命题联结词

联结词优先级（由高到低）

1. 否定 $\neg$

• 真值规则：若 $p$ 为真则 $\neg p$ 为假；若 $p$ 为假则 $\neg p$ 为真。

2. 合取 $\wedge$

• 真值规则：仅当 $p$ 与 $q$ 均为真时 $p \wedge q$ 为真；否则为假。

3. 析取 $\vee$

• 真值规则：若 $p$ 与 $q$ 至少一个为真则 $p \vee q$ 为真；仅当二者皆假时为假。

4. 蕴含 $\rightarrow$

• 真值表：

  $p$	$q$	$p \rightarrow q$
  0	0	1
  0	1	1
  1	0	0
  1	1	1

• 自然语言表述：

  1. 只要 $p$，就 $q$​
  2. 因为 $p$，所以 $q$​
  3. $p$ 仅当 $q$​
  4. 只有 $q$ 才 $p$
  5. 除非 $q$ 才 $p$​
  6. 除非 $q$，否则非 $p$ ​

5. 等价 $\leftrightarrow$

• 真值表：

  $p$	$q$	$p \leftrightarrow q$
  0	0	1
  0	1	0
  1	0	0
  1	1	1

• 自然语言表述：

  1. 当且仅当
  2. …的充要条件

---

2.命题公式、解释与真值表

• 设 $A$ 为任一命题公式：

  1. 永真式（重言式）: $A$ 在各种赋值下均为真
  2. 矛盾式（永假式）: $A$ 在各种赋值下均为假
  3. 可满足式: $A$ 不是矛盾式

• 示例：构造真值表
  命题公式 $A: (\neg p \wedge q) \rightarrow \neg r$​

  $p$	$q$	$r$	$\neg p$	$\neg r$	$\neg p \wedge q$	$(\neg p \wedge q) \rightarrow \neg r$
  0	0	0	1	1	0	1
  0	1	0	1	1	1	1
  1	0	0	0	1	0	1
  1	1	0	0	1	0	0
  1	1	1	0	0	0	1
  1	0	1	0	0	0	1
  1	1	0	0	1	0	1
  1	1	1	0	0	0	1

等值式

1. 双重否定律: $A \Leftrightarrow \neg \neg A$
2. 幂等律: $A \Leftrightarrow A \vee A$ $A \Leftrightarrow A \wedge A$
3. 交换律: $A \vee B \Leftrightarrow B \vee A$ $A \wedge B \Leftrightarrow B \wedge A$
4. 结合律: $(A \vee B) \vee C \Leftrightarrow A \vee (B \vee C)$ $(A \wedge B) \wedge C \Leftrightarrow A \wedge (B \wedge C)$
5. 分配律: $A \vee (B \wedge C) \Leftrightarrow (A \vee B) \wedge (A \vee C)$ ($\vee$ 对 $\wedge$ 的分配律) $A \wedge (B \vee C) \Leftrightarrow (A \wedge B) \vee (A \wedge C)$ ($\wedge$ 对 $\vee$ 的分配律)
6. 德·摩根律: $\neg (A \vee B) \Leftrightarrow \neg A \wedge \neg B$ $\neg (A \wedge B) \Leftrightarrow \neg A \vee \neg B$
7. 吸收律: $A \vee (A \wedge B) \Leftrightarrow A$ $A \wedge (A \vee B) \Leftrightarrow A$
8. 零律: $A \vee 1 \Leftrightarrow 1$ $A \wedge 0 \Leftrightarrow 0$
9. 同一律: $A \vee 0 \Leftrightarrow A$ $A \wedge 1 \Leftrightarrow A$
10. 排中律: $A \vee \neg A \Leftrightarrow 1$
11. 矛盾律: $A \wedge \neg A \Leftrightarrow 0$
12. 蕴涵等值式: $A \rightarrow B \Leftrightarrow \neg A \vee B$
13. 等价等值式: $A \leftrightarrow B \Leftrightarrow (A \rightarrow B) \wedge (B \rightarrow A)$
14. 假言易位（逆否命题）: $A \rightarrow B \Leftrightarrow \neg B \rightarrow \neg A$
15. 等价否定等值式: $A \leftrightarrow B \Leftrightarrow \neg A \leftrightarrow \neg B$
16. 归谬论: $(A \rightarrow B) \wedge (A \rightarrow \neg B) \Leftrightarrow \neg A$

---

3.联结词的完备集

• $S$ 是一个联结词集合，如果任一命题公式可以由仅含 S 中的联结词构成的公式表示，则称 S 是一个联结词完备集。

  • 与非联结词 $\uparrow$
    $p \uparrow q: p \uparrow q \Leftrightarrow \neg(p \land q)$

  • 或非联结词 $\downarrow$
    $p \downarrow q: p \downarrow q \Leftrightarrow \neg(p \lor q)$

  • 以下都是联结词完备集：
    $S_{1}=\{\neg, \land, \lor\}$
    $S_{2}=\{\neg, \land, \lor, \to\}$
    $S_{3}=\{\neg, \land, \lor, \to, \leftrightarrow\}$
    $S_{4}=\{\neg, \land\}$
    $S_{5}=\{\neg, \lor\}$
    $S_{6}=\{\neg, \to\}$
    $S_{7}=\{\uparrow\}$
    $S_{8}=\{\downarrow\}$

---

4.公式的标准型‑范式

1. 简单析取式：仅由有限个文字构成的析取式 例：$p\lor\neg q,\ \neg p\lor q\lor\neg r$

2. 简单合取式：仅由有限个文字构成的合取式 例：$p\land\neg q,\ \neg p\land q\land\neg r$

3. 析取范式：由有限个简单合取式的析取构成的命题式 例：$(\ ) \lor(\ ) \lor(\ )$

4. 合取范式：由有限个简单析取式的合取构成的命题式 例：$(\ ) \land(\ ) \land(\ )$

极小项

• ① 简单合取式
• ② 每个命题变元和它的否定式恰好出现仅出现一次
• ③ 命题变元或它的否定式按照下标从小到大排列

极大项

• ① 简单析取式
• ② 每个命题变元和它的否定式恰好出现仅出现一次
• ③ 命题变元或它的否定式按照下标从小到大排列

极小项用 $m_{数字}$ 表示，极大项用 $M_{数字}$ 表示，其中数字下标是成真赋值对应的二进制转换为十进制后的数字。

1. 主析取范式：所有简单合取式都是极小项的析取范式，取自真值表中所有的成真赋值。
   例：$m_{0} \lor m_{1} \lor m_{3}$，$(p \land q) \lor(\neg p \land q)$，$(p \land q) \lor \neg p$

2. 主合取范式：所有简单析取式都是极大项的合取范式，取自真值表中所有的成假赋值。
   例：$M_{0} \land M_{1} \land M_{3}$，$(p\lor q) \land(\neg p\lor q)$，$(p\lor q) \land\neg p$

---

5.命题逻辑的推理理论

推理的相关概念

1. 设 $A$ 和 $B$ 是两个命题公式，当且仅当 $A \to B$ 是重言式时，称从 $A$ 可推出 $B$，或 $B$ 是前提 $A$ 的有效结论，记为 $A \Rightarrow B$。

2. 命题公式 $A_{1}, A_{2}, \dots, A_{k}$ 推出 $B$ 的推理正确，当且仅当 $A_{1} \land A_{2} \land \cdots \land A_{k} \to B$ 为重言式。

3. 推理的形式结构：
   前提：$A_1,\ A_2,\ \dots,\ A_k$
   结论：$B$

推理的相关公式

1. 附加律: $A\Rightarrow(A\lor B)$
2. 化简律 : $(A\land B) \Rightarrow A$
3. 假言推理: $(A\to B) \land A\Rightarrow B$
4. 拒取式: $(A\to B) \land\neg B\Rightarrow\neg A$
5. 析取三段论: $(A \lor B) \land \neg B \Rightarrow A$
6. 假言三段论: $(A \to B) \land(B \to C) \Rightarrow(A \to C)$
7. 等价三段论: $(A \leftrightarrow B) \land(B \leftrightarrow C) \Rightarrow(A \leftrightarrow C)$
8. 构造性二难: $(A\to B) \land(C\to D) \land(A\lor C) \Rightarrow(B\lor D)$
9. 破坏性二难: $(A\to B) \land(C\to D) \land(\neg B\lor\neg D) \Rightarrow(\neg A\lor\neg C)$

解题方法

1. 附加前提法

 例题：证明 $A\lor B\to C\land D,\ D\lor E\to P \Rightarrow A\to P$

• step1：从题干中提取出前提和结论

  • 前提：$A\lor B\to C\land D,\ D\lor E\to P$
  • 结论：$A\to P$

• step2：证明

  1. $A$          附加前提引入
  2. $A\lor B$        ① 附加律
  3. $A\lor B\to C\land D$  前提引入
  4. $C\land D$       ②③ 假言推理
  5. $D$          ④ 化简律
  6. $D\lor E$       ⑤ 附加律
  7. $D\lor E\to P$    前提引入
  8. $P$          ⑥⑦ 假言推理

 得证 $A\to P$ 是有效结论。

2. 归谬法

 例题：如果小张守第一垒并且小李向$B$队投球，则$A$队取胜；$A$队没有成为联赛的第一名；小张守第一垒。因此，小李没向$B$队投球。

• step1：设原子命题
  • $p$：小张守第一垒
  • $q$：小李向$B$队投球
  • $r$：$A$队取胜
  • $s$：$A$队成为联赛第一名
• step2：前提、结论
  • 前提：$(p\land q) \to r,\ \neg r\lor s,\ \neg s,\ p$
  • 结论：$\neg q$

解读：或者$A$队未取胜，或者$A$队成为联赛第一名。

• step3：证明（归谬法，结论的否定引入）
  1. $q$       结论的否定引入
  2. $p$       前提引入
  3. $p\land q$     ①② 合取
  4. $(p\land q) \to r$  前提引入
  5. $r$       ③④ 假言推理
  6. $\neg r\lor s$    前提引入
  7. $s$       ⑤⑥ 析取三段论
  8. $\neg s$      前提引入
  9. $s\land\neg s$    ⑦⑧ 合取，推出矛盾，故 $\neg q$ 成立。