ѧ
JOURNAL OF SOFTWARE
1999 2 No.2 1999



滻ͼйصĴ*
1,2Ʒ3
ժҪָʹù᷽Զ,ɾ걸Զ֤,滻ͼйصļ,Է͸.
ؼʡ,滻,һ,,ɾ.
ͼšTP18
Errors Related to Substitution and Set Operations 
CHENG Xiao-chun1,2Jiang Yun-fei3 
AbstractIn this paper, some errors related to substitution and set operations in the proof procedures of lifting lemma and the completeness theorem of deletion strategy, which are in the literatures on resolution-based automated reasoning, are pointed out, analyzed, and corrected.
Key wordsResolution, substitution, unification, set, deletion strategy.
ЧоҪ,ڿ.
ԭ14ǸӾӾ.ڹп֤ܲõӾ.Ϊ߹Ч,Ӿɾԣ13ɾеһ.
ָʹù᷽Զ,ɾ걸Զ֤,滻ͼйصļ,Է͸.
1֤еĴ
Changף1е84ҳ͵85ҳ֤,ʹ¶:
C is a resolvent of C1 and C2. 
C=({,...,})({,...,}) 
C=...=({,...,})({,...,}) 
and  is more general than .
Clearly, C is an instance of C.
Ǵģ

C1={P(y),P(x)},C2={P(a),Q(a)}, 
C1={P(a),P(x)},C2={P(a),Q(a)}=C2,
r1=r2=1,L1==P(x),L2==P(a),
=, ={a/x}(x滻Ϊa), ={a/y}(y滻Ϊa), ={a/x}(x滻Ϊa),
C=({})({})
 =({P(y),P(a) }{P(a)})({P(a),Q(a)}{P(a)})
 ={P(y),Q(a)},
C=({})({}) 
=({P(a),P(a)}{P(a)})({P(a),Q(a)}{P(a)})
={Q(a)}.
C䲻C.
ԭ
({})(C1{L1}).,=ǲܱ֤({})({})({})({}).練ʾ,.,C1ɺһֱ=C1C1ɺһֶʱ,{}δǣ{}.
ԵĴ˵Changף1֤Ǵ,˵Ǵ.ʵ,ȷ.1987,𻪺ͽƷף2е60ҳ63ҳһ˵֤.1989,LeitschҲָChang˵5.
2ɾ걸Զ֤еĴ
ף2е71ҳɾԵһֶ:SӾ伯.ӾǴSƳCһ,D:C1,C2,...,Ck=C.Ci(1ik)ʽ,CiĳCj(j<i),Ciɾ.ǳƶԴDʵɾ.
ף2е71ҳɾԵ걸Զ.
𻪺ͽƷף2ݵ72ҳ,ɾ걸Զ֤,¼:
1. 67УC=L1šL1G,GӾ,L1ԭ,CDĹCL1D֡L2,R(C,D)=DҡG.DR(C,D).
DR(C,D)ȷ,R(C,D)=DҡgǴ.

C={P(x),P(x),P(a)},L1=P(x),G={P(a)}, 
D={P(a)},L2=P(a),={a/x}(x滻Ϊa),
R(C,D)=(Cң{})(Dң{(L2)})
=({P(a),P(a),P(a)}{P(a)})({P(a)}{P(a)})
={P(a)},
DҡG={P(a),P(a)}.
Ȼ,R(C,D)=DҡGǴ.
DR(C,D)ĸ֤
R(C,D)=(C-{})(D-{(L2)}) 
=({,}G-{})(D-{}).
ΪcL1DСL2ǹ,Ȼ,=.
ǡR(C,D)={L1}...(Dң{L1})=Dҡ...
ˡDR(C,D).
2. 1517УCǡD1(ӦΪCD1),D1=L1D1,D2=L2D2,
D1,D2Ӿ.L1L2mguǦ,R(D1,D2)=(D1D2)ң{,}.

L1=L1šL1,D2=L2L2. 
L1L2mguǦ,,
=,ġ1=1,ġ2=2,
R(D1,D2)=({})({})={,},
(d1D2)-{,}={,}-{,}=.
3. 1819У(D2=L2D2,L1L2mguǦ)(1) L1C,C=L1C,R(C,D2)=(CD2)ң{,}.

C=l1šL1,D2=L2L2, 
L1L2mguǦ.
=, C=L1, D2=L2,
R(C,D2)=(CǦң{})({})={,},
(CD2)ң{,}={,}{,}=.
ûӰɾԵ걸,ȷ֤£
1(ɾԵ걸). SǲӾ伯,ڹʹɾ,ȻڴSƳӾĹ.
֤:ȷsӾ.
1. C1Ϊʽ,C1C2йʽR(C1,C2),R(C1,C2)Ϊʽ,C2.
C1=L1l1G,GӾ,L1L1Ϊ.C1C2йԭӵmgu.
(1.1) C1L1C2l2ǹ,
R(C1,C2)=({})({})=({}Gң{})({}). 
Ȼ={,R(C1,C2)=....,R(C1,C2)C2.
C1ĹΪL1,֤ͬR(C1,C2)C2.
(1.2) C1ĹֲL1L1,R(C1,C2)={,}...,R(C1,C2)ʽ.
2. C1C2,C3һC2йʽR(C2,C3)Ӿ,R(C2,C3)C1,C3C1йʽR(C1,C3),R(C1,C3)R(C2,C3).
C1C2,L2L3ֱC2C3еĹ,L2L3ԭӵmgu,R(C2,C3)=({})({}).
(2.1) L2,C3йʽR(,C3)=({})({}).ΪC2,,{}{},R(,C3)R(C2,C3).ɹ13,C1C3ĹʽR(C1,C3),(R(C1,C3))=R(,C3)R(C2,C3).,R(C1,C3)R(C2,C3).
(2.2) L2,=.L2ɺһΪ,...,,C3L3ɺһΪ,...,,L3{,...,}.=...==,=...=
