在SOP格式中最小化布尔函数的方法

Question

我正在处理布尔函数,我只能(但安全地)假设它们作为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的评估被删除.

Answer 1

根据您的假设，在执行所需的函数之前，您需要一个函数来评估您的签名。

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

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