We consider the problem of decomposing a positive DNF into a conjunction of DNFs, which may share a (possibly empty) given set of variables △. This problem has interesting connections with traditional applications of positive DNFs, e.g., in game theory, and with the broad topic of minimization of boolean functions. We show that the finest △-decomposition components of a positive DNF can be computed in polynomial time and provide a decomposition algorithm based on factorization of multilinear boolean polynomials.
展开▼
