离散数学-2
用等值演算法证明下列等式：
- $(p \wedge q)(p \vee \neg q) \Leftrightarrow p$
- $\neg(p \leftrightarrow q) \Leftrightarrow ((p \vee q) \wedge \neg(p\wedge q))$
让我们使用等值演算法证明这两个等式。
- 证明 $(p \wedge q)(p \vee \neg q) \Leftrightarrow p$:
首先，展开左侧的表达式：
$(p \wedge q)(p \vee \neg q)$
现在，使用分配律 $(A \wedge B)(A \vee C) \Leftrightarrow A \wedge (B \wedge (A \vee C))$：
$p \wedge (q \wedge (p \vee \neg q))$
接下来，使用恒等式 $p \wedge (q \wedge (p \vee \neg q)) \Leftrightarrow (p \wedge q \wedge p) \vee (p \wedge q \wedge \neg q)$：
$(p \wedge q \wedge p) \vee (p \wedge q \wedge \neg q)$
再次使用分配律 $(A \wedge B) \vee (A \wedge C) \Leftrightarrow A \wedge (B \vee C)$：
$p \wedge (q \wedge p \vee \neg q)$
现在，使用恒等式 $q \wedge p \vee \neg q \Leftrightarrow (q \wedge p) \vee (\neg q)$：
$p \wedge ((q \wedge p) \vee (\neg q))$
再次使用分配律 $(A \wedge B) \vee (A \wedge C) \Leftrightarrow A \wedge (B \vee C)$：
$p \wedge (q \wedge p) \vee (p \wedge \neg q)$
现在，使用恒等式 $q \wedge p \Leftrightarrow p \wedge q$：
$(p \wedge p \wedge q) \vee (p \wedge \neg q)$
再次使用恒等式 $p \wedge p \wedge q \Leftrightarrow p \wedge q \wedge p$：
$(p \wedge q \wedge p) \vee (p \wedge \neg q)$
最后，使用交换律 $p \wedge q \wedge p \Leftrightarrow p \wedge p \wedge q$ 和结合律 $p \wedge p \wedge q \Leftrightarrow p \wedge (p \wedge q)$：
$(p \wedge (p \wedge q)) \vee (p \wedge \neg q)$
再次使用恒等式 $p \wedge (p \wedge q) \Leftrightarrow (p \wedge p) \wedge q$：
$((p \wedge p) \wedge q) \vee (p \wedge \neg q)$
现在，使用恒等式 $p \wedge p \Leftrightarrow p$：
$(p \wedge q) \vee (p \wedge \neg q)$
最后，使用分配律 $A \vee (B \wedge C) \Leftrightarrow (A \vee B) \wedge (A \vee C)$：
$(p \wedge q) \vee (p \wedge \neg q) \Leftrightarrow p \wedge (q \vee \neg q)$
由于 $q \vee \neg q$ 是恒等于真值 $1$ 的表达式，我们得出：
$(p \wedge q) \vee (p \wedge \neg q) \Leftrightarrow p \wedge 1$
再次使用恒等式 $A \wedge 1 \Leftrightarrow A$：
$(p \wedge q) \vee (p \wedge \neg q) \Leftrightarrow p$
因此，我们证明了第一个等式。
- 证明 $\neg(p \leftrightarrow q) \Leftrightarrow ((p \vee q) \wedge \neg(p\wedge q))$:
首先，展开左侧的表达式：
$\neg(p \leftrightarrow q)$
使用双蕴涵的定义 $A \leftrightarrow B \Leftrightarrow (A \wedge B) \vee (\neg A \wedge \neg B)$：
$\neg((p \wedge q) \vee (\neg p \wedge \neg q))$
使用德·摩根定律 $\neg(A \vee B) \Leftrightarrow (\neg A \wedge \neg B)$：
$\neg(p \wedge q) \wedge \neg(\neg p \wedge \neg q)$
再次使用德·摩根定律 $\neg(A \wedge B) \Leftrightarrow (\neg A \vee \neg B)$：
$(\neg p \ve \neg q) \wedge (p \vee q)$
现在，展开右侧的表达式：
$(p \vee q) \wedge \neg(p \wedge q)$
使用德·摩根定律 $\neg(A \wedge B) \Leftrightarrow (\neg A \vee \neg B)$：
$(p \vee q) \wedge (\neg p \vee \neg q)$
再次使用分配律 $A \wedge (B \vee C) \Leftrightarrow (A \wedge B) \vee (A \wedge C)$：
$(p \wedge \neg p \vee p \wedge \neg q \vee q \wedge \neg p \vee q \wedge \neg q)$
使用恒等式 $A \wedge \neg A \Leftrightarrow 0$ 和 $A \vee 0 \Leftrightarrow A$：
$(0 \vee 0 \vee 0 \vee 0)$
因此，右侧表达式简化为 $0$。
现在，左侧表达式是 $(\neg p \vee \neg q) \wedge (p \vee q)$，而右侧表达式是 $0$。
使用恒等式 $A \wedge 0 \Leftrightarrow 0$：
$(\neg p \vee \neg q) \wedge (p \vee q) \Leftrightarrow 0\
)
因此，我们证明了第二个等式。