可满足赋值算子的设计与实现
收稿日期: 2010-03-14
修回日期: 2010-06-12
网络出版日期: 2010-09-02
Design And Implementation of a Satisfiable Assignment Operator
Received date: 2010-03-14
Revised date: 2010-06-12
Online published: 2010-09-02
王倩1,陈彩1,吕关锋1,苏开乐2 . 可满足赋值算子的设计与实现[J]. 计算机工程与科学, 2010 , 32(9) : 139 -141 . DOI: 10.3969/j.issn.1007130X.2010.
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 unredundant 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.
/
| 〈 |
|
〉 |