TSTP Solution File: COM128+1 by Twee---2.4.2
View Problem
- Process Solution
%------------------------------------------------------------------------------
% File : Twee---2.4.2
% Problem : COM128+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 : n027.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 0.20s 0.62s
% Output : Proof 0.20s
% Verified :
% SZS Type : -
% Comments :
%------------------------------------------------------------------------------
%----WARNING: Could not form TPTP format derivation
%------------------------------------------------------------------------------
%----ORIGINAL SYSTEM OUTPUT
% 0.00/0.13 % Problem : COM128+1 : TPTP v8.1.2. Released v6.4.0.
% 0.00/0.13 % Command : parallel-twee %s --tstp --conditional-encoding if --smaller --drop-non-horn --give-up-on-saturation --explain-encoding --formal-proof
% 0.13/0.35 % Computer : n027.cluster.edu
% 0.13/0.35 % Model : x86_64 x86_64
% 0.13/0.35 % CPU : Intel(R) Xeon(R) CPU E5-2620 v4 @ 2.10GHz
% 0.13/0.35 % Memory : 8042.1875MB
% 0.13/0.35 % OS : Linux 3.10.0-693.el7.x86_64
% 0.13/0.35 % CPULimit : 300
% 0.13/0.35 % WCLimit : 300
% 0.13/0.35 % DateTime : Tue Aug 29 13:19:38 EDT 2023
% 0.13/0.35 % CPUTime :
% 0.20/0.62 Command-line arguments: --flip-ordering --lhs-weight 1 --depth-weight 60 --distributivity-heuristic
% 0.20/0.62
% 0.20/0.62 % SZS status Theorem
% 0.20/0.62
% 0.20/0.62 % SZS output start Proof
% 0.20/0.62 Take the following subset of the input axioms:
% 0.20/0.63 fof('DIFF-abs-app', axiom, ![VVar0, VTyp0, VExp0, VExp1, VExp2]: vabs(VVar0, VTyp0, VExp0)!=vapp(VExp1, VExp2)).
% 0.20/0.63 fof('DIFF-empty-bind', axiom, ![VCtx0, VVar0_2, VTyp0_2]: vempty!=vbind(VVar0_2, VTyp0_2, VCtx0)).
% 0.20/0.63 fof('DIFF-noExp-someExp', axiom, ![VExp0_2]: vnoExp!=vsomeExp(VExp0_2)).
% 0.20/0.63 fof('DIFF-noType-someType', axiom, ![VTyp0_2]: vnoType!=vsomeType(VTyp0_2)).
% 0.20/0.63 fof('DIFF-var-abs', axiom, ![VVar1, VExp0_2, VVar0_2, VTyp0_2]: vvar(VVar0_2)!=vabs(VVar1, VTyp0_2, VExp0_2)).
% 0.20/0.63 fof('DIFF-var-app', axiom, ![VExp0_2, VVar0_2, VExp1_2]: vvar(VVar0_2)!=vapp(VExp0_2, VExp1_2)).
% 0.20/0.63 fof('fresh-unequal-var-3', conjecture, ![Vx, Ve, Ve1, Vfresh]: (Vfresh=vgensym(vapp(vapp(Ve, Ve1), vvar(Vx))) => Vx!=Vfresh)).
% 0.20/0.63 fof('gensym-is-fresh', axiom, ![Vv, Ve3]: (vgensym(Ve3)=Vv => ~visFreeVar(Vv, Ve3))).
% 0.20/0.63 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)))))))).
% 0.20/0.63 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)))))))))))).
% 0.20/0.63 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)))))))))))))).
% 0.20/0.63 fof(isFreeVar0, axiom, ![VExp0_2, Vx2, VVar0_2, Vv2]: ((VVar0_2=Vv2 & VExp0_2=vvar(Vx2)) => ((Vx2=Vv2 => visFreeVar(VVar0_2, VExp0_2)) & (visFreeVar(VVar0_2, VExp0_2) => Vx2=Vv2)))).
% 0.20/0.63 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)))))).
% 0.20/0.63 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)))))).
% 0.20/0.63 fof(isSomeExp0, axiom, ![VOptExp0]: (VOptExp0=vnoExp => ~visSomeExp(VOptExp0))).
% 0.20/0.63 fof(isSomeType0, axiom, ![VOptTyp0]: (VOptTyp0=vnoType => ~visSomeType(VOptTyp0))).
% 0.20/0.63 fof(isValue1, axiom, ![VExp0_2, Vx2]: (VExp0_2=vvar(Vx2) => ~visValue(VExp0_2))).
% 0.20/0.63 fof(isValue2, axiom, ![VExp0_2, Ve1_2, Ve2_2]: (VExp0_2=vapp(Ve1_2, Ve2_2) => ~visValue(VExp0_2))).
% 0.20/0.63
% 0.20/0.63 Now clausify the problem and encode Horn clauses using encoding 3 of
% 0.20/0.63 http://www.cse.chalmers.se/~nicsma/papers/horn.pdf.
% 0.20/0.63 We repeatedly replace C & s=t => u=v by the two clauses:
% 0.20/0.63 fresh(y, y, x1...xn) = u
% 0.20/0.63 C => fresh(s, t, x1...xn) = v
% 0.20/0.63 where fresh is a fresh function symbol and x1..xn are the free
% 0.20/0.63 variables of u and v.
% 0.20/0.63 A predicate p(X) is encoded as p(X)=true (this is sound, because the
% 0.20/0.63 input problem has no model of domain size 1).
% 0.20/0.63
% 0.20/0.63 The encoding turns the above axioms into the following unit equations and goals:
% 0.20/0.63
% 0.20/0.63 Axiom 1 (fresh-unequal-var-3_1): vx = vfresh.
% 0.20/0.63 Axiom 2 (isFreeVar0_1): fresh71(X, X, Y, Z) = true2.
% 0.20/0.63 Axiom 3 (isFreeVar2_2): fresh65(X, X, Y, Z) = true2.
% 0.20/0.63 Axiom 4 (isFreeVar0_1): fresh71(X, vvar(Y), X, Y) = visFreeVar(Y, X).
% 0.20/0.63 Axiom 5 (fresh-unequal-var-3): vfresh = vgensym(vapp(vapp(ve, ve1), vvar(vx))).
% 0.20/0.63 Axiom 6 (isFreeVar2_2): fresh66(X, X, Y, Z, W, V) = visFreeVar(W, Y).
% 0.20/0.63 Axiom 7 (isFreeVar2_2): fresh66(visFreeVar(X, Y), true2, Z, W, X, Y) = fresh65(Z, vapp(W, Y), Z, X).
% 0.20/0.63
% 0.20/0.63 Goal 1 (gensym-is-fresh): tuple2(vgensym(X), visFreeVar(Y, X)) = tuple2(Y, true2).
% 0.20/0.63 The goal is true when:
% 0.20/0.63 X = vapp(vapp(ve, ve1), vvar(vx))
% 0.20/0.63 Y = vx
% 0.20/0.63
% 0.20/0.63 Proof:
% 0.20/0.63 tuple2(vgensym(vapp(vapp(ve, ve1), vvar(vx))), visFreeVar(vx, vapp(vapp(ve, ve1), vvar(vx))))
% 0.20/0.63 = { by axiom 5 (fresh-unequal-var-3) R->L }
% 0.20/0.63 tuple2(vfresh, visFreeVar(vx, vapp(vapp(ve, ve1), vvar(vx))))
% 0.20/0.63 = { by axiom 1 (fresh-unequal-var-3_1) R->L }
% 0.20/0.63 tuple2(vx, visFreeVar(vx, vapp(vapp(ve, ve1), vvar(vx))))
% 0.20/0.63 = { by axiom 6 (isFreeVar2_2) R->L }
% 0.20/0.63 tuple2(vx, fresh66(true2, true2, vapp(vapp(ve, ve1), vvar(vx)), vapp(ve, ve1), vx, vvar(vx)))
% 0.20/0.63 = { by axiom 2 (isFreeVar0_1) R->L }
% 0.20/0.63 tuple2(vx, fresh66(fresh71(vvar(vx), vvar(vx), vvar(vx), vx), true2, vapp(vapp(ve, ve1), vvar(vx)), vapp(ve, ve1), vx, vvar(vx)))
% 0.20/0.63 = { by axiom 4 (isFreeVar0_1) }
% 0.20/0.63 tuple2(vx, fresh66(visFreeVar(vx, vvar(vx)), true2, vapp(vapp(ve, ve1), vvar(vx)), vapp(ve, ve1), vx, vvar(vx)))
% 0.20/0.63 = { by axiom 7 (isFreeVar2_2) }
% 0.20/0.63 tuple2(vx, fresh65(vapp(vapp(ve, ve1), vvar(vx)), vapp(vapp(ve, ve1), vvar(vx)), vapp(vapp(ve, ve1), vvar(vx)), vx))
% 0.20/0.63 = { by axiom 3 (isFreeVar2_2) }
% 0.20/0.63 tuple2(vx, true2)
% 0.20/0.63 % SZS output end Proof
% 0.20/0.63
% 0.20/0.63 RESULT: Theorem (the conjecture is true).
%------------------------------------------------------------------------------