0.07/0.11 % Problem : theBenchmark.p : TPTP v0.0.0. Released v0.0.0. 0.07/0.12 % Command : twee %s --tstp --casc --quiet --explain-encoding --conditional-encoding if --smaller --drop-non-horn 0.12/0.33 % Computer : n014.cluster.edu 0.12/0.33 % Model : x86_64 x86_64 0.12/0.33 % CPU : Intel(R) Xeon(R) CPU E5-2620 v4 @ 2.10GHz 0.12/0.33 % Memory : 8042.1875MB 0.12/0.33 % OS : Linux 3.10.0-693.el7.x86_64 0.12/0.33 % CPULimit : 960 0.12/0.33 % WCLimit : 120 0.12/0.33 % DateTime : Thu Jul 2 06:37:55 EDT 2020 0.12/0.33 % CPUTime : 0.19/0.48 % SZS status Theorem 0.19/0.48 0.19/0.48 % SZS output start Proof 0.19/0.48 Take the following subset of the input axioms: 0.19/0.48 fof('DIFF-abs-app', axiom, ![VVar0, VExp0, VExp1, VTyp0, VExp2]: vapp(VExp1, VExp2)!=vabs(VVar0, VTyp0, VExp0)). 0.19/0.48 fof('DIFF-empty-bind', axiom, ![VVar0, VTyp0, VCtx0]: vbind(VVar0, VTyp0, VCtx0)!=vempty). 0.19/0.48 fof('DIFF-noExp-someExp', axiom, ![VExp0]: vnoExp!=vsomeExp(VExp0)). 0.19/0.48 fof('DIFF-noType-someType', axiom, ![VTyp0]: vsomeType(VTyp0)!=vnoType). 0.19/0.48 fof('DIFF-var-abs', axiom, ![VVar0, VExp0, VTyp0, VVar1]: vabs(VVar1, VTyp0, VExp0)!=vvar(VVar0)). 0.19/0.48 fof('DIFF-var-app', axiom, ![VVar0, VExp0, VExp1]: vapp(VExp0, VExp1)!=vvar(VVar0)). 0.19/0.48 fof('T-Preservation-T-var', conjecture, ![VT, Vx, VC, Veout]: ((vreduce(vvar(Vx))=vsomeExp(Veout) & vtcheck(VC, vvar(Vx), VT)) => vtcheck(VC, Veout, VT))). 0.19/0.48 fof('gensym-is-fresh', axiom, ![Ve, Vv]: (~visFreeVar(Vv, Ve) <= vgensym(Ve)=Vv)). 0.19/0.48 fof('reduce-INV', axiom, ![VExp0, RESULT]: ((?[Ve1, Ve2, Ve1red]: (RESULT=vsomeExp(vapp(vgetSomeExp(Ve1red), Ve2)) & (vreduce(Ve1)=Ve1red & (VExp0=vapp(Ve1, Ve2) & (![VVx0, VVS0, VVe10]: vabs(VVx0, VVS0, VVe10)!=Ve1 & visSomeExp(Ve1red))))) | (?[Ve1, Ve2, Vx, VS, Ve2red]: (vnoExp=RESULT & (~visSomeExp(Ve2red) & (Ve2red=vreduce(Ve2) & (~visValue(Ve2) & VExp0=vapp(vabs(Vx, VS, Ve1), Ve2))))) | (?[Vx]: (vvar(Vx)=VExp0 & vnoExp=RESULT) | (?[Ve1, Ve2, Vx, VS, Ve2red]: (~visSomeExp(Ve2red) & (visValue(Ve2) & (vsomeExp(vsubst(Vx, Ve2, Ve1))=RESULT & (vreduce(Ve2)=Ve2red & VExp0=vapp(vabs(Vx, VS, Ve1), Ve2))))) | (?[Ve1, Ve2, Ve1red]: (vreduce(Ve1)=Ve1red & (vnoExp=RESULT & (~visSomeExp(Ve1red) & (![VVx0, VVS0, VVe10]: Ve1!=vabs(VVx0, VVS0, VVe10) & vapp(Ve1, Ve2)=VExp0)))) | (?[Ve1, Ve2, Vx, VS, Ve2red]: (vreduce(Ve2)=Ve2red & (visSomeExp(Ve2red) & (vsomeExp(vapp(vabs(Vx, VS, Ve1), vgetSomeExp(Ve2red)))=RESULT & vapp(vabs(Vx, VS, Ve1), Ve2)=VExp0))) | ?[Ve, Vx, VS]: (vnoExp=RESULT & VExp0=vabs(Vx, VS, Ve)))))))) <= RESULT=vreduce(VExp0))). 0.19/0.48 fof('subst-INV', axiom, ![VVar0, VExp0, VExp1, RESULT]: ((?[Ve, Ve1, Ve2, Vx]: (VExp1=vapp(Ve1, Ve2) & (Ve=VExp0 & (Vx=VVar0 & RESULT=vapp(vsubst(Vx, Ve, Ve1), vsubst(Vx, Ve, Ve2))))) | (?[VT, Ve, Ve1, Vx, Vy]: (VExp0=Ve & (VVar0=Vx & (Vx=Vy & (vabs(Vy, VT, Ve1)=RESULT & VExp1=vabs(Vy, VT, Ve1))))) | (?[Ve, Vx, Vy]: (RESULT=Ve & (VExp1=vvar(Vy) & (Vx=VVar0 & (VExp0=Ve & Vy=Vx)))) | (?[Ve, Vx, Vy]: (vvar(Vy)=VExp1 & (vvar(Vy)=RESULT & (Vx!=Vy & (VVar0=Vx & VExp0=Ve)))) | (?[VT, Ve, Ve1, Vx, Vy, Vfresh]: (Vy!=Vx & (VVar0=Vx & (VExp0=Ve & (VExp1=vabs(Vy, VT, Ve1) & (RESULT=vsubst(Vx, Ve, vabs(Vfresh, VT, vsubst(Vy, vvar(Vfresh), Ve1))) & (vgensym(vapp(vapp(Ve, Ve1), vvar(Vx)))=Vfresh & visFreeVar(Vy, Ve))))))) | ?[VT, Ve, Ve1, Vx, Vy]: (Ve=VExp0 & (RESULT=vabs(Vy, VT, vsubst(Vx, Ve, Ve1)) & (~visFreeVar(Vy, Ve) & (Vx=VVar0 & (Vx!=Vy & vabs(Vy, VT, Ve1)=VExp1)))))))))) <= vsubst(VVar0, VExp0, VExp1)=RESULT)). 0.19/0.48 fof(isFreeVar1, axiom, ![VVar0, VExp0, VT, Ve, Vv, Vx]: ((((Vv!=Vx & visFreeVar(Vv, Ve)) => visFreeVar(VVar0, VExp0)) & (visFreeVar(VVar0, VExp0) => (Vx!=Vv & visFreeVar(Vv, Ve)))) <= (Vv=VVar0 & VExp0=vabs(Vx, VT, Ve)))). 0.19/0.48 fof(isSomeExp0, axiom, ![VOptExp0]: (VOptExp0=vnoExp => ~visSomeExp(VOptExp0))). 0.19/0.48 fof(isSomeType0, axiom, ![VOptTyp0]: (vnoType=VOptTyp0 => ~visSomeType(VOptTyp0))). 0.19/0.48 fof(isValue1, axiom, ![VExp0, Vx]: (VExp0=vvar(Vx) => ~visValue(VExp0))). 0.19/0.48 fof(isValue2, axiom, ![VExp0, Ve1, Ve2]: (vapp(Ve1, Ve2)=VExp0 => ~visValue(VExp0))). 0.19/0.48 fof(reduce0, axiom, ![VExp0, RESULT, Vx]: ((vreduce(VExp0)=RESULT => vnoExp=RESULT) <= VExp0=vvar(Vx))). 0.19/0.48 0.19/0.48 Now clausify the problem and encode Horn clauses using encoding 3 of 0.19/0.48 http://www.cse.chalmers.se/~nicsma/papers/horn.pdf. 0.19/0.48 We repeatedly replace C & s=t => u=v by the two clauses: 0.19/0.48 fresh(y, y, x1...xn) = u 0.19/0.48 C => fresh(s, t, x1...xn) = v 0.19/0.48 where fresh is a fresh function symbol and x1..xn are the free 0.19/0.48 variables of u and v. 0.19/0.48 A predicate p(X) is encoded as p(X)=true (this is sound, because the 0.19/0.48 input problem has no model of domain size 1). 0.19/0.48 0.19/0.48 The encoding turns the above axioms into the following unit equations and goals: 0.19/0.48 0.19/0.48 Axiom 1 (reduce0): fresh22(X, X, Y) = Y. 0.19/0.48 Axiom 2 (reduce0): fresh50(X, X, Y, Z, W) = vnoExp. 0.19/0.48 Axiom 3 (reduce0): fresh50(vreduce(X), Y, Z, X, Y) = fresh22(X, vvar(Z), Y). 0.19/0.48 Axiom 4 (T-Preservation-T-var): vreduce(vvar(sK1_T-Preservation-T-var_Vx)) = vsomeExp(sK3_T-Preservation-T-var_Veout). 0.19/0.48 0.19/0.48 Goal 1 (DIFF-noExp-someExp): vnoExp = vsomeExp(X). 0.19/0.48 The goal is true when: 0.19/0.48 X = sK3_T-Preservation-T-var_Veout 0.19/0.48 0.19/0.48 Proof: 0.19/0.48 vnoExp 0.19/0.48 = { by axiom 2 (reduce0) } 0.19/0.48 fresh50(vreduce(vvar(sK1_T-Preservation-T-var_Vx)), vreduce(vvar(sK1_T-Preservation-T-var_Vx)), sK1_T-Preservation-T-var_Vx, vvar(sK1_T-Preservation-T-var_Vx), vreduce(vvar(sK1_T-Preservation-T-var_Vx))) 0.19/0.48 = { by axiom 3 (reduce0) } 0.19/0.48 fresh22(vvar(sK1_T-Preservation-T-var_Vx), vvar(sK1_T-Preservation-T-var_Vx), vreduce(vvar(sK1_T-Preservation-T-var_Vx))) 0.19/0.48 = { by axiom 1 (reduce0) } 0.19/0.48 vreduce(vvar(sK1_T-Preservation-T-var_Vx)) 0.19/0.48 = { by axiom 4 (T-Preservation-T-var) } 0.19/0.48 vsomeExp(sK3_T-Preservation-T-var_Veout) 0.19/0.48 % SZS output end Proof 0.19/0.48 0.19/0.48 RESULT: Theorem (the conjecture is true). 0.19/0.49 EOF