-
题名NT-HIT(k)公式的存在性
- 1
-
-
作者
赵英阳
许道云
-
机构
贵州大学计算机科学系
-
出处
《贵州大学学报（自然科学版）》
2005年第2期169-175,共7页
-
基金
贵州省高层次人才特助经费资助
贵州省自然科学基金资助课题
-
文摘
一个合取范式(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公式
不可满足公式
鸽巢原理
-
Keywords
non-tautology, hitting formula, unsatisfiable formula, the pigeon-hole principle.
-
分类号
O141.3
[理学—数学]
TP301.5
[理学—基础数学]
-
