5

我正在处理布尔函数，我只能（但安全地）假设它们作为 SOP 进来并且不包含否定（例如(A && B && C) || (A && B && D)）。析取的数量通常> 5，连词的数量通常> 10。

因为在我的情况下，计算每个变量的值是困难的，并且结果被认为是短暂的，所以我需要能够最小化关于变量出现的所述函数。这种最小化的结果不需要是任何正常的形式，并且可以嵌套任意深度。

之前问过类似的问题，SO指出了使用扇出最小化、卡诺图、QM 或 BDD 的一般解决方案。在处理这些方法之前 - 这会大量破坏我的代码 - 我想仔细检查关于输入函数的先验已知事实是否不会产生使用更小但不太通用的最小化方法的可能性。

应用吸收和分配定律的 AFAICS 将始终提供最小形式。是否有可能利用函数作为 SOP 出现并且没有否定的事实？在我看来，应该有一个对变量进行简单交集和联合操作的递归算法，以产生所需的结果。

有人能描述一下那个算法吗？

编辑：征求意见：在对该主题进行了一些研究之后，在我看来，这里提出的问题等同于找到给定函数的减少 BDD 的最佳变量排序。

背景：最小化的函数被传递到作业队列以计算所有所需变量的值。之后对函数进行评估。考虑应用示例：

  • 输入函数 (A && B && C) || (A && B && D)可以写成A && B && (C || D)，这样就不必计算A和B两次。C和D的评估在作业队列中被序列化，因为只有其中一个需要被证明是正确的。
  • (A && B && C) || (A && B && C && D) || (A && B && X && E)简化为A && B && (C || (X && E))。X && E的评估被认为更难，因此在队列中放在C的评估之后， D的评估被丢弃。
4

4 回答 4

1

这是一个简单的算法：

让我们考虑一个例子：ABC+ABD

有

  • 2 项 T1 = ABC 和 T2=ABD
  • 4 个变量 A、B、C 和 D

首先将您的表达式转换为 2D 表（它不是 k-map）：

    T1  T2
A   1   1 
B   1   1   
C   1   0
D   0   1 

**begin** 
**While** the table is not empty do :
    **if** a row or a column have only zeros, **then** 
           remove it from table and continue. 
    **end if**
    **if** there is a row or more with only ones **then** 
           factor the vars corresponding to the rows 
           and remove the rows from the table 
    **else** 
           get the rows having a max number of ones, 
           do their scalar prod 
           from the scalar prod obtained, 
           get the columns corresponding to zeros (terms) 
           and put aside the one having a min number of ones 
           and remove its column from the table
    **end else**

**end while**

close brackets
**end**

适用于上表：

    T1  T2
A   1   1 
B   1   1   
C   1   0
D   0   1

迭代1： 有2行只有A和B，将它们分解并从表中删除：

表达式将以 : AB(... 开头，表格现在是 :

    T1  T2  
C   1   0
D   0   1

迭代 2： 没有行只有一个。两行的最大数量等于 1 ，它们的标量 prod 为 0 0 ，两列为零， T1 和 T2 都具有相同的数量 1 ，没有 min ，将其中一个放在一边，让我们拿 T1 并删除它来自表格：表达式将以：AB(T1+ and T1 is 1*C+0*D = C 表达式将以：AB(C+... 开头) 表格现在是：

    T2  
C   0
D   1

迭代 3： C 行只有 0，我们将删除它，D 行只有 1，我们将其分解并从表中删除

现在的表达式是： AB(C+D(...

桌子现在是：空的

迭代4： 表为空-> while 结束

右括号：

表达式为 AB(C+D)

它不是最佳算法，但不如 k-maps 通用，因为它考虑了表达式是 SOP 且没有否定的事实

于 2013-09-08T19:12:37.533 回答
0

从复杂性的角度来看，我认为有一些部分相关的结果似乎表明这个问题很难。

根据Elbassoni、Makino 和 Rauf 的“On the Readability of Monotone Boolean Formulae”（pdf 链接），很难确定 CNF 或 DNF 中的布尔公式是否可以重写为每个变量最多出现的公式k 次（对于 k >= 2）。请注意，此结果与问题陈述不匹配，因为原始公式不是单调的（即：可能包含否定）。

根据Goldsmith、Hagen 和 Mundelhenk 的“DNF 的复杂性和单调公式的同构”（pdf 链接），计算任意单调布尔函数的最小 DNF 是 NP 难的。此结果不完全匹配，因为原始公式未在 DNF 中给出，并且输出公式仅限于 DNF。

于 2013-09-09T20:15:54.867 回答
0

根据您的假设，您需要一个函数来评估您的签名，然后再执行所需的函数。

至少在 java 中，没有先验算法可以为您做到这一点，因此您需要对其进行编码并不断迭代，直到找到最通用的抽象。

布尔代数

在那里，您已经在逻辑中应用了所有属性，前三个对您最有用，因为您不想使用 NOT 操作。我希望这有帮助。

于 2013-09-06T13:00:17.577 回答
0

我会用“常识”算法来做；我不确定它是最优的，但在这种情况下很难表达“最优”。我假设您在评估条款的顺序上没有任何“偏好”，但这可以毫无困难地包含在程序中。

让x_1...x_n成为您的决策变量，y_1...成为每个y_m形式的连接子句：您希望最小化的表达式是的总和。prod_{i in I_j} x_ijj=1my_j

决策变量可以首先“分区”：

  • 如果它们出现在所有 中I_j，则无论如何都需要对其进行评估；首先执行此操作（然后将其从集合中删除I_j）
  • 如果它们没有出现在任何集合中I_j，则不需要对其进行评估（I(j)也将它们从集合中删除）。

如果x_i所有子句中出现的其中一个为假，则表达式为假；结尾。

否则，目标是找到一个集合I_j，例如所有的x_i都是真的（或证明不存在）。

I_j通过增加基数来排序，以最小化评估次数。保留一个数组（比如z_i），例如z_i=1ifx_i已经被评估为 true，否则为 false。对于该有序列表中的每个集合I_j：

对于每i一个I_j：

  • 评估x_i（如果z_i为假）；

    • 如果x_i为假，则删除I_j所有包含i.
    • 如果是真的，存储1并z_j继续

  • 如果这个循环结束（所有都x_i为真），则表达式为真。结尾。

  • 如果集合列表I_j为空，则表达式为假。结尾。
  • 否则，转到下一个I_j。

它的优点是实现起来非常简单，而且我相信应该非常高效。

于 2013-09-06T14:04:45.810 回答