0.11/0.12 % Problem : theBenchmark.p : TPTP v0.0.0. Released v0.0.0. 0.11/0.12 % Command : parallel-twee %s --tstp --conditional-encoding if --smaller --drop-non-horn --give-up-on-saturation --explain-encoding --formal-proof 0.12/0.34 % Computer : n005.cluster.edu 0.12/0.34 % Model : x86_64 x86_64 0.12/0.34 % CPU : Intel(R) Xeon(R) CPU E5-2620 v4 @ 2.10GHz 0.12/0.34 % Memory : 8042.1875MB 0.12/0.34 % OS : Linux 3.10.0-693.el7.x86_64 0.12/0.34 % CPULimit : 1200 0.12/0.34 % WCLimit : 120 0.12/0.34 % DateTime : Tue Jul 13 16:05:18 EDT 2021 0.12/0.34 % CPUTime : 12.57/2.02 % SZS status Theorem 12.57/2.02 13.14/2.06 % SZS output start Proof 13.14/2.06 Take the following subset of the input axioms: 13.14/2.06 fof(a, conjecture, leq(multiplication(a, multiplication(a, multiplication(a, multiplication(a, multiplication(a, a))))), star(a))). 13.14/2.06 fof(additive_associativity, axiom, ![A, B, C]: addition(A, addition(B, C))=addition(addition(A, B), C)). 13.14/2.06 fof(additive_commutativity, axiom, ![A, B]: addition(A, B)=addition(B, A)). 13.14/2.06 fof(additive_idempotence, axiom, ![A]: addition(A, A)=A). 13.14/2.06 fof(left_distributivity, axiom, ![A, B, C]: addition(multiplication(A, C), multiplication(B, C))=multiplication(addition(A, B), C)). 13.14/2.06 fof(multiplicative_associativity, axiom, ![A, B, C]: multiplication(multiplication(A, B), C)=multiplication(A, multiplication(B, C))). 13.14/2.06 fof(multiplicative_left_identity, axiom, ![A]: multiplication(one, A)=A). 13.14/2.06 fof(multiplicative_right_identity, axiom, ![A]: A=multiplication(A, one)). 13.14/2.06 fof(order, axiom, ![A, B]: (B=addition(A, B) <=> leq(A, B))). 13.14/2.06 fof(right_distributivity, axiom, ![A, B, C]: addition(multiplication(A, B), multiplication(A, C))=multiplication(A, addition(B, C))). 13.14/2.06 fof(star_unfold_left, axiom, ![A]: leq(addition(one, multiplication(star(A), A)), star(A))). 13.14/2.06 fof(star_unfold_right, axiom, ![A]: leq(addition(one, multiplication(A, star(A))), star(A))). 13.14/2.06 13.14/2.06 Now clausify the problem and encode Horn clauses using encoding 3 of 13.14/2.06 http://www.cse.chalmers.se/~nicsma/papers/horn.pdf. 13.14/2.06 We repeatedly replace C & s=t => u=v by the two clauses: 13.14/2.06 fresh(y, y, x1...xn) = u 13.14/2.06 C => fresh(s, t, x1...xn) = v 13.14/2.06 where fresh is a fresh function symbol and x1..xn are the free 13.14/2.06 variables of u and v. 13.14/2.06 A predicate p(X) is encoded as p(X)=true (this is sound, because the 13.14/2.06 input problem has no model of domain size 1). 13.14/2.06 13.14/2.06 The encoding turns the above axioms into the following unit equations and goals: 13.14/2.06 13.14/2.06 Axiom 1 (additive_idempotence): addition(X, X) = X. 13.14/2.06 Axiom 2 (additive_commutativity): addition(X, Y) = addition(Y, X). 13.14/2.06 Axiom 3 (multiplicative_right_identity): X = multiplication(X, one). 13.14/2.06 Axiom 4 (multiplicative_left_identity): multiplication(one, X) = X. 13.14/2.06 Axiom 5 (order_1): fresh(X, X, Y, Z) = Z. 13.14/2.06 Axiom 6 (order): fresh3(X, X, Y, Z) = true. 13.14/2.06 Axiom 7 (additive_associativity): addition(X, addition(Y, Z)) = addition(addition(X, Y), Z). 13.14/2.06 Axiom 8 (multiplicative_associativity): multiplication(multiplication(X, Y), Z) = multiplication(X, multiplication(Y, Z)). 13.14/2.06 Axiom 9 (order_1): fresh(leq(X, Y), true, X, Y) = addition(X, Y). 13.14/2.06 Axiom 10 (order): fresh3(X, addition(Y, X), Y, X) = leq(Y, X). 13.14/2.06 Axiom 11 (right_distributivity): addition(multiplication(X, Y), multiplication(X, Z)) = multiplication(X, addition(Y, Z)). 13.14/2.06 Axiom 12 (left_distributivity): addition(multiplication(X, Y), multiplication(Z, Y)) = multiplication(addition(X, Z), Y). 13.14/2.06 Axiom 13 (star_unfold_right): leq(addition(one, multiplication(X, star(X))), star(X)) = true. 13.14/2.06 Axiom 14 (star_unfold_left): leq(addition(one, multiplication(star(X), X)), star(X)) = true. 13.14/2.06 13.14/2.06 Lemma 15: multiplication(addition(one, Y), X) = addition(X, multiplication(Y, X)). 13.14/2.06 Proof: 13.14/2.06 multiplication(addition(one, Y), X) 13.14/2.06 = { by axiom 12 (left_distributivity) R->L } 13.14/2.06 addition(multiplication(one, X), multiplication(Y, X)) 13.14/2.06 = { by axiom 4 (multiplicative_left_identity) } 13.14/2.06 addition(X, multiplication(Y, X)) 13.14/2.06 13.14/2.06 Lemma 16: addition(one, multiplication(addition(X, one), star(X))) = star(X). 13.14/2.06 Proof: 13.14/2.06 addition(one, multiplication(addition(X, one), star(X))) 13.14/2.06 = { by axiom 2 (additive_commutativity) R->L } 13.14/2.06 addition(one, multiplication(addition(one, X), star(X))) 13.14/2.06 = { by lemma 15 } 13.14/2.06 addition(one, addition(star(X), multiplication(X, star(X)))) 13.14/2.06 = { by axiom 2 (additive_commutativity) R->L } 13.14/2.06 addition(one, addition(multiplication(X, star(X)), star(X))) 13.14/2.06 = { by axiom 7 (additive_associativity) } 13.14/2.06 addition(addition(one, multiplication(X, star(X))), star(X)) 13.14/2.06 = { by axiom 9 (order_1) R->L } 13.14/2.06 fresh(leq(addition(one, multiplication(X, star(X))), star(X)), true, addition(one, multiplication(X, star(X))), star(X)) 13.14/2.06 = { by axiom 13 (star_unfold_right) } 13.14/2.06 fresh(true, true, addition(one, multiplication(X, star(X))), star(X)) 13.14/2.06 = { by axiom 5 (order_1) } 13.14/2.06 star(X) 13.14/2.06 13.14/2.06 Lemma 17: addition(one, star(X)) = star(X). 13.14/2.06 Proof: 13.14/2.06 addition(one, star(X)) 13.14/2.06 = { by lemma 16 R->L } 13.14/2.06 addition(one, addition(one, multiplication(addition(X, one), star(X)))) 13.14/2.06 = { by axiom 7 (additive_associativity) } 13.14/2.06 addition(addition(one, one), multiplication(addition(X, one), star(X))) 13.14/2.06 = { by axiom 1 (additive_idempotence) } 13.14/2.06 addition(one, multiplication(addition(X, one), star(X))) 13.14/2.06 = { by lemma 16 } 13.14/2.06 star(X) 13.14/2.06 13.14/2.06 Lemma 18: multiplication(X, addition(Y, one)) = addition(X, multiplication(X, Y)). 13.14/2.06 Proof: 13.14/2.06 multiplication(X, addition(Y, one)) 13.14/2.06 = { by axiom 2 (additive_commutativity) R->L } 13.14/2.06 multiplication(X, addition(one, Y)) 13.14/2.06 = { by axiom 11 (right_distributivity) R->L } 13.14/2.06 addition(multiplication(X, one), multiplication(X, Y)) 13.14/2.06 = { by axiom 3 (multiplicative_right_identity) R->L } 13.14/2.06 addition(X, multiplication(X, Y)) 13.14/2.06 13.14/2.06 Lemma 19: multiplication(star(X), addition(X, one)) = star(X). 13.14/2.06 Proof: 13.14/2.06 multiplication(star(X), addition(X, one)) 13.14/2.06 = { by lemma 18 } 13.14/2.06 addition(star(X), multiplication(star(X), X)) 13.14/2.06 = { by lemma 17 R->L } 13.14/2.06 addition(addition(one, star(X)), multiplication(star(X), X)) 13.14/2.06 = { by axiom 7 (additive_associativity) R->L } 13.14/2.06 addition(one, addition(star(X), multiplication(star(X), X))) 13.14/2.06 = { by axiom 2 (additive_commutativity) } 13.14/2.06 addition(one, addition(multiplication(star(X), X), star(X))) 13.14/2.06 = { by axiom 7 (additive_associativity) } 13.14/2.06 addition(addition(one, multiplication(star(X), X)), star(X)) 13.14/2.06 = { by axiom 9 (order_1) R->L } 13.14/2.06 fresh(leq(addition(one, multiplication(star(X), X)), star(X)), true, addition(one, multiplication(star(X), X)), star(X)) 13.14/2.06 = { by axiom 14 (star_unfold_left) } 13.14/2.06 fresh(true, true, addition(one, multiplication(star(X), X)), star(X)) 13.14/2.06 = { by axiom 5 (order_1) } 13.14/2.06 star(X) 13.14/2.07 13.14/2.07 Lemma 20: multiplication(multiplication(X, multiplication(Y, Z)), W) = multiplication(X, multiplication(Y, multiplication(Z, W))). 13.14/2.07 Proof: 13.14/2.07 multiplication(multiplication(X, multiplication(Y, Z)), W) 13.14/2.07 = { by axiom 8 (multiplicative_associativity) } 13.14/2.07 multiplication(X, multiplication(multiplication(Y, Z), W)) 13.14/2.07 = { by axiom 8 (multiplicative_associativity) } 13.14/2.07 multiplication(X, multiplication(Y, multiplication(Z, W))) 13.14/2.07 13.14/2.07 Lemma 21: addition(star(X), multiplication(star(X), X)) = star(X). 13.14/2.07 Proof: 13.14/2.07 addition(star(X), multiplication(star(X), X)) 13.14/2.07 = { by lemma 18 R->L } 13.14/2.07 multiplication(star(X), addition(X, one)) 13.14/2.07 = { by lemma 19 } 13.14/2.07 star(X) 13.14/2.07 13.14/2.07 Lemma 22: multiplication(multiplication(X, multiplication(Y, multiplication(Z, W))), V) = multiplication(X, multiplication(Y, multiplication(Z, multiplication(W, V)))). 13.14/2.07 Proof: 13.14/2.07 multiplication(multiplication(X, multiplication(Y, multiplication(Z, W))), V) 13.14/2.07 = { by axiom 8 (multiplicative_associativity) } 13.14/2.07 multiplication(X, multiplication(multiplication(Y, multiplication(Z, W)), V)) 13.14/2.07 = { by lemma 20 } 13.14/2.07 multiplication(X, multiplication(Y, multiplication(Z, multiplication(W, V)))) 13.14/2.07 13.14/2.07 Lemma 23: addition(star(X), addition(Y, multiplication(star(X), X))) = addition(Y, star(X)). 13.14/2.07 Proof: 13.14/2.07 addition(star(X), addition(Y, multiplication(star(X), X))) 13.14/2.07 = { by axiom 2 (additive_commutativity) R->L } 13.14/2.07 addition(star(X), addition(multiplication(star(X), X), Y)) 13.14/2.07 = { by axiom 7 (additive_associativity) } 13.14/2.07 addition(addition(star(X), multiplication(star(X), X)), Y) 13.14/2.07 = { by lemma 21 } 13.14/2.07 addition(star(X), Y) 13.14/2.07 = { by axiom 2 (additive_commutativity) } 13.14/2.07 addition(Y, star(X)) 13.14/2.07 13.14/2.07 Lemma 24: addition(star(X), multiplication(addition(Y, star(X)), X)) = addition(star(X), multiplication(Y, X)). 13.14/2.07 Proof: 13.14/2.07 addition(star(X), multiplication(addition(Y, star(X)), X)) 13.14/2.07 = { by axiom 12 (left_distributivity) R->L } 13.14/2.07 addition(star(X), addition(multiplication(Y, X), multiplication(star(X), X))) 13.14/2.07 = { by lemma 23 } 13.14/2.07 addition(multiplication(Y, X), star(X)) 13.14/2.07 = { by axiom 2 (additive_commutativity) } 13.14/2.07 addition(star(X), multiplication(Y, X)) 13.14/2.07 13.14/2.07 Goal 1 (a): leq(multiplication(a, multiplication(a, multiplication(a, multiplication(a, multiplication(a, a))))), star(a)) = true. 13.14/2.07 Proof: 13.14/2.07 leq(multiplication(a, multiplication(a, multiplication(a, multiplication(a, multiplication(a, a))))), star(a)) 13.14/2.07 = { by axiom 10 (order) R->L } 13.14/2.07 fresh3(star(a), addition(multiplication(a, multiplication(a, multiplication(a, multiplication(a, multiplication(a, a))))), star(a)), multiplication(a, multiplication(a, multiplication(a, multiplication(a, multiplication(a, a))))), star(a)) 13.14/2.07 = { by axiom 2 (additive_commutativity) R->L } 13.14/2.07 fresh3(star(a), addition(star(a), multiplication(a, multiplication(a, multiplication(a, multiplication(a, multiplication(a, a)))))), multiplication(a, multiplication(a, multiplication(a, multiplication(a, multiplication(a, a))))), star(a)) 13.14/2.07 = { by lemma 22 R->L } 13.14/2.07 fresh3(star(a), addition(star(a), multiplication(a, multiplication(multiplication(a, multiplication(a, multiplication(a, a))), a))), multiplication(a, multiplication(a, multiplication(a, multiplication(a, multiplication(a, a))))), star(a)) 13.33/2.07 = { by axiom 8 (multiplicative_associativity) R->L } 13.33/2.07 fresh3(star(a), addition(star(a), multiplication(multiplication(a, multiplication(a, multiplication(a, multiplication(a, a)))), a)), multiplication(a, multiplication(a, multiplication(a, multiplication(a, multiplication(a, a))))), star(a)) 13.33/2.07 = { by lemma 24 R->L } 13.33/2.07 fresh3(star(a), addition(star(a), multiplication(addition(multiplication(a, multiplication(a, multiplication(a, multiplication(a, a)))), star(a)), a)), multiplication(a, multiplication(a, multiplication(a, multiplication(a, multiplication(a, a))))), star(a)) 13.33/2.07 = { by axiom 2 (additive_commutativity) R->L } 13.33/2.07 fresh3(star(a), addition(star(a), multiplication(addition(star(a), multiplication(a, multiplication(a, multiplication(a, multiplication(a, a))))), a)), multiplication(a, multiplication(a, multiplication(a, multiplication(a, multiplication(a, a))))), star(a)) 13.33/2.07 = { by lemma 22 R->L } 13.33/2.07 fresh3(star(a), addition(star(a), multiplication(addition(star(a), multiplication(multiplication(a, multiplication(a, multiplication(a, a))), a)), a)), multiplication(a, multiplication(a, multiplication(a, multiplication(a, multiplication(a, a))))), star(a)) 13.33/2.07 = { by lemma 24 R->L } 13.33/2.07 fresh3(star(a), addition(star(a), multiplication(addition(star(a), multiplication(addition(multiplication(a, multiplication(a, multiplication(a, a))), star(a)), a)), a)), multiplication(a, multiplication(a, multiplication(a, multiplication(a, multiplication(a, a))))), star(a)) 13.33/2.07 = { by lemma 23 R->L } 13.33/2.07 fresh3(star(a), addition(star(a), multiplication(addition(star(a), multiplication(addition(star(a), addition(multiplication(a, multiplication(a, multiplication(a, a))), multiplication(star(a), a))), a)), a)), multiplication(a, multiplication(a, multiplication(a, multiplication(a, multiplication(a, a))))), star(a)) 13.33/2.07 = { by lemma 20 R->L } 13.33/2.07 fresh3(star(a), addition(star(a), multiplication(addition(star(a), multiplication(addition(star(a), addition(multiplication(multiplication(a, multiplication(a, a)), a), multiplication(star(a), a))), a)), a)), multiplication(a, multiplication(a, multiplication(a, multiplication(a, multiplication(a, a))))), star(a)) 13.33/2.07 = { by axiom 12 (left_distributivity) } 13.33/2.07 fresh3(star(a), addition(star(a), multiplication(addition(star(a), multiplication(addition(star(a), multiplication(addition(multiplication(a, multiplication(a, a)), star(a)), a)), a)), a)), multiplication(a, multiplication(a, multiplication(a, multiplication(a, multiplication(a, a))))), star(a)) 13.33/2.07 = { by lemma 23 R->L } 13.33/2.07 fresh3(star(a), addition(star(a), multiplication(addition(star(a), multiplication(addition(star(a), multiplication(addition(star(a), addition(multiplication(a, multiplication(a, a)), multiplication(star(a), a))), a)), a)), a)), multiplication(a, multiplication(a, multiplication(a, multiplication(a, multiplication(a, a))))), star(a)) 13.33/2.07 = { by axiom 8 (multiplicative_associativity) R->L } 13.33/2.07 fresh3(star(a), addition(star(a), multiplication(addition(star(a), multiplication(addition(star(a), multiplication(addition(star(a), addition(multiplication(multiplication(a, a), a), multiplication(star(a), a))), a)), a)), a)), multiplication(a, multiplication(a, multiplication(a, multiplication(a, multiplication(a, a))))), star(a)) 13.33/2.07 = { by axiom 12 (left_distributivity) } 13.33/2.07 fresh3(star(a), addition(star(a), multiplication(addition(star(a), multiplication(addition(star(a), multiplication(addition(star(a), multiplication(addition(multiplication(a, a), star(a)), a)), a)), a)), a)), multiplication(a, multiplication(a, multiplication(a, multiplication(a, multiplication(a, a))))), star(a)) 13.33/2.07 = { by lemma 23 R->L } 13.33/2.07 fresh3(star(a), addition(star(a), multiplication(addition(star(a), multiplication(addition(star(a), multiplication(addition(star(a), multiplication(addition(star(a), addition(multiplication(a, a), multiplication(star(a), a))), a)), a)), a)), a)), multiplication(a, multiplication(a, multiplication(a, multiplication(a, multiplication(a, a))))), star(a)) 13.33/2.07 = { by axiom 12 (left_distributivity) } 13.33/2.07 fresh3(star(a), addition(star(a), multiplication(addition(star(a), multiplication(addition(star(a), multiplication(addition(star(a), multiplication(addition(star(a), multiplication(addition(a, star(a)), a)), a)), a)), a)), a)), multiplication(a, multiplication(a, multiplication(a, multiplication(a, multiplication(a, a))))), star(a)) 13.33/2.07 = { by lemma 17 R->L } 13.33/2.07 fresh3(star(a), addition(star(a), multiplication(addition(star(a), multiplication(addition(star(a), multiplication(addition(star(a), multiplication(addition(star(a), multiplication(addition(a, addition(one, star(a))), a)), a)), a)), a)), a)), multiplication(a, multiplication(a, multiplication(a, multiplication(a, multiplication(a, a))))), star(a)) 13.33/2.07 = { by axiom 7 (additive_associativity) } 13.33/2.07 fresh3(star(a), addition(star(a), multiplication(addition(star(a), multiplication(addition(star(a), multiplication(addition(star(a), multiplication(addition(star(a), multiplication(addition(addition(a, one), star(a)), a)), a)), a)), a)), a)), multiplication(a, multiplication(a, multiplication(a, multiplication(a, multiplication(a, a))))), star(a)) 13.33/2.07 = { by lemma 19 R->L } 13.33/2.07 fresh3(star(a), addition(star(a), multiplication(addition(star(a), multiplication(addition(star(a), multiplication(addition(star(a), multiplication(addition(star(a), multiplication(addition(addition(a, one), multiplication(star(a), addition(a, one))), a)), a)), a)), a)), a)), multiplication(a, multiplication(a, multiplication(a, multiplication(a, multiplication(a, a))))), star(a)) 13.33/2.07 = { by lemma 15 R->L } 13.33/2.07 fresh3(star(a), addition(star(a), multiplication(addition(star(a), multiplication(addition(star(a), multiplication(addition(star(a), multiplication(addition(star(a), multiplication(multiplication(addition(one, star(a)), addition(a, one)), a)), a)), a)), a)), a)), multiplication(a, multiplication(a, multiplication(a, multiplication(a, multiplication(a, a))))), star(a)) 13.33/2.07 = { by lemma 17 } 13.33/2.07 fresh3(star(a), addition(star(a), multiplication(addition(star(a), multiplication(addition(star(a), multiplication(addition(star(a), multiplication(addition(star(a), multiplication(multiplication(star(a), addition(a, one)), a)), a)), a)), a)), a)), multiplication(a, multiplication(a, multiplication(a, multiplication(a, multiplication(a, a))))), star(a)) 13.33/2.07 = { by lemma 19 } 13.33/2.07 fresh3(star(a), addition(star(a), multiplication(addition(star(a), multiplication(addition(star(a), multiplication(addition(star(a), multiplication(addition(star(a), multiplication(star(a), a)), a)), a)), a)), a)), multiplication(a, multiplication(a, multiplication(a, multiplication(a, multiplication(a, a))))), star(a)) 13.33/2.07 = { by lemma 21 } 13.33/2.07 fresh3(star(a), addition(star(a), multiplication(addition(star(a), multiplication(addition(star(a), multiplication(addition(star(a), multiplication(star(a), a)), a)), a)), a)), multiplication(a, multiplication(a, multiplication(a, multiplication(a, multiplication(a, a))))), star(a)) 13.33/2.07 = { by lemma 21 } 13.33/2.07 fresh3(star(a), addition(star(a), multiplication(addition(star(a), multiplication(addition(star(a), multiplication(star(a), a)), a)), a)), multiplication(a, multiplication(a, multiplication(a, multiplication(a, multiplication(a, a))))), star(a)) 13.33/2.07 = { by lemma 21 } 13.33/2.07 fresh3(star(a), addition(star(a), multiplication(addition(star(a), multiplication(star(a), a)), a)), multiplication(a, multiplication(a, multiplication(a, multiplication(a, multiplication(a, a))))), star(a)) 13.33/2.07 = { by lemma 21 } 13.33/2.07 fresh3(star(a), addition(star(a), multiplication(star(a), a)), multiplication(a, multiplication(a, multiplication(a, multiplication(a, multiplication(a, a))))), star(a)) 13.33/2.07 = { by lemma 21 } 13.33/2.07 fresh3(star(a), star(a), multiplication(a, multiplication(a, multiplication(a, multiplication(a, multiplication(a, a))))), star(a)) 13.33/2.07 = { by axiom 6 (order) } 13.33/2.07 true 13.33/2.07 % SZS output end Proof 13.33/2.07 13.33/2.07 RESULT: Theorem (the conjecture is true). 13.33/2.08 EOF