2.6.1.3 H解释
解释I:谓词公式G在论域D上任何一组真值的指定称为一个解释。
H解释:子句集S在的H域上的解释称为H解释。
I是H域下的一个指派。简单地说,原子集A中的各元素真假组合都是H的解释(或真或假只取一个)。或者说凡对A中各元素真假值的一个具体设定,都是S的一个H解释。
由子句集S建立H域、原子集A,希望定义于一般论域D上使S为真的任一解释I,可由依于S的H域上的某个解释I*来实现。这样,便使任意论域D上S为真的问题,化成了仅有可数个元素的H域上S为真的问题了。从而子句集S在D上不可满足问题化成了H上的不可满足的问题。
几个术语的定义:
没有变量出现的原子、文字、子句和子句集,分别称为基原子、基文字、基子句和基子句集。基例:子句集S中某子句C中所有变元符号均以S的H域中的元素代入时,所得的基子句C'称为C的一个基例。
若一个解释I*使得某个基子句为假,则此解释I*为假。
|