可满足赋值算子的设计与实现  

Design And Implementation of a Satisfiable Assignment Operator

作　　者：王倩[1] 陈彩[1] 吕关锋[1] 苏开乐[2] 

机构地区：[1]北京工业大学计算机学院,北京100124 [2]北京大学信息科学技术学院,北京100871

出　　处：《计算机工程与科学》2010年第9期139-141,168,共4页Computer Engineering & Science

摘　　要：在很多应用领域中,我们都需要获取逻辑公式所有无冗余的可满足解集合,即集合中的任意两个解不能互相蕴涵。为了获取无冗余解集合,本文提出了两种实现方案。由于二叉决策图BDD具有对逻辑公式的高效表达特性,因此两种方案都是在逻辑公式转换成BDD的基础上实现的[1]。一种方案是直接对该BDD进行遍历,获取从根节点到终端节点1的所有路径集合,然后借助一致性理论获取无冗余解的一致性算子的实现。另一种方案借助香农分解定理对BDD先进行逐层分解,然后对分解后的BDD再进行一致性运算的可满足赋值算子的实现。本文最后对两种方案的实验效果进行对比分析。In some applications,we need to obtain the set of all satisfiable assignments of a Boolean function,in which assignments can not imply each other. Therefore,we introduce two solutions based on the expression of BDD for the Boolean function. One of the solutions is the Consensus Operator. In order to do that,what we need to do is to obtain all the paths starting from the root node to the terminal node that is labeled with 1 because it is very trivial to see that every path represents a satisfiable assignment. Then we will get the un-redundant assignment by the consensus law. The other solution is the satisfiable assignment operator. We need to to decompose BDD by the Shannon＇s decomposition and then execute the consensus operator. Finally,the paper will present some of our experimental results for the two schemes respectively.

关 键 词：BDD 一致性理论 可满足赋值算子 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]