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.03/0.23 % Computer : n158.star.cs.uiowa.edu 0.03/0.23 % Model : x86_64 x86_64 0.03/0.23 % CPU : Intel(R) Xeon(R) CPU E5-2609 0 @ 2.40GHz 0.03/0.23 % Memory : 32218.625MB 0.03/0.23 % OS : Linux 3.10.0-693.2.2.el7.x86_64 0.03/0.23 % CPULimit : 300 0.03/0.23 % DateTime : Sat Jul 14 04:25:39 CDT 2018 0.03/0.23 % CPUTime : 0.44/0.67 % SZS status Theorem 0.44/0.67 0.44/0.67 % SZS output start Proof 0.44/0.67 Take the following subset of the input axioms: 0.50/0.68 fof(ax83, axiom, 0.50/0.68 ![U]: 0.50/0.68 (ssList(U) 0.50/0.68 => ![V]: ((nil=app(U, V) <=> (U=nil & nil=V)) <= ssList(V)))). 0.50/0.68 fof(ax84, axiom, ![U]: (ssList(U) => app(U, nil)=U)). 0.50/0.68 fof(co1, conjecture, 0.50/0.68 ![U]: 0.50/0.68 (ssList(U) 0.50/0.68 => ![V]: 0.50/0.68 (![W]: 0.50/0.68 (![X]: 0.50/0.68 ((nil!=V 0.50/0.68 | (W!=U 0.50/0.68 | (U=nil 0.50/0.68 | (![Y]: 0.50/0.68 ((X!=app(W, Y) 0.50/0.68 | (~strictorderedP(W) 0.50/0.68 | ?[Z]: 0.50/0.68 (?[X1]: 0.50/0.68 (ssList(X1) 0.50/0.68 & (?[X2]: 0.50/0.68 (?[X3]: 0.50/0.68 (ssList(X3) 0.50/0.68 & (W=app(X3, cons(X2, nil)) 0.50/0.68 & lt(X2, Z))) 0.50/0.68 & ssItem(X2)) 0.50/0.68 & app(cons(Z, nil), X1)=Y)) 0.50/0.68 & ssItem(Z)))) 0.50/0.68 <= ssList(Y)) 0.50/0.68 | ((X!=nil & W=nil) | X!=V))))) 0.50/0.68 <= ssList(X)) 0.50/0.68 <= ssList(W)) 0.50/0.68 <= ssList(V)))). 0.50/0.68 0.50/0.68 Now clausify the problem and encode Horn clauses using encoding 3 of 0.50/0.68 http://www.cse.chalmers.se/~nicsma/papers/horn.pdf. 0.50/0.68 We repeatedly replace C & s=t => u=v by the two clauses: 0.50/0.68 $$fresh(y, y, x1...xn) = u 0.50/0.68 C => $$fresh(s, t, x1...xn) = v 0.50/0.68 where $$fresh is a fresh function symbol and x1..xn are the free 0.50/0.68 variables of u and v. 0.50/0.68 A predicate p(X) is encoded as p(X)=$$true (this is sound, because the 0.50/0.68 input problem has no model of domain size 1). 0.50/0.68 0.50/0.68 The encoding turns the above axioms into the following unit equations and goals: 0.50/0.68 0.50/0.68 Axiom 257 (ax83_2): $$fresh110(X, X, Y) = Y. 0.50/0.68 Axiom 258 (ax83_2): $$fresh23(X, X, Y, Z) = nil. 0.50/0.68 Axiom 259 (ax83_2): $$fresh111(X, X, Y, Z) = $$fresh110(nil, app(Y, Z), Z). 0.50/0.68 Axiom 260 (ax84): $$fresh11(X, X, Y) = Y. 0.50/0.68 Axiom 309 (ax84): $$fresh11(ssList(X), $$true2, X) = app(X, nil). 0.50/0.68 Axiom 387 (ax83_2): $$fresh111(ssList(X), $$true2, Y, X) = $$fresh23(ssList(Y), $$true2, Y, X). 0.50/0.68 Axiom 393 (co1): sK2_co1_X = app(sK3_co1_W, sK1_co1_Y). 0.50/0.68 Axiom 394 (co1_1): nil = sK4_co1_V. 0.50/0.68 Axiom 395 (co1_2): sK3_co1_W = sK5_co1_U. 0.50/0.68 Axiom 396 (co1_3): sK2_co1_X = sK4_co1_V. 0.50/0.68 Axiom 397 (co1_4): ssList(sK5_co1_U) = $$true2. 0.50/0.68 Axiom 401 (co1_8): ssList(sK1_co1_Y) = $$true2. 0.50/0.68 0.50/0.68 Lemma 402: sK2_co1_X = nil. 0.50/0.68 Proof: 0.50/0.68 sK2_co1_X 0.50/0.68 = { by axiom 396 (co1_3) } 0.50/0.68 sK4_co1_V 0.50/0.68 = { by axiom 394 (co1_1) } 0.50/0.68 nil 0.50/0.68 0.50/0.68 Lemma 403: ssList(sK3_co1_W) = $$true2. 0.50/0.68 Proof: 0.50/0.68 ssList(sK3_co1_W) 0.50/0.68 = { by axiom 395 (co1_2) } 0.50/0.68 ssList(sK5_co1_U) 0.50/0.68 = { by axiom 397 (co1_4) } 0.50/0.68 $$true2 0.50/0.68 0.50/0.68 Goal 1 (co1_11): sK5_co1_U = nil. 0.50/0.68 Proof: 0.50/0.68 sK5_co1_U 0.50/0.68 = { by axiom 395 (co1_2) } 0.50/0.68 sK3_co1_W 0.50/0.68 = { by axiom 260 (ax84) } 0.50/0.68 $$fresh11($$true2, $$true2, sK3_co1_W) 0.50/0.68 = { by lemma 403 } 0.50/0.68 $$fresh11(ssList(sK3_co1_W), $$true2, sK3_co1_W) 0.50/0.68 = { by axiom 309 (ax84) } 0.50/0.68 app(sK3_co1_W, nil) 0.50/0.68 = { by axiom 258 (ax83_2) } 0.50/0.68 app(sK3_co1_W, $$fresh23($$true2, $$true2, sK3_co1_W, sK1_co1_Y)) 0.50/0.68 = { by lemma 403 } 0.50/0.68 app(sK3_co1_W, $$fresh23(ssList(sK3_co1_W), $$true2, sK3_co1_W, sK1_co1_Y)) 0.50/0.68 = { by axiom 387 (ax83_2) } 0.50/0.68 app(sK3_co1_W, $$fresh111(ssList(sK1_co1_Y), $$true2, sK3_co1_W, sK1_co1_Y)) 0.50/0.68 = { by axiom 401 (co1_8) } 0.50/0.68 app(sK3_co1_W, $$fresh111($$true2, $$true2, sK3_co1_W, sK1_co1_Y)) 0.50/0.68 = { by axiom 259 (ax83_2) } 0.50/0.68 app(sK3_co1_W, $$fresh110(nil, app(sK3_co1_W, sK1_co1_Y), sK1_co1_Y)) 0.50/0.68 = { by axiom 393 (co1) } 0.50/0.68 app(sK3_co1_W, $$fresh110(nil, sK2_co1_X, sK1_co1_Y)) 0.50/0.68 = { by lemma 402 } 0.50/0.68 app(sK3_co1_W, $$fresh110(nil, nil, sK1_co1_Y)) 0.50/0.68 = { by axiom 257 (ax83_2) } 0.50/0.68 app(sK3_co1_W, sK1_co1_Y) 0.50/0.68 = { by axiom 393 (co1) } 0.50/0.68 sK2_co1_X 0.50/0.68 = { by lemma 402 } 0.50/0.68 nil 0.50/0.68 % SZS output end Proof 0.50/0.68 0.50/0.68 RESULT: Theorem (the conjecture is true). 0.50/0.69 EOF