【作者】 赵英阳； 许道云；

【机构】 贵州大学计算机科学系；

【摘要】 <正> 1 引言我们称一个极小不可满足(minimal unsatisfi-able)公式(简称,MU公式)F是最大的(maximal),如果增加任意一个文字L(L∈lit(F))到F的任一子句C中后(请注意:L(?)C,产生的公式不再是极小不可满足公式(此时,新公式是一个可满足公式)。MAX表示最大的MU公式,MAX(k)=MU(k)∩MAX。对应地,一个MU公式F是边缘的(mar-ginal),如果从F中删去任意一个文字后,得到一个非极小不可满足公式MARG表示边缘的MU公式集且MARG(k)=MU(k)∩MARG。更多还原

【Abstract】 Based on the conditions of NT-HIT formula, we construct a proposition formula Hn,m such that Hn,m is satisfiable if and only if there exists a NT-HIT formula F with n variables and m clauses . By the properties of Hn,m , we prove that for any formula F∈NT-HJT(1) there exists a literal L occurring exactly once in F,and show that NT-HIT(k) is an empty set for k≥2. Thus, we solve positively two open problems in [1].更多还原