245 |
245 |
246 goal HOL.thy "(! x. P x & Q x) = ((! x. P x) & (! x. Q x))"; |
246 goal HOL.thy "(! x. P x & Q x) = ((! x. P x) & (! x. Q x))"; |
247 by (safe_meson_tac 1); |
247 by (safe_meson_tac 1); |
248 result(); |
248 result(); |
249 |
249 |
250 goal HOL.thy "(? x. P --> Q x) = (P --> (? x.Q x))"; |
250 goal HOL.thy "(? x. P --> Q x) = (P --> (? x. Q x))"; |
251 by (safe_meson_tac 1); |
251 by (safe_meson_tac 1); |
252 result(); |
252 result(); |
253 |
253 |
254 goal HOL.thy "(? x.P x --> Q) = ((! x.P x) --> Q)"; |
254 goal HOL.thy "(? x. P x --> Q) = ((! x. P x) --> Q)"; |
255 by (safe_meson_tac 1); |
255 by (safe_meson_tac 1); |
256 result(); |
256 result(); |
257 |
257 |
258 goal HOL.thy "((! x.P x) | Q) = (! x. P x | Q)"; |
258 goal HOL.thy "((! x. P x) | Q) = (! x. P x | Q)"; |
259 by (safe_meson_tac 1); |
259 by (safe_meson_tac 1); |
260 result(); |
260 result(); |
261 |
261 |
262 goal HOL.thy "(! x. P x --> P(f x)) & P d --> P(f(f(f d)))"; |
262 goal HOL.thy "(! x. P x --> P(f x)) & P d --> P(f(f(f d)))"; |
263 by (safe_meson_tac 1); |
263 by (safe_meson_tac 1); |
305 by (safe_meson_tac 1); |
305 by (safe_meson_tac 1); |
306 result(); |
306 result(); |
307 |
307 |
308 writeln"Problem 24"; (*The first goal clause is useless*) |
308 writeln"Problem 24"; (*The first goal clause is useless*) |
309 goal HOL.thy "~(? x. S x & Q x) & (! x. P x --> Q x | R x) & \ |
309 goal HOL.thy "~(? x. S x & Q x) & (! x. P x --> Q x | R x) & \ |
310 \ (~(? x.P x) --> (? x.Q x)) & (! x. Q x | R x --> S x) \ |
310 \ (~(? x. P x) --> (? x. Q x)) & (! x. Q x | R x --> S x) \ |
311 \ --> (? x. P x & R x)"; |
311 \ --> (? x. P x & R x)"; |
312 by (safe_meson_tac 1); |
312 by (safe_meson_tac 1); |
313 result(); |
313 result(); |
314 |
314 |
315 writeln"Problem 25"; |
315 writeln"Problem 25"; |
338 result(); |
338 result(); |
339 |
339 |
340 writeln"Problem 28. AMENDED"; (*14 Horn clauses*) |
340 writeln"Problem 28. AMENDED"; (*14 Horn clauses*) |
341 goal HOL.thy "(! x. P x --> (! x. Q x)) & \ |
341 goal HOL.thy "(! x. P x --> (! x. Q x)) & \ |
342 \ ((! x. Q x | R x) --> (? x. Q x & S x)) & \ |
342 \ ((! x. Q x | R x) --> (? x. Q x & S x)) & \ |
343 \ ((? x.S x) --> (! x. L x --> M x)) \ |
343 \ ((? x. S x) --> (! x. L x --> M x)) \ |
344 \ --> (! x. P x & L x --> M x)"; |
344 \ --> (! x. P x & L x --> M x)"; |
345 by (safe_meson_tac 1); |
345 by (safe_meson_tac 1); |
346 result(); |
346 result(); |
347 |
347 |
348 writeln"Problem 29. Essentially the same as Principia Mathematica *11.71"; |
348 writeln"Problem 29. Essentially the same as Principia Mathematica *11.71"; |
359 \ --> (! x. S x)"; |
359 \ --> (! x. S x)"; |
360 by (safe_meson_tac 1); |
360 by (safe_meson_tac 1); |
361 result(); |
361 result(); |
362 |
362 |
363 writeln"Problem 31"; (*10 Horn clauses; first negative clauses is useless*) |
363 writeln"Problem 31"; (*10 Horn clauses; first negative clauses is useless*) |
364 goal HOL.thy "~(? x.P x & (Q x | R x)) & \ |
364 goal HOL.thy "~(? x. P x & (Q x | R x)) & \ |
365 \ (? x. L x & P x) & \ |
365 \ (? x. L x & P x) & \ |
366 \ (! x. ~ R x --> M x) \ |
366 \ (! x. ~ R x --> M x) \ |
367 \ --> (? x. L x & M x)"; |
367 \ --> (? x. L x & M x)"; |
368 by (safe_meson_tac 1); |
368 by (safe_meson_tac 1); |
369 result(); |
369 result(); |
405 by (safe_meson_tac 1); |
405 by (safe_meson_tac 1); |
406 result(); |
406 result(); |
407 |
407 |
408 writeln"Problem 37"; (*10 Horn clauses*) |
408 writeln"Problem 37"; (*10 Horn clauses*) |
409 goal HOL.thy "(! z. ? w. ! x. ? y. \ |
409 goal HOL.thy "(! z. ? w. ! x. ? y. \ |
410 \ (P x z --> P y w) & P y z & (P y w --> (? u.Q u w))) & \ |
410 \ (P x z --> P y w) & P y z & (P y w --> (? u. Q u w))) & \ |
411 \ (! x z. ~P x z --> (? y. Q y z)) & \ |
411 \ (! x z. ~P x z --> (? y. Q y z)) & \ |
412 \ ((? x y. Q x y) --> (! x. R x x)) \ |
412 \ ((? x y. Q x y) --> (! x. R x x)) \ |
413 \ --> (! x. ? y. R x y)"; |
413 \ --> (! x. ? y. R x y)"; |
414 by (safe_meson_tac 1); (*causes unification tracing messages*) |
414 by (safe_meson_tac 1); (*causes unification tracing messages*) |
415 result(); |
415 result(); |
473 result(); |
473 result(); |
474 |
474 |
475 writeln"Problem 46"; (*26 Horn clauses; 21-step proof*) |
475 writeln"Problem 46"; (*26 Horn clauses; 21-step proof*) |
476 goal HOL.thy |
476 goal HOL.thy |
477 "(! x. f x & (! y. f y & h y x --> g y) --> g x) & \ |
477 "(! x. f x & (! y. f y & h y x --> g y) --> g x) & \ |
478 \ ((? x.f x & ~g x) --> \ |
478 \ ((? x. f x & ~g x) --> \ |
479 \ (? x. f x & ~g x & (! y. f y & ~g y --> j x y))) & \ |
479 \ (? x. f x & ~g x & (! y. f y & ~g y --> j x y))) & \ |
480 \ (! x y. f x & f y & h x y --> ~j y x) \ |
480 \ (! x y. f x & f y & h x y --> ~j y x) \ |
481 \ --> (! x. f x --> g x)"; |
481 \ --> (! x. f x --> g x)"; |
482 by (safe_best_meson_tac 1); |
482 by (safe_best_meson_tac 1); |
483 (*1.7 secs; iter. deepening is slightly slower*) |
483 (*1.7 secs; iter. deepening is slightly slower*) |
484 result(); |
484 result(); |
485 |
485 |
486 writeln"Problem 47. Schubert's Steamroller"; |
486 writeln"Problem 47. Schubert's Steamroller"; |
487 (*26 clauses; 63 Horn clauses*) |
487 (*26 clauses; 63 Horn clauses*) |
488 goal HOL.thy |
488 goal HOL.thy |
489 "(! x. P1 x --> P0 x) & (? x.P1 x) & \ |
489 "(! x. P1 x --> P0 x) & (? x. P1 x) & \ |
490 \ (! x. P2 x --> P0 x) & (? x.P2 x) & \ |
490 \ (! x. P2 x --> P0 x) & (? x. P2 x) & \ |
491 \ (! x. P3 x --> P0 x) & (? x.P3 x) & \ |
491 \ (! x. P3 x --> P0 x) & (? x. P3 x) & \ |
492 \ (! x. P4 x --> P0 x) & (? x.P4 x) & \ |
492 \ (! x. P4 x --> P0 x) & (? x. P4 x) & \ |
493 \ (! x. P5 x --> P0 x) & (? x.P5 x) & \ |
493 \ (! x. P5 x --> P0 x) & (? x. P5 x) & \ |
494 \ (! x. Q1 x --> Q0 x) & (? x.Q1 x) & \ |
494 \ (! x. Q1 x --> Q0 x) & (? x. Q1 x) & \ |
495 \ (! x. P0 x --> ((! y.Q0 y-->R x y) | \ |
495 \ (! x. P0 x --> ((! y. Q0 y-->R x y) | \ |
496 \ (! y.P0 y & S y x & \ |
496 \ (! y. P0 y & S y x & \ |
497 \ (? z.Q0 z&R y z) --> R x y))) & \ |
497 \ (? z. Q0 z&R y z) --> R x y))) & \ |
498 \ (! x y. P3 y & (P5 x|P4 x) --> S x y) & \ |
498 \ (! x y. P3 y & (P5 x|P4 x) --> S x y) & \ |
499 \ (! x y. P3 x & P2 y --> S x y) & \ |
499 \ (! x y. P3 x & P2 y --> S x y) & \ |
500 \ (! x y. P2 x & P1 y --> S x y) & \ |
500 \ (! x y. P2 x & P1 y --> S x y) & \ |
501 \ (! x y. P1 x & (P2 y|Q1 y) --> ~R x y) & \ |
501 \ (! x y. P1 x & (P2 y|Q1 y) --> ~R x y) & \ |
502 \ (! x y. P3 x & P4 y --> R x y) & \ |
502 \ (! x y. P3 x & P4 y --> R x y) & \ |
503 \ (! x y. P3 x & P5 y --> ~R x y) & \ |
503 \ (! x y. P3 x & P5 y --> ~R x y) & \ |
504 \ (! x. (P4 x|P5 x) --> (? y.Q0 y & R x y)) \ |
504 \ (! x. (P4 x|P5 x) --> (? y. Q0 y & R x y)) \ |
505 \ --> (? x y. P0 x & P0 y & (? z. Q1 z & R y z & R x y))"; |
505 \ --> (? x y. P0 x & P0 y & (? z. Q1 z & R y z & R x y))"; |
506 by (safe_meson_tac 1); (*119 secs*) |
506 by (safe_meson_tac 1); (*119 secs*) |
507 result(); |
507 result(); |
508 |
508 |
509 (*The Los problem? Circulated by John Harrison*) |
509 (*The Los problem? Circulated by John Harrison*) |
516 result(); |
516 result(); |
517 |
517 |
518 (*A similar example, suggested by Johannes Schumann and credited to Pelletier*) |
518 (*A similar example, suggested by Johannes Schumann and credited to Pelletier*) |
519 goal HOL.thy "(!x y z. P x y --> P y z --> P x z) --> \ |
519 goal HOL.thy "(!x y z. P x y --> P y z --> P x z) --> \ |
520 \ (!x y z. Q x y --> Q y z --> Q x z) --> \ |
520 \ (!x y z. Q x y --> Q y z --> Q x z) --> \ |
521 \ (!x y.Q x y --> Q y x) --> (!x y. P x y | Q x y) --> \ |
521 \ (!x y. Q x y --> Q y x) --> (!x y. P x y | Q x y) --> \ |
522 \ (!x y.P x y) | (!x y.Q x y)"; |
522 \ (!x y. P x y) | (!x y. Q x y)"; |
523 by (safe_best_meson_tac 1); (*2.7 secs*) |
523 by (safe_best_meson_tac 1); (*2.7 secs*) |
524 result(); |
524 result(); |
525 |
525 |
526 writeln"Problem 50"; |
526 writeln"Problem 50"; |
527 (*What has this to do with equality?*) |
527 (*What has this to do with equality?*) |
528 goal HOL.thy "(! x. P a x | (! y.P x y)) --> (? x. ! y.P x y)"; |
528 goal HOL.thy "(! x. P a x | (! y. P x y)) --> (? x. ! y. P x y)"; |
529 by (safe_meson_tac 1); |
529 by (safe_meson_tac 1); |
530 result(); |
530 result(); |
531 |
531 |
532 writeln"Problem 55"; |
532 writeln"Problem 55"; |
533 |
533 |