人工智能原理

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

　　3.3.4　限制方法
　　限制（Circumscription）是表达常识性知识和常识性推理时时常用的方法。直观地说，是在处理问题时总要做些假设来进行的，这种假设就是一种限制。CWA和谓词完备化方法对信任集的扩充都是依古典完备性观点来进行的，然而也可以从某种最小化原则来理解。例如：
　　　　　Δ＝(

x)(E→P(x))
　　而谓词完备化公式为
　　　　　(

x)(P(x)→E)
这种扩充仅限于满足P的个体必须是E，也即除使Δ中E→P(x)成立的个体外，不能再有个体满足P了。这就是P的一种最小扩充。
　　严格地说，限制像谓词完备化那样是一个过程，这个过程是来寻求一个公式作为假设，以便扩充已知的信任集Δ，要求对所做的假设加以约束，使满足某谓词的那些个体，仅只是Δ中使该谓词成立的那些个体。
　　1．最小模型
　　对已知的信任集Δ，M和M^*是Δ的两个模型（使Δ成立的解释），满足
　　（1）M、M^*有相同的个体域。
　　（2）M、M^*对Δ中除P而外的所有其它谓词和常项有同样的设定。
　　（3）M^*中满足P的个体集是M中满足P的个体集的子集。
　　便有　M^*≤ pM
　　如论域　D＝{1,2}上
　　　　　　Δ＝(

x)(

y)(Py)∧Q(x,y))
　　　　　　　=[(P(1)∧Q(1,1))∨(P(2)∧Q(1,2))]∧[(P(1)∧Q(2,1))∨(P(2)∧Q(2,2))]
　　若

M：	P(1)	P(2)	Q(1,1)	Q(1,2)	Q(2,1)	Q(2,2)
	T	T	F	T	F	T
M^*：	P(1)	P(2)	Q(1,1)	Q(1,2)	Q(2,1)	Q(2,2)
	F	T	F	T	F	T

　　显然有△|M＝T，△|M^*＝T所以M，M^*都是△的模型。M，M^*对Q的真值设定是相同的，而对P来说，M中有{1,2}中的元素使P为真，而M*中仅有{2}中的2使P为真，{2}

{1,2}。
　　于是有　M^* ≤ pM
　　如果　M^* ≤ pM　而且 M^*≠M，则有 M^* ＜pM
　　对△来说，如果对任一 M^* ≤ pM，必有M＝Mm时，就说Mm是P的最小模型。对任一个△来说，最小模型不一定总存在。
　　2．依最小化原则建立假设
　　给了含有谓词P的信任集△（为简单仅考虑△中的谓词P），来寻找对△的假设（扩充）公式Φp，使得对△∧Φp的任一模型M，不存在△的模型M^*满足
　　　　　　M^* ＜pM
或说扩充后△∧Φp的模型对P来说不能比原来△的模型来得大，是一种最小的扩充。依这最小化原则所得的△∧Φp便是△对P的限制。
　　设P^*是某个谓词常项，它与P有同样的变元个数，由P来构造Φp，可指出
　　(

x)(P^*(x)→P(x))∧～(

x)(P(x)→(P^*(x))∧△(P^*)
的任一模型都不是△对P的最小模型。从而
　　～((

x)(P^*(x)→P(x))∧～(

x)(P(x)→P^*(x))∧△(P^*))
的任一模型是△对P的最小模型。于是
　　Φp=(

P^*)～((

x)(P^*(x)→P(x))∧～

x(P(x)→P^*(x)∧△(P^*))
为△对P的限制公式。有
　　CIRC[△,P]
　　=△∧(

P^*)～((

x)P^*(x)→P(x))∧～(

x)(P(x)→P^*(x)∧△(P^*)))
　　=△∧(

P^*)((△(P^*)∧(

x)P^*(x)→P(x)))→(

x)(P(x)→P^*(x)))
　　这个公式是高阶逻辑公式，因为量词作用于谓词P*了，但在很多情形可化为一阶逻辑公式。公式
　　Φp=(

P^*)((△(P^*)∧(

x)(P^*(x)→P(x)))→(

x)(P(x)→P(x^*)))
是说，如果求得P^*使△(P^*)成立，又满足(

x)(P^*(x)→P(x)那么(

x)(P(x)→P^*(x))便可作为推理的结论。

例:

　△＝is Block(a)∧isBlock(b)∧is Block(c)
　谓词P(x)=is Block(x), △可写成△(P)或△(is Block)。于是有
　Φp=(△P^*)∧(

x)(P^*(x)→is block(x))→(

x)(is Block(x)→P^*(x))
　选取 P^*(x)=(x=a)∨(x=b)∨(x=c)
　　　△(P^*)=((a=a)∨(a=b)∨(a=c))∧((b=a)∨(b=b)∨(b=c))∧((c=a)∨(c=b)∨(c=c))
　　　　　　=T。
　而　(

x)(P^*(x)→ is Block(x))＝T，于是有
　　　(

x)(is Block(x)→((x=a)∨(x=B)∨(x=c)))
这样在限制方法中，引入Φp后便可推出
　　　is Block(x)→((x=a)∨(x=b)∨(x=c))
这一结论。这是非单调的，因将其它积木块加入△中，该结论就不成立了。

　　CIR[△,P]还可成另一种形式。将P^*记作P∧P'（P'是与P的变元个数相同的谓词常项），于是有
　　Φp=△(P∧P')∧(

x)(P(x)∧P'(x)→P(x))→(

x)(P(x)→P(x)∧P'(x))
从而得
　　　　　　△(P∧P')→(

x)(P(x)→P'(x))
　　若将　(

x)(P^*(x)→P(x)) 记作 P^*≤P，而
　　　　　P^*<P 表示(P^*≤P)∧～(P≤P^*)
　　　　　P^*=P 表示(P^*≤P)∧(P≤P^*)
于是φp就是
　　　　　(

P^*)(△(P^*)∧(P^*≤P)→(P≤P^*))
得　　　　(

P^*)(△(P^*)→～(P^*<P))
　　　　　=～(

P^*)(△(P^*)∧(P^*<P))
　　这就更明显地可看出，最小模型限制表明，不存在P*满足△而且使P*成立的外延是P成立外延的真子集。

	定理 5
	已知谓词P和信任集△(P)，对任一P'来说，如果　△(P)├△(P')∧(P'≤P) 则　CIRC[△,P]= △(P)∧(P=P')

　　这定理是说，如果△(P)能证明△(P')∧ (P'≤P) 那么P＝P'就是△对P的限制公式。