简化9变量布尔表达式

Question

我正在尝试创建一个tic-tac-toe程序作为心理练习,我将董事会状态存储为booleans,如下所示:

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

我想简化这个布尔表达式......

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

我的第一个想法是使用卡诺图,但没有在线求解器支持9个变量.

并且还有一个问题:

首先,我如何知道布尔条件是否已经尽可能简单？

第二个:上面简化的布尔条件是什么？

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)没有更短的布尔公式(见下面的点).如果切换到矩阵,也许你可以找到另一种解决方案.

1.确保我们得到最小的配方

通常,很难找到最小的公式.如果您对此感兴趣,请参阅最近的这篇论文.但在我们的案例中,有一个简单的证据.

我们将推理公式作为最小相对于公式的大小,其中一个变量a,size(a)=1为布尔运算size(A&B) = size(A|B) = size(A) + 1 + size(B),和否定size(!A) = size(A)(因此,我们可以假设我们有否定范式,不需任何费用).就这个尺寸而言,我们的配方尺寸为37.

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

详细证明

让我们假设给定的公式F是最小的并且采用NNF格式.

1. F不能包含否定变量之类的!a.为此,注释F应该是单调的,也就是说,如果它返回"true"(有一个获胜的行),那么将变量之一更改为falseto true不应该改变该结果.根据维基百科,F可以不加否定地书写.更好的是,我们可以证明我们可以消除这种否定.根据这个答案,我们可以转换回DNF格式,删除中间的否定变量或替换它们true.

2. 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则仍然是正确的,这与公式的目的相矛盾.

3. 每个子树看起来都会a&b检查一个独特的行.因此,最后一个字母应该出现在相应的分离上方(a&b|...)&{c somewhere for sure here},或者这个叶子是无用的,可以安全地移除a或b.事实上,假设c不出现以上,而游戏就是a&b&c为true所有的其它变量false.那么c应该在上面的表达式返回false,所以a&b总是无用的.所以通过删除有一个较短的表达a&b.

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

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

QED.

Answer 2

一种选择是手动绘制卡诺图。由于您有9变量，因此会形成一个 2^4 x 2^5 的网格，该网格相当大，并且从方程的外观来看，可能也不是很有趣。

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