第三章 不确定和非单调推理方法

　　3.3.2 谓词完备化法
　　（1）△仅包含P(a)的情形
　　　　P(a)等价于
　　　　　　(x)(x=a→P(x))
　　这时，对P的完备化公式是
　　　　　　(x)(P(x)→x=a)
　　从而使得△对P完备。（若△＝A→B，那么～(B→A)是由△推不出来的，所以B→A∈△asm。从而△∪△asm=A←→B）。
　　△和其完备化公式的合取称作△对P的完备化，如以COMP[△,P]表示，便有
　　　　　　COMP[△,P]=(x)(Px)→x=a)∧△
　　　　　　　　　　　=(x)(P(x)←→x=a)
这个例子的谓词完备化同CWA方法有同样的结果。
　　（2） △含两个公式的情形
　　如△包含P(a)和P(b)。这时对P的完备化公式是
　　　　　　(x)(P(x)→(x=a)∨(x=b))
这个例子的谓词完备化同CWA方法也有同样的结论。
　　如果△中出现谓词P和其它谓词的析取，或P中含有变量时，谓词完备化就复杂些。
　　（3）△是对P单一子句情形
　　一个子句集对P是单一的，如果其中的每个带有正文字P的子句最多出现一次P。对P是单一的子句对P也是Horn 子句，但反过来并不一定对。如Q(a)∨～P(b)∨P(a)对P是Horn子句但对P不是单一的。
　　下面仅讨论对P是单一的子句的完备化问题。
　　设△是对P单一的子句集，可将△中每个含有正文字P的那些子句写成
　　　　　　(y)((Q1∧…∧Qm)→P(t))
　　其中t是项（t1,… tn）,Qi是不含P的文字，Qi和t都可含变量y。
　　上式可写成
　　　　　　(y)(x)(((x=t)∧Q1∧…∧Qm)→P(x))
其中x是不出现于t中的边元，x=t即x1= t1,… xn = tn 。
　　由于y不出现在蕴涵式的右端，该公式又等价于
　　　　　　(x)(((y)((x=t)∧Q1∧… Qm))→P(x))
(这里使用了公式(x)(A(x)→B)(x)A(x)→B)这种形式可视作一种标准形。
　　设△中有K个子句含有正文字P，这些子句的标准形为
　　　　　　(x)(E1→P(x))
　　　　　　　　　　　…
　　　　　　(x)(Ek→P(x))
而Ei是由存在量词约束的一些文字的合取。
　　将这些公式写成一个蕴涵式得
　　　　　　(x)((E1∨E2∨…∨Ek)→P(x))
　　这时便可得对P的完备化公式
　　　　　　(x)(P(x)→(E1∨E2∨…∨Ek))
　　于是
　　　　　　COMP[△,P]=(x)(P(x)←→(E1∨…∨Ek)∧△
例题 例3:
  　Δ是
　　(x)(Ostrich(x)→Bird(x))
　　Bird(Tweety)
　　～Ostrich(Sam)
其中Δ对Bird 是单一的。对Bird实现完备化，先写成标准形得
　　(x)((Ostrich(x)∨(x=Tweety))) →Bird(x))
　于是
　　COMP[△,bird]
　　=Δ∧(x)→(Bird(x)←→(Ostrich(x)∨(x=Tweety)))
在这个完备化公式集下，可证明～Bird(Sam)。

　　这个例子中，Δ告诉我们Tweety是鸟，Sam 不是驼鸟，所有的驼鸟都是鸟。而Δ对Bird 的完备化是提出一种假设的方法，指出了除Δ中的说明之外再没有别的鸟了，即只有Tweety 和Ostrich是鸟。引入这个假设后进行推理可知Sam不是鸟。
　　谓词完备化法对已知信任集Δ的扩充仅是一种最小的扩充。如Δ＝E(x)→P(x),所扩充的仅是使P(x)→E(x)成立的那些个体。
　　如果不限制Δ对P是单一的，这种完备化过程可能出现对P的循环定义，从而并没有给出新的假设。对P是Horn 的子句集也可使用这种完备化。
　　尽管在简单情形下，谓词完备化与CWA方法有同样的结果，但一般情况下它们是不同的。例如，Δ仅含P(a)，且可含有常量b时，CWA法的假设集包含～P(b)，而谓词完备化公式是(x)(P(x)←→(x=a))，这两个结果是不等价的。
　　（4）谓词完备化同CWA一样是非单调的
　　如果例3中增加了条件
　　　　　　Penguin(x)→Bird(x)
　　那么对Bird 的完备化公式为
　　　　　　Bird(x)→Ostrich(x)∨(x=Tweety)∨Penguin(x)
　　这时便不能证明原有结论～Bird(Sam)了，因为Sam虽不是驼鸟但可能是Penguin.从而使结论减少了。
定理 定理3
  　如果Δ是对P单一的子句集，而且是一致的，那么Δ对P的完备化也是一致的。
　　还可以平行的实现几个谓词的谓词完备化。在一个谓词集的平行谓词完备化中，每个谓词可分别在不考虑其它谓词的情况下被完备化，然后将这些分别完备化的公式的合取加入Δ。
　　对P是单一的子句集中，可将那些含有正文字P的子句组合成标准形
　　　　　　(x)(E1∨…∨Ek→P(x))
　　简记为 (x)(E→P(x)),P不出现在E中。
　　对Δ中的谓词集π＝{P1,…,Pn}来实现平行完备化，可先写出标准形
　　　　　　(x)(E1→P1(x))
　　　　　　　　…
　　　　　　(x)(En→Pn(x))
平行完备化就是将
　　　　　　(x)(Pi(x)→Ei) i=1,…,n
加到Δ中。
　　循环问题会出现。如Δ中有
　　　　　　P(x)→Q(x),Q(x)→R(x),R(x)→P(x)
　　那么对{P，Q，R}平行完备化得
　　　　　　P(x)←→Q(x)←→R(x)←→P(x)
出现循环，使对Δ的完备化并不产生新的信息。
　　为避免对Pi的循环，需将π＝{P1,…,Pn}排序，使得每个Ei中不出现{P1,…,Pn}中的任一个，也不出现{P1,…,Pi-1}的任一负文字。如果能办这一点就说Δ中这个些子句对π是有序的。
定理 定理4
  　如果Δ是一致的且对π是有序的，则Δ对π的平行完备化也是一致的。