对于析取范式构造的进一步分析

A FURTHER ANALYSIS ON THE CONSTRUCTION OF DISJUNCTIVE NORMAL FORM(DNF)

本文考虑具有优先代表资格的ＮＰ完全问题的对偶问题——析取范式永真性判定问题．本文从构造的角度对析取范式作了分析，得出了如下结果：在由ｎ个确定的命题变元所可能构成的一切不含均覆盖的析取范式中，含有三角式的析取范式占绝大多数．基于这个结果，本文得出了一个求解析取范式永真性判定问题的近似快速算法．

Considering the decision problem for validity of DNF,the following result is obtained by analysing the problem from the constructive view point:Among all DNFs without any equal covering generated by composing n definite proposition variables,those with property o easy decision,that is those having triangular forms,are in the most majority.Based on the above result,an approximately fast algorithm is obtained for the decision problem of DNF validity.