I believe what you want your problem is: Given a boolean function $\phi$, find the set of its prime clauses (aka prime implicates) of a boolean function $\phi$. implicates). This is equivalent to finding all the prime implicants of $\lnot\phi$.How hard this is depends on the form
You will find in which $\phi$ is given (as was mentioned). The the paper A Knowledge Compilation Map contains many references to other papers that study discuss variants of this problem. For example, the paper Algorithms for various restrictions Selective Enumeration of Prime Implicants focuses on the representation of case when $\phi$.\phi$ is given in DNF or CNF (and also has many good references). Another interesting paper is Implicit and Incremental Computation of Primes and Essential Primes of Boolean Functions that represents the resulting set as a BDD, which may be much smaller than a simple list. (Though a ZBDD, invented later, might work even better.)
In short, there are lots of algorithms, none works fast all the time, but some might be fast enough in practice.
(Note: Knuth uses the term conjunctive prime form for the conjunction of prime clauses. This appears in fascicle 0 of volume 4 of TAoCP from 2005-2009. But the name didn't yet caught on.)
