论文部分内容阅读
逻辑系统在人工智能及计算机科学中有相当广泛的应用。人们不但利用它们来对知识进行表示和推理,还非常关心它们之间的表达能力关系。表达能力比较的标准并不唯一。一种经典的标准是逻辑等价关系,可是在这种比较标准下,许多具有非常不同特征的逻辑系统被认为是等价的。比如,命题逻辑、命题缺省逻辑、命题限制理论等在这个标准下是完全等价的,但前者是单调逻辑而后两者是著名的非单调逻辑且推理难度(指模型存在判定,下同)广泛认为比前者要高一层。这样,在逻辑等价关系下不能很好地区别各种逻辑系统。
另一种标准是由Gogic等提出的简洁性标准,即在逻辑等价的前提下,考察不同逻辑系统表示同一组模型时所需的公式长度,或者说知识库的大小。这种办法可以将逻辑等价的一些逻辑与另一些区别出来,比如命题缺省逻辑就比命题逻辑要严格简洁。但简洁性标准不考虑转换公式所需要的时间,也就是说,一个系统的知识库转换成等价的另一个系统下的知识库可能花指数时间。
赵希顺与Hans Kleine Buening提出了一种弱化的比较方法,即模型等价归约,这种转换不要求严格的逻辑等价性,但要求转换是可以快速计算的,而且转换前后的公式的模型有——对应的快速计算关系。这在实际应用中的意义是:模型等价归约允许我们快速地对一部分不同逻辑系统的知识库进行互相转换推理。比如回答集逻辑程序被认为是严格简洁于命题逻辑的,虽然它们的推理难度相同(均为NP完全),在要求刻画相同模型的情况下,一个逻辑程序转成命题逻辑公式最难时会有指数增长。但在模型等价归约下,它们表示能力是一样的,即我们可以快速地在两种数据库间进行转换推理。不过,模型等价归约并不能对同一推理难度完全实现互相快速转换,比如赵希顺与Hans KleineBuening等发现带存在量词的命题公式((E)PF)就似乎比命题逻辑,逻辑程序都要强,因此提出一个猜想:在模型等价归约下,(E)PF是模型判定问题在NP类中的那些逻辑系统中最强的吗?
本文对这个猜想作出以下回答:
●在所有模型检测问题在NP中的NP逻辑系统中,(E)PF是最强的(极大的)。
●在所有模型检测问题在P中的NP逻辑系统中,PF(命题逻辑)是最强的(极大的)。
●一般而言,我们猜测不存在极大的NP逻辑系统,因为存在一些NP逻辑系统在多项式时间模型等价归约下是不可比较的。