可满足性问题的充分必要条件

1、中苗科技200712可满足性问题的充分必要条件郭成(淮爭工孕Itlt理科学从.江苏连云港222005)M鼻：可沟足鼻问题是计算机和人工智能领城内的一个*要的冋豪.是杲一个祓证明是NPC的问是.*丈主矣杞子句皋邊行分给出转定义、角草集定义，转同构定义.畀且证胡转同构不凍变子句集的可満足性.论丈证明了可満足子句舉的三个尢矣*件.并且it些尢要条件才以用于判斷可沟足问恳的完仝搜索和不完金搜索算決.关子句集；賦值；樓；两草集；*)#；转同构Sufficientandnecessaryczditk心forSAT.GUOCheng(MathematicsandPhysicsDepartmentHuaiHa

2、iInWMecftechnology,JiangSu,LianYunGang222005)Abstract:SatisfiabilityproblemsbbrevuttedtoSTicaveryimportantproblemincomputerscienceandartificialintelligenceandisfirstlyprovediobtaNPCproblemInthispaper,thesetsofclausesareresearched,givingthedeGnitionsofflipping,simplesetsofclausesandflippingisomorphis

3、m.Moreover,Iprovethatflippingdoesn9taffectthesatisfiabilityofasetofclausesandthreesufficientandnecessaryconditionsareproved.Intheendofthispaper,itissimplydiscussedthattheseconditionscanbeutilizedincompletealgorithmandincompletealgorithmofSAT.Keywords:setsofclausesiassignment,modelssimplesetsiflippin

4、glflippingisomorphism1引亩可满足性问题(satisfiabilityproblem,简称SAT)是指合取范式的可满足性问题.简单可以叙述为，对于个合适公式.通常我们假定已经转化为CNF的形式.即一个合取范式.那么是否有一个算法能在多项式的时间内找到该公式的一个赋值，使的其真值为真吗？逻辑公式的可满足性判定是计算机和人工智能领域内的一个重要的问题，解决SAT问题对解决数学、计算机科学.电子工程技术中的些实际问题都有非常柬要的意义对于可满足性SAT问题.己经被证明是一个NPC问题，并且是第一个被证明是NPC问题，详见文献命题原子。表朋命題的符号，用小写字母表示。文字。甜题原子

5、和命题原子的否定统称为文字.命聽原子称为正文字.命题原子的否定称为负文字。例如P为命题原子.同时也是一个止文字.-P为命题原子P的否定，同时也是一个负文字。子句有限个文字的析取.例如，子句。子句集有限个子句构成的集合.命题原子集。一个子句集中的所有的原子的集合.賦值命毬原子集到集合P的映射，T表示真值为真.F茨示真值为假。可满足模。对于一个子句集S.如果存在一个赋值中使得S中的每个子句在该赋值下的真值为真，那么称S是可满足的.并且称赋值中为S的一个模.例如：子句集S=p,V-V2VV祁22祁”-7rp小F、PVp2Vpj命题原子集合*P|，PPJ赋值中I:Vi(Pi)=7,Vl(p2)=7，V

6、i(P)=赋值幻:V1(A)-7.V|(P2)-Ftvl(p3)=7其中在赋值中2下，S中的每个子句真值为真，所以幻是S的一个模。显然，如果一个子句集S的命題原子集A中的原子个数为n,那么S的不同赋值的数目为2J判断S是否可満足，可以通过鲨证2个赋值中.哪个是其模.这样最坏的情况是要验证2次显然这样的算法量坏复杂度为2J比如，不可满足子句集便需要全部验证完毕才能给出结论.到目前为止.判定SAT问题算法最坏的情况都是指数的，不过算法平均意义上是多项式的，见文献叫对于2-SAT问JS有线性的时间复杂度的算法，对于Horn子句集，己经有线性的时间复杂度的算法，见文献2可満足子旬集的件2.1關转同构收

7、稿日期：2007-11-15修回日期：2007-12-04墓金项目：淮海工学院校内基金(项目号:I200532)作看简介：郭成(1972-),男.汉族.河北怀安.硕士研究生.应用数学。定义1翻转P如果s中有子句包含有文字P,则把P改写为如果S中有子句包含rp.则把改写成P,称翻转P。若詡转I中的每个原子，称翻转1例1.S=p,V-ip,Vp,-ip,Vp,V-p,p,Vp,Vp,1=PPjo若翻转P,则可以由s得到一个新的子句集s：s=(-p*-papP,Vpf,-,p(Vp：VpJ.若翻转I,则可以由s得到一个新的子句集s“，并且s=(PfVp2-IP,V-ip2Vp,p,v-in.,Vp,

8、o定理1若S为个子句IA,翻转T,得到-个新的子句集S,则S町满足当冃.仅当S可滿足。证明：必要性证明，即S可满足，证明S可满足。因为S可满足，令W为S的一个模。由中构造S的一个賦值2:弋pwAV(p)=7.如果pe/,v(p)=F:中(P)=F.如果pe/,v(P)=7:V(P)=V(P)f如果卜面证明中为s的模。令c是s中的任意-个子句，则S中的一定存在子句C,翻转I时，由C得到。2为5的模.C在V下的真值为真.则C中有文字L,L在w下真值为真。如果L为正文字P,则V(P)=7如果则中P在C中.翻转I.P被SS转，rtic得到c；所以c中有负文字所以c在中下的真值为真。如果PW则w(p)7

9、(p27。P在C中.翻转I,P没有被翻转.由C得到C；所以C中有正文字P.所以C在中下的真值为真。如果L为负文字卡，则W(P2F,如果pwl.则V(P)=7e-P在C中，翻转1.P被朋转，由C得到C；所以C*有止文字P,所以C在W卜的真值为真。如果P电I则V(P)=M/(P)-A。在C中.翻转I.P没佇被翻转.由c得到C；所以C中有负文字F,所以C在/下的真值为真。由上可知.对FS中的任氫个子句C在w卜宾值为真。所以“为S的一个模。充分性证明.即S可满足.证明S可满足。s可满足.令中为s的一个模。由中构造S的一个赋值中:PP如果,V(p)-F:W(P)=F,如果pw/,V(p)=7:V(P)=

10、V(p).如果poF面证明w为S的模。令(:是s中的任意一个子句.乱转I,由c得到s中的了句c：0为S的一个模.c在中F的真值为真.则c中有文字L,L在/下的真值为真。如果L为正艾字F.则w27.如境Pf则wWfP在c中.转I.P被18转.由C甬到0斫以C中有负文字4所以下的真值为如果pJ,则WS2中(刃二7。P在C中，翻转1,P没有被詡转.由c得到c.所以c中冇正文字p,所以crr：w卜的真值为真。如果L为负文则v(p)=F.如果,则V(P)=7。在C中，翻转I,P被翻转，由C得到C；所以C中有止文字P,所以C在w卜的真值为真。如果pel则v(P)-v(P)=oPACK翻转Ip没有被翻转.由

11、C得到C：所以C中有负文字rp.所以C在中卜的真值为真。由卜-可知.对于s中的任意-个子hjc在中卜真值为真.所以中为S的一个模。证明完毕。曲定理1可知，翻转不会彩响一个了句集的可满足性。并且如果子句集S翻转I得到子句集S；则子句集S也町以翻转I得到子句集S。由此给出如下定义：定义2如果f句集S通过翻转1得到子句集S；则称这两个子句集是翻转同构的。2.2简单集定义3简单集正简单集如果S中的每个子句都至少包含冇个正文字.则称S为正简单集。例如PZ祁二VPv-Plvp：vrPp(vp?V为一八正简单集。负简单集如果S中的每个f句都至少包含有一个负文字，则称S为负简单集。例如，为一个负简单集；止简单

12、集和负简单集统称为简单集中科技200712定理2S如果为一个简单集，则S为可满足的.证明：如果S为一个正简单集，则给出S的赋值v：v(p)=75，由于S中的每一个子句都有正文字，所以每个子句在賦值w下的真值为真，即賦值w为S的一个模，S可满足.如果S为一个负简单集，则给出S的赋值v：v(P)=FgA,由于S中的每一个子句都有负文字，所以每个子句在赋值w下的真值为真，即赋值w为S的一个模，S可满足.2.3三个充豪条件定理3S是可满足的充要条件是S翻转同构一个负简单集.证明：充分性的证明.若SIB转同构一个负简唯集，由定理2,负简单集可满足，由定理1可知，S可满足.必要性的证明.由于S可满足，则存

13、在使得S可满足的一个模中.令/=plw(p)=7,pw/,翻转I，则得到一个子句集S；下面证明S为一个负简单集.对于S中的任意一个子句C；由于S是翻转1御到，故一定存在S中的子句C,翻转I,由C得到C.V是s的一个模，所以C在W下的真值为真，所以C中有文字L,在中下L的真值为真.a)L是一个正文字P,w(p)=7,则p“，所以P被翻转，因此C中有负文字B)L是一个负文字，叭则p軽/,所以没有IH转P,因此C中有负文字卩。所以中的任意一个子句都有一个负文字，故咼一个负简单集。定理4S是可满足的充要条件是S翻转同构一个正简单集.证明：(1)充分性的证明.若SIB转同构一个负简单集，由定理2,负简单

14、集可满足，由定理1可知，S可满足.(2)必要性的证明.由干S可满足，则存在使得S可满足的一个模*令/plW(P)F,peQ8翻转I,则得到一个子句集S；下面证明S为一个正简单集.对于S中的任意一个子句C,由于S超19转得到，故一定存在S中的子句C,翻转I,由C得到CV是S的一个模，所以C在W下的真值为真，所以C中有文字L,在中下L的真值为真.C)L是一个正文字P理(P”匚则P“，所以P没有被翻转，虫此C中有正文孑PG).是一个魚文字几中(刃=尸，則P,所以P被製转，因此C*肴正文字P所以s中的任意一个子句c都有一个正文字，故s是一个正简单集.由定理3和定理4可以得到：定理5S是可满足的充要条件

15、是S8转同构一个简单集.3剜初转不改变子句集合的可满足性，可满足子句集翻转同构简单集.利用本文给出的充娶条件，可以判斷一个子句集是否为可满足的，并且可以用来给出对子句集的模的不完全技索算法，也可以给出完全搜第算法，本文只是证明三个充要条件，由于篇幅，算法具体问题不进行详细具体讨论.希文敵：L1JSACookThecoaplexityoftheorerprovingprocedure(JACMS/BposiusonTheoryofcomputing,1971(3):151-158S.Ben-Davis.B.Chor,0.Goldre)chfHLuby.OnthetheoryofaveragecasecoplexityJJof*CoaputerandSystemsSciences,1992(44):193-219B.AspvalltM.F.Plass.R.E.TarianALinear-tinealgorithafortestingthetruthofcertainquantifiedBooleanforulas(刀IPL.】9798(3):121-123W.F.Dowling,J.H.