Abstract
We propose an approach for decomposing Boolean satisfiability problems while extending recent results of \cite{sul2} on solving Boolean systems of equations. Developments in \cite{sul2} were aimed at the expansion of functions in orthonormal (ON) sets of base functions as a generalization of the Boole-Shannon expansion and the derivation of the consistency condition for the equation in terms of the expansion co-efficients. In this paper, we further extend the Boole-Shannon expansion over an arbitrary set of base functions and derive the consistency condition for . The generalization of the Boole-Shannon formula presented in this paper is in terms of \emph{cofactors} as co-efficients with respect to a set of CNFs called a \emph{base} which appear in a given Boolean CNF formula itself. This approach results in a novel parallel algorithm for decomposition of a CNF formula and computation of all satisfying assignments when they exist by using the given data set of CNFs itself as the base.
Connections
Explore this paper’s authors, topics and related work.
Building this map preview
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Reviews 0
Write a review
No reviews yet.
Discussion 0
Add a comment
No comments yet.