algorithm - 最小化 SOP 形式 bool 函数的方法

Question

我正在处理 bool 函数，我只能(但安全地)假设它们作为 SOP 出现并且不包含否定(例如 (A && B && C) || (A && B && D)).析取数通常 > 5，内连词数通常 > 10。

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

之前问过类似的问题，SO points到使用扇出最小化、卡诺图、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 的评估被丢弃。

Answer 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(... table 现在是:

    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行只有零，我们将删除它，D行只有一个，我们将其分解并从表中删除

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

表格现在是空的

迭代 4:表是空的 -> 结束

右括号:

表达式为AB(C+D)

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