逻辑

l1ng21y12026 · 2025-11-28 10:05:24 · 算法·理论

逻辑

本文由 AI 生成，人类整理。link。

1. 蕴含 (Implication) 的等价形式

2. 双条件 (Biconditional) 的等价形式

• a \leftrightarrow b \equiv (a \rightarrow b) \wedge (b \rightarrow a)
• a \leftrightarrow b \equiv (a \wedge b) \vee (\neg a \wedge \neg b)

3. 德摩根定律 (De Morgan's Laws)

• \neg (a \wedge b) \equiv \neg a \vee \neg b
• \neg (a \vee b) \equiv \neg a \wedge \neg b

4. 分配律 (Distributive Laws)

• a \wedge (b \vee c) \equiv (a \wedge b) \vee (a \wedge c)
• a \vee (b \wedge c) \equiv (a \vee b) \wedge (a \vee c)

5. 吸收律 (Absorption Laws)

• a \wedge (a \vee b) \equiv a
• a \vee (a \wedge b) \equiv a

6. 其他有用等价

• 假言推理 (Modus Ponens)： 如果 a \rightarrow b 和 a 为真，则 b 为真。

• 拒取式 (Modus Tollens)： 如果 a \rightarrow b 和 \neg b 为真，则 \neg a 为真。

• 链式推理 (Hypothetical Syllogism)： 如果 a \rightarrow b 和 b \rightarrow c 为真，则 a \rightarrow c 为真。

逻辑推理例子

例子1：将蕴含转化为析取

问题： 将 p \rightarrow (q \wedge r) 转化为只使用否定和析取的形式。

步骤：

1. 应用蕴含的等价形式：p \rightarrow (q \wedge r) \equiv \neg p \vee (q \wedge r)
2. 这已经只用了否定和析取，目标已达到。
3. 所以，p \rightarrow (q \wedge r) \equiv \neg p \vee (q \wedge r)。

例子2：证明逆否命题等价

问题： 证明 a \rightarrow b \equiv \neg b \rightarrow \neg a。

步骤：

1. 从左边开始：a \rightarrow b \equiv \neg a \vee b （蕴含等价）
2. 考虑右边：\neg b \rightarrow \neg a \equiv \neg (\neg b) \vee \neg a \equiv b \vee \neg a （蕴含等价和双重否定）
3. 由于析取满足交换律，b \vee \neg a \equiv \neg a \vee b
4. 因此，两边相等。

例子3：简化复杂表达式

问题： 简化 (p \rightarrow q) \wedge (p \vee q)。

步骤：

1. 将蕴含转化：p \rightarrow q \equiv \neg p \vee q
2. 表达式变为：(\neg p \vee q) \wedge (p \vee q)
3. 应用分配律：视作 A \wedge B，其中 A = \neg p \vee q, B = p \vee q
4. 分配律：(\neg p \vee q) \wedge (p \vee q) \equiv [\neg p \wedge (p \vee q)] \vee [q \wedge (p \vee q)]
5. 简化每个部分：
   • \neg p \wedge (p \vee q) \equiv (\neg p \wedge p) \vee (\neg p \wedge q) \equiv \text{假} \vee (\neg p \wedge q) \equiv \neg p \wedge q
6. 整体为：(\neg p \wedge q) \vee q \equiv q （吸收律）
7. 因此，简化后为 q。

例子4：使用德摩根定律

问题： 将 \neg (p \rightarrow q) 转化为合取形式。

步骤：

1. p \rightarrow q \equiv \neg p \vee q$，所以 $\neg (p \rightarrow q) \equiv \neg (\neg p \vee q)
2. 应用德摩根定律：\neg (\neg p \vee q) \equiv \neg (\neg p) \wedge \neg q \equiv p \wedge \neg q
3. 因此，\neg (p \rightarrow q) \equiv p \wedge \neg q。这表示蕴含的否定是"前件真且后件假"。

应用

OI 中逻辑推理在 2-SAT 中直接应用。

在 网络流 的最小割建图中也有转化逻辑限制条件，变为最小割能接受的形式的作用。