贵州大学学报（自然科学版）
貴州大學學報（自然科學版）
귀주대학학보（자연과학판）
JOURNAL OF GUIZHOU UNIVERSITY(NATURAL SCIENCE)
2005年
2期
169-175
,共7页
非重言式%Hitting公式%不可满足公式%鸽巢原理
非重言式%Hitting公式%不可滿足公式%鴿巢原理
비중언식%Hitting공식%불가만족공식%합소원리
一个合取范式(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]中的两个公开的问题.
一箇閤取範式(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]中的兩箇公開的問題.
일개합취범식(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]중적량개공개적문제.
