analysis - 证明卡诺图的非最优性

Question

在寻找专门针对 K-map 最优性的文献时，我将不胜感激。

例如，我了解如何在 SOP(乘积和)表达式和 K-map 之间进行映射，以及为什么通常您希望 K-map 优化表达式更简单，因为找到了 1 的最大分组对应于在一个朴素的 SOP 表达式中找到一些冗余。

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

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

我试图阅读:this
但是在那篇论文中，只是提到了寻找最优 bool 表达式的问题是在 NP 中，我认为作者只是在暗示 K-maps 不可能是最优的，因为作为一种算法，它们不是在 NP 时间内运行的.

为什么 K-maps 不是最优的，而不仅仅是以“反例”的方式......实际上为什么？你能证明给我看，还是指导我去证明？

Answer 1

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

未执行的代数运算包括例如 Distributivity of ∧ over ∨ .应用该规则可能会为您提供具有较少项的函数。

k-map 不会使用即 xor 为您提供方程。 , 因为得到的方程只使用 or和 and和 not .所以，如果我采用从函数派生的真值表( ^ 是 xor ):
lambda a, b, c, d: a ^ b ^ c ^ d
生成的真值表将没有矩形，并且 SOP 形式可能被认为是不理想的:

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)

如果您只使用 or和 and并且您的输入函数比您的输出函数短，您在输入中使用括号。如果是这种情况，您还可以在 k-map 的输出中分解出一些变量(使用 bool 代数)，并且您将得到一个至少一样短的方程。

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

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