经典命题逻辑中多分歧合取式的析取等价性证明问询

你这个观察完全正确——不存在这样的合取式φ，下面给你一个简洁的证明思路，不用繁琐的枚举：

首先明确前提：α和β是基于相同命题变元集的合取式，且存在至少2个分歧变元（即至少有两个不同的命题变元p、q，使得α含p当且仅当β含¬p，α含q当且仅当β含¬q），我们可以把α、β拆分为：

• α = (分歧变元的文字组合) ∧ γ
• β = (对应分歧变元的否定文字组合) ∧ γ
  其中γ是α和β中完全一致的文字组成的合取式（非分歧部分）。

证明核心：赋值矛盾法 #

假设存在合取式φ，使得$(\alpha \lor \beta) \equiv \varphi$，那么φ与$\alpha \lor \beta$在所有赋值下真值完全相同。我们构造几个关键赋值来导出矛盾：

1. 赋值v₁：让所有分歧变元的取值都使α和β同时为假
   对分歧变元p、q，取p的真值使α中的p文字为假，q的真值使α中的q文字为假；非分歧变元取使γ为真的真值。此时α中p、q文字都为假，α整体为假；β中对应的¬p、¬q文字也为假（比如α含p时p取假，β含¬p则¬p为假），β整体也为假。因此$\alpha \lor \beta$在v₁下为假，那么φ在v₁下也必须为假——作为合取式，φ中至少有一个文字在v₁下为假，这个文字只能是某个分歧变元的否定文字（如¬p、¬q），因为γ的文字在v₁下都是真的。

2. 赋值v_p：让p的取值使α为真，其他分歧变元的取值也使α为真
   取p的真值使α中的p文字为真，其他所有分歧变元的取值都匹配α中的对应文字，非分歧变元取使γ为真的真值。此时α的所有文字都为真，α整体为真，因此$\alpha \lor \beta$为真，φ在v_p下必须为真——这意味着φ中所有文字在v_p下都为真，所以φ不能包含¬p（因为v_p下p为真，¬p为假，会导致φ为假，矛盾）。

3. 同理构造赋值v_q：让q的取值使α为真，其他分歧变元的取值也使α为真
   此时α整体为真，$\alpha \lor \beta$为真，φ在v_q下必须为真，因此φ不能包含¬q。

矛盾导出 #

从步骤1，φ必须包含至少一个分歧变元的否定文字（如¬p或¬q）；但步骤2和3分别排除了φ包含¬p和¬q的可能。如果分歧变元更多（比如3个及以上），用同样的方法可以排除所有分歧变元的否定文字，同时非分歧部分的否定文字会导致在使α为真的赋值下φ为假，也会产生矛盾。

因此，不存在这样的合取式φ，你的猜想是对的。

备注：内容来源于stack exchange，提问作者ShyPerson