第二章 归结推理方法

　　2.3.2 H解释
　　由子句集S建立H域、原子集A，希望定义于一般论域D上使S为真的任一解释I，可由依于S的H域上的某个解释I*来实现 。这样，便使任一论域D上S为真的问题，化成了仅有可数个元素的H域上S为真的问题了。从而子句集S在D上的不可满足问题化成了H上的不可满足问题，这是很有意义的结果。
　　以　S={P(x)∨Q(x),R(f(y))} 为例，有
　　　　H={a,f(a),f(f(a)), …}
　　　　A={P(a),Q(a),R(a),P(f(a)),Q(f(a)),R(f(a)),…}
　　凡对A中的各元素真假值的一个具体设定，都是S的一个H解释。如
　　I1*={P(a),Q(a),R(a),P(f(a)),Q(f(a)),R(f(a)), …}
　　I2*={～P(a),～Q(a),～R(a),～P(f(a)),Q(f(a)),R(f(a)), …}
　　I3*={P(a),～Q(a),～R(a),P(f(a)),Q(f(a)),～R(f(a)), …}
　　I1*,I2*,I3*中出现的P(a)指P(a)取值为T，出现的～P(a)指～P(a)=T或说P(a)取值为F。显然在H域上，这样定义的I*下，S的真假值就确定了。如
　　　　S|I1*=T， S|I2*=F， S|I3*=F
　　这是因为
　　　　S={P(x)∨Q(x),R(f(y))}
　　的逻辑含义是
　　　　(x)(y)((P(x)∨Q(x)) ∧R(f(y)))
　　而论域 H={a,f(a),P(f(a)), …}。
　　我们关心的是，对论域D上的任一解释I，若有S|I=T，如何求得一个相应的H解释I*，使得S|I*=T成立。
　　可通过两个例子来说明由I寻求I*的过程。
例题 例1:
  　S={P(x),Q(y,f(y,a))}
　有 H={a,f(a,a),f(a,f(a,a)),f(f(a,a),a),f(f(a,a),f(a,a)),…}
　　 A={P(a),Q(a,a),P(f(a,a,)),Q(a,f(a,a)),Q(f(a,a),a),Q(f(a,a),f(a,a)),…}
　设 D={1,2}，解释I作如下设定
a f(1,1) f(1,2) f(2,1) f(2,2)  
2 1 2 2 2 1
P(1) P(2) Q(1,1) Q(1,2) Q(2,1) Q(2,2)
T T F T T F
　于是有
　　S|I= P(1) ∧ Q(1,f(1,2)) 　 对应 x=1,y=1
　　　　∧P(1) ∧ Q(2,f(2,2)) 　对应 x=1,y=2
　　　　∧P(2) ∧ Q(1,f(1,2)) 　对应 x=2,y=1
　　　　∧P(2) ∧ Q(2,f(2,2)) 　对应 x=2,y=2
　　　=T
　可按下列对应方法来选取相应的I*，依I取
　　a→2
　　f(a ,a)→f(2,2)→1
　　f(a ,f(a ,a))→f(2,1)→2
　　f(f(a ,a,),a)→f(1,2)→2
　　f(f(a ,a),f(a ,a))→f(1,1)→1
　　…
　　P(a)→P(2)→T
　　Q(a ,a)→Q(2,2)→F
　　P(f(a ,a))→P(1)→T
　　Q(a ,f(a ,a))→Q(2,1)→T
　　Q(f(a ,a),a)→Q(1,2)→T
　　Q(f(a,a),f(a,a))→Q(1,1)→F
　　…
　于是得对应于I的
　　I*={P(a),～Q(a,a),P(f(a,a)),Q(a,f(a,a)),Q(f(a,a),a),～Q(f(a,a),f(a,a)), …}
　在I*下S的真值
　　S|I* =P(a)∧ Q(a,f(a,a))
　　　　　　　(x=a,y=a 对应于x=2,y=2)
　　　　　∧P(a) ∧ Q(f(a,a),f(f(a,a),a))
　　　　　　　(x=a,y=f(a,a)对应于x=2,y=1)
　　　　　∧P(f(a,a)) ∧ Q(a,f(a,a))
　　　　　　　(x=f(a,a)),y=a对应于x=1,y=2)
　　　　　∧P(f(a,a)) ∧Q(f(a,a),f(f(a,a),a))
　　　　　　　(x=f(a,a),y=f(a,a)对应于x=1,y=1)
　　　　　∧P(a) ∧ Q(f(a,f(a,a)),f(f(a,f(a,a)),a))
　　　　　　　(x=a,y=f(a,f(a,a))对应于x=2,y=2)
　　　　　…
　　　　=T
例题 例2:
  　S={(P(x)∨ Q(x),R(f(y))}S中不出现常量符号。
　H={a,f(a),P(f(a)), …}
　A={P(a),Q(a),R(a),P(f(a)),Q(f(a)),R(f(a)), …}
　仍设D={1,2}，解释I作如下设定
f(1) f(2) P(1) P(2) Q(1) Q(2) R(1) R(2)
2 2 T F F T F T

　于是有S|I=T
　由于I对常量符号a没有设定，这时a 设定1或2(D中元素)，便有相应于I的两H解释I1*和I2*，同例1的计算得
　　I1*={P(a),～Q(a),～R(a),～P(f(a)),Q(f(a)),R(f(a)),～P(f(f(a))),Q(f(f(a))),R(f(f(a))), …}
　　I2*={～P(a),Q(a),R(a),～P(f(a)),Q(f(a)),R(f(a)),～P(f(f(a))),Q(f(f(a))),R(f(f(a))), …}
　有S|I1*=T， S|I2*=T。
　这样便实现了由I来确定相应的I*的问题，实际上仅依I对S中出现的个体及函数符号的设定，随之对A的元素的设定，这样便将I*建立起来了。
　严格地说由I到I*，实为H域到D域的映射，对H中每个常量、每个函数依I来规定D中的一个确定的元素。可如下递归定义：
　若S中有常量符号，任一a∈H0，在I下a取值为a0,就规定a→a0。
　若S中无常量符号，H0={a},就规定a→a0,而a0是D中任一元素。
　若f(, …,)是 S中任一函数符号，任取(h1,…,hn)∈(=Hi×…×Hi 共n个)。当在I下(h1,…,hn)取值为(,…,)，且在I下对应值为f(,…,)(为D的元素)，就规定
　　　f(h1,…,hn)→f(,…,)
　这样已依I确定了H中元素到D的映射值，而S中的谓词完全对应于I中的设定，便得I*，于是可得
定理 定理 2.3.2(1)
  　设I是S的论域D上的解释，存在对应于I的H解释I*，使得若有S|I=T，必有S|I*=T。
定理 定理 2.3.2(2)
  　子句集S是不可满足的，当且仅当在所有的S的H解释下为假。
证明 证明
  　S 在一般论域D上是不可满足的，必然在H域上是不可满足的。
　反过来，依定理2.3.2(1)，若S在任一H解释I*下均为假，而S在某个解释I下为真，这是不可能的。因S在某个I0下为真必有I0*存在，使得S在I0*下也为真。
　这个定理将S在一般论域D上的不可满足问题化成了可数集H上的不可满足问题。今后的讨论只需在S的H域上进行了，不必再涉及一般论域D。所谈的解释不作说明都认为是H解释了
定理 定理 2.3.2(3)
  　子句集S是不可满足的当且仅当对每个解释I下，至少有S的某个子句的某个基例为假。
　因为S的逻辑含义是所包含的子句的合取，而且变量受全称量词作用。那么在某个解释I(均指H解释)下为假，只需某个子句的某个基例为假，而S是不可满足要求在任一解释下均为假，从而定理2.3.2(3)成立。这个结果常被引用。