TSTP Solution File: COM144+1 by Twee---2.4.2
View Problem
- Process Solution
%------------------------------------------------------------------------------
% File : Twee---2.4.2
% Problem : COM144+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 : n016.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:39 EDT 2023
% Result : Theorem 0.20s 0.58s
% Output : Proof 2.07s
% Verified :
% SZS Type : -
% Comments :
%------------------------------------------------------------------------------
%----WARNING: Could not form TPTP format derivation
%------------------------------------------------------------------------------
%----ORIGINAL SYSTEM OUTPUT
% 0.11/0.11 % Problem : COM144+1 : TPTP v8.1.2. Released v6.4.0.
% 0.11/0.12 % Command : parallel-twee %s --tstp --conditional-encoding if --smaller --drop-non-horn --give-up-on-saturation --explain-encoding --formal-proof
% 0.13/0.33 % Computer : n016.cluster.edu
% 0.13/0.33 % Model : x86_64 x86_64
% 0.13/0.33 % CPU : Intel(R) Xeon(R) CPU E5-2620 v4 @ 2.10GHz
% 0.13/0.33 % Memory : 8042.1875MB
% 0.13/0.33 % OS : Linux 3.10.0-693.el7.x86_64
% 0.13/0.33 % CPULimit : 300
% 0.13/0.33 % WCLimit : 300
% 0.13/0.33 % DateTime : Tue Aug 29 13:52:46 EDT 2023
% 0.13/0.33 % CPUTime :
% 0.20/0.58 Command-line arguments: --flatten
% 0.20/0.58
% 0.20/0.58 % SZS status Theorem
% 0.20/0.58
% 0.20/0.59 % SZS output start Proof
% 0.20/0.59 Take the following subset of the input axioms:
% 0.20/0.60 fof('DIFF-abs-app', axiom, ![VVar0, VTyp0, VExp0, VExp1, VExp2]: vabs(VVar0, VTyp0, VExp0)!=vapp(VExp1, VExp2)).
% 0.20/0.60 fof('DIFF-empty-bind', axiom, ![VCtx0, VVar0_2, VTyp0_2]: vempty!=vbind(VVar0_2, VTyp0_2, VCtx0)).
% 0.20/0.60 fof('DIFF-noExp-someExp', axiom, ![VExp0_2]: vnoExp!=vsomeExp(VExp0_2)).
% 0.20/0.60 fof('DIFF-noType-someType', axiom, ![VTyp0_2]: vnoType!=vsomeType(VTyp0_2)).
% 0.20/0.60 fof('DIFF-var-abs', axiom, ![VVar1, VExp0_2, VVar0_2, VTyp0_2]: vvar(VVar0_2)!=vabs(VVar1, VTyp0_2, VExp0_2)).
% 0.20/0.60 fof('DIFF-var-app', axiom, ![VExp0_2, VVar0_2, VExp1_2]: vvar(VVar0_2)!=vapp(VExp0_2, VExp1_2)).
% 0.20/0.60 fof('T-Preservation-T-abs', conjecture, ![Vx, VS, VT, VC, Veout]: ((vreduce(vabs(Vx, VS, ve1))=vsomeExp(Veout) & vtcheck(VC, vabs(Vx, VS, ve1), VT)) => vtcheck(VC, Veout, VT))).
% 0.20/0.60 fof('gensym-is-fresh', axiom, ![Ve, Vv]: (vgensym(Ve)=Vv => ~visFreeVar(Vv, Ve))).
% 0.20/0.60 fof('lookup-INV', axiom, ![RESULT, VVar0_2, VCtx0_2]: (vlookup(VVar0_2, VCtx0_2)=RESULT => (?[Vx2]: (VVar0_2=Vx2 & (VCtx0_2=vempty & RESULT=vnoType)) | (?[Vy, VTy, Vx2, VC2]: (VVar0_2=Vx2 & (VCtx0_2=vbind(Vy, VTy, VC2) & (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.07/0.60 fof('reduce-INV', axiom, ![VExp0_2, RESULT2]: (vreduce(VExp0_2)=RESULT2 => (?[Vx2]: (VExp0_2=vvar(Vx2) & RESULT2=vnoExp) | (?[Vx2, VS2, Ve3]: (VExp0_2=vabs(Vx2, VS2, Ve3) & RESULT2=vnoExp) | (?[Ve1, Ve2, Ve2red, Vx2, VS2]: (VExp0_2=vapp(vabs(Vx2, VS2, Ve1), Ve2) & (Ve2red=vreduce(Ve2) & (visSomeExp(Ve2red) & RESULT2=vsomeExp(vapp(vabs(Vx2, VS2, Ve1), vgetSomeExp(Ve2red)))))) | (?[Vx2, VS2, Ve1_2, Ve2_2, 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)))))) | (?[Vx2, VS2, Ve1_2, Ve2_2, 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.07/0.60 fof('subst-INV', axiom, ![VExp0_2, RESULT2, VVar0_2, VExp1_2]: (vsubst(VVar0_2, VExp0_2, VExp1_2)=RESULT2 => (?[Vx2, Ve3, Vy2]: (VVar0_2=Vx2 & (VExp0_2=Ve3 & (VExp1_2=vvar(Vy2) & (Vx2=Vy2 & RESULT2=Ve3)))) | (?[Vx2, Ve3, Vy2]: (VVar0_2=Vx2 & (VExp0_2=Ve3 & (VExp1_2=vvar(Vy2) & (Vx2!=Vy2 & RESULT2=vvar(Vy2))))) | (?[Vx2, Ve3, Ve1_2, Ve2_2]: (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))))) | (?[VT2, Vx2, Ve3, Ve1_2, Vy2]: (VVar0_2=Vx2 & (VExp0_2=Ve3 & (VExp1_2=vabs(Vy2, VT2, Ve1_2) & (Vx2=Vy2 & RESULT2=vabs(Vy2, VT2, Ve1_2))))) | (?[Vfresh, VT2, Vx2, Ve3, Ve1_2, Vy2]: (VVar0_2=Vx2 & (VExp0_2=Ve3 & (VExp1_2=vabs(Vy2, VT2, Ve1_2) & (Vx2!=Vy2 & (visFreeVar(Vy2, Ve3) & (Vfresh=vgensym(vapp(vapp(Ve3, Ve1_2), vvar(Vx2))) & RESULT2=vsubst(Vx2, Ve3, vabs(Vfresh, VT2, vsubst(Vy2, vvar(Vfresh), Ve1_2))))))))) | ?[VT2, Vx2, Ve3, Ve1_2, 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.07/0.60 fof(isFreeVar1, axiom, ![VT2, VExp0_2, Vx2, Ve3, 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.07/0.60 fof(isSomeExp0, axiom, ![VOptExp0]: (VOptExp0=vnoExp => ~visSomeExp(VOptExp0))).
% 2.07/0.60 fof(isSomeType0, axiom, ![VOptTyp0]: (VOptTyp0=vnoType => ~visSomeType(VOptTyp0))).
% 2.07/0.60 fof(isValue1, axiom, ![VExp0_2, Vx2]: (VExp0_2=vvar(Vx2) => ~visValue(VExp0_2))).
% 2.07/0.60 fof(isValue2, axiom, ![VExp0_2, Ve1_2, Ve2_2]: (VExp0_2=vapp(Ve1_2, Ve2_2) => ~visValue(VExp0_2))).
% 2.07/0.60 fof(reduce1, axiom, ![VExp0_2, Vx2, VS2, Ve3, RESULT2]: (VExp0_2=vabs(Vx2, VS2, Ve3) => (RESULT2=vreduce(VExp0_2) => RESULT2=vnoExp))).
% 2.07/0.60
% 2.07/0.60 Now clausify the problem and encode Horn clauses using encoding 3 of
% 2.07/0.60 http://www.cse.chalmers.se/~nicsma/papers/horn.pdf.
% 2.07/0.60 We repeatedly replace C & s=t => u=v by the two clauses:
% 2.07/0.60 fresh(y, y, x1...xn) = u
% 2.07/0.60 C => fresh(s, t, x1...xn) = v
% 2.07/0.60 where fresh is a fresh function symbol and x1..xn are the free
% 2.07/0.60 variables of u and v.
% 2.07/0.60 A predicate p(X) is encoded as p(X)=true (this is sound, because the
% 2.07/0.60 input problem has no model of domain size 1).
% 2.07/0.60
% 2.07/0.60 The encoding turns the above axioms into the following unit equations and goals:
% 2.07/0.60
% 2.07/0.60 Axiom 1 (reduce1): fresh48(X, X, Y) = vnoExp.
% 2.07/0.60 Axiom 2 (T-Preservation-T-abs): vreduce(vabs(vx, vs, ve1)) = vsomeExp(veout).
% 2.07/0.60 Axiom 3 (reduce1): fresh17(X, X, Y, Z, W, V, U) = W.
% 2.07/0.60 Axiom 4 (reduce1): fresh17(X, vreduce(Y), Z, Y, X, W, V) = fresh48(Y, vabs(Z, W, V), X).
% 2.07/0.60
% 2.07/0.60 Goal 1 (DIFF-noExp-someExp): vnoExp = vsomeExp(X).
% 2.07/0.60 The goal is true when:
% 2.07/0.60 X = veout
% 2.07/0.60
% 2.07/0.60 Proof:
% 2.07/0.60 vnoExp
% 2.07/0.60 = { by axiom 1 (reduce1) R->L }
% 2.07/0.60 fresh48(vabs(vx, vs, ve1), vabs(vx, vs, ve1), vreduce(vabs(vx, vs, ve1)))
% 2.07/0.60 = { by axiom 4 (reduce1) R->L }
% 2.07/0.60 fresh17(vreduce(vabs(vx, vs, ve1)), vreduce(vabs(vx, vs, ve1)), vx, vabs(vx, vs, ve1), vreduce(vabs(vx, vs, ve1)), vs, ve1)
% 2.07/0.60 = { by axiom 3 (reduce1) }
% 2.07/0.60 vreduce(vabs(vx, vs, ve1))
% 2.07/0.60 = { by axiom 2 (T-Preservation-T-abs) }
% 2.07/0.60 vsomeExp(veout)
% 2.07/0.60 % SZS output end Proof
% 2.07/0.60
% 2.07/0.60 RESULT: Theorem (the conjecture is true).
%------------------------------------------------------------------------------