| NT-HIT(k)公式的存在性 |
| |
| 引用本文： | 赵英阳,许道云.NT-HIT(k)公式的存在性[J].贵州大学学报(自然科学版),2005,22(2):169-175. |
| |
| 作者姓名： | 赵英阳 许道云 |
| |
| 作者单位： | 贵州大学计算机科学系,贵州,贵阳,550025;贵州大学计算机科学系,贵州,贵阳,550025 |
| |
| 基金项目： | 贵州省高层次人才特助经费资助，贵州省自然科学基金资助课题 |
| |
| 摘 要： | 一个合取范式(CNF)公式F是NT-HIT公式，如果F中的任意两个不同的子句中恰有一对互补文字。NT-HIT(k)是公式的子句数与变元数之差为k的NT-HIT公式类。通过构造一个命题公式Hn，m，我们证明了：(1)Hn，m可满足当且仅当存在一个含有n个变元和m个子句的NT-HIT公式。(2)对于NT-HIT(1)中的任意一个公式F，存在一个文字L，L在F中仅出现一次。进一步，我们证明了：对于k≥2，公式Hn,n k是一个不可满足公式。于是，对于k≥2，NT-HIT(k)是一个空集。从而就解决了1]中的两个公开的问题。
|
| 关 键 词： | 非重言式 Hitting公式 不可满足公式 鸽巢原理 |
| 文章编号： | 1000-5269(2005)02-0169-07 |
| 修稿时间： | 2005年2月2日 |
The Existences of NT-HIT Formulas |
| |
| ZHAO Ying-yang,XU Dao-yun.The Existences of NT-HIT Formulas[J].Journal of Guizhou University(Natural Science),2005,22(2):169-175. |
| |
| Authors: | ZHAO Ying-yang XU Dao-yun |
| |
| Abstract: | |
| |
| Keywords: | non-tautology hitting formula unsatisfiable formula the pigeon-hole principle |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
