基于回答集(或稳定模型)语义的逻辑程序(Answer Set Program,简称ASP),是一种描述性问题求解的范例。由于其非单调的本质特征和各种有效的回答集求解系统的出现,而被广泛应用于智能规划、诊断、调度等领域。相变(phase transition)是研究复杂系统性质的一种重要方法,在可满足性问题(SAT)和正规逻辑程序等方面获得了深刻的理论结果。析取逻辑程序回答集存在性等问题的复杂性在多项式分层上比正规逻辑程序高一层,本文研究析取逻辑程序的相变性质,主要包括:(1)证明了任何析取逻辑程序模等价于句法简单的析取逻辑程序,即对任何析取逻辑程序P,存在一个析取逻辑程序Q,其中的所有规则头中(至多)含有2个原子,规则体中(至多)含有两个文字,使得在限制到P中出现的原子集上时P和Q有相同的回答集。(2)证明了规则头中(至多)含有2个原子的最大析取逻辑程序回答集的存在性问题,规则体中文字数大于1时,最大逻辑程序没有回答集;规则体文字数为1时,最大逻辑程序有n个大小为n)1(-的回答集,其中n为程序中的原子数。(3)借用图的kernel性质,将判断逻辑程序是否具有回答集用能量函数表示出来,通过求解能量函数的基函数就可以判断该函数是否具有回答集。(4)实验结果表明,析取逻辑程序规则体中负文字比ratio?(0,1)时,随着nm/值增加,在某个关键值点有回答集概率由1迅速减为0,发生相变;随着nm/增加,求解回答集需要环的数量达到稳定值,等于n。对于ratio(28)1时,随着nm/值增加,程序存在回答集的概率会有一个“凹陷”现象,称为“首次半相变”,其中,n为程序中的原子数,m为程序中的规则数。