证明卡诺图的非最优性

Question

我希望能得到一些帮助来寻找专门解决 K-map 最优性的文献。

例如，我了解如何在 SOP（乘积和）表达式和 K-map 之间进行映射，以及为什么通常您会期望 K-map 优化表达式更简单，因为找到了 1 的最大分组相当于在简单的 SOP 表达式中查找一些冗余。

我隐约看到 K-map 方法可能不会产生最佳解决方案，因为我们实际上所做的唯一一件事似乎是利用布尔代数的分配和恒等 (A + A' = 1) 属性。但我真的不明白我们没有使用 K-map 执行哪些代数运算，这可能使我们能够达到更优化的解决方案。

结果是我不知道如何开始证明 K-map 并不总是最优的。

我试图阅读：this ，但在那篇论文中，它只是引用了寻找最佳布尔表达式的问题是在 NP 中，我认为作者只是含蓄地说 K-map 不可能是最佳的，因为作为一种算法它们不是在 NP 时间内运行。

为什么 K-map 不是最优的，而且不仅仅是以“反例”的方式......实际上为什么？你能向我证明这一点，或者指导我证明吗？

Answer 1

您认为什么是最佳的？K-map 只为您提供 SOP 或 POS 形式的最优方程。所以这取决于你想要什么。

\n\n

未执行的代数运算包括例如Distributivity of \xe2\x88\xa7 over \xe2\x88\xa8. 应用该规则可能会为您提供一个项数更少的函数。

\n\n

k-map 不会为您提供使用 ie 的方程xor，因为生成的方程仅使用or和and和not。^因此，如果我采用从函数（使用being xor）导出的真值表：

\n\n

lambda a, b, c, d: a ^ b ^ c ^ d

\n\n

生成的真值表将没有矩形，并且 SOP 形式可能被认为不是最佳的：

\n\n

lambda a, b, c, d: (not a and b and c and d) or (not a and not b and not c and d) or (not a and not b and c and not d) or (not a and b and not c and not d) or (a and b and c and not d) or (a and b and not c and d) or (a and not b and c and d) or (a and not b and not c and not d)\n

\n\n

\n\n

如果您仅使用orandand并且您的输入函数比输出函数短，则您在输入中使用了括号。如果是这种情况，您还可以在 k-map 的输出中分解出一些变量（使用布尔代数），并且您将得到一个至少同样短的方程。

\n\n

概括：最小化布尔函数就像找到任何其他数字序列的方程一样。总会有多种解决方案。但哪个函数是最简单的呢？我可能会说：“给我一个函数，它对于 0 返回 1，对于 1 返回 2，对于 2 返回 4，对于 3 返回 8”。你可以说“函数是 pow(2,x)”。我可以说“错了！我在想 1 << x”。函数不相等的所有值都在规范的范围之外。它们对应于K-map中的“不知道”。

\n\n

当我说“我的函数更简单，因为我只是对所有项进行异或”时，您可以说：“但是如果我添加一个额外的变量并且它不遵循您的模式，那么您的函数就会变得过于笨拙和复杂，我的仍然遵循 SOP 或 POS 模式”。

\n