7

我正在尝试编写一段可以将布尔表达式的 LENGTH 减少到最小的代码，因此代码应该将表达式中的元素数量减少到尽可能少。现在我被困住了，我需要一些帮助=[

规则如下：布尔表达式中可以有任意数量的元素，但它只包含 AND 和 OR 运算符，以及括号。

例如，如果我传入一个布尔表达式：ABC+BCD+DE，则最佳输出为 BC(A+D)+DE，与原来的相比节省了 2 个单位空间，因为这两个 BC 合二为一。

我的逻辑是，我会尝试找出表达式中出现频率最高的元素，并将其分解出来。然后我递归地调用该函数对分解的表达式做同样的事情，直到它被完全分解。但是，我怎样才能找到原始表达式中最常见的元素？也就是说，在上面的例子中，BC? 似乎我必须尝试所有不同的元素组合，并找出每个组合在整个表达式中出现的次数。但这听起来真的很幼稚。第二

有人可以提示如何有效地做到这一点吗？甚至我可以在 Google 上搜索到的一些关键字也可以。

4

6 回答 6

5

您正在寻找的是一种最小化布尔函数的方法。这是芯片设计社区特别感兴趣的事情。用于您的目的的一种技术是Quine-McCluskey 算法，或者您可以使用Li-aung Yip 在评论中建议的卡诺图。

于 2012-07-04T08:05:18.287 回答
4

抱歉，我还没有阅读所有那些很酷的算法，但是你问到找到共同因素，所以我想到了以下内容：

import itertools
def commons(exprs):
    groups = []
    for n in range(2, len(exprs)+1):
        for comb in itertools.combinations(exprs, n):
            common = set.intersection(*map(set, comb))
            if common:
                groups.append(
                            (len(common), n, comb, ''.join(common)))
    return sorted(groups, reverse=True)

>>> exprs
['ABC', 'BCD', 'DE', 'ABCE']

>>> commons(exprs)
[(3, 2, ('ABC', 'ABCE'), 'ACB'),
 (2, 3, ('ABC', 'BCD', 'ABCE'), 'CB'),
 (2, 2, ('BCD', 'ABCE'), 'CB'),
 (2, 2, ('ABC', 'BCD'), 'CB'),
 (1, 2, ('DE', 'ABCE'), 'E'),
 (1, 2, ('BCD', 'DE'), 'D')]

该函数返回一个按以下顺序排序的列表：

  1. 公因数的长度
  2. 具有该公因数的项数
于 2012-07-04T08:28:50.347 回答
2

使用Quine-McCluskey算法来最小化布尔表达式。它在功能上等同于卡诺图方法，但更适合在计算机上实现。

于 2012-07-04T08:17:38.983 回答
2

您可能还想查看Espresso 启发式逻辑最小化器。

于 2013-10-30T18:34:44.327 回答
1

不幸的是，大多数给定的建议可能实际上并没有给@turtlesoup 他/她正在寻找的东西。@turtlesoup 要求一种方法来最小化给定布尔表达式的字符数。大多数简化方法不会将字符数作为简化的重点。当谈到电子产品的最小化时，用户通常希望门（或零件）的数量最少。就表达式的“长度”而言，这并不总是会导致更短的表达式——大多数时候会，但并非总是如此。事实上，有时表达式可能会变得更大，就长度而言，尽管从电子学的角度来看它可能更简单（需要构建更少的门）。

boolengine.com 是我所知道的关于数字电路布尔简化的最好的简化工具。它不允许数百个输入，但它允许 14 个，这比大多数简化工具要多得多。

在使用电子产品时，简化程序通常将表达式分解为乘积之和形式。所以表达式'(ab)+'cd 变成了'c+'b+'a+d。“简化”结果需要更多字符作为表达式打印，但从电子学的角度来看更容易构建。它只需要一个 4 输入 OR 门和 3 个反相器（4 个部件）。而原始表达式需要 2 个 AND 门、2 个反相器和一个 OR 门（5 个部分）。

把@turtlesoup 的例子给BoolEngine 后，显示BC(A+D)+DE 变成了E+D+ABC。这是一个较短的表达式，通常是。但肯定不总是。

于 2014-10-02T14:55:34.697 回答
0

这是一个实现卡诺图的小程序：http ://www-ihs.theoinf.tu-ilmenau.de/~sane/projekte/karnaugh/embed_karnaugh.html

您可以输入表达式或填写真值表。

于 2012-10-23T12:57:44.057 回答