Given a finite set of statements known to be true, I need to derive all the "non-redundant" statements in disjunctive form using only literals that can be derived from this set of statements, i e all statements on the form (a ∨ b ∨ c ∨ ...) where a, b ... are literals. By non-redundant I mean that I do not wish to include a statement if one of the literals could be removed and it would still always be true (given the initial set of statements).


Another way of looking at this would be that I want a statements in conjunctive normal form, but that includes all non-redundant statements as the inner groups, not just the minimal set equivalent to the initial set of statements.


A naive algorithm for this would be to test all assignments of truth values to literals, keeping only the ones that 1) are true given the initial set of statements 2) are non-redundant (tested by assigning false to each of the literals in the statement, checking if it still remains slow). However, the number of literals I'll be working with will be so large that this naive approach is not feasible.


**Edit:**


What I'm looking for is an algorithm that will efficiently produce the set of statements as described above, such as the strategies that can be used to convert to a conjunctive normal form.



Deriving the complete set of "non-redundant" true statements in disjunctive form in propositional logic
I believe your problem is: Given a boolean function $\phi$, find the set of its prime clauses (aka prime implicates). This is equivalent to finding all the prime implicants of $\lnot\phi$.


You will find in the paper [A Knowledge Compilation Map](http://scholar.google.co.uk/scholar?cluster=4020517321592725796) many references to papers that discuss variants of this problem. For example, the paper [Algorithms for Selective Enumeration of Prime Implicants](http://scholar.google.co.uk/scholar?cluster=3018518818059820501) focuses on the case when $\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](http://scholar.google.co.uk/scholar?cluster=9792089307967946883) 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](http://www-cs-faculty.stanford.edu/~uno/taocp.html) from 2005-2009. But the name didn't yet caught on.)


