A generalization of the algorithm of Heidtmann to non-monotone formulas

[摘要] The following problem from reliability theory is considered. Given a disjunctive normal form (DNF) phi = phi(1) v...v phi(r), we want to find a representation of phi into disjoint formulas, i.e. find formulas eta(1),...,eta(s), such that phi = eta(1) v...v eta(s) and eta(i) boolean AND eta(j) = perpendicular to whenever i not equal j. In addition, the formulas eta(1),...,eta(s) must be simple enough that the computation of their probabilities is a simple task. Of course, it is also better if there is only a small number of formulas eta(i) in the representation. It has recently been discovered that this problem also appears in the calculation of degrees of support in the context of probabilistic assumption-based reasoning and the Dempster-Shafer theory of evidence (Kohlas and Monney, 1995). In this paper we present a new method to solve this problem, where each formula eta(1), is a so-called mix-product. Our method can be applied to any DNF, not only to monotone ones like the method of Heidtmann (1989). However, when applied to monotone formulas, both methods generate the same results. Compared to the algorithm of Abraham (1979) which can also be applied to any DNF, our method is considerably more efficient and will generate a much smaller number of disjoint terms in most cases (see Section 5).

[发布日期] 1996-12-17

[关键词] Boolean functions;decomposition methods;sum of disjoint products;reliability algorithms;assumption-based reasoning