boolean - 简化 9 个变量的 boolean 表达式

Question

我正在尝试创建一个井字游戏程序作为一种心理练习，并且我将董事会状态存储为 boolean 值，如下所示:

http://i.imgur.com/xBiuoAO.png

我想简化这个 boolean 表达式...

(a&b&c) | (d&e&f) | (g&h&i) | (a&d&g) | (b&e&h) | (c&f&i) | (a&e&i) | (g&e&c)

我的第一个想法是使用 Karnaugh Map但是没有在线求解器支持 9 个变量。

和继承人的问题:

首先，我怎么知道 boolean 条件是否已经尽可能简单？

第二:上面简化的 boolean 条件是什么？

Answer 1

2. 简化条件:

原来的表达

a&b&c|d&e&f|g&h&i|a&d&g|b&e&h|c&f&i|a&e&i|g&e&c

可以简化为以下，知道 & 比 | 更优先

e&(d&f|b&h|a&i|g&c)|a&(b&c|d&g)|i&(g&h|c&f)

短 4 个字符，在最坏情况下执行 18 &和 |评价(原评价为 23)
没有更短的 boolean 公式(见下点)。如果您 switch to matrices ，也许你可以找到另一种解决方案。

1. 确保我们得到最小的公式

通常，很难找到最小的公式。见 this recent paper如果你更感兴趣。但在我们的例子中，有一个简单的证明。

我们将推理公式为 最小 关于公式大小，其中变量 a , size(a)=1 , 对于 boolean 运算 size(A&B) = size(A|B) = size(A) + 1 + size(B) ，并用于否定 size(!A) = size(A) (因此我们可以假设我们免费获得了 Negation Normal Form)。
对于该大小，我们的公式大小为 37。

你不能做得更好的证据在于首先要注意有 8 行要检查，并且总是有一对字母区分 2 个不同的行。由于我们可以将这 8 个检查重新组合为不少于 3 个与剩余变量的连接，因此最终公式中的变量数量应至少为 8*2+3 = 19 ，从中我们可以推导出最小树的大小。

详细证明

让我们假设给定的公式 F是 最小 并在 NNF格式。

F不能包含否定变量，如 !a .为此，请注意 F应该是单调的，也就是说，如果它返回“true”(有一个获胜行)，则更改 false 中的变量之一至 true不应该改变那个结果。 According to Wikipedia , F可以不写否定。更好的是，我们可以证明我们可以消除否定。关注 this answer ，我们可以从 DNF 格式来回转换，删除中间的否定变量或将它们替换为 true .

F不能包含像两个变量析取的子树 a|b .
为了使此公式有用且不可与 a 互换或 b ，这意味着存在相互矛盾的分配，例如F[a|b] = true和 F[a] = false ，因此 a = false和 b = true因为单调。此外，在这种情况下，转动 b至 false使整个公式false因为 false = F[a] = F[a|false] >= F[a|b](b = false) .
因此有一行经过 b这是真理的因，它不能通过a ，因此例如 e = true和 h = true .
并且该行的检查通过表达式 a|b用于测试 b .但是，这意味着使用 a,e,h为真，所有其他设置为假，F仍然是正确的，这与公式的目的相矛盾。

每个子树看起来都像 a&b检查唯一行。所以最后一个字母应该出现在相应的析取符 (a&b|...)&{c somewhere for sure here} 的正上方。 ，或者这片叶子没有用，a 或 b 都可以安全地移除。事实上，假设 c上面没有出现，游戏是哪里a&b&c是 true和所有其他变量是 false .然后 c 应该在上面的表达式返回 false , 所以 a&b将永远无用。所以通过删除 a&b 有一个更短的表达式.

有 8 个独立的分支，所以至少有 8 个 a&b 类型的子树.由于 a，我们无法使用 2 个连词的析取重新组合它们。 , f和 h从不共享相同的行，因此必须有 3 个外部变量。 8*2+3使 19 个变量出现在最终公式中。
具有 19 个变量的树不能少于 18 个运算符，因此总大小必须至少为 19+18 = 37。

您可以拥有上述公式的变体。

QED。