logic - 两个布尔表达式的相等性

Question

我有两个布尔表达式：

¬aΛ¬b V ¬aΛ¬c V aΛ¬bΛ¬c #1

¬aΛ¬b V ¬aΛ¬c V ¬bΛ¬c #2

我知道它们是相同的，因为它们的真值表是相同的。我的问题是，我怎样才能使它们在表达方面平等。

您可能会注意到它们之间的唯一区别是 #1 在它的最后一个 OR 术语中有一个额外的“a”。各种试图摆脱额外“a”的保理方法均未成功。

score 3 · Accepted Answer

我不知道你所说的“表达方式”到底是什么意思，但如果你根据 a 是真还是假来分解它们，就会很容易看出。

如果 a 为真（前两项在 Eq1 和 Eq2 中均为假）：
Eq1 => Eq2 = ~b & ~c
>~b & ~c

如果 a 为假：
Eq1 => Eq2 ~b | ~c
=> ~b | ~c | (~b & ~c)== Eq1

编辑：您可以使用布尔标识更正式地使用相同的参数：

(~a & ~b | ~a & ~c | ~b & ~c) == ((~a & ~b) | (~a & ~c) | (~b & ~c)) & (a | ~a)

因为 (a | ~a) == 1 和x & 1 = x

然后使用&over的分布|：

== (((~a & ~b) | (~a & ~c) | (~b & ~c)) & a) | (((~a & ~b) | (~a & ~c) | (~b & ~c)) & ~a)

现在，您将每个“案例”作为 main 两侧的附加事实|。再次应用分发会将这个事实推到内部案例中，并最终做出与我上面所做的相同的取消。只看左侧的第一个分布：

((~a & ~b) | x) & a) == (a & ~a & b) | (a & x) == 0 | (a & x) == a & x

其中 x 是另外两个 or 表达式。遵循此策略将为您提供与上述相同的答案。如果你卡住了，我可以带你走得更远，但你应该可以从这里走。

score 0 · Accepted Answer

通常，您需要将表达式转换为析取范式。为此，您对基本连词进行析取：为真值表中的每个 1 写出所有变量或其反转的对应连词，然后对所有这些连词进行析取。合取范式也存在，但很少使用。

对于许多变量的表达式，析取范式变得非常大。在这种情况下，您可能希望使用最小化算法（例如Quine-McCluskey 算法），但这非常复杂且计算量很大（最小化问题是NP 难题，并且这些算法的运行时间通常比仅计算真相要差得多桌子）。

如果您只需要一个通用表示来比较相同变量的任何布尔表达式，您还可以比较这些表达式的真值表：

2 回答 2