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 : n127.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:56:55 CDT 2018 0.02/0.23 % CPUTime : 0.06/0.38 % SZS status Theorem 0.06/0.38 0.06/0.38 % SZS output start Proof 0.06/0.38 Take the following subset of the input axioms: 0.06/0.38 fof('DIFF-abs-app', axiom, 0.06/0.38 ![VExp0, VTyp0, VVar0, VExp1, VExp2]: 0.06/0.38 vapp(VExp1, VExp2)!=vabs(VVar0, VTyp0, VExp0)). 0.06/0.38 fof('DIFF-empty-bind', axiom, 0.06/0.38 ![VTyp0, VVar0, VCtx0]: vempty!=vbind(VVar0, VTyp0, VCtx0)). 0.06/0.38 fof('DIFF-noExp-someExp', axiom, 0.06/0.38 ![VExp0]: vsomeExp(VExp0)!=vnoExp). 0.06/0.38 fof('DIFF-noType-someType', axiom, 0.06/0.38 ![VTyp0]: vnoType!=vsomeType(VTyp0)). 0.06/0.38 fof('DIFF-var-abs', axiom, 0.06/0.38 ![VExp0, VTyp0, VVar0, VVar1]: 0.06/0.38 vabs(VVar1, VTyp0, VExp0)!=vvar(VVar0)). 0.06/0.38 fof('DIFF-var-app', axiom, 0.06/0.38 ![VExp0, VVar0, VExp1]: vapp(VExp0, VExp1)!=vvar(VVar0)). 0.06/0.38 fof('fresh-unequal-var-3', conjecture, 0.06/0.38 ![Ve1, Ve, Vx, Vfresh]: 0.06/0.38 (Vfresh=vgensym(vapp(vapp(Ve, Ve1), vvar(Vx))) => Vfresh!=Vx)). 0.06/0.38 fof('gensym-is-fresh', axiom, 0.06/0.38 ![Ve, Vv]: (~visFreeVar(Vv, Ve) <= vgensym(Ve)=Vv)). 0.06/0.38 fof('reduce-INV', axiom, 0.06/0.38 ![VExp0, RESULT]: 0.06/0.38 ((?[Vx]: (vnoExp=RESULT & vvar(Vx)=VExp0) 0.06/0.38 | (?[Ve1, Ve2, Vx, VS, Ve2red]: 0.06/0.38 (VExp0=vapp(vabs(Vx, VS, Ve1), Ve2) 0.06/0.38 & (visSomeExp(Ve2red) 0.06/0.38 & (vsomeExp(vapp(vabs(Vx, VS, Ve1), vgetSomeExp(Ve2red)))=RESULT 0.06/0.38 & Ve2red=vreduce(Ve2)))) 0.06/0.38 | (?[Ve1, Ve2, Vx, VS, Ve2red]: 0.06/0.38 (~visSomeExp(Ve2red) 0.06/0.38 & (visValue(Ve2) 0.06/0.38 & (vsomeExp(vsubst(Vx, Ve2, Ve1))=RESULT 0.06/0.38 & (Ve2red=vreduce(Ve2) & VExp0=vapp(vabs(Vx, VS, Ve1), Ve2))))) 0.06/0.38 | (?[Ve1, Ve2, Ve1red]: 0.06/0.38 (VExp0=vapp(Ve1, Ve2) 0.06/0.38 & (![VVx0, VVS0, VVe10]: Ve1!=vabs(VVx0, VVS0, VVe10) 0.06/0.38 & (RESULT=vnoExp & (~visSomeExp(Ve1red) & Ve1red=vreduce(Ve1))))) 0.06/0.38 | (?[Ve1, Ve2, Ve1red]: 0.06/0.38 (vreduce(Ve1)=Ve1red 0.06/0.38 & (visSomeExp(Ve1red) 0.06/0.39 & (vsomeExp(vapp(vgetSomeExp(Ve1red), Ve2))=RESULT 0.06/0.39 & (![VVx0, VVS0, VVe10]: Ve1!=vabs(VVx0, VVS0, VVe10) 0.06/0.39 & vapp(Ve1, Ve2)=VExp0)))) 0.06/0.39 | (?[Ve1, Ve2, Vx, VS, Ve2red]: 0.06/0.39 (~visValue(Ve2) 0.06/0.39 & (RESULT=vnoExp 0.06/0.39 & (~visSomeExp(Ve2red) 0.06/0.39 & (Ve2red=vreduce(Ve2) 0.06/0.39 & VExp0=vapp(vabs(Vx, VS, Ve1), Ve2))))) 0.06/0.39 | ?[Ve, Vx, VS]: (vnoExp=RESULT & VExp0=vabs(Vx, VS, Ve)))))))) 0.06/0.39 <= RESULT=vreduce(VExp0))). 0.06/0.39 fof('subst-INV', axiom, 0.06/0.39 ![VExp0, RESULT, VVar0, VExp1]: 0.06/0.39 ((?[Ve, Vx, Vy]: 0.06/0.39 (VExp0=Ve 0.06/0.39 & (vvar(Vy)=VExp1 & (Vx!=Vy & (vvar(Vy)=RESULT & VVar0=Vx)))) 0.06/0.39 | (?[Ve1, Ve2, Ve, Vx]: 0.06/0.39 (VExp0=Ve 0.06/0.39 & (VExp1=vapp(Ve1, Ve2) 0.06/0.39 & (RESULT=vapp(vsubst(Vx, Ve, Ve1), vsubst(Vx, Ve, Ve2)) 0.06/0.39 & Vx=VVar0))) 0.06/0.39 | (?[Ve1, VT, Ve, Vx, Vy, Vfresh]: 0.06/0.39 (Vx=VVar0 0.06/0.39 & (VExp0=Ve 0.06/0.39 & (RESULT=vsubst(Vx, Ve, 0.06/0.39 vabs(Vfresh, VT, vsubst(Vy, vvar(Vfresh), Ve1))) 0.06/0.39 & (Vfresh=vgensym(vapp(vapp(Ve, Ve1), vvar(Vx))) 0.06/0.39 & (visFreeVar(Vy, Ve) 0.06/0.39 & (Vx!=Vy & vabs(Vy, VT, Ve1)=VExp1)))))) 0.06/0.39 | (?[Ve1, VT, Ve, Vx, Vy]: 0.06/0.39 (VVar0=Vx 0.06/0.39 & (VExp0=Ve 0.06/0.39 & (~visFreeVar(Vy, Ve) 0.06/0.39 & (RESULT=vabs(Vy, VT, vsubst(Vx, Ve, Ve1)) 0.06/0.39 & (Vy!=Vx & vabs(Vy, VT, Ve1)=VExp1))))) 0.06/0.39 | (?[Ve1, VT, Ve, Vx, Vy]: 0.06/0.39 (VExp0=Ve 0.06/0.39 & (Vx=Vy 0.06/0.39 & (RESULT=vabs(Vy, VT, Ve1) 0.06/0.39 & (VExp1=vabs(Vy, VT, Ve1) & Vx=VVar0)))) 0.06/0.39 | ?[Ve, Vx, Vy]: 0.06/0.39 (Ve=VExp0 0.06/0.39 & (RESULT=Ve & (Vx=Vy & (vvar(Vy)=VExp1 & Vx=VVar0))))))))) 0.06/0.39 <= vsubst(VVar0, VExp0, VExp1)=RESULT)). 0.06/0.39 fof(isFreeVar0, axiom, 0.06/0.39 ![VExp0, VVar0, Vv, Vx]: 0.06/0.39 (((visFreeVar(VVar0, VExp0) <= Vv=Vx) 0.06/0.39 & (Vx=Vv <= visFreeVar(VVar0, VExp0))) 0.06/0.39 <= (VExp0=vvar(Vx) & Vv=VVar0))). 0.06/0.39 fof(isFreeVar1, axiom, 0.06/0.39 ![VExp0, VVar0, VT, Ve, Vv, Vx]: 0.06/0.39 ((Vv=VVar0 & VExp0=vabs(Vx, VT, Ve)) 0.06/0.39 => (((Vv!=Vx & visFreeVar(Vv, Ve)) <= visFreeVar(VVar0, VExp0)) 0.06/0.39 & (visFreeVar(VVar0, VExp0) <= (visFreeVar(Vv, Ve) & Vx!=Vv))))). 0.06/0.39 fof(isFreeVar2, axiom, 0.06/0.39 ![VExp0, Ve1, Ve2, VVar0, Vv]: 0.06/0.39 ((VVar0=Vv & vapp(Ve1, Ve2)=VExp0) 0.06/0.39 => ((visFreeVar(VVar0, VExp0) 0.06/0.39 => (visFreeVar(Vv, Ve1) | visFreeVar(Vv, Ve2))) 0.06/0.39 & (visFreeVar(VVar0, VExp0) 0.06/0.39 <= (visFreeVar(Vv, Ve1) | visFreeVar(Vv, Ve2)))))). 0.06/0.39 fof(isSomeExp0, axiom, 0.06/0.39 ![VOptExp0]: (vnoExp=VOptExp0 => ~visSomeExp(VOptExp0))). 0.06/0.39 fof(isSomeType0, axiom, 0.06/0.39 ![VOptTyp0]: (~visSomeType(VOptTyp0) <= VOptTyp0=vnoType)). 0.06/0.39 fof(isValue1, axiom, 0.06/0.39 ![VExp0, Vx]: (vvar(Vx)=VExp0 => ~visValue(VExp0))). 0.06/0.39 fof(isValue2, axiom, 0.06/0.39 ![VExp0, Ve1, Ve2]: (~visValue(VExp0) <= VExp0=vapp(Ve1, Ve2))). 0.06/0.39 0.06/0.39 Now clausify the problem and encode Horn clauses using encoding 3 of 0.06/0.39 http://www.cse.chalmers.se/~nicsma/papers/horn.pdf. 0.06/0.39 We repeatedly replace C & s=t => u=v by the two clauses: 0.06/0.39 $$fresh(y, y, x1...xn) = u 0.06/0.39 C => $$fresh(s, t, x1...xn) = v 0.06/0.39 where $$fresh is a fresh function symbol and x1..xn are the free 0.06/0.39 variables of u and v. 0.06/0.39 A predicate p(X) is encoded as p(X)=$$true (this is sound, because the 0.06/0.39 input problem has no model of domain size 1). 0.06/0.39 0.06/0.39 The encoding turns the above axioms into the following unit equations and goals: 0.06/0.39 0.06/0.39 Axiom 35 (isFreeVar0): $$fresh75(X, X, Y, Z) = $$true2. 0.06/0.39 Axiom 42 (isFreeVar2_2): $$fresh70(X, X, Y, Z, W, V) = visFreeVar(W, Y). 0.06/0.39 Axiom 43 (isFreeVar2_2): $$fresh69(X, X, Y, Z) = $$true2. 0.06/0.39 Axiom 137 (isFreeVar2_2): $$fresh70(visFreeVar(X, Y), $$true2, Z, W, X, Y) = $$fresh69(vapp(W, Y), Z, Z, X). 0.06/0.39 Axiom 151 (isFreeVar0): $$fresh75(X, vvar(Y), Y, X) = visFreeVar(Y, X). 0.06/0.39 Axiom 159 (fresh-unequal-var-3): sK3_fresh-unequal-var-3_Vfresh = vgensym(vapp(vapp(sK2_fresh-unequal-var-3_Ve, sK1_fresh-unequal-var-3_Ve1), vvar(sK4_fresh-unequal-var-3_Vx))). 0.06/0.39 Axiom 160 (fresh-unequal-var-3_1): sK3_fresh-unequal-var-3_Vfresh = sK4_fresh-unequal-var-3_Vx. 0.06/0.39 0.06/0.39 Goal 1 (gensym-is-fresh): tuple2(vgensym(X), visFreeVar(Y, X)) = tuple2(Y, $$true2). 0.06/0.39 The goal is true when: 0.06/0.39 X = vapp(vapp(sK2_fresh-unequal-var-3_Ve, sK1_fresh-unequal-var-3_Ve1), vvar(sK4_fresh-unequal-var-3_Vx)) 0.06/0.39 Y = sK4_fresh-unequal-var-3_Vx 0.06/0.39 0.06/0.39 Proof: 0.06/0.39 tuple2(vgensym(vapp(vapp(sK2_fresh-unequal-var-3_Ve, sK1_fresh-unequal-var-3_Ve1), vvar(sK4_fresh-unequal-var-3_Vx))), visFreeVar(sK4_fresh-unequal-var-3_Vx, vapp(vapp(sK2_fresh-unequal-var-3_Ve, sK1_fresh-unequal-var-3_Ve1), vvar(sK4_fresh-unequal-var-3_Vx)))) 0.06/0.39 = { by axiom 159 (fresh-unequal-var-3) } 0.06/0.39 tuple2(sK3_fresh-unequal-var-3_Vfresh, visFreeVar(sK4_fresh-unequal-var-3_Vx, vapp(vapp(sK2_fresh-unequal-var-3_Ve, sK1_fresh-unequal-var-3_Ve1), vvar(sK4_fresh-unequal-var-3_Vx)))) 0.06/0.39 = { by axiom 160 (fresh-unequal-var-3_1) } 0.06/0.39 tuple2(sK4_fresh-unequal-var-3_Vx, visFreeVar(sK4_fresh-unequal-var-3_Vx, vapp(vapp(sK2_fresh-unequal-var-3_Ve, sK1_fresh-unequal-var-3_Ve1), vvar(sK4_fresh-unequal-var-3_Vx)))) 0.06/0.39 = { by axiom 42 (isFreeVar2_2) } 0.06/0.39 tuple2(sK4_fresh-unequal-var-3_Vx, $$fresh70($$true2, $$true2, vapp(vapp(sK2_fresh-unequal-var-3_Ve, sK1_fresh-unequal-var-3_Ve1), vvar(sK4_fresh-unequal-var-3_Vx)), vapp(sK2_fresh-unequal-var-3_Ve, sK1_fresh-unequal-var-3_Ve1), sK4_fresh-unequal-var-3_Vx, vvar(sK4_fresh-unequal-var-3_Vx))) 0.06/0.39 = { by axiom 35 (isFreeVar0) } 0.06/0.39 tuple2(sK4_fresh-unequal-var-3_Vx, $$fresh70($$fresh75(vvar(sK4_fresh-unequal-var-3_Vx), vvar(sK4_fresh-unequal-var-3_Vx), sK4_fresh-unequal-var-3_Vx, vvar(sK4_fresh-unequal-var-3_Vx)), $$true2, vapp(vapp(sK2_fresh-unequal-var-3_Ve, sK1_fresh-unequal-var-3_Ve1), vvar(sK4_fresh-unequal-var-3_Vx)), vapp(sK2_fresh-unequal-var-3_Ve, sK1_fresh-unequal-var-3_Ve1), sK4_fresh-unequal-var-3_Vx, vvar(sK4_fresh-unequal-var-3_Vx))) 0.06/0.39 = { by axiom 151 (isFreeVar0) } 0.06/0.39 tuple2(sK4_fresh-unequal-var-3_Vx, $$fresh70(visFreeVar(sK4_fresh-unequal-var-3_Vx, vvar(sK4_fresh-unequal-var-3_Vx)), $$true2, vapp(vapp(sK2_fresh-unequal-var-3_Ve, sK1_fresh-unequal-var-3_Ve1), vvar(sK4_fresh-unequal-var-3_Vx)), vapp(sK2_fresh-unequal-var-3_Ve, sK1_fresh-unequal-var-3_Ve1), sK4_fresh-unequal-var-3_Vx, vvar(sK4_fresh-unequal-var-3_Vx))) 0.06/0.39 = { by axiom 137 (isFreeVar2_2) } 0.06/0.39 tuple2(sK4_fresh-unequal-var-3_Vx, $$fresh69(vapp(vapp(sK2_fresh-unequal-var-3_Ve, sK1_fresh-unequal-var-3_Ve1), vvar(sK4_fresh-unequal-var-3_Vx)), vapp(vapp(sK2_fresh-unequal-var-3_Ve, sK1_fresh-unequal-var-3_Ve1), vvar(sK4_fresh-unequal-var-3_Vx)), vapp(vapp(sK2_fresh-unequal-var-3_Ve, sK1_fresh-unequal-var-3_Ve1), vvar(sK4_fresh-unequal-var-3_Vx)), sK4_fresh-unequal-var-3_Vx)) 0.06/0.39 = { by axiom 43 (isFreeVar2_2) } 0.06/0.39 tuple2(sK4_fresh-unequal-var-3_Vx, $$true2) 0.06/0.39 % SZS output end Proof 0.06/0.39 0.06/0.39 RESULT: Theorem (the conjecture is true). 0.06/0.39 EOF