332 |
351 |
333 |
352 |
334 (* ------------------------ Further rewrites ----------------------------------------- *) |
353 (* ------------------------ Further rewrites ----------------------------------------- *) |
335 section "Further rewrites"; |
354 section "Further rewrites"; |
336 |
355 |
337 qed_goalw "NotBox" TLA.thy [dmd_def] "|- (~[]F) = (<>~F)" |
356 Goalw [dmd_def] "|- (~[]F) = (<>~F)"; |
338 (fn _ => [ Simp_tac 1 ]); |
357 by (Simp_tac 1); |
339 |
358 qed "NotBox"; |
340 qed_goalw "NotDmd" TLA.thy [dmd_def] "|- (~<>F) = ([]~F)" |
359 |
341 (fn _ => [ Simp_tac 1 ]); |
360 Goalw [dmd_def] "|- (~<>F) = ([]~F)"; |
|
361 by (Simp_tac 1); |
|
362 qed "NotDmd"; |
342 |
363 |
343 (* These are not by default included in temp_css, because they could be harmful, |
364 (* These are not by default included in temp_css, because they could be harmful, |
344 e.g. []F & ~[]F becomes []F & <>~F !! *) |
365 e.g. []F & ~[]F becomes []F & <>~F !! *) |
345 val more_temp_simps = (map temp_rewrite [STL3, DmdDmd, NotBox, NotDmd]) |
366 val more_temp_simps = (map temp_rewrite [STL3, DmdDmd, NotBox, NotDmd]) |
346 @ (map (fn th => (temp_unlift th) RS eq_reflection) |
367 @ (map (fn th => (temp_unlift th) RS eq_reflection) |
347 [NotBox, NotDmd]); |
368 [NotBox, NotDmd]); |
348 |
369 |
349 qed_goal "BoxDmdBox" TLA.thy "|- ([]<>[]F) = (<>[]F)" |
370 Goal "|- ([]<>[]F) = (<>[]F)"; |
350 (fn _ => [ auto_tac (temp_css addSDs2 [STL2]), |
371 by (auto_tac (temp_css addSDs2 [STL2])); |
351 rtac ccontr 1, |
372 by (rtac ccontr 1); |
352 subgoal_tac "sigma |= <>[][]F & <>[]~[]F" 1, |
373 by (subgoal_tac "sigma |= <>[][]F & <>[]~[]F" 1); |
353 etac thin_rl 1, |
374 by (etac thin_rl 1); |
354 Auto_tac, |
375 by Auto_tac; |
355 dtac (temp_use STL6) 1, atac 1, |
376 by (dtac (temp_use STL6) 1); |
356 Asm_full_simp_tac 1, |
377 by (atac 1); |
357 ALLGOALS (asm_full_simp_tac (simpset() addsimps more_temp_simps)) |
378 by (Asm_full_simp_tac 1); |
358 ]); |
379 by (ALLGOALS (asm_full_simp_tac (simpset() addsimps more_temp_simps))); |
359 |
380 qed "BoxDmdBox"; |
360 qed_goalw "DmdBoxDmd" TLA.thy [dmd_def] "|- (<>[]<>F) = ([]<>F)" |
381 |
361 (fn _ => [ auto_tac (temp_css addsimps2 [rewrite_rule [dmd_def] BoxDmdBox]) ]); |
382 Goalw [dmd_def] "|- (<>[]<>F) = ([]<>F)"; |
|
383 by (auto_tac (temp_css addsimps2 [rewrite_rule [dmd_def] BoxDmdBox])); |
|
384 qed "DmdBoxDmd"; |
362 |
385 |
363 val more_temp_simps = more_temp_simps @ (map temp_rewrite [BoxDmdBox, DmdBoxDmd]); |
386 val more_temp_simps = more_temp_simps @ (map temp_rewrite [BoxDmdBox, DmdBoxDmd]); |
364 |
387 |
365 |
388 |
366 (* ------------------------ Miscellaneous ----------------------------------- *) |
389 (* ------------------------ Miscellaneous ----------------------------------- *) |
367 |
390 |
368 qed_goal "BoxOr" TLA.thy |
391 Goal "!!sigma. [| sigma |= []F | []G |] ==> sigma |= [](F | G)"; |
369 "!!sigma. [| sigma |= []F | []G |] ==> sigma |= [](F | G)" |
392 by (fast_tac (temp_cs addSEs [STL4E]) 1); |
370 (fn _ => [ fast_tac (temp_cs addSEs [STL4E]) 1 ]); |
393 qed "BoxOr"; |
371 |
394 |
372 (* "persistently implies infinitely often" *) |
395 (* "persistently implies infinitely often" *) |
373 qed_goal "DBImplBD" TLA.thy "|- <>[]F --> []<>F" |
396 Goal "|- <>[]F --> []<>F"; |
374 (fn _ => [Clarsimp_tac 1, |
397 by (Clarsimp_tac 1); |
375 rtac ccontr 1, |
398 by (rtac ccontr 1); |
376 asm_full_simp_tac (simpset() addsimps more_temp_simps) 1, |
399 by (asm_full_simp_tac (simpset() addsimps more_temp_simps) 1); |
377 dtac (temp_use STL6) 1, atac 1, |
400 by (dtac (temp_use STL6) 1); |
378 Asm_full_simp_tac 1 |
401 by (atac 1); |
379 ]); |
402 by (Asm_full_simp_tac 1); |
380 |
403 qed "DBImplBD"; |
381 qed_goal "BoxDmdDmdBox" TLA.thy |
404 |
382 "|- []<>F & <>[]G --> []<>(F & G)" |
405 Goal "|- []<>F & <>[]G --> []<>(F & G)"; |
383 (fn _ => [Clarsimp_tac 1, |
406 by (Clarsimp_tac 1); |
384 rtac ccontr 1, |
407 by (rtac ccontr 1); |
385 rewrite_goals_tac more_temp_simps, |
408 by (rewrite_goals_tac more_temp_simps); |
386 dtac (temp_use STL6) 1, atac 1, |
409 by (dtac (temp_use STL6) 1); |
387 subgoal_tac "sigma |= <>[]~F" 1, |
410 by (atac 1); |
388 force_tac (temp_css addsimps2 [dmd_def]) 1, |
411 by (subgoal_tac "sigma |= <>[]~F" 1); |
389 fast_tac (temp_cs addEs [DmdImplE,STL4E]) 1 |
412 by (force_tac (temp_css addsimps2 [dmd_def]) 1); |
390 ]); |
413 by (fast_tac (temp_cs addEs [DmdImplE,STL4E]) 1); |
|
414 qed "BoxDmdDmdBox"; |
391 |
415 |
392 |
416 |
393 (* ------------------------------------------------------------------------- *) |
417 (* ------------------------------------------------------------------------- *) |
394 (*** TLA-specific theorems: primed formulas ***) |
418 (*** TLA-specific theorems: primed formulas ***) |
395 (* ------------------------------------------------------------------------- *) |
419 (* ------------------------------------------------------------------------- *) |
396 section "priming"; |
420 section "priming"; |
397 |
421 |
398 (* ------------------------ TLA2 ------------------------------------------- *) |
422 (* ------------------------ TLA2 ------------------------------------------- *) |
399 qed_goal "STL2_pr" TLA.thy |
423 Goal "|- []P --> Init P & Init P`"; |
400 "|- []P --> Init P & Init P`" |
424 by (fast_tac (temp_cs addSIs [primeI, STL2_gen]) 1); |
401 (fn _ => [fast_tac (temp_cs addSIs [primeI, STL2_gen]) 1]); |
425 qed "STL2_pr"; |
402 |
426 |
403 (* Auxiliary lemma allows priming of boxed actions *) |
427 (* Auxiliary lemma allows priming of boxed actions *) |
404 qed_goal "BoxPrime" TLA.thy "|- []P --> []($P & P$)" |
428 Goal "|- []P --> []($P & P$)"; |
405 (fn _ => [Clarsimp_tac 1, |
429 by (Clarsimp_tac 1); |
406 etac dup_boxE 1, |
430 by (etac dup_boxE 1); |
407 rewtac boxInit_act, |
431 by (rewtac boxInit_act); |
408 etac STL4E 1, |
432 by (etac STL4E 1); |
409 auto_tac (temp_css addsimps2 Init_simps addSDs2 [STL2_pr]) |
433 by (auto_tac (temp_css addsimps2 Init_simps addSDs2 [STL2_pr])); |
410 ]); |
434 qed "BoxPrime"; |
411 |
435 |
412 qed_goal "TLA2" TLA.thy "|- $P & P$ --> A ==> |- []P --> []A" |
436 val prems = goal thy "|- $P & P$ --> A ==> |- []P --> []A"; |
413 (fn prems => [Clarsimp_tac 1, |
437 by (Clarsimp_tac 1); |
414 dtac (temp_use BoxPrime) 1, |
438 by (dtac (temp_use BoxPrime) 1); |
415 auto_tac (temp_css addsimps2 [Init_stp_act_rev] addSIs2 prems addSEs2 [STL4E]) |
439 by (auto_tac (temp_css addsimps2 [Init_stp_act_rev] |
416 ]); |
440 addSIs2 prems addSEs2 [STL4E])); |
417 |
441 qed "TLA2"; |
418 qed_goal "TLA2E" TLA.thy |
442 |
419 "[| sigma |= []P; |- $P & P$ --> A |] ==> sigma |= []A" |
443 val prems = goal thy |
420 (fn prems => [REPEAT (resolve_tac (prems @ (prems RL [temp_use TLA2])) 1)]); |
444 "[| sigma |= []P; |- $P & P$ --> A |] ==> sigma |= []A"; |
421 |
445 by (REPEAT (resolve_tac (prems @ (prems RL [temp_use TLA2])) 1)); |
422 qed_goalw "DmdPrime" TLA.thy [dmd_def] "|- (<>P`) --> (<>P)" |
446 qed "TLA2E"; |
423 (fn _ => [ fast_tac (temp_cs addSEs [TLA2E]) 1 ]); |
447 |
|
448 Goalw [dmd_def] "|- (<>P`) --> (<>P)"; |
|
449 by (fast_tac (temp_cs addSEs [TLA2E]) 1); |
|
450 qed "DmdPrime"; |
424 |
451 |
425 bind_thm("PrimeDmd", (temp_use InitDmd_gen) RS (temp_use DmdPrime)); |
452 bind_thm("PrimeDmd", (temp_use InitDmd_gen) RS (temp_use DmdPrime)); |
426 |
453 |
427 (* ------------------------ INV1, stable --------------------------------------- *) |
454 (* ------------------------ INV1, stable --------------------------------------- *) |
428 section "stable, invariant"; |
455 section "stable, invariant"; |
429 |
456 |
430 qed_goal "ind_rule" TLA.thy |
457 val prems = goal thy |
431 "[| sigma |= []H; sigma |= Init P; |- H --> (Init P & ~[]F --> Init(P`) & F) |] \ |
458 "[| sigma |= []H; sigma |= Init P; |- H --> (Init P & ~[]F --> Init(P`) & F) |] \ |
432 \ ==> sigma |= []F" |
459 \ ==> sigma |= []F"; |
433 (fn prems => [rtac (temp_use indT) 1, |
460 by (rtac (temp_use indT) 1); |
434 REPEAT (resolve_tac (prems @ (prems RL [STL4E])) 1)]); |
461 by (REPEAT (resolve_tac (prems @ (prems RL [STL4E])) 1)); |
435 |
462 qed "ind_rule"; |
436 qed_goalw "box_stp_act" TLA.thy [boxInit_act] "|- ([]$P) = ([]P)" |
463 |
437 (K [simp_tac (simpset() addsimps Init_simps) 1]); |
464 Goalw [boxInit_act] "|- ([]$P) = ([]P)"; |
|
465 by (simp_tac (simpset() addsimps Init_simps) 1); |
|
466 qed "box_stp_act"; |
438 bind_thm("box_stp_actI", zero_var_indexes ((temp_use box_stp_act) RS iffD2)); |
467 bind_thm("box_stp_actI", zero_var_indexes ((temp_use box_stp_act) RS iffD2)); |
439 bind_thm("box_stp_actD", zero_var_indexes ((temp_use box_stp_act) RS iffD1)); |
468 bind_thm("box_stp_actD", zero_var_indexes ((temp_use box_stp_act) RS iffD1)); |
440 |
469 |
441 val more_temp_simps = (temp_rewrite box_stp_act)::more_temp_simps; |
470 val more_temp_simps = (temp_rewrite box_stp_act)::more_temp_simps; |
442 |
471 |
443 qed_goalw "INV1" TLA.thy [stable_def,boxInit_stp,boxInit_act] |
472 Goalw [stable_def,boxInit_stp,boxInit_act] |
444 "|- (Init P) --> (stable P) --> []P" |
473 "|- (Init P) --> (stable P) --> []P"; |
445 (K [Clarsimp_tac 1, |
474 by (Clarsimp_tac 1); |
446 etac ind_rule 1, |
475 by (etac ind_rule 1); |
447 auto_tac (temp_css addsimps2 Init_simps addEs2 [ind_rule]) |
476 by (auto_tac (temp_css addsimps2 Init_simps addEs2 [ind_rule])); |
448 ]); |
477 qed "INV1"; |
449 |
478 |
450 qed_goalw "StableT" TLA.thy [stable_def] |
479 Goalw [stable_def] |
451 "|- $P & A --> P` ==> |- []A --> stable P" |
480 "!!P. |- $P & A --> P` ==> |- []A --> stable P"; |
452 (fn [prem] => [fast_tac (temp_cs addSEs [STL4E] addIs [prem]) 1]); |
481 by (fast_tac (temp_cs addSEs [STL4E]) 1); |
453 |
482 qed "StableT"; |
454 qed_goal "Stable" TLA.thy |
483 |
455 "[| sigma |= []A; |- $P & A --> P` |] ==> sigma |= stable P" |
484 val prems = goal thy |
456 (fn prems => [ REPEAT (resolve_tac (prems @ [temp_use StableT]) 1) ]); |
485 "[| sigma |= []A; |- $P & A --> P` |] ==> sigma |= stable P"; |
|
486 by (REPEAT (resolve_tac (prems @ [temp_use StableT]) 1)); |
|
487 qed "Stable"; |
457 |
488 |
458 (* Generalization of INV1 *) |
489 (* Generalization of INV1 *) |
459 qed_goalw "StableBox" TLA.thy [stable_def] |
490 Goalw [stable_def] "|- (stable P) --> [](Init P --> []P)"; |
460 "|- (stable P) --> [](Init P --> []P)" |
491 by (Clarsimp_tac 1); |
461 (K [Clarsimp_tac 1, |
492 by (etac dup_boxE 1); |
462 etac dup_boxE 1, |
493 by (force_tac (temp_css addsimps2 [stable_def] addEs2 [STL4E, INV1]) 1); |
463 force_tac (temp_css addsimps2 [stable_def] addEs2 [STL4E, INV1]) 1]); |
494 qed "StableBox"; |
464 |
495 |
465 qed_goal "DmdStable" TLA.thy |
496 Goal "|- (stable P) & <>P --> <>[]P"; |
466 "|- (stable P) & <>P --> <>[]P" |
497 by (Clarsimp_tac 1); |
467 (fn _ => [Clarsimp_tac 1, |
498 by (rtac DmdImpl2 1); |
468 rtac DmdImpl2 1, |
499 by (etac (temp_use StableBox) 2); |
469 etac (temp_use StableBox) 2, |
500 by (asm_simp_tac (simpset() addsimps [dmdInitD]) 1); |
470 asm_simp_tac (simpset() addsimps [dmdInitD]) 1 |
501 qed "DmdStable"; |
471 ]); |
|
472 |
502 |
473 (* ---------------- (Semi-)automatic invariant tactics ---------------------- *) |
503 (* ---------------- (Semi-)automatic invariant tactics ---------------------- *) |
474 |
504 |
475 (* inv_tac reduces goals of the form ... ==> sigma |= []P *) |
505 (* inv_tac reduces goals of the form ... ==> sigma |= []P *) |
476 fun inv_tac css = SELECT_GOAL |
506 fun inv_tac css = SELECT_GOAL |
489 fun auto_inv_tac ss = SELECT_GOAL |
519 fun auto_inv_tac ss = SELECT_GOAL |
490 ((inv_tac (claset(),ss) 1) THEN |
520 ((inv_tac (claset(),ss) 1) THEN |
491 (TRYALL (action_simp_tac (ss addsimps [Init_stp,Init_act]) [] [squareE]))); |
521 (TRYALL (action_simp_tac (ss addsimps [Init_stp,Init_act]) [] [squareE]))); |
492 |
522 |
493 |
523 |
494 qed_goalw "unless" TLA.thy [dmd_def] |
524 Goalw [dmd_def] "|- []($P --> P` | Q`) --> (stable P) | <>Q"; |
495 "|- []($P --> P` | Q`) --> (stable P) | <>Q" |
525 by (clarsimp_tac (temp_css addSDs2 [BoxPrime]) 1); |
496 (fn _ => [clarsimp_tac (temp_css addSDs2 [BoxPrime]) 1, |
526 by (merge_box_tac 1); |
497 merge_box_tac 1, |
527 by (etac swap 1); |
498 etac swap 1, |
528 by (fast_tac (temp_cs addSEs [Stable]) 1); |
499 fast_tac (temp_cs addSEs [Stable]) 1 |
529 qed "unless"; |
500 ]); |
|
501 |
530 |
502 |
531 |
503 (* --------------------- Recursive expansions --------------------------------------- *) |
532 (* --------------------- Recursive expansions --------------------------------------- *) |
504 section "recursive expansions"; |
533 section "recursive expansions"; |
505 |
534 |
506 (* Recursive expansions of [] and <> for state predicates *) |
535 (* Recursive expansions of [] and <> for state predicates *) |
507 qed_goal "BoxRec" TLA.thy "|- ([]P) = (Init P & []P`)" |
536 Goal "|- ([]P) = (Init P & []P`)"; |
508 (fn _ => [auto_tac (temp_css addSIs2 [STL2_gen]), |
537 by (auto_tac (temp_css addSIs2 [STL2_gen])); |
509 fast_tac (temp_cs addSEs [TLA2E]) 1, |
538 by (fast_tac (temp_cs addSEs [TLA2E]) 1); |
510 auto_tac (temp_css addsimps2 [stable_def] addSEs2 [INV1,STL4E]) |
539 by (auto_tac (temp_css addsimps2 [stable_def] addSEs2 [INV1,STL4E])); |
511 ]); |
540 qed "BoxRec"; |
512 |
541 |
513 qed_goalw "DmdRec" TLA.thy [dmd_def, temp_rewrite BoxRec] "|- (<>P) = (Init P | <>P`)" |
542 Goalw [dmd_def, temp_rewrite BoxRec] "|- (<>P) = (Init P | <>P`)"; |
514 (K [ auto_tac (temp_css addsimps2 Init_simps) ]); |
543 by (auto_tac (temp_css addsimps2 Init_simps)); |
515 |
544 qed "DmdRec"; |
516 qed_goal "DmdRec2" TLA.thy |
545 |
517 "!!sigma. [| sigma |= <>P; sigma |= []~P` |] ==> sigma |= Init P" |
546 Goal "!!sigma. [| sigma |= <>P; sigma |= []~P` |] ==> sigma |= Init P"; |
518 (K [ force_tac (temp_css addsimps2 [DmdRec,dmd_def]) 1]); |
547 by (force_tac (temp_css addsimps2 [DmdRec,dmd_def]) 1); |
519 |
548 qed "DmdRec2"; |
520 (* The "-->" part of the following is a little intricate. *) |
549 |
521 qed_goal "InfinitePrime" TLA.thy "|- ([]<>P) = ([]<>P`)" |
550 Goal "|- ([]<>P) = ([]<>P`)"; |
522 (fn _ => [Auto_tac, |
551 by Auto_tac; |
523 rtac classical 1, |
552 by (rtac classical 1); |
524 rtac (temp_use DBImplBD) 1, |
553 by (rtac (temp_use DBImplBD) 1); |
525 subgoal_tac "sigma |= <>[]P" 1, |
554 by (subgoal_tac "sigma |= <>[]P" 1); |
526 fast_tac (temp_cs addSEs [DmdImplE,TLA2E]) 1, |
555 by (fast_tac (temp_cs addSEs [DmdImplE,TLA2E]) 1); |
527 subgoal_tac "sigma |= <>[](<>P & []~P`)" 1, |
556 by (subgoal_tac "sigma |= <>[](<>P & []~P`)" 1); |
528 force_tac (temp_css addsimps2 [boxInit_stp] |
557 by (force_tac (temp_css addsimps2 [boxInit_stp] |
529 addSEs2 [DmdImplE,STL4E,DmdRec2]) 1, |
558 addSEs2 [DmdImplE,STL4E,DmdRec2]) 1); |
530 force_tac (temp_css addSIs2 [STL6] addsimps2 more_temp_simps) 1, |
559 by (force_tac (temp_css addSIs2 [STL6] addsimps2 more_temp_simps) 1); |
531 fast_tac (temp_cs addIs [DmdPrime] addSEs [STL4E]) 1 |
560 by (fast_tac (temp_cs addIs [DmdPrime] addSEs [STL4E]) 1); |
532 ]); |
561 qed "InfinitePrime"; |
533 |
562 |
534 qed_goal "InfiniteEnsures" TLA.thy |
563 val prems = goalw thy [temp_rewrite InfinitePrime] |
535 "[| sigma |= []N; sigma |= []<>A; |- A & N --> P` |] ==> sigma |= []<>P" |
564 "[| sigma |= []N; sigma |= []<>A; |- A & N --> P` |] ==> sigma |= []<>P"; |
536 (fn prems => [rewtac (temp_rewrite InfinitePrime), |
565 by (rtac InfImpl 1); |
537 rtac InfImpl 1, |
566 by (REPEAT (resolve_tac prems 1)); |
538 REPEAT (resolve_tac prems 1) |
567 qed "InfiniteEnsures"; |
539 ]); |
|
540 |
568 |
541 (* ------------------------ fairness ------------------------------------------- *) |
569 (* ------------------------ fairness ------------------------------------------- *) |
542 section "fairness"; |
570 section "fairness"; |
543 |
571 |
544 (* alternative definitions of fairness *) |
572 (* alternative definitions of fairness *) |
545 qed_goalw "WF_alt" TLA.thy [WF_def,dmd_def] |
573 Goalw [WF_def,dmd_def] |
546 "|- WF(A)_v = ([]<>~Enabled(<A>_v) | []<><A>_v)" |
574 "|- WF(A)_v = ([]<>~Enabled(<A>_v) | []<><A>_v)"; |
547 (fn _ => [ fast_tac temp_cs 1 ]); |
575 by (fast_tac temp_cs 1); |
548 |
576 qed "WF_alt"; |
549 qed_goalw "SF_alt" TLA.thy [SF_def,dmd_def] |
577 |
550 "|- SF(A)_v = (<>[]~Enabled(<A>_v) | []<><A>_v)" |
578 Goalw [SF_def,dmd_def] |
551 (fn _ => [ fast_tac temp_cs 1 ]); |
579 "|- SF(A)_v = (<>[]~Enabled(<A>_v) | []<><A>_v)"; |
|
580 by (fast_tac temp_cs 1); |
|
581 qed "SF_alt"; |
552 |
582 |
553 (* theorems to "box" fairness conditions *) |
583 (* theorems to "box" fairness conditions *) |
554 qed_goal "BoxWFI" TLA.thy "|- WF(A)_v --> []WF(A)_v" |
584 Goal "|- WF(A)_v --> []WF(A)_v"; |
555 (fn _ => [ auto_tac (temp_css addsimps2 (WF_alt::more_temp_simps) |
585 by (auto_tac (temp_css addsimps2 (WF_alt::more_temp_simps) |
556 addSIs2 [BoxOr]) ]); |
586 addSIs2 [BoxOr])); |
557 |
587 qed "BoxWFI"; |
558 qed_goal "WF_Box" TLA.thy "|- ([]WF(A)_v) = WF(A)_v" |
588 |
559 (fn prems => [ fast_tac (temp_cs addSIs [BoxWFI] addSDs [STL2]) 1 ]); |
589 Goal "|- ([]WF(A)_v) = WF(A)_v"; |
560 |
590 by (fast_tac (temp_cs addSIs [BoxWFI] addSDs [STL2]) 1); |
561 qed_goal "BoxSFI" TLA.thy "|- SF(A)_v --> []SF(A)_v" |
591 qed "WF_Box"; |
562 (fn _ => [ auto_tac (temp_css addsimps2 (SF_alt::more_temp_simps) |
592 |
563 addSIs2 [BoxOr]) ]); |
593 Goal "|- SF(A)_v --> []SF(A)_v"; |
564 |
594 by (auto_tac (temp_css addsimps2 (SF_alt::more_temp_simps) |
565 qed_goal "SF_Box" TLA.thy "|- ([]SF(A)_v) = SF(A)_v" |
595 addSIs2 [BoxOr])); |
566 (fn prems => [ fast_tac (temp_cs addSIs [BoxSFI] addSDs [STL2]) 1 ]); |
596 qed "BoxSFI"; |
|
597 |
|
598 Goal "|- ([]SF(A)_v) = SF(A)_v"; |
|
599 by (fast_tac (temp_cs addSIs [BoxSFI] addSDs [STL2]) 1); |
|
600 qed "SF_Box"; |
567 |
601 |
568 val more_temp_simps = more_temp_simps @ (map temp_rewrite [WF_Box, SF_Box]); |
602 val more_temp_simps = more_temp_simps @ (map temp_rewrite [WF_Box, SF_Box]); |
569 |
603 |
570 qed_goalw "SFImplWF" TLA.thy [SF_def,WF_def] "|- SF(A)_v --> WF(A)_v" |
604 Goalw [SF_def,WF_def] "|- SF(A)_v --> WF(A)_v"; |
571 (fn _ => [ fast_tac (temp_cs addSDs [DBImplBD]) 1 ]); |
605 by (fast_tac (temp_cs addSDs [DBImplBD]) 1); |
|
606 qed "SFImplWF"; |
572 |
607 |
573 (* A tactic that "boxes" all fairness conditions. Apply more_temp_simps to "unbox". *) |
608 (* A tactic that "boxes" all fairness conditions. Apply more_temp_simps to "unbox". *) |
574 val box_fair_tac = SELECT_GOAL (REPEAT (dresolve_tac [BoxWFI,BoxSFI] 1)); |
609 val box_fair_tac = SELECT_GOAL (REPEAT (dresolve_tac [BoxWFI,BoxSFI] 1)); |
575 |
610 |
576 |
611 |
577 (* ------------------------------ leads-to ------------------------------ *) |
612 (* ------------------------------ leads-to ------------------------------ *) |
578 |
613 |
579 section "~>"; |
614 section "~>"; |
580 |
615 |
581 qed_goalw "leadsto_init" TLA.thy [leadsto_def] |
616 Goalw [leadsto_def] "|- (Init F) & (F ~> G) --> <>G"; |
582 "|- (Init F) & (F ~> G) --> <>G" |
617 by (auto_tac (temp_css addSDs2 [STL2])); |
583 (fn _ => [ auto_tac (temp_css addSDs2 [STL2]) ]); |
618 qed "leadsto_init"; |
584 |
619 |
585 (* |- F & (F ~> G) --> <>G *) |
620 (* |- F & (F ~> G) --> <>G *) |
586 bind_thm("leadsto_init_temp", |
621 bind_thm("leadsto_init_temp", |
587 rewrite_rule Init_simps (read_instantiate [("'a","behavior")] leadsto_init)); |
622 rewrite_rule Init_simps (read_instantiate [("'a","behavior")] leadsto_init)); |
588 |
623 |
589 qed_goalw "streett_leadsto" TLA.thy [leadsto_def] |
624 Goalw [leadsto_def] "|- ([]<>Init F --> []<>G) = (<>(F ~> G))"; |
590 "|- ([]<>Init F --> []<>G) = (<>(F ~> G))" (K [ |
625 by Auto_tac; |
591 Auto_tac, |
626 by (asm_full_simp_tac (simpset() addsimps more_temp_simps) 1); |
592 asm_full_simp_tac (simpset() addsimps more_temp_simps) 1, |
627 by (fast_tac (temp_cs addSEs [DmdImplE,STL4E]) 1); |
593 fast_tac (temp_cs addSEs [DmdImplE,STL4E]) 1, |
628 by (fast_tac (temp_cs addSIs [InitDmd] addSEs [STL4E]) 1); |
594 fast_tac (temp_cs addSIs [InitDmd] addSEs [STL4E]) 1, |
629 by (subgoal_tac "sigma |= []<><>G" 1); |
595 subgoal_tac "sigma |= []<><>G" 1, |
630 by (asm_full_simp_tac (simpset() addsimps more_temp_simps) 1); |
596 asm_full_simp_tac (simpset() addsimps more_temp_simps) 1, |
631 by (dtac (temp_use BoxDmdDmdBox) 1); |
597 dtac (temp_use BoxDmdDmdBox) 1, atac 1, |
632 by (atac 1); |
598 fast_tac (temp_cs addSEs [DmdImplE,STL4E]) 1 |
633 by (fast_tac (temp_cs addSEs [DmdImplE,STL4E]) 1); |
599 ]); |
634 qed "streett_leadsto"; |
600 |
635 |
601 qed_goal "leadsto_infinite" TLA.thy |
636 Goal "|- []<>F & (F ~> G) --> []<>G"; |
602 "|- []<>F & (F ~> G) --> []<>G" |
637 by (Clarsimp_tac 1); |
603 (fn _ => [Clarsimp_tac 1, |
638 by (etac ((temp_use InitDmd) RS |
604 etac ((temp_use InitDmd) RS |
639 ((temp_unlift streett_leadsto) RS iffD2 RS mp)) 1); |
605 ((temp_unlift streett_leadsto) RS iffD2 RS mp)) 1, |
640 by (asm_simp_tac (simpset() addsimps [dmdInitD]) 1); |
606 asm_simp_tac (simpset() addsimps [dmdInitD]) 1 |
641 qed "leadsto_infinite"; |
607 ]); |
|
608 |
642 |
609 (* In particular, strong fairness is a Streett condition. The following |
643 (* In particular, strong fairness is a Streett condition. The following |
610 rules are sometimes easier to use than WF2 or SF2 below. |
644 rules are sometimes easier to use than WF2 or SF2 below. |
611 *) |
645 *) |
612 qed_goalw "leadsto_SF" TLA.thy [SF_def] |
646 Goalw [SF_def] "|- (Enabled(<A>_v) ~> <A>_v) --> SF(A)_v"; |
613 "|- (Enabled(<A>_v) ~> <A>_v) --> SF(A)_v" |
647 by (clarsimp_tac (temp_css addSEs2 [leadsto_infinite]) 1); |
614 (K [clarsimp_tac (temp_css addSEs2 [leadsto_infinite]) 1]); |
648 qed "leadsto_SF"; |
615 |
649 |
616 qed_goal "leadsto_WF" TLA.thy |
650 Goal "|- (Enabled(<A>_v) ~> <A>_v) --> WF(A)_v"; |
617 "|- (Enabled(<A>_v) ~> <A>_v) --> WF(A)_v" |
651 by (clarsimp_tac (temp_css addSIs2 [SFImplWF, leadsto_SF]) 1); |
618 (K [ clarsimp_tac (temp_css addSIs2 [SFImplWF, leadsto_SF]) 1 ]); |
652 qed "leadsto_WF"; |
619 |
653 |
620 (* introduce an invariant into the proof of a leadsto assertion. |
654 (* introduce an invariant into the proof of a leadsto assertion. |
621 []I --> ((P ~> Q) = (P /\ I ~> Q)) |
655 []I --> ((P ~> Q) = (P /\ I ~> Q)) |
622 *) |
656 *) |
623 qed_goalw "INV_leadsto" TLA.thy [leadsto_def] |
657 Goalw [leadsto_def] "|- []I & (P & I ~> Q) --> (P ~> Q)"; |
624 "|- []I & (P & I ~> Q) --> (P ~> Q)" |
658 by (Clarsimp_tac 1); |
625 (fn _ => [Clarsimp_tac 1, |
659 by (etac STL4Edup 1); |
626 etac STL4Edup 1, atac 1, |
660 by (atac 1); |
627 auto_tac (temp_css addsimps2 Init_simps addSDs2 [STL2_gen]) |
661 by (auto_tac (temp_css addsimps2 Init_simps addSDs2 [STL2_gen])); |
628 ]); |
662 qed "INV_leadsto"; |
629 |
663 |
630 qed_goalw "leadsto_classical" TLA.thy [leadsto_def,dmd_def] |
664 Goalw [leadsto_def,dmd_def] |
631 "|- (Init F & []~G ~> G) --> (F ~> G)" |
665 "|- (Init F & []~G ~> G) --> (F ~> G)"; |
632 (fn _ => [force_tac (temp_css addsimps2 Init_simps addSEs2 [STL4E]) 1]); |
666 by (force_tac (temp_css addsimps2 Init_simps addSEs2 [STL4E]) 1); |
633 |
667 qed "leadsto_classical"; |
634 qed_goalw "leadsto_false" TLA.thy [leadsto_def] |
668 |
635 "|- (F ~> #False) = ([]~F)" |
669 Goalw [leadsto_def] "|- (F ~> #False) = ([]~F)"; |
636 (fn _ => [ simp_tac (simpset() addsimps [boxNotInitD]) 1 ]); |
670 by (simp_tac (simpset() addsimps [boxNotInitD]) 1); |
637 |
671 qed "leadsto_false"; |
638 qed_goalw "leadsto_exists" TLA.thy [leadsto_def] |
672 |
639 "|- ((? x. F x) ~> G) = (!x. (F x ~> G))" |
673 Goalw [leadsto_def] "|- ((EX x. F x) ~> G) = (ALL x. (F x ~> G))"; |
640 (K [auto_tac (temp_css addsimps2 allT::Init_simps addSEs2 [STL4E])]); |
674 by (auto_tac (temp_css addsimps2 allT::Init_simps addSEs2 [STL4E])); |
641 |
675 qed "leadsto_exists"; |
642 |
676 |
643 (* basic leadsto properties, cf. Unity *) |
677 (* basic leadsto properties, cf. Unity *) |
644 |
678 |
645 qed_goalw "ImplLeadsto_gen" TLA.thy [leadsto_def] |
679 Goalw [leadsto_def] "|- [](Init F --> Init G) --> (F ~> G)"; |
646 "|- [](Init F --> Init G) --> (F ~> G)" |
680 by (auto_tac (temp_css addSIs2 [InitDmd_gen] addSEs2 [STL4E_gen] |
647 (fn _ => [auto_tac (temp_css addSIs2 [InitDmd_gen] |
681 addsimps2 Init_simps)); |
648 addSEs2 [STL4E_gen] addsimps2 Init_simps) |
682 qed "ImplLeadsto_gen"; |
649 ]); |
|
650 |
683 |
651 bind_thm("ImplLeadsto", |
684 bind_thm("ImplLeadsto", |
652 rewrite_rule Init_simps |
685 rewrite_rule Init_simps |
653 (read_instantiate [("'a","behavior"), ("'b","behavior")] ImplLeadsto_gen)); |
686 (read_instantiate [("'a","behavior"), ("'b","behavior")] ImplLeadsto_gen)); |
654 |
687 |
655 qed_goal "ImplLeadsto_simple" TLA.thy |
688 Goal "!!F G. |- F --> G ==> |- F ~> G"; |
656 "|- F --> G ==> |- F ~> G" |
689 by (auto_tac (temp_css addsimps2 [Init_def] |
657 (fn [prem] => [auto_tac (temp_css addsimps2 [Init_def] |
690 addSIs2 [ImplLeadsto_gen,necT])); |
658 addSIs2 [ImplLeadsto_gen,necT,prem])]); |
691 qed "ImplLeadsto_simple"; |
659 |
692 |
660 qed_goalw "EnsuresLeadsto" TLA.thy [leadsto_def] |
693 val [prem] = goalw thy [leadsto_def] |
661 "|- A & $P --> Q` ==> |- []A --> (P ~> Q)" (fn [prem] => [ |
694 "|- A & $P --> Q` ==> |- []A --> (P ~> Q)"; |
662 clarsimp_tac (temp_css addSEs2 [INV_leadsto]) 1, |
695 by (clarsimp_tac (temp_css addSEs2 [INV_leadsto]) 1); |
663 etac STL4E_gen 1, |
696 by (etac STL4E_gen 1); |
664 auto_tac (temp_css addsimps2 Init_defs |
697 by (auto_tac (temp_css addsimps2 Init_defs addSIs2 [PrimeDmd,prem])); |
665 addSIs2 [PrimeDmd, prem]) |
698 qed "EnsuresLeadsto"; |
666 ]); |
699 |
667 |
700 Goalw [leadsto_def] "|- []($P --> Q`) --> (P ~> Q)"; |
668 qed_goalw "EnsuresLeadsto2" TLA.thy [leadsto_def] |
701 by (Clarsimp_tac 1); |
669 "|- []($P --> Q`) --> (P ~> Q)" |
702 by (etac STL4E_gen 1); |
670 (fn _ => [Clarsimp_tac 1, |
703 by (auto_tac (temp_css addsimps2 Init_simps addSIs2 [PrimeDmd])); |
671 etac STL4E_gen 1, |
704 qed "EnsuresLeadsto2"; |
672 auto_tac (temp_css addsimps2 Init_simps addSIs2 [PrimeDmd]) |
705 |
673 ]); |
706 val [p1,p2] = goalw thy [leadsto_def] |
674 |
|
675 qed_goalw "ensures" TLA.thy [leadsto_def] |
|
676 "[| |- $P & N --> P` | Q`; \ |
707 "[| |- $P & N --> P` | Q`; \ |
677 \ |- ($P & N) & A --> Q` \ |
708 \ |- ($P & N) & A --> Q` \ |
678 \ |] ==> |- []N & []([]P --> <>A) --> (P ~> Q)" |
709 \ |] ==> |- []N & []([]P --> <>A) --> (P ~> Q)"; |
679 (fn [p1,p2] => [Clarsimp_tac 1, |
710 by (Clarsimp_tac 1); |
680 etac STL4Edup 1, atac 1, |
711 by (etac STL4Edup 1); |
681 Clarsimp_tac 1, |
712 by (atac 1); |
682 subgoal_tac "sigmaa |= []($P --> P` | Q`)" 1, |
713 by (Clarsimp_tac 1); |
683 dtac (temp_use unless) 1, |
714 by (subgoal_tac "sigmaa |= []($P --> P` | Q`)" 1); |
684 clarsimp_tac (temp_css addSDs2 [INV1]) 1, |
715 by (dtac (temp_use unless) 1); |
685 rtac ((temp_use (p2 RS DmdImpl)) RS (temp_use DmdPrime)) 1, |
716 by (clarsimp_tac (temp_css addSDs2 [INV1]) 1); |
686 force_tac (temp_css addSIs2 [BoxDmd_simple] |
717 by (rtac ((temp_use (p2 RS DmdImpl)) RS (temp_use DmdPrime)) 1); |
687 addsimps2 [split_box_conj,box_stp_act]) 1, |
718 by (force_tac (temp_css addSIs2 [BoxDmd_simple] |
688 force_tac (temp_css addEs2 [STL4E] addDs2 [p1]) 1 |
719 addsimps2 [split_box_conj,box_stp_act]) 1); |
689 ]); |
720 by (force_tac (temp_css addEs2 [STL4E] addDs2 [p1]) 1); |
690 |
721 qed "ensures"; |
691 qed_goal "ensures_simple" TLA.thy |
722 |
|
723 val prems = goal thy |
692 "[| |- $P & N --> P` | Q`; \ |
724 "[| |- $P & N --> P` | Q`; \ |
693 \ |- ($P & N) & A --> Q` \ |
725 \ |- ($P & N) & A --> Q` \ |
694 \ |] ==> |- []N & []<>A --> (P ~> Q)" |
726 \ |] ==> |- []N & []<>A --> (P ~> Q)"; |
695 (fn prems => [Clarsimp_tac 1, |
727 by (Clarsimp_tac 1); |
696 rtac (temp_use ensures) 1, |
728 by (rtac (temp_use ensures) 1); |
697 TRYALL (ares_tac prems), |
729 by (TRYALL (ares_tac prems)); |
698 force_tac (temp_css addSEs2 [STL4E]) 1 |
730 by (force_tac (temp_css addSEs2 [STL4E]) 1); |
699 ]); |
731 qed "ensures_simple"; |
700 |
732 |
701 qed_goal "EnsuresInfinite" TLA.thy |
733 val prems = goal thy |
702 "[| sigma |= []<>P; sigma |= []A; |- A & $P --> Q` |] ==> sigma |= []<>Q" |
734 "[| sigma |= []<>P; sigma |= []A; |- A & $P --> Q` |] ==> sigma |= []<>Q"; |
703 (fn prems => [REPEAT (resolve_tac (prems @ [temp_use leadsto_infinite, |
735 by (REPEAT (resolve_tac (prems @ |
704 temp_use EnsuresLeadsto]) 1)]); |
736 (map temp_use [leadsto_infinite, EnsuresLeadsto])) 1)); |
|
737 qed "EnsuresInfinite"; |
705 |
738 |
706 |
739 |
707 (*** Gronning's lattice rules (taken from TLP) ***) |
740 (*** Gronning's lattice rules (taken from TLP) ***) |
708 section "Lattice rules"; |
741 section "Lattice rules"; |
709 |
742 |
710 qed_goalw "LatticeReflexivity" TLA.thy [leadsto_def] "|- F ~> F" |
743 Goalw [leadsto_def] "|- F ~> F"; |
711 (fn _ => [REPEAT (resolve_tac [necT,InitDmd_gen] 1)]); |
744 by (REPEAT (resolve_tac [necT,InitDmd_gen] 1)); |
712 |
745 qed "LatticeReflexivity"; |
713 qed_goalw "LatticeTransitivity" TLA.thy [leadsto_def] |
746 |
714 "|- (G ~> H) & (F ~> G) --> (F ~> H)" |
747 Goalw [leadsto_def] "|- (G ~> H) & (F ~> G) --> (F ~> H)"; |
715 (fn _ => [Clarsimp_tac 1, |
748 by (Clarsimp_tac 1); |
716 etac dup_boxE 1, (* [][](Init G --> H) *) |
749 by (etac dup_boxE 1); (* [][](Init G --> H) *) |
717 merge_box_tac 1, |
750 by (merge_box_tac 1); |
718 clarsimp_tac (temp_css addSEs2 [STL4E]) 1, |
751 by (clarsimp_tac (temp_css addSEs2 [STL4E]) 1); |
719 rtac dup_dmdD 1, |
752 by (rtac dup_dmdD 1); |
720 subgoal_tac "sigmaa |= <>Init G" 1, |
753 by (subgoal_tac "sigmaa |= <>Init G" 1); |
721 etac DmdImpl2 1, atac 1, |
754 by (etac DmdImpl2 1); |
722 asm_simp_tac (simpset() addsimps [dmdInitD]) 1 |
755 by (atac 1); |
723 ]); |
756 by (asm_simp_tac (simpset() addsimps [dmdInitD]) 1); |
724 |
757 qed "LatticeTransitivity"; |
725 qed_goalw "LatticeDisjunctionElim1" TLA.thy [leadsto_def] |
758 |
726 "|- (F | G ~> H) --> (F ~> H)" |
759 Goalw [leadsto_def] "|- (F | G ~> H) --> (F ~> H)"; |
727 (fn _ => [ auto_tac (temp_css addsimps2 Init_simps addSEs2 [STL4E]) ]); |
760 by (auto_tac (temp_css addsimps2 Init_simps addSEs2 [STL4E])); |
728 |
761 qed "LatticeDisjunctionElim1"; |
729 qed_goalw "LatticeDisjunctionElim2" TLA.thy [leadsto_def] |
762 |
730 "|- (F | G ~> H) --> (G ~> H)" |
763 Goalw [leadsto_def] "|- (F | G ~> H) --> (G ~> H)"; |
731 (fn _ => [ auto_tac (temp_css addsimps2 Init_simps addSEs2 [STL4E]) ]); |
764 by (auto_tac (temp_css addsimps2 Init_simps addSEs2 [STL4E])); |
732 |
765 qed "LatticeDisjunctionElim2"; |
733 qed_goalw "LatticeDisjunctionIntro" TLA.thy [leadsto_def] |
766 |
734 "|- (F ~> H) & (G ~> H) --> (F | G ~> H)" |
767 Goalw [leadsto_def] "|- (F ~> H) & (G ~> H) --> (F | G ~> H)"; |
735 (fn _ => [Clarsimp_tac 1, |
768 by (Clarsimp_tac 1); |
736 merge_box_tac 1, |
769 by (merge_box_tac 1); |
737 auto_tac (temp_css addsimps2 Init_simps addSEs2 [STL4E]) |
770 by (auto_tac (temp_css addsimps2 Init_simps addSEs2 [STL4E])); |
738 ]); |
771 qed "LatticeDisjunctionIntro"; |
739 |
772 |
740 qed_goal "LatticeDisjunction" TLA.thy |
773 Goal "|- (F | G ~> H) = ((F ~> H) & (G ~> H))"; |
741 "|- (F | G ~> H) = ((F ~> H) & (G ~> H))" |
774 by (auto_tac (temp_css addIs2 [LatticeDisjunctionIntro, |
742 (fn _ => [auto_tac (temp_css addIs2 [LatticeDisjunctionIntro, |
775 LatticeDisjunctionElim1, LatticeDisjunctionElim2])); |
743 LatticeDisjunctionElim1, LatticeDisjunctionElim2])]); |
776 qed "LatticeDisjunction"; |
744 |
777 |
745 qed_goal "LatticeDiamond" TLA.thy |
778 Goal "|- (A ~> B | C) & (B ~> D) & (C ~> D) --> (A ~> D)"; |
746 "|- (A ~> B | C) & (B ~> D) & (C ~> D) --> (A ~> D)" |
779 by (Clarsimp_tac 1); |
747 (fn _ => [Clarsimp_tac 1, |
780 by (subgoal_tac "sigma |= (B | C) ~> D" 1); |
748 subgoal_tac "sigma |= (B | C) ~> D" 1, |
781 by (eres_inst_tac [("G", "LIFT (B | C)")] (temp_use LatticeTransitivity) 1); |
749 eres_inst_tac [("G", "LIFT (B | C)")] (temp_use LatticeTransitivity) 1, |
782 by (ALLGOALS (fast_tac (temp_cs addSIs [LatticeDisjunctionIntro]))); |
750 ALLGOALS (fast_tac (temp_cs addSIs [LatticeDisjunctionIntro])) |
783 qed "LatticeDiamond"; |
751 ]); |
784 |
752 |
785 Goal "|- (A ~> D | B) & (B ~> D) --> (A ~> D)"; |
753 qed_goal "LatticeTriangle" TLA.thy |
786 by (Clarsimp_tac 1); |
754 "|- (A ~> D | B) & (B ~> D) --> (A ~> D)" |
787 by (subgoal_tac "sigma |= (D | B) ~> D" 1); |
755 (fn _ => [Clarsimp_tac 1, |
788 by (eres_inst_tac [("G", "LIFT (D | B)")] (temp_use LatticeTransitivity) 1); |
756 subgoal_tac "sigma |= (D | B) ~> D" 1, |
789 by (atac 1); |
757 eres_inst_tac [("G", "LIFT (D | B)")] (temp_use LatticeTransitivity) 1, atac 1, |
790 by (auto_tac (temp_css addIs2 [LatticeDisjunctionIntro,LatticeReflexivity])); |
758 auto_tac (temp_css addSIs2 [LatticeDisjunctionIntro] |
791 qed "LatticeTriangle"; |
759 addIs2 [LatticeReflexivity]) |
792 |
760 ]); |
793 Goal "|- (A ~> B | D) & (B ~> D) --> (A ~> D)"; |
761 |
794 by (Clarsimp_tac 1); |
762 qed_goal "LatticeTriangle2" TLA.thy |
795 by (subgoal_tac "sigma |= B | D ~> D" 1); |
763 "|- (A ~> B | D) & (B ~> D) --> (A ~> D)" |
796 by (eres_inst_tac [("G", "LIFT (B | D)")] (temp_use LatticeTransitivity) 1); |
764 (fn _ => [Clarsimp_tac 1, |
797 by (atac 1); |
765 subgoal_tac "sigma |= B | D ~> D" 1, |
798 by (auto_tac (temp_css addIs2 [LatticeDisjunctionIntro,LatticeReflexivity])); |
766 eres_inst_tac [("G", "LIFT (B | D)")] (temp_use LatticeTransitivity) 1, atac 1, |
799 qed "LatticeTriangle2"; |
767 auto_tac (temp_css addSIs2 [LatticeDisjunctionIntro] |
|
768 addIs2 [LatticeReflexivity]) |
|
769 ]); |
|
770 |
800 |
771 (*** Lamport's fairness rules ***) |
801 (*** Lamport's fairness rules ***) |
772 section "Fairness rules"; |
802 section "Fairness rules"; |
773 |
803 |
774 qed_goal "WF1" TLA.thy |
804 val prems = goal thy |
775 "[| |- $P & N --> P` | Q`; \ |
805 "[| |- $P & N --> P` | Q`; \ |
776 \ |- ($P & N) & <A>_v --> Q`; \ |
806 \ |- ($P & N) & <A>_v --> Q`; \ |
777 \ |- $P & N --> $(Enabled(<A>_v)) |] \ |
807 \ |- $P & N --> $(Enabled(<A>_v)) |] \ |
778 \ ==> |- []N & WF(A)_v --> (P ~> Q)" (fn prems => [ |
808 \ ==> |- []N & WF(A)_v --> (P ~> Q)"; |
779 clarsimp_tac (temp_css addSDs2 [BoxWFI]) 1, |
809 by (clarsimp_tac (temp_css addSDs2 [BoxWFI]) 1); |
780 rtac (temp_use ensures) 1, |
810 by (rtac (temp_use ensures) 1); |
781 TRYALL (ares_tac prems), |
811 by (TRYALL (ares_tac prems)); |
782 etac STL4Edup 1, atac 1, |
812 by (etac STL4Edup 1); |
783 clarsimp_tac (temp_css addsimps2 [WF_def]) 1, |
813 by (atac 1); |
784 rtac (temp_use STL2) 1, |
814 by (clarsimp_tac (temp_css addsimps2 [WF_def]) 1); |
785 clarsimp_tac (temp_css addSEs2 [mp] addSIs2 [InitDmd]) 1, |
815 by (rtac (temp_use STL2) 1); |
786 resolve_tac ((map temp_use (prems RL [STL4])) RL [box_stp_actD]) 1, |
816 by (clarsimp_tac (temp_css addSEs2 [mp] addSIs2 [InitDmd]) 1); |
787 asm_simp_tac (simpset() addsimps [split_box_conj,box_stp_actI]) 1 |
817 by (resolve_tac ((map temp_use (prems RL [STL4])) RL [box_stp_actD]) 1); |
788 ]); |
818 by (asm_simp_tac (simpset() addsimps [split_box_conj,box_stp_actI]) 1); |
|
819 qed "WF1"; |
789 |
820 |
790 (* Sometimes easier to use; designed for action B rather than state predicate Q *) |
821 (* Sometimes easier to use; designed for action B rather than state predicate Q *) |
791 qed_goalw "WF_leadsto" TLA.thy [leadsto_def] |
822 val [prem1,prem2,prem3] = goalw thy [leadsto_def] |
792 "[| |- N & $P --> $Enabled (<A>_v); \ |
823 "[| |- N & $P --> $Enabled (<A>_v); \ |
793 \ |- N & <A>_v --> B; \ |
824 \ |- N & <A>_v --> B; \ |
794 \ |- [](N & [~A]_v) --> stable P |] \ |
825 \ |- [](N & [~A]_v) --> stable P |] \ |
795 \ ==> |- []N & WF(A)_v --> (P ~> B)" |
826 \ ==> |- []N & WF(A)_v --> (P ~> B)"; |
796 (fn [prem1,prem2,prem3] |
827 by (clarsimp_tac (temp_css addSDs2 [BoxWFI]) 1); |
797 => [clarsimp_tac (temp_css addSDs2 [BoxWFI]) 1, |
828 by (etac STL4Edup 1); |
798 etac STL4Edup 1, atac 1, |
829 by (atac 1); |
799 Clarsimp_tac 1, |
830 by (Clarsimp_tac 1); |
800 rtac (temp_use (prem2 RS DmdImpl)) 1, |
831 by (rtac (temp_use (prem2 RS DmdImpl)) 1); |
801 rtac (temp_use BoxDmd_simple) 1, atac 1, |
832 by (rtac (temp_use BoxDmd_simple) 1); |
802 rtac classical 1, |
833 by (atac 1); |
803 rtac (temp_use STL2) 1, |
834 by (rtac classical 1); |
804 clarsimp_tac (temp_css addsimps2 [WF_def] addSEs2 [mp] addSIs2 [InitDmd]) 1, |
835 by (rtac (temp_use STL2) 1); |
805 rtac ((temp_use (prem1 RS STL4)) RS box_stp_actD) 1, |
836 by (clarsimp_tac (temp_css addsimps2 [WF_def] addSEs2 [mp] addSIs2 [InitDmd]) 1); |
806 asm_simp_tac (simpset() addsimps [split_box_conj,box_stp_act]) 1, |
837 by (rtac ((temp_use (prem1 RS STL4)) RS box_stp_actD) 1); |
807 etac (temp_use INV1) 1, |
838 by (asm_simp_tac (simpset() addsimps [split_box_conj,box_stp_act]) 1); |
808 rtac (temp_use prem3) 1, |
839 by (etac (temp_use INV1) 1); |
809 asm_full_simp_tac (simpset() addsimps [split_box_conj,temp_use NotDmd,not_angle]) 1 |
840 by (rtac (temp_use prem3) 1); |
810 ]); |
841 by (asm_full_simp_tac (simpset() addsimps [split_box_conj,temp_use NotDmd,not_angle]) 1); |
811 |
842 qed "WF_leadsto"; |
812 qed_goal "SF1" TLA.thy |
843 |
813 "[| |- $P & N --> P` | Q`; \ |
844 val prems = goal thy |
814 \ |- ($P & N) & <A>_v --> Q`; \ |
845 "[| |- $P & N --> P` | Q`; \ |
815 \ |- []P & []N & []F --> <>Enabled(<A>_v) |] \ |
846 \ |- ($P & N) & <A>_v --> Q`; \ |
816 \ ==> |- []N & SF(A)_v & []F --> (P ~> Q)" |
847 \ |- []P & []N & []F --> <>Enabled(<A>_v) |] \ |
817 (fn prems => [ |
848 \ ==> |- []N & SF(A)_v & []F --> (P ~> Q)"; |
818 clarsimp_tac (temp_css addSDs2 [BoxSFI]) 1, |
849 by (clarsimp_tac (temp_css addSDs2 [BoxSFI]) 1); |
819 rtac (temp_use ensures) 1, |
850 by (rtac (temp_use ensures) 1); |
820 TRYALL (ares_tac prems), |
851 by (TRYALL (ares_tac prems)); |
821 eres_inst_tac [("F","F")] dup_boxE 1, |
852 by (eres_inst_tac [("F","F")] dup_boxE 1); |
822 merge_temp_box_tac 1, |
853 by (merge_temp_box_tac 1); |
823 etac STL4Edup 1, atac 1, |
854 by (etac STL4Edup 1); |
824 clarsimp_tac (temp_css addsimps2 [SF_def]) 1, |
855 by (atac 1); |
825 rtac (temp_use STL2) 1, etac mp 1, |
856 by (clarsimp_tac (temp_css addsimps2 [SF_def]) 1); |
826 resolve_tac (map temp_use (prems RL [STL4])) 1, |
857 by (rtac (temp_use STL2) 1); |
827 asm_simp_tac (simpset() addsimps [split_box_conj, STL3]) 1 |
858 by (etac mp 1); |
828 ]); |
859 by (resolve_tac (map temp_use (prems RL [STL4])) 1); |
829 |
860 by (asm_simp_tac (simpset() addsimps [split_box_conj, STL3]) 1); |
830 qed_goal "WF2" TLA.thy |
861 qed "SF1"; |
831 "[| |- N & <B>_f --> <M>_g; \ |
862 |
832 \ |- $P & P` & <N & A>_f --> B; \ |
863 val [prem1,prem2,prem3,prem4] = goal thy |
833 \ |- P & Enabled(<M>_g) --> Enabled(<A>_f); \ |
864 "[| |- N & <B>_f --> <M>_g; \ |
834 \ |- [](N & [~B]_f) & WF(A)_f & []F & <>[]Enabled(<M>_g) --> <>[]P |] \ |
865 \ |- $P & P` & <N & A>_f --> B; \ |
835 \ ==> |- []N & WF(A)_f & []F --> WF(M)_g" |
866 \ |- P & Enabled(<M>_g) --> Enabled(<A>_f); \ |
836 (fn [prem1,prem2,prem3,prem4] => [ |
867 \ |- [](N & [~B]_f) & WF(A)_f & []F & <>[]Enabled(<M>_g) --> <>[]P |] \ |
837 clarsimp_tac (temp_css addSDs2 [BoxWFI, (temp_use BoxDmdBox) RS iffD2] |
868 \ ==> |- []N & WF(A)_f & []F --> WF(M)_g"; |
838 addsimps2 [read_instantiate [("A","M")] WF_def]) 1, |
869 by (clarsimp_tac (temp_css addSDs2 [BoxWFI, (temp_use BoxDmdBox) RS iffD2] |
839 eres_inst_tac [("F","F")] dup_boxE 1, |
870 addsimps2 [read_instantiate [("A","M")] WF_def]) 1); |
840 merge_temp_box_tac 1, |
871 by (eres_inst_tac [("F","F")] dup_boxE 1); |
841 etac STL4Edup 1, atac 1, |
872 by (merge_temp_box_tac 1); |
842 clarsimp_tac (temp_css addSIs2 [(temp_use BoxDmd_simple) RS (temp_use (prem1 RS DmdImpl))]) 1, |
873 by (etac STL4Edup 1); |
843 rtac classical 1, |
874 by (atac 1); |
844 subgoal_tac "sigmaa |= <>(($P & P` & N) & <A>_f)" 1, |
875 by (clarsimp_tac (temp_css addSIs2 |
845 force_tac (temp_css addsimps2 [angle_def] addSIs2 [prem2] addSEs2 [DmdImplE]) 1, |
876 [(temp_use BoxDmd_simple) RS (temp_use (prem1 RS DmdImpl))]) 1); |
846 rtac (temp_use (rewrite_rule [temp_rewrite DmdDmd] (BoxDmd_simple RS DmdImpl))) 1, |
877 by (rtac classical 1); |
847 asm_full_simp_tac (simpset() addsimps [temp_use NotDmd, not_angle]) 1, |
878 by (subgoal_tac "sigmaa |= <>(($P & P` & N) & <A>_f)" 1); |
848 merge_act_box_tac 1, |
879 by (force_tac (temp_css addsimps2 [angle_def] addSIs2 [prem2] addSEs2 [DmdImplE]) 1); |
849 forward_tac [temp_use prem4] 1, TRYALL atac, |
880 by (rtac (temp_use (rewrite_rule [temp_rewrite DmdDmd] (BoxDmd_simple RS DmdImpl))) 1); |
850 dtac (temp_use STL6) 1, atac 1, |
881 by (asm_full_simp_tac (simpset() addsimps [temp_use NotDmd, not_angle]) 1); |
851 eres_inst_tac [("V","sigmaa |= <>[]P")] thin_rl 1, |
882 by (merge_act_box_tac 1); |
852 eres_inst_tac [("V","sigmaa |= []F")] thin_rl 1, |
883 by (forward_tac [temp_use prem4] 1); |
853 dtac (temp_use BoxWFI) 1, |
884 by (TRYALL atac); |
854 eres_inst_tac [("F", "ACT N & [~B]_f")] dup_boxE 1, |
885 by (dtac (temp_use STL6) 1); |
855 merge_temp_box_tac 1, |
886 by (atac 1); |
856 etac DmdImpldup 1, atac 1, |
887 by (eres_inst_tac [("V","sigmaa |= <>[]P")] thin_rl 1); |
857 auto_tac (temp_css addsimps2 [split_box_conj,STL3,WF_Box,box_stp_act]), |
888 by (eres_inst_tac [("V","sigmaa |= []F")] thin_rl 1); |
858 force_tac (temp_css addSEs2 [read_instantiate [("P","P")] TLA2E]) 1, |
889 by (dtac (temp_use BoxWFI) 1); |
859 rtac (temp_use STL2) 1, |
890 by (eres_inst_tac [("F", "ACT N & [~B]_f")] dup_boxE 1); |
860 force_tac (temp_css addsimps2 [WF_def,split_box_conj] addSEs2 [mp] |
891 by (merge_temp_box_tac 1); |
861 addSIs2 [InitDmd, prem3 RS STL4]) 1 |
892 by (etac DmdImpldup 1); |
862 ]); |
893 by (atac 1); |
863 |
894 by (auto_tac (temp_css addsimps2 [split_box_conj,STL3,WF_Box,box_stp_act])); |
864 qed_goal "SF2" TLA.thy |
895 by (force_tac (temp_css addSEs2 [read_instantiate [("P","P")] TLA2E]) 1); |
865 "[| |- N & <B>_f --> <M>_g; \ |
896 by (rtac (temp_use STL2) 1); |
866 \ |- $P & P` & <N & A>_f --> B; \ |
897 by (force_tac (temp_css addsimps2 [WF_def,split_box_conj] addSEs2 [mp] |
867 \ |- P & Enabled(<M>_g) --> Enabled(<A>_f); \ |
898 addSIs2 [InitDmd, prem3 RS STL4]) 1); |
868 \ |- [](N & [~B]_f) & SF(A)_f & []F & []<>Enabled(<M>_g) --> <>[]P |] \ |
899 qed "WF2"; |
869 \ ==> |- []N & SF(A)_f & []F --> SF(M)_g" |
900 |
870 (fn [prem1,prem2,prem3,prem4] => [ |
901 val [prem1,prem2,prem3,prem4] = goal thy |
871 clarsimp_tac (temp_css addSDs2 [BoxSFI] |
902 "[| |- N & <B>_f --> <M>_g; \ |
872 addsimps2 [read_instantiate [("A","M")] SF_def]) 1, |
903 \ |- $P & P` & <N & A>_f --> B; \ |
873 eres_inst_tac [("F","F")] dup_boxE 1, |
904 \ |- P & Enabled(<M>_g) --> Enabled(<A>_f); \ |
874 eres_inst_tac [("F","TEMP <>Enabled(<M>_g)")] dup_boxE 1, |
905 \ |- [](N & [~B]_f) & SF(A)_f & []F & []<>Enabled(<M>_g) --> <>[]P |] \ |
875 merge_temp_box_tac 1, |
906 \ ==> |- []N & SF(A)_f & []F --> SF(M)_g"; |
876 etac STL4Edup 1, atac 1, |
907 by (clarsimp_tac (temp_css addSDs2 [BoxSFI] |
877 clarsimp_tac (temp_css addSIs2 [(temp_use BoxDmd_simple) RS (temp_use (prem1 RS DmdImpl))]) 1, |
908 addsimps2 [read_instantiate [("A","M")] SF_def]) 1); |
878 rtac classical 1, |
909 by (eres_inst_tac [("F","F")] dup_boxE 1); |
879 subgoal_tac "sigmaa |= <>(($P & P` & N) & <A>_f)" 1, |
910 by (eres_inst_tac [("F","TEMP <>Enabled(<M>_g)")] dup_boxE 1); |
880 force_tac (temp_css addsimps2 [angle_def] addSIs2 [prem2] addSEs2 [DmdImplE]) 1, |
911 by (merge_temp_box_tac 1); |
881 rtac (temp_use (rewrite_rule [temp_rewrite DmdDmd] (BoxDmd_simple RS DmdImpl))) 1, |
912 by (etac STL4Edup 1); |
882 asm_full_simp_tac (simpset() addsimps [temp_use NotDmd, not_angle]) 1, |
913 by (atac 1); |
883 merge_act_box_tac 1, |
914 by (clarsimp_tac (temp_css addSIs2 |
884 forward_tac [temp_use prem4] 1, TRYALL atac, |
915 [(temp_use BoxDmd_simple) RS (temp_use (prem1 RS DmdImpl))]) 1); |
885 eres_inst_tac [("V","sigmaa |= []F")] thin_rl 1, |
916 by (rtac classical 1); |
886 dtac (temp_use BoxSFI) 1, |
917 by (subgoal_tac "sigmaa |= <>(($P & P` & N) & <A>_f)" 1); |
887 eres_inst_tac [("F","TEMP <>Enabled(<M>_g)")] dup_boxE 1, |
918 by (force_tac (temp_css addsimps2 [angle_def] addSIs2 [prem2] addSEs2 [DmdImplE]) 1); |
888 eres_inst_tac [("F", "ACT N & [~B]_f")] dup_boxE 1, |
919 by (rtac (temp_use (rewrite_rule [temp_rewrite DmdDmd] (BoxDmd_simple RS DmdImpl))) 1); |
889 merge_temp_box_tac 1, |
920 by (asm_full_simp_tac (simpset() addsimps [temp_use NotDmd, not_angle]) 1); |
890 etac DmdImpldup 1, atac 1, |
921 by (merge_act_box_tac 1); |
891 auto_tac (temp_css addsimps2 [split_box_conj,STL3,SF_Box,box_stp_act]), |
922 by (forward_tac [temp_use prem4] 1); |
892 force_tac (temp_css addSEs2 [read_instantiate [("P","P")] TLA2E]) 1, |
923 by (TRYALL atac); |
893 rtac (temp_use STL2) 1, |
924 by (eres_inst_tac [("V","sigmaa |= []F")] thin_rl 1); |
894 force_tac (temp_css addsimps2 [SF_def,split_box_conj] addSEs2 [mp,InfImpl] |
925 by (dtac (temp_use BoxSFI) 1); |
895 addSIs2 [prem3]) 1 |
926 by (eres_inst_tac [("F","TEMP <>Enabled(<M>_g)")] dup_boxE 1); |
896 ]); |
927 by (eres_inst_tac [("F", "ACT N & [~B]_f")] dup_boxE 1); |
|
928 by (merge_temp_box_tac 1); |
|
929 by (etac DmdImpldup 1); |
|
930 by (atac 1); |
|
931 by (auto_tac (temp_css addsimps2 [split_box_conj,STL3,SF_Box,box_stp_act])); |
|
932 by (force_tac (temp_css addSEs2 [read_instantiate [("P","P")] TLA2E]) 1); |
|
933 by (rtac (temp_use STL2) 1); |
|
934 by (force_tac (temp_css addsimps2 [SF_def,split_box_conj] addSEs2 [mp,InfImpl] |
|
935 addSIs2 [prem3]) 1); |
|
936 qed "SF2"; |
897 |
937 |
898 (* ------------------------------------------------------------------------- *) |
938 (* ------------------------------------------------------------------------- *) |
899 (*** Liveness proofs by well-founded orderings ***) |
939 (*** Liveness proofs by well-founded orderings ***) |
900 (* ------------------------------------------------------------------------- *) |
940 (* ------------------------------------------------------------------------- *) |
901 section "Well-founded orderings"; |
941 section "Well-founded orderings"; |
902 |
942 |
903 qed_goal "wf_leadsto" TLA.thy |
943 val p1::prems = goal thy |
904 "[| wf r; \ |
944 "[| wf r; \ |
905 \ !!x. sigma |= F x ~> (G | (? y. #((y,x):r) & F y)) \ |
945 \ !!x. sigma |= F x ~> (G | (EX y. #((y,x):r) & F y)) \ |
906 \ |] ==> sigma |= F x ~> G" |
946 \ |] ==> sigma |= F x ~> G"; |
907 (fn p1::prems => |
947 by (rtac (p1 RS wf_induct) 1); |
908 [rtac (p1 RS wf_induct) 1, |
948 by (rtac (temp_use LatticeTriangle) 1); |
909 rtac (temp_use LatticeTriangle) 1, |
949 by (resolve_tac prems 1); |
910 resolve_tac prems 1, |
950 by (auto_tac (temp_css addsimps2 [leadsto_exists])); |
911 auto_tac (temp_css addsimps2 [leadsto_exists]), |
951 by (case_tac "(y,x):r" 1); |
912 case_tac "(y,x):r" 1, |
952 by (Force_tac 1); |
913 Force_tac 1, |
953 by (force_tac (temp_css addsimps2 leadsto_def::Init_simps addSIs2 [necT]) 1); |
914 force_tac (temp_css addsimps2 leadsto_def::Init_simps addSIs2 [necT]) 1]); |
954 qed "wf_leadsto"; |
915 |
955 |
916 (* If r is well-founded, state function v cannot decrease forever *) |
956 (* If r is well-founded, state function v cannot decrease forever *) |
917 qed_goal "wf_not_box_decrease" TLA.thy |
957 Goal "!!r. wf r ==> |- [][ (v`, $v) : #r ]_v --> <>[][#False]_v"; |
918 "!!r. wf r ==> |- [][ (v`, $v) : #r ]_v --> <>[][#False]_v" |
958 by (Clarsimp_tac 1); |
919 (fn _ => [Clarsimp_tac 1, |
959 by (rtac ccontr 1); |
920 rtac ccontr 1, |
960 by (subgoal_tac "sigma |= (EX x. v=#x) ~> #False" 1); |
921 subgoal_tac "sigma |= (? x. v=#x) ~> #False" 1, |
961 by (dtac ((temp_use leadsto_false) RS iffD1 RS (temp_use STL2_gen)) 1); |
922 dtac ((temp_use leadsto_false) RS iffD1 RS (temp_use STL2_gen)) 1, |
962 by (force_tac (temp_css addsimps2 Init_defs) 1); |
923 force_tac (temp_css addsimps2 Init_defs) 1, |
963 by (clarsimp_tac (temp_css addsimps2 [leadsto_exists,not_square]@more_temp_simps) 1); |
924 clarsimp_tac (temp_css addsimps2 [leadsto_exists,not_square]@more_temp_simps) 1, |
964 by (etac wf_leadsto 1); |
925 etac wf_leadsto 1, |
965 by (rtac (temp_use ensures_simple) 1); |
926 rtac (temp_use ensures_simple) 1, TRYALL atac, |
966 by (TRYALL atac); |
927 auto_tac (temp_css addsimps2 [square_def,angle_def]) |
967 by (auto_tac (temp_css addsimps2 [square_def,angle_def])); |
928 ]); |
968 qed "wf_not_box_decrease"; |
929 |
969 |
930 (* "wf r ==> |- <>[][ (v`, $v) : #r ]_v --> <>[][#False]_v" *) |
970 (* "wf r ==> |- <>[][ (v`, $v) : #r ]_v --> <>[][#False]_v" *) |
931 bind_thm("wf_not_dmd_box_decrease", |
971 bind_thm("wf_not_dmd_box_decrease", |
932 standard(rewrite_rule more_temp_simps (wf_not_box_decrease RS DmdImpl))); |
972 standard(rewrite_rule more_temp_simps (wf_not_box_decrease RS DmdImpl))); |
933 |
973 |
934 (* If there are infinitely many steps where v decreases, then there |
974 (* If there are infinitely many steps where v decreases, then there |
935 have to be infinitely many non-stuttering steps where v doesn't decrease. |
975 have to be infinitely many non-stuttering steps where v doesn't decrease. |
936 *) |
976 *) |
937 qed_goal "wf_box_dmd_decrease" TLA.thy |
977 val [prem] = goal thy |
938 "wf r ==> |- []<>((v`, $v) : #r) --> []<><(v`, $v) ~: #r>_v" |
978 "wf r ==> |- []<>((v`, $v) : #r) --> []<><(v`, $v) ~: #r>_v"; |
939 (fn [prem] => [ |
979 by (Clarsimp_tac 1); |
940 Clarsimp_tac 1, |
980 by (rtac ccontr 1); |
941 rtac ccontr 1, |
981 by (asm_full_simp_tac (simpset() addsimps not_angle::more_temp_simps) 1); |
942 asm_full_simp_tac (simpset() addsimps not_angle::more_temp_simps) 1, |
982 by (dtac (prem RS (temp_use wf_not_dmd_box_decrease)) 1); |
943 dtac (prem RS (temp_use wf_not_dmd_box_decrease)) 1, |
983 by (dtac (temp_use BoxDmdDmdBox) 1); |
944 dtac (temp_use BoxDmdDmdBox) 1, atac 1, |
984 by (atac 1); |
945 subgoal_tac "sigma |= []<>((#False)::action)" 1, |
985 by (subgoal_tac "sigma |= []<>((#False)::action)" 1); |
946 Force_tac 1, |
986 by (Force_tac 1); |
947 etac STL4E 1, |
987 by (etac STL4E 1); |
948 rtac DmdImpl 1, |
988 by (rtac DmdImpl 1); |
949 force_tac (temp_css addIs2 [prem RS wf_irrefl]) 1 |
989 by (force_tac (temp_css addIs2 [prem RS wf_irrefl]) 1); |
950 ]); |
990 qed "wf_box_dmd_decrease"; |
951 |
991 |
952 (* In particular, for natural numbers, if n decreases infinitely often |
992 (* In particular, for natural numbers, if n decreases infinitely often |
953 then it has to increase infinitely often. |
993 then it has to increase infinitely often. |
954 *) |
994 *) |
955 qed_goal "nat_box_dmd_decrease" TLA.thy |
995 Goal "!!n::nat stfun. |- []<>(n` < $n) --> []<>($n < n`)"; |
956 "!!n::nat stfun. |- []<>(n` < $n) --> []<>($n < n`)" |
996 by (Clarsimp_tac 1); |
957 (K [Clarsimp_tac 1, |
997 by (subgoal_tac "sigma |= []<><~( (n`,$n) : #less_than )>_n" 1); |
958 subgoal_tac "sigma |= []<><~( (n`,$n) : #less_than )>_n" 1, |
998 by (etac thin_rl 1); |
959 etac thin_rl 1, etac STL4E 1, rtac DmdImpl 1, |
999 by (etac STL4E 1); |
960 clarsimp_tac (temp_css addsimps2 [angle_def]) 1, |
1000 by (rtac DmdImpl 1); |
961 rtac nat_less_cases 1, |
1001 by (clarsimp_tac (temp_css addsimps2 [angle_def]) 1); |
962 Auto_tac, |
1002 by (rtac nat_less_cases 1); |
963 rtac (temp_use wf_box_dmd_decrease) 1, |
1003 by Auto_tac; |
964 auto_tac (temp_css addSEs2 [STL4E,DmdImplE]) |
1004 by (rtac (temp_use wf_box_dmd_decrease) 1); |
965 ]); |
1005 by (auto_tac (temp_css addSEs2 [STL4E,DmdImplE])); |
|
1006 qed "nat_box_dmd_decrease"; |
966 |
1007 |
967 |
1008 |
968 (* ------------------------------------------------------------------------- *) |
1009 (* ------------------------------------------------------------------------- *) |
969 (*** Flexible quantification over state variables ***) |
1010 (*** Flexible quantification over state variables ***) |
970 (* ------------------------------------------------------------------------- *) |
1011 (* ------------------------------------------------------------------------- *) |
971 section "Flexible quantification"; |
1012 section "Flexible quantification"; |
972 |
1013 |
973 qed_goal "aallI" TLA.thy |
1014 val [prem1,prem2] = goal thy |
974 "[| basevars vs; (!!x. basevars (x,vs) ==> sigma |= F x) |] ==> sigma |= (AALL x. F x)" |
1015 "[| basevars vs; (!!x. basevars (x,vs) ==> sigma |= F x) |]\ |
975 (fn [prem1,prem2] => [auto_tac (temp_css addsimps2 [aall_def] addSEs2 [eexE] |
1016 \ ==> sigma |= (AALL x. F x)"; |
976 addSIs2 [prem1] addSDs2 [prem2])]); |
1017 by (auto_tac (temp_css addsimps2 [aall_def] addSEs2 [eexE] |
977 |
1018 addSIs2 [prem1] addSDs2 [prem2])); |
978 qed_goalw "aallE" TLA.thy [aall_def] "|- (AALL x. F x) --> F x" |
1019 qed "aallI"; |
979 (K [Clarsimp_tac 1, etac swap 1, |
1020 |
980 force_tac (temp_css addSIs2 [eexI]) 1]); |
1021 Goalw [aall_def] "|- (AALL x. F x) --> F x"; |
|
1022 by (Clarsimp_tac 1); |
|
1023 by (etac swap 1); |
|
1024 by (force_tac (temp_css addSIs2 [eexI]) 1); |
|
1025 qed "aallE"; |
981 |
1026 |
982 (* monotonicity of quantification *) |
1027 (* monotonicity of quantification *) |
983 qed_goal "eex_mono" TLA.thy |
1028 val [min,maj] = goal thy |
984 "[| sigma |= EEX x. F x; !!x. sigma |= F x --> G x |] ==> sigma |= EEX x. G x" |
1029 "[| sigma |= EEX x. F x; !!x. sigma |= F x --> G x |] ==> sigma |= EEX x. G x"; |
985 (fn [min,maj] => [rtac (unit_base RS (min RS eexE)) 1, |
1030 by (rtac (unit_base RS (min RS eexE)) 1); |
986 rtac (temp_use eexI) 1, |
1031 by (rtac (temp_use eexI) 1); |
987 etac ((rewrite_rule intensional_rews maj) RS mp) 1 |
1032 by (etac ((rewrite_rule intensional_rews maj) RS mp) 1); |
988 ]); |
1033 qed "eex_mono"; |
989 |
1034 |
990 qed_goal "aall_mono" TLA.thy |
1035 val [min,maj] = goal thy |
991 "[| sigma |= AALL x. F(x); !!x. sigma |= F(x) --> G(x) |] ==> sigma |= AALL x. G(x)" |
1036 "[| sigma |= AALL x. F(x); !!x. sigma |= F(x) --> G(x) |] ==> sigma |= AALL x. G(x)"; |
992 (fn [min,maj] => [rtac (unit_base RS aallI) 1, |
1037 by (rtac (unit_base RS aallI) 1); |
993 rtac ((rewrite_rule intensional_rews maj) RS mp) 1, |
1038 by (rtac ((rewrite_rule intensional_rews maj) RS mp) 1); |
994 rtac (min RS (temp_use aallE)) 1 |
1039 by (rtac (min RS (temp_use aallE)) 1); |
995 ]); |
1040 qed "aall_mono"; |
996 |
1041 |
997 (* Derived history introduction rule *) |
1042 (* Derived history introduction rule *) |
998 qed_goal "historyI" TLA.thy |
1043 val [p1,p2,p3,p4,p5] = goal thy |
999 "[| sigma |= Init I; sigma |= []N; basevars vs; \ |
1044 "[| sigma |= Init I; sigma |= []N; basevars vs; \ |
1000 \ (!!h. basevars(h,vs) ==> |- I & h = ha --> HI h); \ |
1045 \ (!!h. basevars(h,vs) ==> |- I & h = ha --> HI h); \ |
1001 \ (!!h s t. [| basevars(h,vs); N (s,t); h t = hb (h s) (s,t) |] ==> HN h (s,t)) \ |
1046 \ (!!h s t. [| basevars(h,vs); N (s,t); h t = hb (h s) (s,t) |] ==> HN h (s,t)) \ |
1002 \ |] ==> sigma |= EEX h. Init (HI h) & [](HN h)" |
1047 \ |] ==> sigma |= EEX h. Init (HI h) & [](HN h)"; |
1003 (fn [p1,p2,p3,p4,p5] |
1048 by (rtac ((temp_use history) RS eexE) 1); |
1004 => [rtac ((temp_use history) RS eexE) 1, |
1049 by (rtac p3 1); |
1005 rtac p3 1, |
1050 by (rtac (temp_use eexI) 1); |
1006 rtac (temp_use eexI) 1, |
1051 by (Clarsimp_tac 1); |
1007 Clarsimp_tac 1, rtac conjI 1, |
1052 by (rtac conjI 1); |
1008 cut_facts_tac [p2] 2, |
1053 by (cut_facts_tac [p2] 2); |
1009 merge_box_tac 2, |
1054 by (merge_box_tac 2); |
1010 force_tac (temp_css addSEs2 [STL4E,p5]) 2, |
1055 by (force_tac (temp_css addSEs2 [STL4E,p5]) 2); |
1011 cut_facts_tac [p1] 1, |
1056 by (cut_facts_tac [p1] 1); |
1012 force_tac (temp_css addsimps2 Init_defs addSEs2 [p4]) 1 |
1057 by (force_tac (temp_css addsimps2 Init_defs addSEs2 [p4]) 1); |
1013 ]); |
1058 qed "historyI"; |
1014 |
1059 |
1015 (* ---------------------------------------------------------------------- |
1060 (* ---------------------------------------------------------------------- |
1016 example of a history variable: existence of a clock |
1061 example of a history variable: existence of a clock |
1017 |
1062 |
1018 Goal "|- EEX h. Init(h = #True) & [](h` = (~$h))"; |
1063 Goal "|- EEX h. Init(h = #True) & [](h` = (~$h))"; |