On Davis–Putnam reductions for minimally unsatisfiable clause-sets

DP-reduction , applied to a clause-set F and a variable v, replaces all clauses containing v by their resolvents (on v). A basic case, where the number of clauses is decreased (i.e., ), is singular DP-reduction (sDP-reduction), where v must occur in one polarity only once. For minimally unsatisfiable F∈MU, sDP-reduction produces another with the same deficiency, that is, δ(F′)=δ(F); recall δ(F)=c(F)−n(F), using n(F) for the number of variables. Let for F∈MU be the set of results of complete sDP-reduction for F; so fulfil F′∈MU, are nonsingular (every literal occurs at least twice), and we have δ(F′)=δ(F). We show that for F∈MU all complete reductions by sDP must have the same length, establishing the singularity index of F. In other words, for we have n(F′)=n(F″). In general the elements of are not even (pairwise) isomorphic. Using the fundamental characterisation by Kleine Büning, we obtain as application of the singularity index, that we have confluence modulo isomorphism (all elements of are pairwise isomorphic) in case δ(F)=2. In general we prove that we have confluence (i.e., ) for saturated F (i.e., F∈SMU). More generally, we show confluence modulo isomorphism for eventually saturatedF, that is, where we have , yielding another proof for confluence modulo isomorphism in case of δ(F)=2.