问简化9变量布尔表达式

EN

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)没有更短的布尔公式(见下文)。如果你使用switch to matrices，也许你可以找到另一个解决方案。

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

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

我们将根据公式大小推断出一个公式是最小的，其中对于变量a，对于布尔运算size(A&B) = size(A|B) = size(A) + 1 + size(B)，对于求反size(!A) = size(A)，对于变量size(a)=1 (因此，我们可以假设我们有免费的Negation Normal Form )。关于这个大小，我们的公式是37。

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

详细证明

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

1. F !a.不能像那样包含被取反的变量为此，请注意F应该是单调的，也就是说，如果它返回"true“(有一个获胜的行)，那么将其中一个变量从false更改为true不会改变结果。According to Wikipedia，F可以在没有否定的情况下编写。更好的是，我们可以证明我们可以删除否定。在this answer之后，我们可以在DNF格式中来回转换，删除中间被求反的变量或将它们替换为true.
2. F a|b.不能包含像两个变量的析取那样的子树DNF对于这个公式是有用的，并且不能与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。并且对此行的检查通过用于测试b的表达式a|b。然而，这意味着在a,e,h为true而所有其他设置为false的情况下，F仍然为true，这与formula.
3. Every子树看起来像a&b检查唯一行的目的相矛盾。因此，最后一个字母应该出现在相应的析取(a&b|...)&{c somewhere for sure here}的正上方，或者这个叶子是无用的，a或b都可以安全地删除。实际上，假设c没有出现在上面，游戏中a&b&c是true，所有其他变量都是false。然后c应该在上面的表达式返回false，所以a&b将永远是无用的。所以有一个更短的表达式，通过删除a&b.
4. There是8个独立的分支，所以至少有8个a&b类型的子树。我们不能使用2个合取的析取来重新组合它们，因为a、f和h从不共享相同的行，因此必须有3个外部变量。8*2+3使19个变量出现在最终公式中。包含19个变量的树不能少于18个运算符，因此总大小必须至少为19+18 =37。

您可以使用上述公式的变体。

QED。

一种选择是手动绘制卡诺图。由于您有9变量，这就形成了一个2^4 x 2^5的网格，这是相当大的，从等式的外观来看，可能也不是很有趣。

通过检查，看起来卡诺图不会为您提供任何有用的信息(卡诺图基本上将诸如((!a)&b) | (a&b)之类的表达式简化为b)，因此从简化的意义上讲，您的表达式已经尽可能简单了。但是，如果你想减少计算次数，你可以使用OR上的AND运算符的分布性来分解出一些变量。

你知道，当没有共同的子项要提取时，这是尽可能简单的(例如，如果你在两个不同的三元组中有"a&b“)。

您知道您的tic tac toe解决方案必须尽可能简单，因为任何一对盒子最多只能属于一条胜利线(只有一条直线可以通过两个给定点)，所以(a & b)不能在您正在检查的任何其他胜利点中重用。

(此外，"simple“可以表示很多事情；指定您的意思可能会帮助您回答自己的问题。)