0.00/0.03 % Problem : theBenchmark.p : TPTP v0.0.0. Released v0.0.0. 0.00/0.04 % Command : twee %s --tstp --casc --quiet --conditional-encoding if --smaller --drop-non-horn 0.02/0.23 % Computer : n117.star.cs.uiowa.edu 0.02/0.23 % Model : x86_64 x86_64 0.02/0.23 % CPU : Intel(R) Xeon(R) CPU E5-2609 0 @ 2.40GHz 0.02/0.23 % Memory : 32218.625MB 0.02/0.23 % OS : Linux 3.10.0-693.2.2.el7.x86_64 0.02/0.23 % CPULimit : 300 0.02/0.23 % DateTime : Sat Jul 14 04:40:55 CDT 2018 0.02/0.24 % CPUTime : 0.06/0.43 % SZS status Theorem 0.06/0.43 0.06/0.43 % SZS output start Proof 0.06/0.43 Take the following subset of the input axioms: 0.06/0.43 fof('DIFF-abs-app', axiom, 0.06/0.43 ![VExp0, VTyp0, VVar0, VExp1, VExp2]: 0.06/0.43 vapp(VExp1, VExp2)!=vabs(VVar0, VTyp0, VExp0)). 0.06/0.43 fof('DIFF-empty-bind', axiom, 0.06/0.43 ![VTyp0, VVar0, VCtx0]: vempty!=vbind(VVar0, VTyp0, VCtx0)). 0.06/0.43 fof('DIFF-noExp-someExp', axiom, 0.06/0.43 ![VExp0]: vsomeExp(VExp0)!=vnoExp). 0.06/0.43 fof('DIFF-noType-someType', axiom, 0.06/0.43 ![VTyp0]: vnoType!=vsomeType(VTyp0)). 0.06/0.43 fof('DIFF-var-abs', axiom, 0.06/0.43 ![VExp0, VTyp0, VVar0, VVar1]: 0.06/0.43 vabs(VVar1, VTyp0, VExp0)!=vvar(VVar0)). 0.06/0.43 fof('DIFF-var-app', axiom, 0.06/0.43 ![VExp0, VVar0, VExp1]: vapp(VExp0, VExp1)!=vvar(VVar0)). 0.06/0.43 fof('fresh-free-2', conjecture, 0.06/0.44 ![Ve, Ve1, Vx, Vfresh]: 0.06/0.44 (vgensym(vapp(vapp(Ve, Ve1), vvar(Vx)))=Vfresh 0.06/0.44 => ~visFreeVar(Vfresh, Ve1))). 0.06/0.44 fof('fresh-unequal-var-3', axiom, 0.06/0.44 ![Ve, Ve1, Vx, Vfresh]: 0.06/0.44 (Vfresh=vgensym(vapp(vapp(Ve, Ve1), vvar(Vx))) => Vfresh!=Vx)). 0.06/0.44 fof('gensym-is-fresh', axiom, 0.06/0.44 ![Ve, Vv]: (~visFreeVar(Vv, Ve) <= vgensym(Ve)=Vv)). 0.06/0.44 fof('reduce-INV', axiom, 0.06/0.44 ![VExp0, RESULT]: 0.06/0.44 ((?[Vx]: (vnoExp=RESULT & vvar(Vx)=VExp0) 0.06/0.44 | (?[Ve1, Vx, Ve2, VS, Ve2red]: 0.06/0.44 (VExp0=vapp(vabs(Vx, VS, Ve1), Ve2) 0.06/0.44 & (visSomeExp(Ve2red) 0.06/0.44 & (vsomeExp(vapp(vabs(Vx, VS, Ve1), vgetSomeExp(Ve2red)))=RESULT 0.06/0.44 & Ve2red=vreduce(Ve2)))) 0.06/0.44 | (?[Ve1, Vx, Ve2, VS, Ve2red]: 0.06/0.44 (~visSomeExp(Ve2red) 0.06/0.44 & (visValue(Ve2) 0.06/0.44 & (vsomeExp(vsubst(Vx, Ve2, Ve1))=RESULT 0.06/0.44 & (Ve2red=vreduce(Ve2) & VExp0=vapp(vabs(Vx, VS, Ve1), Ve2))))) 0.06/0.44 | (?[Ve1, Ve2, Ve1red]: 0.06/0.44 (VExp0=vapp(Ve1, Ve2) 0.06/0.44 & (![VVx0, VVS0, VVe10]: Ve1!=vabs(VVx0, VVS0, VVe10) 0.06/0.44 & (RESULT=vnoExp & (~visSomeExp(Ve1red) & Ve1red=vreduce(Ve1))))) 0.06/0.44 | (?[Ve1, Ve2, Ve1red]: 0.06/0.44 (vreduce(Ve1)=Ve1red 0.06/0.44 & (visSomeExp(Ve1red) 0.06/0.44 & (vsomeExp(vapp(vgetSomeExp(Ve1red), Ve2))=RESULT 0.06/0.44 & (![VVx0, VVS0, VVe10]: Ve1!=vabs(VVx0, VVS0, VVe10) 0.06/0.44 & vapp(Ve1, Ve2)=VExp0)))) 0.06/0.44 | (?[Ve1, Vx, Ve2, VS, Ve2red]: 0.06/0.44 (~visValue(Ve2) 0.06/0.44 & (RESULT=vnoExp 0.06/0.44 & (~visSomeExp(Ve2red) 0.06/0.44 & (Ve2red=vreduce(Ve2) 0.06/0.44 & VExp0=vapp(vabs(Vx, VS, Ve1), Ve2))))) 0.06/0.44 | ?[Ve, Vx, VS]: (vnoExp=RESULT & VExp0=vabs(Vx, VS, Ve)))))))) 0.06/0.44 <= RESULT=vreduce(VExp0))). 0.06/0.44 fof('subst-INV', axiom, 0.06/0.44 ![VExp0, RESULT, VVar0, VExp1]: 0.06/0.44 ((?[Ve, Vx, Vy]: 0.06/0.44 (VExp0=Ve 0.06/0.44 & (vvar(Vy)=VExp1 & (Vx!=Vy & (vvar(Vy)=RESULT & VVar0=Vx)))) 0.06/0.44 | (?[Ve, Ve1, Vx, Ve2]: 0.06/0.44 (VExp0=Ve 0.06/0.44 & (VExp1=vapp(Ve1, Ve2) 0.06/0.44 & (RESULT=vapp(vsubst(Vx, Ve, Ve1), vsubst(Vx, Ve, Ve2)) 0.06/0.44 & Vx=VVar0))) 0.06/0.44 | (?[Ve, Ve1, Vx, VT, Vy, Vfresh]: 0.06/0.44 (Vx=VVar0 0.06/0.44 & (VExp0=Ve 0.06/0.44 & (RESULT=vsubst(Vx, Ve, 0.06/0.44 vabs(Vfresh, VT, vsubst(Vy, vvar(Vfresh), Ve1))) 0.06/0.44 & (Vfresh=vgensym(vapp(vapp(Ve, Ve1), vvar(Vx))) 0.06/0.44 & (visFreeVar(Vy, Ve) 0.06/0.44 & (Vx!=Vy & vabs(Vy, VT, Ve1)=VExp1)))))) 0.06/0.44 | (?[Ve, Ve1, Vx, VT, Vy]: 0.06/0.44 (VVar0=Vx 0.06/0.44 & (VExp0=Ve 0.06/0.44 & (~visFreeVar(Vy, Ve) 0.06/0.44 & (RESULT=vabs(Vy, VT, vsubst(Vx, Ve, Ve1)) 0.06/0.44 & (Vy!=Vx & vabs(Vy, VT, Ve1)=VExp1))))) 0.06/0.44 | (?[Ve, Ve1, Vx, VT, Vy]: 0.06/0.44 (VExp0=Ve 0.06/0.44 & (Vx=Vy 0.06/0.44 & (RESULT=vabs(Vy, VT, Ve1) 0.06/0.44 & (VExp1=vabs(Vy, VT, Ve1) & Vx=VVar0)))) 0.06/0.44 | ?[Ve, Vx, Vy]: 0.06/0.44 (Ve=VExp0 0.06/0.44 & (RESULT=Ve & (Vx=Vy & (vvar(Vy)=VExp1 & Vx=VVar0))))))))) 0.06/0.44 <= vsubst(VVar0, VExp0, VExp1)=RESULT)). 0.06/0.44 fof(isFreeVar1, axiom, 0.06/0.44 ![Ve, Vx, VExp0, VVar0, VT, Vv]: 0.06/0.44 ((Vv=VVar0 & VExp0=vabs(Vx, VT, Ve)) 0.06/0.44 => (((Vv!=Vx & visFreeVar(Vv, Ve)) <= visFreeVar(VVar0, VExp0)) 0.06/0.44 & (visFreeVar(VVar0, VExp0) <= (visFreeVar(Vv, Ve) & Vx!=Vv))))). 0.06/0.44 fof(isFreeVar2, axiom, 0.06/0.44 ![Ve1, VExp0, Ve2, VVar0, Vv]: 0.06/0.44 ((VVar0=Vv & vapp(Ve1, Ve2)=VExp0) 0.06/0.44 => ((visFreeVar(VVar0, VExp0) 0.06/0.44 => (visFreeVar(Vv, Ve1) | visFreeVar(Vv, Ve2))) 0.06/0.44 & (visFreeVar(VVar0, VExp0) 0.06/0.44 <= (visFreeVar(Vv, Ve1) | visFreeVar(Vv, Ve2)))))). 0.06/0.44 fof(isSomeExp0, axiom, 0.06/0.44 ![VOptExp0]: (vnoExp=VOptExp0 => ~visSomeExp(VOptExp0))). 0.06/0.44 fof(isSomeType0, axiom, 0.06/0.44 ![VOptTyp0]: (~visSomeType(VOptTyp0) <= VOptTyp0=vnoType)). 0.06/0.44 fof(isValue1, axiom, 0.06/0.44 ![Vx, VExp0]: (vvar(Vx)=VExp0 => ~visValue(VExp0))). 0.06/0.44 fof(isValue2, axiom, 0.06/0.44 ![Ve1, VExp0, Ve2]: (~visValue(VExp0) <= VExp0=vapp(Ve1, Ve2))). 0.06/0.44 0.06/0.44 Now clausify the problem and encode Horn clauses using encoding 3 of 0.06/0.44 http://www.cse.chalmers.se/~nicsma/papers/horn.pdf. 0.06/0.44 We repeatedly replace C & s=t => u=v by the two clauses: 0.06/0.44 $$fresh(y, y, x1...xn) = u 0.06/0.44 C => $$fresh(s, t, x1...xn) = v 0.06/0.44 where $$fresh is a fresh function symbol and x1..xn are the free 0.06/0.44 variables of u and v. 0.06/0.44 A predicate p(X) is encoded as p(X)=$$true (this is sound, because the 0.06/0.44 input problem has no model of domain size 1). 0.06/0.44 0.06/0.44 The encoding turns the above axioms into the following unit equations and goals: 0.06/0.44 0.06/0.44 Axiom 40 (isFreeVar2_1): $$fresh72(X, X, Y, Z, W, V) = visFreeVar(W, Y). 0.06/0.44 Axiom 41 (isFreeVar2_1): $$fresh71(X, X, Y, Z) = $$true2. 0.06/0.44 Axiom 42 (isFreeVar2_2): $$fresh70(X, X, Y, Z, W, V) = visFreeVar(W, Y). 0.06/0.44 Axiom 43 (isFreeVar2_2): $$fresh69(X, X, Y, Z) = $$true2. 0.06/0.44 Axiom 137 (isFreeVar2_2): $$fresh70(visFreeVar(X, Y), $$true2, Z, W, X, Y) = $$fresh69(vapp(W, Y), Z, Z, X). 0.06/0.44 Axiom 138 (isFreeVar2_1): $$fresh72(visFreeVar(X, Y), $$true2, Z, Y, X, W) = $$fresh71(vapp(Y, W), Z, Z, X). 0.06/0.44 Axiom 159 (fresh-free-2): vgensym(vapp(vapp(sK2_fresh-free-2_Ve, sK3_fresh-free-2_Ve1), vvar(sK1_fresh-free-2_Vx))) = sK4_fresh-free-2_Vfresh. 0.06/0.44 Axiom 160 (fresh-free-2_1): visFreeVar(sK4_fresh-free-2_Vfresh, sK3_fresh-free-2_Ve1) = $$true2. 0.06/0.44 0.06/0.44 Goal 1 (gensym-is-fresh): tuple2(vgensym(X), visFreeVar(Y, X)) = tuple2(Y, $$true2). 0.06/0.44 The goal is true when: 0.06/0.44 X = vapp(vapp(sK2_fresh-free-2_Ve, sK3_fresh-free-2_Ve1), vvar(sK1_fresh-free-2_Vx)) 0.06/0.44 Y = sK4_fresh-free-2_Vfresh 0.06/0.44 0.06/0.44 Proof: 0.06/0.44 tuple2(vgensym(vapp(vapp(sK2_fresh-free-2_Ve, sK3_fresh-free-2_Ve1), vvar(sK1_fresh-free-2_Vx))), visFreeVar(sK4_fresh-free-2_Vfresh, vapp(vapp(sK2_fresh-free-2_Ve, sK3_fresh-free-2_Ve1), vvar(sK1_fresh-free-2_Vx)))) 0.06/0.44 = { by axiom 159 (fresh-free-2) } 0.06/0.44 tuple2(sK4_fresh-free-2_Vfresh, visFreeVar(sK4_fresh-free-2_Vfresh, vapp(vapp(sK2_fresh-free-2_Ve, sK3_fresh-free-2_Ve1), vvar(sK1_fresh-free-2_Vx)))) 0.06/0.44 = { by axiom 40 (isFreeVar2_1) } 0.06/0.44 tuple2(sK4_fresh-free-2_Vfresh, $$fresh72($$true2, $$true2, vapp(vapp(sK2_fresh-free-2_Ve, sK3_fresh-free-2_Ve1), vvar(sK1_fresh-free-2_Vx)), vapp(sK2_fresh-free-2_Ve, sK3_fresh-free-2_Ve1), sK4_fresh-free-2_Vfresh, vvar(sK1_fresh-free-2_Vx))) 0.06/0.44 = { by axiom 43 (isFreeVar2_2) } 0.06/0.44 tuple2(sK4_fresh-free-2_Vfresh, $$fresh72($$fresh69(vapp(sK2_fresh-free-2_Ve, sK3_fresh-free-2_Ve1), vapp(sK2_fresh-free-2_Ve, sK3_fresh-free-2_Ve1), vapp(sK2_fresh-free-2_Ve, sK3_fresh-free-2_Ve1), sK4_fresh-free-2_Vfresh), $$true2, vapp(vapp(sK2_fresh-free-2_Ve, sK3_fresh-free-2_Ve1), vvar(sK1_fresh-free-2_Vx)), vapp(sK2_fresh-free-2_Ve, sK3_fresh-free-2_Ve1), sK4_fresh-free-2_Vfresh, vvar(sK1_fresh-free-2_Vx))) 0.06/0.44 = { by axiom 137 (isFreeVar2_2) } 0.06/0.44 tuple2(sK4_fresh-free-2_Vfresh, $$fresh72($$fresh70(visFreeVar(sK4_fresh-free-2_Vfresh, sK3_fresh-free-2_Ve1), $$true2, vapp(sK2_fresh-free-2_Ve, sK3_fresh-free-2_Ve1), sK2_fresh-free-2_Ve, sK4_fresh-free-2_Vfresh, sK3_fresh-free-2_Ve1), $$true2, vapp(vapp(sK2_fresh-free-2_Ve, sK3_fresh-free-2_Ve1), vvar(sK1_fresh-free-2_Vx)), vapp(sK2_fresh-free-2_Ve, sK3_fresh-free-2_Ve1), sK4_fresh-free-2_Vfresh, vvar(sK1_fresh-free-2_Vx))) 0.06/0.44 = { by axiom 160 (fresh-free-2_1) } 0.06/0.44 tuple2(sK4_fresh-free-2_Vfresh, $$fresh72($$fresh70($$true2, $$true2, vapp(sK2_fresh-free-2_Ve, sK3_fresh-free-2_Ve1), sK2_fresh-free-2_Ve, sK4_fresh-free-2_Vfresh, sK3_fresh-free-2_Ve1), $$true2, vapp(vapp(sK2_fresh-free-2_Ve, sK3_fresh-free-2_Ve1), vvar(sK1_fresh-free-2_Vx)), vapp(sK2_fresh-free-2_Ve, sK3_fresh-free-2_Ve1), sK4_fresh-free-2_Vfresh, vvar(sK1_fresh-free-2_Vx))) 0.06/0.44 = { by axiom 42 (isFreeVar2_2) } 0.06/0.44 tuple2(sK4_fresh-free-2_Vfresh, $$fresh72(visFreeVar(sK4_fresh-free-2_Vfresh, vapp(sK2_fresh-free-2_Ve, sK3_fresh-free-2_Ve1)), $$true2, vapp(vapp(sK2_fresh-free-2_Ve, sK3_fresh-free-2_Ve1), vvar(sK1_fresh-free-2_Vx)), vapp(sK2_fresh-free-2_Ve, sK3_fresh-free-2_Ve1), sK4_fresh-free-2_Vfresh, vvar(sK1_fresh-free-2_Vx))) 0.06/0.44 = { by axiom 138 (isFreeVar2_1) } 0.06/0.44 tuple2(sK4_fresh-free-2_Vfresh, $$fresh71(vapp(vapp(sK2_fresh-free-2_Ve, sK3_fresh-free-2_Ve1), vvar(sK1_fresh-free-2_Vx)), vapp(vapp(sK2_fresh-free-2_Ve, sK3_fresh-free-2_Ve1), vvar(sK1_fresh-free-2_Vx)), vapp(vapp(sK2_fresh-free-2_Ve, sK3_fresh-free-2_Ve1), vvar(sK1_fresh-free-2_Vx)), sK4_fresh-free-2_Vfresh)) 0.06/0.44 = { by axiom 41 (isFreeVar2_1) } 0.06/0.44 tuple2(sK4_fresh-free-2_Vfresh, $$true2) 0.06/0.44 % SZS output end Proof 0.06/0.44 0.06/0.44 RESULT: Theorem (the conjecture is true). 0.06/0.46 EOF