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