多路复用器实现的逻辑等价性证明：等价规则优雅解法问询

嘿，很高兴你已经通过真值表确认了这两个命题的等价性！咱们用逻辑等价规则来做更优雅的推导，核心思路是证明额外添加的析取项$(a \wedge b)$其实已经被原命题$(a \wedge \neg c) \vee (b \wedge c)$所蕴含，因此加上它不会改变原命题的真值。

核心逻辑：吸收律的延伸 #

要证明：
$$(a \wedge \neg c) \vee (b \wedge c) \equiv (a \wedge \neg c) \vee (b \wedge c) \vee (a \wedge b)$$
我们只需要证明：$(a \wedge b)$蕴含原命题，即$(a \wedge b) \rightarrow [(a \wedge \neg c) \vee (b \wedge c)]$是重言式。根据逻辑等价规则，当$Q \Rightarrow P$时，$P \vee Q \equiv P$。

方法1：用等价规则代数推导 #

我们从右边的式子出发，逐步化简到左边：

1. 首先，对额外的析取项$(a \wedge b)$使用同一律（任何命题与重言式合取仍为自身）：
   $$a \wedge b = (a \wedge b) \wedge (c \vee \neg c)$$
   这里$c \vee \neg c$是重言式（排中律）。

2. 用分配律展开上式：
   $$(a \wedge b) \wedge (c \vee \neg c) = (a \wedge b \wedge c) \vee (a \wedge b \wedge \neg c)$$

3. 将右边的原式替换后得到：
   $$(a \wedge \neg c) \vee (b \wedge c) \vee (a \wedge b \wedge c) \vee (a \wedge b \wedge \neg c)$$

4. 对式子分组并提取公因子（分配律逆运算）：

   • 第一组：$(a \wedge \neg c) \vee (a \wedge b \wedge \neg c) = (a \wedge \neg c) \wedge (1 \vee b)$
     其中$1$代表重言式，$1 \vee b$恒为真，根据同一律，这部分等价于$(a \wedge \neg c)$。
   • 第二组：$(b \wedge c) \vee (a \wedge b \wedge c) = (b \wedge c) \wedge (1 \vee a)$
     同理，$1 \vee a$恒为真，这部分等价于$(b \wedge c)$。

5. 合并两组结果，最终得到：
   $$(a \wedge \neg c) \vee (b \wedge c)$$
   也就是左边的原式，等价性得证。

方法2：用蕴含式的语义证明 #

假设$(a \wedge b)$为真，那么$a$和$b$都为真：

• 如果$c$为真：则$b \wedge c$为真，因此$(a \wedge \neg c) \vee (b \wedge c)$为真；
• 如果$c$为假：则$a \wedge \neg c$为真，因此$(a \wedge \neg c) \vee (b \wedge c)$为真；

无论$c$的取值如何，原命题都为真，说明$(a \wedge b)$的真值被原命题完全覆盖，因此添加它不会改变原式的真值，二者等价。

内容的提问来源于stack exchange，提问作者rcmpgrc