0.11/0.12 % Problem : theBenchmark.p : TPTP v0.0.0. Released v0.0.0. 0.11/0.13 % Command : parallel-twee %s --tstp --conditional-encoding if --smaller --drop-non-horn --give-up-on-saturation --explain-encoding --formal-proof 0.13/0.34 % Computer : n008.cluster.edu 0.13/0.34 % Model : x86_64 x86_64 0.13/0.34 % CPU : Intel(R) Xeon(R) CPU E5-2620 v4 @ 2.10GHz 0.13/0.34 % Memory : 8042.1875MB 0.13/0.34 % OS : Linux 3.10.0-693.el7.x86_64 0.13/0.34 % CPULimit : 1200 0.13/0.34 % WCLimit : 120 0.13/0.34 % DateTime : Tue Jul 13 16:06:44 EDT 2021 0.13/0.35 % CPUTime : 17.15/2.58 % SZS status Theorem 17.15/2.58 17.68/2.59 % SZS output start Proof 17.68/2.59 Take the following subset of the input axioms: 17.68/2.59 fof(additive_associativity, axiom, ![A, B, C]: addition(A, addition(B, C))=addition(addition(A, B), C)). 17.68/2.59 fof(additive_commutativity, axiom, ![A, B]: addition(A, B)=addition(B, A)). 17.68/2.59 fof(distributivity2, axiom, ![A, B, C]: multiplication(addition(A, B), C)=addition(multiplication(A, C), multiplication(B, C))). 17.68/2.59 fof(goals, conjecture, ![X0, X1]: (leq(strong_iteration(multiplication(star(X0), X1)), multiplication(star(X1), strong_iteration(multiplication(star(X0), X1)))) & leq(multiplication(star(X1), strong_iteration(multiplication(star(X0), X1))), strong_iteration(multiplication(star(X0), X1))))). 17.68/2.59 fof(idempotence, axiom, ![A]: addition(A, A)=A). 17.68/2.59 fof(infty_unfold1, axiom, ![A]: strong_iteration(A)=addition(multiplication(A, strong_iteration(A)), one)). 17.68/2.59 fof(multiplicative_left_identity, axiom, ![A]: multiplication(one, A)=A). 17.68/2.59 fof(order, axiom, ![A, B]: (B=addition(A, B) <=> leq(A, B))). 17.68/2.59 fof(star_induction1, axiom, ![A, B, C]: (leq(multiplication(star(A), B), C) <= leq(addition(multiplication(A, C), B), C))). 17.68/2.59 fof(star_unfold1, axiom, ![A]: addition(one, multiplication(A, star(A)))=star(A)). 17.68/2.59 17.68/2.59 Now clausify the problem and encode Horn clauses using encoding 3 of 17.68/2.59 http://www.cse.chalmers.se/~nicsma/papers/horn.pdf. 17.68/2.59 We repeatedly replace C & s=t => u=v by the two clauses: 17.68/2.59 fresh(y, y, x1...xn) = u 17.68/2.59 C => fresh(s, t, x1...xn) = v 17.68/2.59 where fresh is a fresh function symbol and x1..xn are the free 17.68/2.59 variables of u and v. 17.68/2.59 A predicate p(X) is encoded as p(X)=true (this is sound, because the 17.68/2.59 input problem has no model of domain size 1). 17.68/2.59 17.68/2.59 The encoding turns the above axioms into the following unit equations and goals: 17.68/2.59 17.68/2.59 Axiom 1 (multiplicative_left_identity): multiplication(one, X) = X. 17.68/2.59 Axiom 2 (idempotence): addition(X, X) = X. 17.68/2.59 Axiom 3 (additive_commutativity): addition(X, Y) = addition(Y, X). 17.68/2.59 Axiom 4 (additive_associativity): addition(X, addition(Y, Z)) = addition(addition(X, Y), Z). 17.68/2.59 Axiom 5 (order): fresh5(X, X, Y, Z) = true. 17.68/2.59 Axiom 6 (star_unfold1): addition(one, multiplication(X, star(X))) = star(X). 17.68/2.59 Axiom 7 (infty_unfold1): strong_iteration(X) = addition(multiplication(X, strong_iteration(X)), one). 17.68/2.59 Axiom 8 (star_induction1): fresh3(X, X, Y, Z, W) = true. 17.68/2.59 Axiom 9 (distributivity2): multiplication(addition(X, Y), Z) = addition(multiplication(X, Z), multiplication(Y, Z)). 17.68/2.59 Axiom 10 (order): fresh5(X, addition(Y, X), Y, X) = leq(Y, X). 17.68/2.59 Axiom 11 (star_induction1): fresh3(leq(addition(multiplication(X, Y), Z), Y), true, X, Z, Y) = leq(multiplication(star(X), Z), Y). 17.68/2.59 17.68/2.59 Lemma 12: addition(one, star(X)) = star(X). 17.68/2.59 Proof: 17.68/2.59 addition(one, star(X)) 17.68/2.59 = { by axiom 6 (star_unfold1) R->L } 17.68/2.59 addition(one, addition(one, multiplication(X, star(X)))) 17.68/2.59 = { by axiom 4 (additive_associativity) } 17.68/2.59 addition(addition(one, one), multiplication(X, star(X))) 17.68/2.59 = { by axiom 2 (idempotence) } 17.68/2.59 addition(one, multiplication(X, star(X))) 17.68/2.59 = { by axiom 6 (star_unfold1) } 17.68/2.59 star(X) 17.68/2.59 17.68/2.59 Lemma 13: addition(X, multiplication(Y, X)) = multiplication(addition(Y, one), X). 17.68/2.59 Proof: 17.68/2.59 addition(X, multiplication(Y, X)) 17.68/2.59 = { by axiom 1 (multiplicative_left_identity) R->L } 17.68/2.59 addition(multiplication(one, X), multiplication(Y, X)) 17.68/2.59 = { by axiom 9 (distributivity2) R->L } 17.68/2.59 multiplication(addition(one, Y), X) 17.68/2.59 = { by axiom 3 (additive_commutativity) } 17.68/2.59 multiplication(addition(Y, one), X) 17.68/2.59 17.68/2.59 Lemma 14: addition(one, multiplication(X, strong_iteration(X))) = strong_iteration(X). 17.68/2.59 Proof: 17.68/2.59 addition(one, multiplication(X, strong_iteration(X))) 17.68/2.59 = { by axiom 3 (additive_commutativity) R->L } 17.68/2.59 addition(multiplication(X, strong_iteration(X)), one) 17.68/2.59 = { by axiom 7 (infty_unfold1) R->L } 17.68/2.59 strong_iteration(X) 17.68/2.59 17.68/2.59 Goal 1 (goals): tuple(leq(multiplication(star(x1), strong_iteration(multiplication(star(x0), x1))), strong_iteration(multiplication(star(x0), x1))), leq(strong_iteration(multiplication(star(x0_2), x1_2)), multiplication(star(x1_2), strong_iteration(multiplication(star(x0_2), x1_2))))) = tuple(true, true). 17.68/2.59 Proof: 17.68/2.59 tuple(leq(multiplication(star(x1), strong_iteration(multiplication(star(x0), x1))), strong_iteration(multiplication(star(x0), x1))), leq(strong_iteration(multiplication(star(x0_2), x1_2)), multiplication(star(x1_2), strong_iteration(multiplication(star(x0_2), x1_2))))) 17.68/2.59 = { by axiom 1 (multiplicative_left_identity) R->L } 17.68/2.59 tuple(leq(multiplication(star(x1), strong_iteration(multiplication(star(x0), x1))), strong_iteration(multiplication(star(x0), x1))), leq(multiplication(one, strong_iteration(multiplication(star(x0_2), x1_2))), multiplication(star(x1_2), strong_iteration(multiplication(star(x0_2), x1_2))))) 17.68/2.59 = { by axiom 10 (order) R->L } 17.68/2.59 tuple(leq(multiplication(star(x1), strong_iteration(multiplication(star(x0), x1))), strong_iteration(multiplication(star(x0), x1))), fresh5(multiplication(star(x1_2), strong_iteration(multiplication(star(x0_2), x1_2))), addition(multiplication(one, strong_iteration(multiplication(star(x0_2), x1_2))), multiplication(star(x1_2), strong_iteration(multiplication(star(x0_2), x1_2)))), multiplication(one, strong_iteration(multiplication(star(x0_2), x1_2))), multiplication(star(x1_2), strong_iteration(multiplication(star(x0_2), x1_2))))) 17.68/2.59 = { by axiom 9 (distributivity2) R->L } 17.68/2.59 tuple(leq(multiplication(star(x1), strong_iteration(multiplication(star(x0), x1))), strong_iteration(multiplication(star(x0), x1))), fresh5(multiplication(star(x1_2), strong_iteration(multiplication(star(x0_2), x1_2))), multiplication(addition(one, star(x1_2)), strong_iteration(multiplication(star(x0_2), x1_2))), multiplication(one, strong_iteration(multiplication(star(x0_2), x1_2))), multiplication(star(x1_2), strong_iteration(multiplication(star(x0_2), x1_2))))) 17.68/2.59 = { by lemma 12 } 17.68/2.59 tuple(leq(multiplication(star(x1), strong_iteration(multiplication(star(x0), x1))), strong_iteration(multiplication(star(x0), x1))), fresh5(multiplication(star(x1_2), strong_iteration(multiplication(star(x0_2), x1_2))), multiplication(star(x1_2), strong_iteration(multiplication(star(x0_2), x1_2))), multiplication(one, strong_iteration(multiplication(star(x0_2), x1_2))), multiplication(star(x1_2), strong_iteration(multiplication(star(x0_2), x1_2))))) 17.68/2.59 = { by axiom 5 (order) } 17.68/2.59 tuple(leq(multiplication(star(x1), strong_iteration(multiplication(star(x0), x1))), strong_iteration(multiplication(star(x0), x1))), true) 17.68/2.59 = { by axiom 1 (multiplicative_left_identity) R->L } 17.68/2.59 tuple(leq(multiplication(star(x1), multiplication(one, strong_iteration(multiplication(star(x0), x1)))), strong_iteration(multiplication(star(x0), x1))), true) 17.68/2.59 = { by axiom 11 (star_induction1) R->L } 17.68/2.59 tuple(fresh3(leq(addition(multiplication(x1, strong_iteration(multiplication(star(x0), x1))), multiplication(one, strong_iteration(multiplication(star(x0), x1)))), strong_iteration(multiplication(star(x0), x1))), true, x1, multiplication(one, strong_iteration(multiplication(star(x0), x1))), strong_iteration(multiplication(star(x0), x1))), true) 17.68/2.59 = { by axiom 9 (distributivity2) R->L } 17.68/2.59 tuple(fresh3(leq(multiplication(addition(x1, one), strong_iteration(multiplication(star(x0), x1))), strong_iteration(multiplication(star(x0), x1))), true, x1, multiplication(one, strong_iteration(multiplication(star(x0), x1))), strong_iteration(multiplication(star(x0), x1))), true) 17.68/2.59 = { by lemma 13 R->L } 17.68/2.59 tuple(fresh3(leq(addition(strong_iteration(multiplication(star(x0), x1)), multiplication(x1, strong_iteration(multiplication(star(x0), x1)))), strong_iteration(multiplication(star(x0), x1))), true, x1, multiplication(one, strong_iteration(multiplication(star(x0), x1))), strong_iteration(multiplication(star(x0), x1))), true) 17.68/2.59 = { by axiom 3 (additive_commutativity) R->L } 17.68/2.59 tuple(fresh3(leq(addition(multiplication(x1, strong_iteration(multiplication(star(x0), x1))), strong_iteration(multiplication(star(x0), x1))), strong_iteration(multiplication(star(x0), x1))), true, x1, multiplication(one, strong_iteration(multiplication(star(x0), x1))), strong_iteration(multiplication(star(x0), x1))), true) 17.68/2.59 = { by lemma 14 R->L } 17.68/2.59 tuple(fresh3(leq(addition(multiplication(x1, strong_iteration(multiplication(star(x0), x1))), addition(one, multiplication(multiplication(star(x0), x1), strong_iteration(multiplication(star(x0), x1))))), strong_iteration(multiplication(star(x0), x1))), true, x1, multiplication(one, strong_iteration(multiplication(star(x0), x1))), strong_iteration(multiplication(star(x0), x1))), true) 17.68/2.59 = { by axiom 3 (additive_commutativity) R->L } 17.68/2.59 tuple(fresh3(leq(addition(multiplication(x1, strong_iteration(multiplication(star(x0), x1))), addition(multiplication(multiplication(star(x0), x1), strong_iteration(multiplication(star(x0), x1))), one)), strong_iteration(multiplication(star(x0), x1))), true, x1, multiplication(one, strong_iteration(multiplication(star(x0), x1))), strong_iteration(multiplication(star(x0), x1))), true) 17.68/2.59 = { by axiom 3 (additive_commutativity) R->L } 17.68/2.59 tuple(fresh3(leq(addition(addition(multiplication(multiplication(star(x0), x1), strong_iteration(multiplication(star(x0), x1))), one), multiplication(x1, strong_iteration(multiplication(star(x0), x1)))), strong_iteration(multiplication(star(x0), x1))), true, x1, multiplication(one, strong_iteration(multiplication(star(x0), x1))), strong_iteration(multiplication(star(x0), x1))), true) 17.68/2.59 = { by axiom 4 (additive_associativity) R->L } 17.68/2.59 tuple(fresh3(leq(addition(multiplication(multiplication(star(x0), x1), strong_iteration(multiplication(star(x0), x1))), addition(one, multiplication(x1, strong_iteration(multiplication(star(x0), x1))))), strong_iteration(multiplication(star(x0), x1))), true, x1, multiplication(one, strong_iteration(multiplication(star(x0), x1))), strong_iteration(multiplication(star(x0), x1))), true) 17.68/2.59 = { by axiom 3 (additive_commutativity) } 17.68/2.60 tuple(fresh3(leq(addition(multiplication(multiplication(star(x0), x1), strong_iteration(multiplication(star(x0), x1))), addition(multiplication(x1, strong_iteration(multiplication(star(x0), x1))), one)), strong_iteration(multiplication(star(x0), x1))), true, x1, multiplication(one, strong_iteration(multiplication(star(x0), x1))), strong_iteration(multiplication(star(x0), x1))), true) 17.68/2.60 = { by axiom 4 (additive_associativity) } 17.68/2.60 tuple(fresh3(leq(addition(addition(multiplication(multiplication(star(x0), x1), strong_iteration(multiplication(star(x0), x1))), multiplication(x1, strong_iteration(multiplication(star(x0), x1)))), one), strong_iteration(multiplication(star(x0), x1))), true, x1, multiplication(one, strong_iteration(multiplication(star(x0), x1))), strong_iteration(multiplication(star(x0), x1))), true) 17.68/2.60 = { by axiom 9 (distributivity2) R->L } 17.68/2.60 tuple(fresh3(leq(addition(multiplication(addition(multiplication(star(x0), x1), x1), strong_iteration(multiplication(star(x0), x1))), one), strong_iteration(multiplication(star(x0), x1))), true, x1, multiplication(one, strong_iteration(multiplication(star(x0), x1))), strong_iteration(multiplication(star(x0), x1))), true) 17.68/2.60 = { by axiom 3 (additive_commutativity) } 17.68/2.60 tuple(fresh3(leq(addition(one, multiplication(addition(multiplication(star(x0), x1), x1), strong_iteration(multiplication(star(x0), x1)))), strong_iteration(multiplication(star(x0), x1))), true, x1, multiplication(one, strong_iteration(multiplication(star(x0), x1))), strong_iteration(multiplication(star(x0), x1))), true) 17.68/2.60 = { by axiom 3 (additive_commutativity) } 17.68/2.60 tuple(fresh3(leq(addition(one, multiplication(addition(x1, multiplication(star(x0), x1)), strong_iteration(multiplication(star(x0), x1)))), strong_iteration(multiplication(star(x0), x1))), true, x1, multiplication(one, strong_iteration(multiplication(star(x0), x1))), strong_iteration(multiplication(star(x0), x1))), true) 17.68/2.60 = { by lemma 13 } 17.68/2.60 tuple(fresh3(leq(addition(one, multiplication(multiplication(addition(star(x0), one), x1), strong_iteration(multiplication(star(x0), x1)))), strong_iteration(multiplication(star(x0), x1))), true, x1, multiplication(one, strong_iteration(multiplication(star(x0), x1))), strong_iteration(multiplication(star(x0), x1))), true) 17.68/2.60 = { by axiom 3 (additive_commutativity) } 17.68/2.60 tuple(fresh3(leq(addition(one, multiplication(multiplication(addition(one, star(x0)), x1), strong_iteration(multiplication(star(x0), x1)))), strong_iteration(multiplication(star(x0), x1))), true, x1, multiplication(one, strong_iteration(multiplication(star(x0), x1))), strong_iteration(multiplication(star(x0), x1))), true) 17.68/2.60 = { by lemma 12 } 17.68/2.60 tuple(fresh3(leq(addition(one, multiplication(multiplication(star(x0), x1), strong_iteration(multiplication(star(x0), x1)))), strong_iteration(multiplication(star(x0), x1))), true, x1, multiplication(one, strong_iteration(multiplication(star(x0), x1))), strong_iteration(multiplication(star(x0), x1))), true) 17.68/2.60 = { by lemma 14 } 17.68/2.60 tuple(fresh3(leq(strong_iteration(multiplication(star(x0), x1)), strong_iteration(multiplication(star(x0), x1))), true, x1, multiplication(one, strong_iteration(multiplication(star(x0), x1))), strong_iteration(multiplication(star(x0), x1))), true) 17.68/2.60 = { by axiom 10 (order) R->L } 17.68/2.60 tuple(fresh3(fresh5(strong_iteration(multiplication(star(x0), x1)), addition(strong_iteration(multiplication(star(x0), x1)), strong_iteration(multiplication(star(x0), x1))), strong_iteration(multiplication(star(x0), x1)), strong_iteration(multiplication(star(x0), x1))), true, x1, multiplication(one, strong_iteration(multiplication(star(x0), x1))), strong_iteration(multiplication(star(x0), x1))), true) 17.68/2.60 = { by axiom 2 (idempotence) } 17.68/2.60 tuple(fresh3(fresh5(strong_iteration(multiplication(star(x0), x1)), strong_iteration(multiplication(star(x0), x1)), strong_iteration(multiplication(star(x0), x1)), strong_iteration(multiplication(star(x0), x1))), true, x1, multiplication(one, strong_iteration(multiplication(star(x0), x1))), strong_iteration(multiplication(star(x0), x1))), true) 17.68/2.60 = { by axiom 5 (order) } 17.68/2.60 tuple(fresh3(true, true, x1, multiplication(one, strong_iteration(multiplication(star(x0), x1))), strong_iteration(multiplication(star(x0), x1))), true) 17.68/2.60 = { by axiom 8 (star_induction1) } 17.68/2.60 tuple(true, true) 17.68/2.60 % SZS output end Proof 17.68/2.60 17.68/2.60 RESULT: Theorem (the conjecture is true). 17.68/2.60 EOF