在寻找专门针对 K-map 最优性的文献时，我将不胜感激。
例如，我了解如何在 SOP（积和）表达式和 K-map 之间进行映射，以及为什么通常您希望 K-map 优化表达式更简单，因为找到了 1 的最大分组对应于在一个朴素的 SOP 表达式中找到一些冗余。
我可以隐约看出，K-map 方法可能不会产生最优解，因为我们实际上在做的唯一一件事就是利用布尔代数的分布和恒等 (A + A' = 1) 属性。但是我真的不明白我们没有使用 K-map 执行哪些代数运算，这可能使我们能够达到更优化的解决方案。
结果是我不知道如何开始证明 K-map 并不总是最优的。
我试图阅读：this 但是在那篇论文中，只是引用了在 NP 中找到最优布尔表达式的问题，我认为作者只是在暗示 K-maps 不可能是最优的，因为作为一种算法他们没有在 NP 时间运行。
为什么 K-maps 不是最优的，而不仅仅是以“反例”的方式......实际上为什么？你能证明给我看，还是指导我去证明？
如果它对某人有所帮助，我将尝试描述我在尝试实现 K-map 时在最优性方面面临的挑战python。这是我用于 SOP 形式的 4 变量布尔函数的贪心算法：
x或¬x）的所有小项，然后选择仅覆盖函数中的一个子集的唯一小项xy或¬wz）的所有最小项，并选择覆盖函数中尚未覆盖的子集的唯一项。xyz或¬wxy）的所有最小项，并选择覆盖函数中尚未覆盖的子集的唯一项。现在，让我们考虑f(w,x,y,z)=∑(0,2,4,5,8,10,11,12,13,15)如下所示的函数：
使用上述步骤，我首先陷入了以下局部最小值，这绝对是 SOP 的最小表示，但不是最小表示：
f(w,x,y,z) = x¬y + ¬x¬z + w¬xy + wxz. 表示 f 需要 4 个最小项，这是次优的。该算法犯的严重错误是它选择了几个 3-variable minterms和w¬xy，wxz当单个（wyz尚未覆盖。一旦它选择了w¬xy，它就必须选择另一个 minterm，因为一个还没有被发现。
现在，如果不是在这一步，算法使用wyz在考虑其他两个之前考虑的 3 变量最小项的顺序，它将输出最佳 SOP: f(wxyz) = x¬y + ¬x¬z + wyz，如下所示。
