============================== Prover9 =============================== Prover9 (32) version April-2007, April 2007. Process 28057 was started by mccune on cleo, Fri Apr 13 09:56:38 2007 The command was "/home/mccune/bin/prover9 -f dist-short-long.in". ============================== end of head =========================== ============================== INPUT ================================= % Reading from file dist-short-long.in assign(max_seconds,30). assign(order,kbo). set(lex_order_vars). formulas(sos). f(x,x,y) = x # label(majority). f(x,y,z) = f(z,x,y) # label(2a). f(x,y,z) = f(x,z,y) # label(2b). f(f(x,w,y),w,z) = f(x,w,f(y,w,z)) # label(associativity). f(f(x,y,z),u,w) = f(x,f(y,u,w),f(z,u,w)) # label(dist_short). end_of_list. formulas(goals). f(f(x,y,z),u,w) = f(f(x,u,w),f(y,u,w),f(z,u,w)) # answer(dist_long). end_of_list. ============================== end of input ========================== ============================== PROCESS NON-CLAUSAL FORMULAS ========== % Formulas that are not ordinary clauses: 1 f(f(x,y,z),u,w) = f(f(x,u,w),f(y,u,w),f(z,u,w)) # answer(dist_long) # label(goal). [goal]. ============================== end of process non-clausal formulas === ============================== PROCESS INITIAL CLAUSES =============== % Clauses before input processing: formulas(usable). end_of_list. formulas(sos). f(x,x,y) = x # label(majority). [assumption]. f(x,y,z) = f(z,x,y) # label(2a). [assumption]. f(x,y,z) = f(x,z,y) # label(2b). [assumption]. f(f(x,y,z),y,u) = f(x,y,f(z,y,u)) # label(associativity). [assumption]. f(f(x,y,z),u,v) = f(x,f(y,u,v),f(z,u,v)) # label(dist_short). [assumption]. f(f(c1,c4,c5),f(c2,c4,c5),f(c3,c4,c5)) != f(f(c1,c2,c3),c4,c5) # answer(dist_long). [deny(1)]. end_of_list. formulas(demodulators). end_of_list. ============================== PREDICATE ELIMINATION ================= No predicates eliminated. ============================== end predicate elimination ============= Auto_denials: (no changes). Term ordering decisions: Function symbol KB weights: c1=1. c2=1. c3=1. c4=1. c5=1. f=1. Relation symbol precedence: lex([ = ]). Function symbol precedence: lex([ c1, c2, c3, c4, c5, f ]). Skipping inverse_order, because term ordering is KBO. Unfolding symbols: (none). Auto_inference settings: % set(paramodulation). % (positive equality literals) % set(paramodulation) -> set(back_demod). Auto_process settings: (no changes). ============================== end of process initial clauses ======== ============================== CLAUSES FOR SEARCH ==================== % Clauses after input processing: formulas(usable). end_of_list. formulas(sos). 2 f(x,x,y) = x # label(majority). [assumption]. 3 f(x,y,z) = f(z,x,y) # label(2a). [assumption]. 4 f(x,y,z) = f(x,z,y) # label(2b). [assumption]. 6 f(x,y,f(x,z,u)) = f(x,z,f(x,y,u)). [copy(5),rewrite(3(2),3(2),3(3,R),4(3)),rewrite(3(1,R),4(1),4(3),3(4,R),4(4))]. 8 f(x,f(y,z,u),f(z,u,v)) = f(z,u,f(x,y,v)). [copy(7),rewrite(3(2),3(2)),flip(a),rewrite(3(2),3(2))]. 10 f(f(c1,c4,c5),f(c2,c4,c5),f(c3,c4,c5)) != f(c4,c5,f(c1,c2,c3)) # answer(dist_long). [copy(9),rewrite(3(20),3(20))]. end_of_list. formulas(demodulators). 2 f(x,x,y) = x # label(majority). [assumption]. 3 f(x,y,z) = f(z,x,y) # label(2a). [assumption]. % (lex-dep) 4 f(x,y,z) = f(x,z,y) # label(2b). [assumption]. % (lex-dep) 8 f(x,f(y,z,u),f(z,u,v)) = f(z,u,f(x,y,v)). [copy(7),rewrite(3(2),3(2)),flip(a),rewrite(3(2),3(2))]. end_of_list. ============================== end of clauses for search ============= ============================== SEARCH ================================ % Starting search at 0.00 seconds. given #1 (I,wt=6): 2 f(x,x,y) = x # label(majority). [assumption]. given #2 (I,wt=9): 3 f(x,y,z) = f(z,x,y) # label(2a). [assumption]. given #3 (I,wt=9): 4 f(x,y,z) = f(x,z,y) # label(2b). [assumption]. given #4 (I,wt=15): 6 f(x,y,f(x,z,u)) = f(x,z,f(x,y,u)). [copy(5),rewrite(3(2),3(2),3(3,R),4(3)),rewrite(3(1,R),4(1),4(3),3(4,R),4(4))]. given #5 (I,wt=18): 8 f(x,f(y,z,u),f(z,u,v)) = f(z,u,f(x,y,v)). [copy(7),rewrite(3(2),3(2)),flip(a),rewrite(3(2),3(2))]. given #6 (I,wt=21): 10 f(f(c1,c4,c5),f(c2,c4,c5),f(c3,c4,c5)) != f(c4,c5,f(c1,c2,c3)) # answer(dist_long). [copy(9),rewrite(3(20),3(20))]. given #7 (A,wt=6): 11 f(x,y,y) = y. [para(3(a,1),2(a,1))]. given #8 (T,wt=12): 27 f(x,y,f(x,z,y)) = f(x,z,y). [para(11(a,1),6(a,1,3)),flip(a)]. given #9 (T,wt=12): 28 f(x,y,f(x,y,z)) = f(x,y,z). [para(11(a,1),6(a,1)),rewrite(4(3),27(3)),flip(a)]. given #10 (T,wt=15): 12 f(x,y,f(z,x,u)) = f(z,x,f(x,y,u)). [para(6(a,1),3(a,2)),rewrite(4(2),3(3,R),4(3)),flip(a)]. given #11 (T,wt=15): 13 f(x,y,f(x,z,u)) = f(x,u,f(x,y,z)). [para(3(a,1),6(a,1,3)),rewrite(3(1,R),4(1))]. given #12 (A,wt=21): 14 f(x,y,f(x,z,f(x,u,v))) = f(x,u,f(x,y,f(x,z,v))). [para(6(a,1),6(a,1,3))]. given #13 (T,wt=15): 29 f(x,y,f(z,u,y)) = f(u,y,f(x,z,y)). [para(11(a,1),8(a,1,3)),rewrite(4(2))]. given #14 (T,wt=12): 84 f(x,y,f(z,x,y)) = f(z,x,y). [para(2(a,1),29(a,1,3)),rewrite(4(2),3(3,R),4(3)),flip(a)]. given #15 (T,wt=15): 34 f(x,y,f(z,y,u)) = f(z,y,f(x,y,u)). [para(12(a,1),3(a,2)),rewrite(4(2),3(3,R),4(3))]. given #16 (T,wt=15): 35 f(x,y,f(z,x,u)) = f(z,x,f(x,u,y)). [para(3(a,1),12(a,1)),rewrite(3(2),3(2),4(3))]. given #17 (A,wt=18): 16 f(x,f(y,z,u),f(y,z,v)) = f(y,z,f(x,u,v)). [para(8(a,1),3(a,1)),rewrite(3(4),3(4),3(5,R)),flip(a)]. given #18 (T,wt=15): 43 f(x,y,f(x,z,u)) = f(x,u,f(x,z,y)). [para(3(a,1),13(a,1)),rewrite(3(2),3(2),4(3))]. given #19 (T,wt=15): 85 f(x,y,f(z,u,x)) = f(u,x,f(z,x,y)). [para(3(a,1),29(a,1)),rewrite(3(2),4(2),3(3),3(3))]. given #20 (T,wt=15): 86 f(x,y,f(z,u,y)) = f(z,y,f(x,u,y)). [para(29(a,2),4(a,2)),rewrite(4(2),3(3,R),4(3))]. given #21 (T,wt=15): 151 f(x,y,f(x,z,f(y,u,z))) = f(x,y,z). [para(16(a,1),29(a,1)),rewrite(32(3),11(1),3(4,R),4(4),124(5),4(2)),flip(a)]. given #22 (A,wt=18): 17 f(x,f(y,z,u),f(y,u,v)) = f(y,u,f(x,z,v)). [para(3(a,1),8(a,1,2)),rewrite(3(2,R),4(2),3(5,R),4(5))]. given #23 (T,wt=15): 153 f(x,y,f(z,u,x)) = f(z,x,f(u,x,y)). [para(29(a,1),16(a,2)),rewrite(11(2),4(2),3(3,R),4(3),3(4,R),4(4)),flip(a)]. given #24 (T,wt=15): 167 f(x,y,f(y,z,f(x,z,u))) = f(x,y,z). [para(85(a,1),8(a,1)),rewrite(3(1),4(1),3(2,R),4(2),3(4),2(4),3(4),3(4))]. given #25 (T,wt=15): 168 f(x,y,f(z,y,f(z,x,u))) = f(z,x,y). [para(8(a,1),85(a,1)),rewrite(3(1),2(1),3(2),3(2)),flip(a)]. given #26 (T,wt=15): 170 f(x,y,f(x,z,f(y,z,u))) = f(x,y,z). [para(28(a,1),85(a,1,3)),rewrite(3(3,R),11(3),4(4),124(5)),flip(a)]. given #27 (A,wt=24): 18 f(x,f(y,z,u),f(x,v,f(y,z,w))) = f(x,v,f(y,z,f(x,u,w))). [para(8(a,1),6(a,1,3)),rewrite(3(4),3(4)),flip(a)]. given #28 (T,wt=15): 180 f(x,y,f(z,x,f(z,y,u))) = f(z,x,y). [para(84(a,1),85(a,1,3)),rewrite(3(3,R),11(3),4(4),108(5),3(3,R),4(3)),flip(a)]. given #29 (T,wt=15): 186 f(x,y,f(x,z,f(u,y,z))) = f(x,y,z). [para(27(a,1),86(a,1,3)),rewrite(11(3),157(5),145(4)),flip(a)]. given #30 (T,wt=15): 190 f(x,y,f(x,z,f(z,y,u))) = f(x,z,y). [para(3(a,1),151(a,1)),rewrite(3(1),3(3),3(3),4(4))]. given #31 (T,wt=15): 199 f(x,f(y,z,u),f(x,y,z)) = f(x,y,z). [para(151(a,1),13(a,1)),rewrite(4(2)),flip(a)]. given #32 (A,wt=24): 20 f(x,f(y,z,u),f(x,v,f(z,u,w))) = f(x,v,f(z,u,f(x,y,w))). [para(8(a,1),6(a,2,3))]. given #33 (T,wt=15): 200 f(x,f(y,z,u),f(x,y,u)) = f(x,y,u). [para(13(a,1),151(a,1))]. given #34 (T,wt=15): 226 f(x,y,f(z,y,f(x,z,u))) = f(x,z,y). [para(8(a,1),153(a,1)),rewrite(3(1),2(1),3(2),3(2)),flip(a)]. given #35 (T,wt=15): 239 f(x,y,f(z,x,u)) = f(x,u,f(z,x,y)). [para(29(a,1),167(a,2)),rewrite(3(1),3(2),4(3),157(4),145(3),234(4),4(3),3(4,R),4(4))]. given #36 (T,wt=15): 326 f(x,y,f(z,u,y)) = f(u,y,f(z,x,y)). [para(153(a,1),180(a,2)),rewrite(4(3),3(4,R),4(4),324(5),3(3))]. given #37 (A,wt=27): 21 f(x,f(y,z,f(y,u,v)),f(u,w,f(y,z,v))) = f(u,f(y,z,v),f(x,y,w)). [para(6(a,1),8(a,1,2)),rewrite(4(4))]. given #38 (T,wt=15): 327 f(x,y,f(x,z,f(z,u,y))) = f(x,z,y). [para(3(a,1),186(a,1)),rewrite(3(1),3(3),3(3),4(4))]. given #39 (T,wt=15): 328 f(x,f(y,z,u),f(x,z,u)) = f(x,z,u). [para(13(a,1),186(a,1))]. given #40 (T,wt=15): 435 f(x,y,f(y,z,f(x,u,z))) = f(x,y,z). [para(151(a,1),200(a,1,3)),rewrite(4(1),4(5),157(5),32(4),358(4),4(1),4(4),170(6))]. given #41 (T,wt=18): 32 f(x,y,f(z,u,f(x,y,v))) = f(x,y,f(z,u,v)). [para(27(a,1),8(a,1,3)),rewrite(4(2),8(3),4(3)),flip(a)]. given #42 (A,wt=24): 22 f(x,f(y,z,u),f(z,v,f(z,u,w))) = f(z,u,f(x,y,f(z,v,w))). [para(6(a,1),8(a,1,3))]. given #43 (T,wt=18): 145 f(x,y,f(z,u,f(x,v,y))) = f(x,y,f(z,v,u)). [para(27(a,1),16(a,1,2)),rewrite(17(3),4(4)),flip(a)]. given #44 (T,wt=18): 154 f(x,y,f(z,u,f(v,x,y))) = f(x,y,f(z,v,u)). [para(84(a,1),16(a,1,2)),rewrite(8(3),4(4)),flip(a)]. given #45 (T,wt=18): 230 f(x,y,f(y,z,f(x,u,f(x,z,v)))) = f(x,y,z). [para(6(a,1),167(a,1,3,3))]. given #46 (T,wt=18): 233 f(x,y,f(y,z,f(z,u,f(x,z,v)))) = f(x,y,z). [para(12(a,2),167(a,1,3,3))]. given #47 (A,wt=21): 23 f(x,y,f(z,u,f(z,v,w))) = f(x,y,f(z,v,f(z,u,w))). [para(6(a,1),8(a,2,3)),rewrite(8(4))]. given #48 (T,wt=18): 312 f(x,y,f(z,y,f(x,u,f(x,z,v)))) = f(x,z,y). [para(168(a,1),18(a,1,3)),rewrite(3(2,R),4(2),199(3),3(2,R),4(2)),flip(a)]. given #49 (T,wt=18): 342 f(x,f(y,z,f(y,u,v)),f(x,y,u)) = f(x,y,u). [para(6(a,1),199(a,1,2))]. given #50 (T,wt=18): 346 f(x,f(y,z,f(z,u,v)),f(x,z,u)) = f(x,z,u). [para(12(a,1),199(a,1,2))]. given #51 (T,wt=18): 348 f(x,f(y,z,f(y,u,v)),f(x,y,v)) = f(x,y,v). [para(13(a,2),199(a,1,2))]. given #52 (A,wt=24): 24 f(f(x,y,z),f(x,y,u),f(v,w,v6)) = f(x,y,f(z,u,f(v,w,v6))). [para(8(a,1),8(a,1,2)),rewrite(3(3),3(3),3(5),16(5),3(3),3(3),16(5),8(3),3(4),3(4)),flip(a)]. given #53 (T,wt=18): 353 f(x,f(y,z,f(z,u,v)),f(x,z,v)) = f(x,z,v). [para(29(a,2),199(a,1,2)),rewrite(3(1),4(3),4(5))]. given #54 (T,wt=18): 424 f(x,f(y,z,u),f(y,v,z)) = f(y,z,f(v,x,u)). [para(200(a,1),12(a,1,3)),rewrite(3(2),3(2),3(3,R),3(6),3(6),3(7,R),217(8),11(4))]. given #55 (T,wt=18): 437 f(x,y,f(z,f(y,u,z),f(x,z,v))) = f(x,y,z). [para(200(a,1),167(a,2)),rewrite(4(5),139(6),4(3),3(4,R),372(6),32(5))]. given #56 (T,wt=18): 444 f(x,y,f(x,z,f(y,u,f(y,v,z)))) = f(x,y,z). [para(200(a,1),199(a,1,3)),rewrite(3(3),4(5),157(5),145(4),3(2,R),4(2),200(7))]. given #57 (A,wt=30): 25 f(x,f(y,z,f(u,v,w)),f(v,w,f(z,u,v6))) = f(z,f(u,v,w),f(x,y,f(v,w,v6))). [para(8(a,1),8(a,1,3))]. ============================== PROOF ================================= % Proof 1 at 1.36 (+ 0.00) seconds: dist_long. % Length of proof is 36. % Level of proof is 10. % Maximum clause weight is 30. % Given clauses 57. 1 f(f(x,y,z),u,w) = f(f(x,u,w),f(y,u,w),f(z,u,w)) # answer(dist_long) # label(goal). [goal]. 2 f(x,x,y) = x # label(majority). [assumption]. 3 f(x,y,z) = f(z,x,y) # label(2a). [assumption]. 4 f(x,y,z) = f(x,z,y) # label(2b). [assumption]. 5 f(f(x,y,z),y,u) = f(x,y,f(z,y,u)) # label(associativity). [assumption]. 6 f(x,y,f(x,z,u)) = f(x,z,f(x,y,u)). [copy(5),rewrite(3(2),3(2),3(3,R),4(3)),rewrite(3(1,R),4(1),4(3),3(4,R),4(4))]. 7 f(f(x,y,z),u,v) = f(x,f(y,u,v),f(z,u,v)) # label(dist_short). [assumption]. 8 f(x,f(y,z,u),f(z,u,v)) = f(z,u,f(x,y,v)). [copy(7),rewrite(3(2),3(2)),flip(a),rewrite(3(2),3(2))]. 9 f(f(c1,c4,c5),f(c2,c4,c5),f(c3,c4,c5)) != f(f(c1,c2,c3),c4,c5) # answer(dist_long). [deny(1)]. 10 f(f(c1,c4,c5),f(c2,c4,c5),f(c3,c4,c5)) != f(c4,c5,f(c1,c2,c3)) # answer(dist_long). [copy(9),rewrite(3(20),3(20))]. 11 f(x,y,y) = y. [para(3(a,1),2(a,1))]. 12 f(x,y,f(z,x,u)) = f(z,x,f(x,y,u)). [para(6(a,1),3(a,2)),rewrite(4(2),3(3,R),4(3)),flip(a)]. 13 f(x,y,f(x,z,u)) = f(x,u,f(x,y,z)). [para(3(a,1),6(a,1,3)),rewrite(3(1,R),4(1))]. 16 f(x,f(y,z,u),f(y,z,v)) = f(y,z,f(x,u,v)). [para(8(a,1),3(a,1)),rewrite(3(4),3(4),3(5,R)),flip(a)]. 17 f(x,f(y,z,u),f(y,u,v)) = f(y,u,f(x,z,v)). [para(3(a,1),8(a,1,2)),rewrite(3(2,R),4(2),3(5,R),4(5))]. 25 f(x,f(y,z,f(u,v,w)),f(v,w,f(z,u,v6))) = f(z,f(u,v,w),f(x,y,f(v,w,v6))). [para(8(a,1),8(a,1,3))]. 27 f(x,y,f(x,z,y)) = f(x,z,y). [para(11(a,1),6(a,1,3)),flip(a)]. 29 f(x,y,f(z,u,y)) = f(u,y,f(x,z,y)). [para(11(a,1),8(a,1,3)),rewrite(4(2))]. 32 f(x,y,f(z,u,f(x,y,v))) = f(x,y,f(z,u,v)). [para(27(a,1),8(a,1,3)),rewrite(4(2),8(3),4(3)),flip(a)]. 34 f(x,y,f(z,y,u)) = f(z,y,f(x,y,u)). [para(12(a,1),3(a,2)),rewrite(4(2),3(3,R),4(3))]. 84 f(x,y,f(z,x,y)) = f(z,x,y). [para(2(a,1),29(a,1,3)),rewrite(4(2),3(3,R),4(3)),flip(a)]. 85 f(x,y,f(z,u,x)) = f(u,x,f(z,x,y)). [para(3(a,1),29(a,1)),rewrite(3(2),4(2),3(3),3(3))]. 108 f(x,f(y,z,x),f(u,v,f(y,z,x))) = f(z,x,f(u,y,f(y,x,v))). [para(29(a,1),29(a,1,3)),rewrite(3(2),3(2),8(4)),flip(a)]. 124 f(x,f(y,x,z),f(u,v,f(y,x,z))) = f(y,x,f(u,z,f(x,z,v))). [para(34(a,1),29(a,1,3)),rewrite(3(2),3(2),16(4)),flip(a)]. 151 f(x,y,f(x,z,f(y,u,z))) = f(x,y,z). [para(16(a,1),29(a,1)),rewrite(32(3),11(1),3(4,R),4(4),124(5),4(2)),flip(a)]. 152 f(x,f(y,z,f(z,u,v)),f(z,v,w)) = f(z,v,f(x,w,f(y,z,u))). [para(29(a,2),16(a,1,2)),rewrite(3(1),3(3,R),4(3),4(5),4(6),3(7,R),4(7))]. 153 f(x,y,f(z,u,x)) = f(z,x,f(u,x,y)). [para(29(a,1),16(a,2)),rewrite(11(2),4(2),3(3,R),4(3),3(4,R),4(4)),flip(a)]. 154 f(x,y,f(z,u,f(v,x,y))) = f(x,y,f(z,v,u)). [para(84(a,1),16(a,1,2)),rewrite(8(3),4(4)),flip(a)]. 180 f(x,y,f(z,x,f(z,y,u))) = f(z,x,y). [para(84(a,1),85(a,1,3)),rewrite(3(3,R),11(3),4(4),108(5),3(3,R),4(3)),flip(a)]. 200 f(x,f(y,z,u),f(x,y,u)) = f(x,y,u). [para(13(a,1),151(a,1))]. 217 f(x,f(y,z,u),f(v,f(y,u,w),f(y,z,u))) = f(y,u,f(z,v,f(z,x,w))). [para(17(a,1),12(a,1,3)),rewrite(3(2,R),4(2),3(4,R),4(4),17(4),3(2,R),4(2),3(7,R)),flip(a)]. 226 f(x,y,f(z,y,f(x,z,u))) = f(x,z,y). [para(8(a,1),153(a,1)),rewrite(3(1),2(1),3(2),3(2)),flip(a)]. 424 f(x,f(y,z,u),f(y,v,z)) = f(y,z,f(v,x,u)). [para(200(a,1),12(a,1,3)),rewrite(3(2),3(2),3(3,R),3(6),3(6),3(7,R),217(8),11(4))]. 1418 f(x,f(y,z,u),f(v,z,f(z,u,w))) = f(z,u,f(y,x,f(v,z,w))). [para(12(a,1),25(a,1,2)),rewrite(3(3,R),4(3),152(5),424(3),3(1,R),4(1)),flip(a)]. 1488 f(x,f(y,z,u),f(v,z,u)) = f(z,u,f(v,x,y)). [para(25(a,1),180(a,1,3)),rewrite(3(5,R),4(5),1418(6),3(4,R),4(4),3(6,R),4(6),25(6),3(4,R),4(4),226(4),4(6),154(6),4(4))]. 1591 $F # answer(dist_long). [back_rewrite(10),rewrite(1488(13),3(9),154(10),3(6,R),4(6)),xx(a)]. ============================== end of proof ========================== ============================== STATISTICS ============================ Given=57. Generated=14716. Kept=1586. proofs=1. Usable=52. Sos=1124. Demods=993. Limbo=103, Disabled=313. Hints=0. Weight_deleted=0. Literals_deleted=0. Forward_subsumed=13129. Back_subsumed=44. Sos_limit_deleted=0. Sos_displaced=0. Sos_removed=0. New_demodulators=1252 (2 lex), Back_demodulated=263. Back_unit_deleted=0. Demod_attempts=215081. Demod_rewrites=75283. Res_instance_prunes=0. Para_instance_prunes=0. Basic_paramod_prunes=0. Nonunit_fsub_feature_tests=0. Nonunit_bsub_feature_tests=0. Megabytes=1.86. User_CPU=1.36, System_CPU=0.00, Wall_clock=1. ============================== end of statistics ===================== ============================== end of search ========================= THEOREM PROVED Exiting with 1 proof. Process 28057 exit (max_proofs) Fri Apr 13 09:56:39 2007