TSTP Solution File: COM129+1 by Twee---2.4.2
View Problem
- Process Solution
%------------------------------------------------------------------------------
% File : Twee---2.4.2
% Problem : COM129+1 : TPTP v8.1.2. Released v6.4.0.
% Transfm : none
% Format : tptp:raw
% Command : parallel-twee %s --tstp --conditional-encoding if --smaller --drop-non-horn --give-up-on-saturation --explain-encoding --formal-proof
% Computer : n021.cluster.edu
% Model : x86_64 x86_64
% CPU : Intel(R) Xeon(R) CPU E5-2620 v4 2.10GHz
% Memory : 8042.1875MB
% OS : Linux 3.10.0-693.el7.x86_64
% CPULimit : 300s
% WCLimit : 300s
% DateTime : Wed Aug 30 18:45:37 EDT 2023
% Result : Theorem 1.34s 0.64s
% Output : Proof 2.31s
% Verified :
% SZS Type : -
% Comments :
%------------------------------------------------------------------------------
%----WARNING: Could not form TPTP format derivation
%------------------------------------------------------------------------------
%----ORIGINAL SYSTEM OUTPUT
% 0.07/0.13 % Problem : COM129+1 : TPTP v8.1.2. Released v6.4.0.
% 0.07/0.14 % Command : parallel-twee %s --tstp --conditional-encoding if --smaller --drop-non-horn --give-up-on-saturation --explain-encoding --formal-proof
% 0.14/0.35 % Computer : n021.cluster.edu
% 0.14/0.35 % Model : x86_64 x86_64
% 0.14/0.35 % CPU : Intel(R) Xeon(R) CPU E5-2620 v4 @ 2.10GHz
% 0.14/0.35 % Memory : 8042.1875MB
% 0.14/0.35 % OS : Linux 3.10.0-693.el7.x86_64
% 0.14/0.35 % CPULimit : 300
% 0.14/0.35 % WCLimit : 300
% 0.14/0.35 % DateTime : Tue Aug 29 12:59:29 EDT 2023
% 0.14/0.35 % CPUTime :
% 1.34/0.64 Command-line arguments: --flatten
% 1.34/0.64
% 1.34/0.64 % SZS status Theorem
% 1.34/0.64
% 1.34/0.64 % SZS output start Proof
% 1.34/0.64 Take the following subset of the input axioms:
% 2.31/0.66 fof('DIFF-abs-app', axiom, ![VVar0, VTyp0, VExp0, VExp1, VExp2]: vabs(VVar0, VTyp0, VExp0)!=vapp(VExp1, VExp2)).
% 2.31/0.66 fof('DIFF-empty-bind', axiom, ![VCtx0, VVar0_2, VTyp0_2]: vempty!=vbind(VVar0_2, VTyp0_2, VCtx0)).
% 2.31/0.66 fof('DIFF-noExp-someExp', axiom, ![VExp0_2]: vnoExp!=vsomeExp(VExp0_2)).
% 2.31/0.66 fof('DIFF-noType-someType', axiom, ![VTyp0_2]: vnoType!=vsomeType(VTyp0_2)).
% 2.31/0.66 fof('DIFF-var-abs', axiom, ![VVar1, VExp0_2, VVar0_2, VTyp0_2]: vvar(VVar0_2)!=vabs(VVar1, VTyp0_2, VExp0_2)).
% 2.31/0.66 fof('DIFF-var-app', axiom, ![VExp0_2, VVar0_2, VExp1_2]: vvar(VVar0_2)!=vapp(VExp0_2, VExp1_2)).
% 2.31/0.66 fof('fresh-free-2', conjecture, ![Vx, Ve, Ve1, Vfresh]: (Vfresh=vgensym(vapp(vapp(Ve, Ve1), vvar(Vx))) => ~visFreeVar(Vfresh, Ve1))).
% 2.31/0.66 fof('fresh-unequal-var-3', axiom, ![Ve3, Ve1_2, Vx2, Vfresh2]: (Vfresh2=vgensym(vapp(vapp(Ve3, Ve1_2), vvar(Vx2))) => Vx2!=Vfresh2)).
% 2.31/0.66 fof('gensym-is-fresh', axiom, ![Vv, Ve3]: (vgensym(Ve3)=Vv => ~visFreeVar(Vv, Ve3))).
% 2.31/0.66 fof('lookup-INV', axiom, ![RESULT, VVar0_2, VCtx0_2]: (vlookup(VVar0_2, VCtx0_2)=RESULT => (?[Vx2]: (VVar0_2=Vx2 & (VCtx0_2=vempty & RESULT=vnoType)) | (?[VC, Vy, VTy, Vx2]: (VVar0_2=Vx2 & (VCtx0_2=vbind(Vy, VTy, VC) & (Vx2=Vy & RESULT=vsomeType(VTy)))) | ?[Vx2, Vy2, VC2, VTy2]: (VVar0_2=Vx2 & (VCtx0_2=vbind(Vy2, VTy2, VC2) & (Vx2!=Vy2 & RESULT=vlookup(Vx2, VC2)))))))).
% 2.31/0.66 fof('reduce-INV', axiom, ![VExp0_2, RESULT2]: (vreduce(VExp0_2)=RESULT2 => (?[Vx2]: (VExp0_2=vvar(Vx2) & RESULT2=vnoExp) | (?[VS, Ve3, Vx2]: (VExp0_2=vabs(Vx2, VS, Ve3) & RESULT2=vnoExp) | (?[Ve2, Ve2red, Ve1_2, Vx2, VS2]: (VExp0_2=vapp(vabs(Vx2, VS2, Ve1_2), Ve2) & (Ve2red=vreduce(Ve2) & (visSomeExp(Ve2red) & RESULT2=vsomeExp(vapp(vabs(Vx2, VS2, Ve1_2), vgetSomeExp(Ve2red)))))) | (?[Ve1_2, Ve2_2, Vx2, VS2, Ve2red2]: (VExp0_2=vapp(vabs(Vx2, VS2, Ve1_2), Ve2_2) & (Ve2red2=vreduce(Ve2_2) & (~visSomeExp(Ve2red2) & (visValue(Ve2_2) & RESULT2=vsomeExp(vsubst(Vx2, Ve2_2, Ve1_2)))))) | (?[Ve1_2, Ve2_2, Vx2, VS2, Ve2red2]: (VExp0_2=vapp(vabs(Vx2, VS2, Ve1_2), Ve2_2) & (Ve2red2=vreduce(Ve2_2) & (~visSomeExp(Ve2red2) & (~visValue(Ve2_2) & RESULT2=vnoExp)))) | (?[Ve1red, Ve1_2, Ve2_2]: (VExp0_2=vapp(Ve1_2, Ve2_2) & (![VVx0, VVS0, VVe10]: Ve1_2!=vabs(VVx0, VVS0, VVe10) & (Ve1red=vreduce(Ve1_2) & (visSomeExp(Ve1red) & RESULT2=vsomeExp(vapp(vgetSomeExp(Ve1red), Ve2_2)))))) | ?[Ve1_2, Ve2_2, Ve1red2]: (VExp0_2=vapp(Ve1_2, Ve2_2) & (![VVx0_2, VVS0_2, VVe10_2]: Ve1_2!=vabs(VVx0_2, VVS0_2, VVe10_2) & (Ve1red2=vreduce(Ve1_2) & (~visSomeExp(Ve1red2) & RESULT2=vnoExp)))))))))))).
% 2.31/0.66 fof('subst-INV', axiom, ![VExp0_2, VVar0_2, VExp1_2, RESULT2]: (vsubst(VVar0_2, VExp0_2, VExp1_2)=RESULT2 => (?[Ve3, Vx2, Vy2]: (VVar0_2=Vx2 & (VExp0_2=Ve3 & (VExp1_2=vvar(Vy2) & (Vx2=Vy2 & RESULT2=Ve3)))) | (?[Ve3, Vx2, Vy2]: (VVar0_2=Vx2 & (VExp0_2=Ve3 & (VExp1_2=vvar(Vy2) & (Vx2!=Vy2 & RESULT2=vvar(Vy2))))) | (?[Ve3, Ve1_2, Ve2_2, Vx2]: (VVar0_2=Vx2 & (VExp0_2=Ve3 & (VExp1_2=vapp(Ve1_2, Ve2_2) & RESULT2=vapp(vsubst(Vx2, Ve3, Ve1_2), vsubst(Vx2, Ve3, Ve2_2))))) | (?[VT, Ve3, Ve1_2, Vx2, Vy2]: (VVar0_2=Vx2 & (VExp0_2=Ve3 & (VExp1_2=vabs(Vy2, VT, Ve1_2) & (Vx2=Vy2 & RESULT2=vabs(Vy2, VT, Ve1_2))))) | (?[VT2, Ve3, Ve1_2, Vx2, Vy2, Vfresh2]: (VVar0_2=Vx2 & (VExp0_2=Ve3 & (VExp1_2=vabs(Vy2, VT2, Ve1_2) & (Vx2!=Vy2 & (visFreeVar(Vy2, Ve3) & (Vfresh2=vgensym(vapp(vapp(Ve3, Ve1_2), vvar(Vx2))) & RESULT2=vsubst(Vx2, Ve3, vabs(Vfresh2, VT2, vsubst(Vy2, vvar(Vfresh2), Ve1_2))))))))) | ?[VT2, Ve3, Ve1_2, Vx2, Vy2]: (VVar0_2=Vx2 & (VExp0_2=Ve3 & (VExp1_2=vabs(Vy2, VT2, Ve1_2) & (Vx2!=Vy2 & (~visFreeVar(Vy2, Ve3) & RESULT2=vabs(Vy2, VT2, vsubst(Vx2, Ve3, Ve1_2)))))))))))))).
% 2.31/0.66 fof(isFreeVar1, axiom, ![VT2, Ve3, VExp0_2, Vx2, VVar0_2, Vv2]: ((VVar0_2=Vv2 & VExp0_2=vabs(Vx2, VT2, Ve3)) => (((Vx2!=Vv2 & visFreeVar(Vv2, Ve3)) => visFreeVar(VVar0_2, VExp0_2)) & (visFreeVar(VVar0_2, VExp0_2) => (Vx2!=Vv2 & visFreeVar(Vv2, Ve3)))))).
% 2.31/0.66 fof(isFreeVar2, axiom, ![VExp0_2, Ve1_2, Ve2_2, VVar0_2, Vv2]: ((VVar0_2=Vv2 & VExp0_2=vapp(Ve1_2, Ve2_2)) => (((visFreeVar(Vv2, Ve1_2) | visFreeVar(Vv2, Ve2_2)) => visFreeVar(VVar0_2, VExp0_2)) & (visFreeVar(VVar0_2, VExp0_2) => (visFreeVar(Vv2, Ve1_2) | visFreeVar(Vv2, Ve2_2)))))).
% 2.31/0.66 fof(isSomeExp0, axiom, ![VOptExp0]: (VOptExp0=vnoExp => ~visSomeExp(VOptExp0))).
% 2.31/0.66 fof(isSomeType0, axiom, ![VOptTyp0]: (VOptTyp0=vnoType => ~visSomeType(VOptTyp0))).
% 2.31/0.66 fof(isValue1, axiom, ![VExp0_2, Vx2]: (VExp0_2=vvar(Vx2) => ~visValue(VExp0_2))).
% 2.31/0.66 fof(isValue2, axiom, ![VExp0_2, Ve1_2, Ve2_2]: (VExp0_2=vapp(Ve1_2, Ve2_2) => ~visValue(VExp0_2))).
% 2.31/0.66
% 2.31/0.66 Now clausify the problem and encode Horn clauses using encoding 3 of
% 2.31/0.66 http://www.cse.chalmers.se/~nicsma/papers/horn.pdf.
% 2.31/0.66 We repeatedly replace C & s=t => u=v by the two clauses:
% 2.31/0.66 fresh(y, y, x1...xn) = u
% 2.31/0.66 C => fresh(s, t, x1...xn) = v
% 2.31/0.66 where fresh is a fresh function symbol and x1..xn are the free
% 2.31/0.66 variables of u and v.
% 2.31/0.66 A predicate p(X) is encoded as p(X)=true (this is sound, because the
% 2.31/0.66 input problem has no model of domain size 1).
% 2.31/0.66
% 2.31/0.66 The encoding turns the above axioms into the following unit equations and goals:
% 2.31/0.66
% 2.31/0.66 Axiom 1 (fresh-free-2_1): visFreeVar(vfresh, ve1) = true2.
% 2.31/0.66 Axiom 2 (isFreeVar2_1): fresh67(X, X, Y, Z) = true2.
% 2.31/0.66 Axiom 3 (isFreeVar2_2): fresh65(X, X, Y, Z) = true2.
% 2.31/0.66 Axiom 4 (isFreeVar2_1): fresh68(X, X, Y, Z, W, V) = visFreeVar(W, Y).
% 2.31/0.66 Axiom 5 (isFreeVar2_2): fresh66(X, X, Y, Z, W, V) = visFreeVar(W, Y).
% 2.31/0.66 Axiom 6 (fresh-free-2): vfresh = vgensym(vapp(vapp(ve, ve1), vvar(vx))).
% 2.31/0.66 Axiom 7 (isFreeVar2_1): fresh68(visFreeVar(X, Y), true2, Z, Y, X, W) = fresh67(Z, vapp(Y, W), Z, X).
% 2.31/0.66 Axiom 8 (isFreeVar2_2): fresh66(visFreeVar(X, Y), true2, Z, W, X, Y) = fresh65(Z, vapp(W, Y), Z, X).
% 2.31/0.66
% 2.31/0.66 Goal 1 (gensym-is-fresh): tuple2(vgensym(X), visFreeVar(Y, X)) = tuple2(Y, true2).
% 2.31/0.66 The goal is true when:
% 2.31/0.66 X = vapp(vapp(ve, ve1), vvar(vx))
% 2.31/0.66 Y = vgensym(vapp(vapp(ve, ve1), vvar(vx)))
% 2.31/0.66
% 2.31/0.66 Proof:
% 2.31/0.66 tuple2(vgensym(vapp(vapp(ve, ve1), vvar(vx))), visFreeVar(vgensym(vapp(vapp(ve, ve1), vvar(vx))), vapp(vapp(ve, ve1), vvar(vx))))
% 2.31/0.66 = { by axiom 4 (isFreeVar2_1) R->L }
% 2.31/0.66 tuple2(vgensym(vapp(vapp(ve, ve1), vvar(vx))), fresh68(visFreeVar(vfresh, ve1), visFreeVar(vfresh, ve1), vapp(vapp(ve, ve1), vvar(vx)), vapp(ve, ve1), vgensym(vapp(vapp(ve, ve1), vvar(vx))), vvar(vx)))
% 2.31/0.66 = { by axiom 1 (fresh-free-2_1) }
% 2.31/0.66 tuple2(vgensym(vapp(vapp(ve, ve1), vvar(vx))), fresh68(true2, visFreeVar(vfresh, ve1), vapp(vapp(ve, ve1), vvar(vx)), vapp(ve, ve1), vgensym(vapp(vapp(ve, ve1), vvar(vx))), vvar(vx)))
% 2.31/0.66 = { by axiom 3 (isFreeVar2_2) R->L }
% 2.31/0.66 tuple2(vgensym(vapp(vapp(ve, ve1), vvar(vx))), fresh68(fresh65(vapp(ve, ve1), vapp(ve, ve1), vapp(ve, ve1), vgensym(vapp(vapp(ve, ve1), vvar(vx)))), visFreeVar(vfresh, ve1), vapp(vapp(ve, ve1), vvar(vx)), vapp(ve, ve1), vgensym(vapp(vapp(ve, ve1), vvar(vx))), vvar(vx)))
% 2.31/0.66 = { by axiom 6 (fresh-free-2) R->L }
% 2.31/0.66 tuple2(vgensym(vapp(vapp(ve, ve1), vvar(vx))), fresh68(fresh65(vapp(ve, ve1), vapp(ve, ve1), vapp(ve, ve1), vfresh), visFreeVar(vfresh, ve1), vapp(vapp(ve, ve1), vvar(vx)), vapp(ve, ve1), vgensym(vapp(vapp(ve, ve1), vvar(vx))), vvar(vx)))
% 2.31/0.66 = { by axiom 8 (isFreeVar2_2) R->L }
% 2.31/0.66 tuple2(vgensym(vapp(vapp(ve, ve1), vvar(vx))), fresh68(fresh66(visFreeVar(vfresh, ve1), true2, vapp(ve, ve1), ve, vfresh, ve1), visFreeVar(vfresh, ve1), vapp(vapp(ve, ve1), vvar(vx)), vapp(ve, ve1), vgensym(vapp(vapp(ve, ve1), vvar(vx))), vvar(vx)))
% 2.31/0.66 = { by axiom 1 (fresh-free-2_1) R->L }
% 2.31/0.66 tuple2(vgensym(vapp(vapp(ve, ve1), vvar(vx))), fresh68(fresh66(visFreeVar(vfresh, ve1), visFreeVar(vfresh, ve1), vapp(ve, ve1), ve, vfresh, ve1), visFreeVar(vfresh, ve1), vapp(vapp(ve, ve1), vvar(vx)), vapp(ve, ve1), vgensym(vapp(vapp(ve, ve1), vvar(vx))), vvar(vx)))
% 2.31/0.66 = { by axiom 5 (isFreeVar2_2) }
% 2.31/0.66 tuple2(vgensym(vapp(vapp(ve, ve1), vvar(vx))), fresh68(visFreeVar(vfresh, vapp(ve, ve1)), visFreeVar(vfresh, ve1), vapp(vapp(ve, ve1), vvar(vx)), vapp(ve, ve1), vgensym(vapp(vapp(ve, ve1), vvar(vx))), vvar(vx)))
% 2.31/0.66 = { by axiom 6 (fresh-free-2) }
% 2.31/0.66 tuple2(vgensym(vapp(vapp(ve, ve1), vvar(vx))), fresh68(visFreeVar(vgensym(vapp(vapp(ve, ve1), vvar(vx))), vapp(ve, ve1)), visFreeVar(vfresh, ve1), vapp(vapp(ve, ve1), vvar(vx)), vapp(ve, ve1), vgensym(vapp(vapp(ve, ve1), vvar(vx))), vvar(vx)))
% 2.31/0.66 = { by axiom 1 (fresh-free-2_1) }
% 2.31/0.66 tuple2(vgensym(vapp(vapp(ve, ve1), vvar(vx))), fresh68(visFreeVar(vgensym(vapp(vapp(ve, ve1), vvar(vx))), vapp(ve, ve1)), true2, vapp(vapp(ve, ve1), vvar(vx)), vapp(ve, ve1), vgensym(vapp(vapp(ve, ve1), vvar(vx))), vvar(vx)))
% 2.31/0.66 = { by axiom 7 (isFreeVar2_1) }
% 2.31/0.66 tuple2(vgensym(vapp(vapp(ve, ve1), vvar(vx))), fresh67(vapp(vapp(ve, ve1), vvar(vx)), vapp(vapp(ve, ve1), vvar(vx)), vapp(vapp(ve, ve1), vvar(vx)), vgensym(vapp(vapp(ve, ve1), vvar(vx)))))
% 2.31/0.66 = { by axiom 2 (isFreeVar2_1) }
% 2.31/0.66 tuple2(vgensym(vapp(vapp(ve, ve1), vvar(vx))), true2)
% 2.31/0.66 = { by axiom 1 (fresh-free-2_1) R->L }
% 2.31/0.66 tuple2(vgensym(vapp(vapp(ve, ve1), vvar(vx))), visFreeVar(vfresh, ve1))
% 2.31/0.66 = { by axiom 1 (fresh-free-2_1) }
% 2.31/0.66 tuple2(vgensym(vapp(vapp(ve, ve1), vvar(vx))), true2)
% 2.31/0.66 % SZS output end Proof
% 2.31/0.66
% 2.31/0.66 RESULT: Theorem (the conjecture is true).
%------------------------------------------------------------------------------