用均覆盖和锥形式对析取范式的结构分析及其近似快速求解算法

AN ANALYSIS ON THE CONSTRUCTION OF DISJUNCTIVE NORMAL FORM(DNF) BY MEANS OF EQUAL COVERING AND CONE FORM

本文对析取范式的结构作了结构分析，得出了如下结果：在恰由ｎ个确定的命题变元所可能构成的一切析取范式中，含均覆盖的析取范式的比例当ｎ趋于无穷大时等于１．在其余的析取范式中，含锥形式的比例当ｎ趋于无穷大时亦等于１．基于分析结果，给出了一个判定析取范式永真性的快速算法．

By analysing the construction of DNF, the following results are obtained: among all DNFs generated by composing n definite proposition variables,most of the DNFs are with equal covering when n approaches infinity. For those DNFs without equal covering, most of them are with cone form. Based on the above result, an approximately fast algorithm is obtained for the decision problem of DNF validity.