Reducing number of operations in a disjunctive normal form

Question

Suppose that we have some big DNF which doesn't have any redudant members (for example, if it contains $x_i$ then it can't contain something like $x_ix_j$). My question is: is there some effective algorithm that can reduce, if possible, this DNF to the form (by grouping some members) with the smallest amount of logical operations "or" and "and" in it. If there is no any effective, so what is the most effective one?

Answer 1

There is such an algorithm: but it is extremely inefficient: given your original DNF $\phi$ say, enumerate all formulas $\psi$ that contain no more symbols than $\phi$ and contain no variables that are not in $\phi$; then find the shortest such $\psi$ that is equivalent to $\phi$. If you could find the desired formula $\psi$ efficiently, than you could efficiently solve UNSAT, the converse of the boolean satisfiability problem. But UNSAT is co-NP-complete, so I don't think we know much about the most effective solution to your problem. The large body of research on SAT-solving and logic circuit optimization may provide you with some useful algorithms.