逻辑

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

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

• $a \rightarrow b \equiv \neg a \vee b$ （最基础的等价形式）
• $a \rightarrow b \equiv \neg b \rightarrow \neg a$ （逆否命题）
• $a \rightarrow b \equiv \neg (a \wedge \neg b)$ （蕴含的否定形式）

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. 其他有用等价

• $a \vee \neg a \equiv \text{真}$ （排中律）
• $a \wedge \neg a \equiv \text{假}$ （矛盾律）
• $a \vee \text{假} \equiv a$，$a \wedge \text{真} \equiv a$ （恒等律）
• 假言推理 (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：将蕴含转化为析取

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：证明逆否命题等价

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：简化复杂表达式

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$
   • $q \wedge (p \vee q) \equiv (q \wedge p) \vee (q \wedge q) \equiv (p \wedge q) \vee q \equiv q$ （吸收律）
6. 整体为：$(\neg p \wedge q) \vee q \equiv q$ （吸收律）
7. 因此，简化后为 $q$。

例子4：使用德摩根定律

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 中直接应用。

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