0.04/0.12 % Problem : theBenchmark.p : TPTP v0.0.0. Released v0.0.0. 0.12/0.13 % Command : twee %s --tstp --casc --quiet --explain-encoding --conditional-encoding if --smaller --drop-non-horn 0.14/0.34 % Computer : n014.cluster.edu 0.14/0.34 % Model : x86_64 x86_64 0.14/0.34 % CPU : Intel(R) Xeon(R) CPU E5-2620 v4 @ 2.10GHz 0.14/0.34 % Memory : 8042.1875MB 0.14/0.34 % OS : Linux 3.10.0-693.el7.x86_64 0.14/0.34 % CPULimit : 180 0.14/0.34 % DateTime : Thu Aug 29 09:18:24 EDT 2019 0.14/0.35 % CPUTime : 0.21/0.41 % SZS status Unsatisfiable 0.21/0.41 0.21/0.41 % SZS output start Proof 0.21/0.41 Take the following subset of the input axioms: 0.21/0.41 fof(composition_associativity_5, axiom, ![A, B, C]: composition(composition(A, B), C)=composition(A, composition(B, C))). 0.21/0.41 fof(composition_distributivity_7, axiom, ![A, B, C]: composition(join(A, B), C)=join(composition(A, C), composition(B, C))). 0.21/0.41 fof(composition_identity_6, axiom, ![A]: A=composition(A, one)). 0.21/0.41 fof(converse_cancellativity_11, axiom, ![A, B]: join(composition(converse(A), complement(composition(A, B))), complement(B))=complement(B)). 0.21/0.41 fof(converse_idempotence_8, axiom, ![A]: converse(converse(A))=A). 0.21/0.41 fof(converse_multiplicativity_10, axiom, ![A, B]: converse(composition(A, B))=composition(converse(B), converse(A))). 0.21/0.41 fof(def_top_12, axiom, ![A]: join(A, complement(A))=top). 0.21/0.41 fof(goals_14, negated_conjecture, top!=composition(top, top)). 0.21/0.41 fof(maddux1_join_commutativity_1, axiom, ![A, B]: join(B, A)=join(A, B)). 0.21/0.41 fof(maddux2_join_associativity_2, axiom, ![A, B, C]: join(join(A, B), C)=join(A, join(B, C))). 0.21/0.41 0.21/0.41 Now clausify the problem and encode Horn clauses using encoding 3 of 0.21/0.41 http://www.cse.chalmers.se/~nicsma/papers/horn.pdf. 0.21/0.41 We repeatedly replace C & s=t => u=v by the two clauses: 0.21/0.41 fresh(y, y, x1...xn) = u 0.21/0.41 C => fresh(s, t, x1...xn) = v 0.21/0.41 where fresh is a fresh function symbol and x1..xn are the free 0.21/0.41 variables of u and v. 0.21/0.41 A predicate p(X) is encoded as p(X)=true (this is sound, because the 0.21/0.41 input problem has no model of domain size 1). 0.21/0.41 0.21/0.41 The encoding turns the above axioms into the following unit equations and goals: 0.21/0.41 0.21/0.41 Axiom 1 (maddux1_join_commutativity_1): join(X, Y) = join(Y, X). 0.21/0.41 Axiom 2 (composition_identity_6): X = composition(X, one). 0.21/0.41 Axiom 3 (converse_idempotence_8): converse(converse(X)) = X. 0.21/0.41 Axiom 4 (maddux2_join_associativity_2): join(join(X, Y), Z) = join(X, join(Y, Z)). 0.21/0.41 Axiom 5 (converse_cancellativity_11): join(composition(converse(X), complement(composition(X, Y))), complement(Y)) = complement(Y). 0.21/0.41 Axiom 6 (def_top_12): join(X, complement(X)) = top. 0.21/0.41 Axiom 7 (converse_multiplicativity_10): converse(composition(X, Y)) = composition(converse(Y), converse(X)). 0.21/0.41 Axiom 8 (composition_associativity_5): composition(composition(X, Y), Z) = composition(X, composition(Y, Z)). 0.21/0.41 Axiom 9 (composition_distributivity_7): composition(join(X, Y), Z) = join(composition(X, Z), composition(Y, Z)). 0.21/0.41 0.21/0.41 Lemma 10: composition(converse(one), X) = X. 0.21/0.41 Proof: 0.21/0.41 composition(converse(one), X) 0.21/0.41 = { by axiom 3 (converse_idempotence_8) } 0.21/0.41 composition(converse(one), converse(converse(X))) 0.21/0.41 = { by axiom 7 (converse_multiplicativity_10) } 0.21/0.41 converse(composition(converse(X), one)) 0.21/0.41 = { by axiom 2 (composition_identity_6) } 0.21/0.41 converse(converse(X)) 0.21/0.41 = { by axiom 3 (converse_idempotence_8) } 0.21/0.41 X 0.21/0.41 0.21/0.41 Lemma 11: composition(one, X) = X. 0.21/0.41 Proof: 0.21/0.41 composition(one, X) 0.21/0.41 = { by lemma 10 } 0.21/0.41 composition(converse(one), composition(one, X)) 0.21/0.41 = { by axiom 8 (composition_associativity_5) } 0.21/0.41 composition(composition(converse(one), one), X) 0.21/0.41 = { by axiom 2 (composition_identity_6) } 0.21/0.41 composition(converse(one), X) 0.21/0.41 = { by lemma 10 } 0.21/0.41 X 0.21/0.41 0.21/0.41 Lemma 12: join(X, join(Y, Z)) = join(Z, join(X, Y)). 0.21/0.41 Proof: 0.21/0.41 join(X, join(Y, Z)) 0.21/0.41 = { by axiom 4 (maddux2_join_associativity_2) } 0.21/0.41 join(join(X, Y), Z) 0.21/0.41 = { by axiom 1 (maddux1_join_commutativity_1) } 0.21/0.41 join(Z, join(X, Y)) 0.21/0.41 0.21/0.41 Lemma 13: join(top, X) = top. 0.21/0.41 Proof: 0.21/0.41 join(top, X) 0.21/0.41 = { by axiom 1 (maddux1_join_commutativity_1) } 0.21/0.41 join(X, top) 0.21/0.41 = { by axiom 6 (def_top_12) } 0.21/0.41 join(X, join(complement(X), complement(complement(X)))) 0.21/0.41 = { by lemma 12 } 0.21/0.41 join(complement(X), join(complement(complement(X)), X)) 0.21/0.41 = { by lemma 12 } 0.21/0.41 join(complement(complement(X)), join(X, complement(X))) 0.21/0.41 = { by axiom 6 (def_top_12) } 0.21/0.41 join(complement(complement(X)), top) 0.21/0.41 = { by axiom 1 (maddux1_join_commutativity_1) } 0.21/0.41 join(top, complement(complement(X))) 0.21/0.41 = { by axiom 6 (def_top_12) } 0.21/0.41 join(join(complement(X), complement(complement(X))), complement(complement(X))) 0.21/0.41 = { by axiom 4 (maddux2_join_associativity_2) } 0.21/0.41 join(complement(X), join(complement(complement(X)), complement(complement(X)))) 0.21/0.41 = { by lemma 10 } 0.21/0.41 join(complement(X), join(complement(complement(X)), composition(converse(one), complement(complement(X))))) 0.21/0.41 = { by lemma 11 } 0.21/0.41 join(complement(X), join(complement(complement(X)), composition(converse(one), complement(composition(one, complement(X)))))) 0.21/0.41 = { by axiom 1 (maddux1_join_commutativity_1) } 0.21/0.41 join(complement(X), join(composition(converse(one), complement(composition(one, complement(X)))), complement(complement(X)))) 0.21/0.41 = { by axiom 5 (converse_cancellativity_11) } 0.21/0.41 join(complement(X), complement(complement(X))) 0.21/0.41 = { by axiom 6 (def_top_12) } 0.21/0.41 top 0.21/0.41 0.21/0.41 Goal 1 (goals_14): top = composition(top, top). 0.21/0.41 Proof: 0.21/0.41 top 0.21/0.41 = { by lemma 13 } 0.21/0.41 join(top, composition(top, top)) 0.21/0.41 = { by lemma 11 } 0.21/0.41 join(composition(one, top), composition(top, top)) 0.21/0.41 = { by axiom 9 (composition_distributivity_7) } 0.21/0.41 composition(join(one, top), top) 0.21/0.41 = { by axiom 1 (maddux1_join_commutativity_1) } 0.21/0.41 composition(join(top, one), top) 0.21/0.41 = { by lemma 13 } 0.21/0.41 composition(top, top) 0.21/0.41 % SZS output end Proof 0.21/0.41 0.21/0.41 RESULT: Unsatisfiable (the axioms are contradictory). 0.21/0.41 EOF