author | oheimb |
Mon, 21 Sep 1998 23:12:31 +0200 | |
changeset 5521 | 7970832271cc |
parent 5490 | 85855f65d0c6 |
child 5536 | 130f3d891fb2 |
permissions | -rw-r--r-- |
4776 | 1 |
(* Title: HOL/UNITY/Reach.thy |
2 |
ID: $Id$ |
|
3 |
Author: Lawrence C Paulson, Cambridge University Computer Laboratory |
|
4 |
Copyright 1998 University of Cambridge |
|
5 |
||
6 |
Reachability in Directed Graphs. From Chandy and Misra, section 6.4. |
|
4896
4727272f3db6
New syntax for function update; moved to main HOL directory
paulson
parents:
4776
diff
changeset
|
7 |
[ this example took only four days!] |
4776 | 8 |
*) |
9 |
||
10 |
(*TO SIMPDATA.ML?? FOR CLASET?? *) |
|
11 |
val major::prems = goal thy |
|
12 |
"[| if P then Q else R; \ |
|
13 |
\ [| P; Q |] ==> S; \ |
|
14 |
\ [| ~ P; R |] ==> S |] ==> S"; |
|
15 |
by (cut_facts_tac [major] 1); |
|
16 |
by (blast_tac (claset() addSDs [if_bool_eq_disj RS iffD1] addIs prems) 1); |
|
17 |
qed "ifE"; |
|
18 |
||
19 |
AddSEs [ifE]; |
|
20 |
||
21 |
||
5426
566f47250bd0
A new approach, using simp_of_act and simp_of_set to activate definitions when
paulson
parents:
5424
diff
changeset
|
22 |
Addsimps [Rprg_def RS def_prg_simps]; |
4776 | 23 |
|
5426
566f47250bd0
A new approach, using simp_of_act and simp_of_set to activate definitions when
paulson
parents:
5424
diff
changeset
|
24 |
Addsimps [simp_of_act asgt_def]; |
4776 | 25 |
|
26 |
(*All vertex sets are finite*) |
|
27 |
AddIffs [[subset_UNIV, finite_graph] MRS finite_subset]; |
|
28 |
||
5426
566f47250bd0
A new approach, using simp_of_act and simp_of_set to activate definitions when
paulson
parents:
5424
diff
changeset
|
29 |
Addsimps [simp_of_set reach_invariant_def]; |
4776 | 30 |
|
5426
566f47250bd0
A new approach, using simp_of_act and simp_of_set to activate definitions when
paulson
parents:
5424
diff
changeset
|
31 |
Goal "Invariant Rprg reach_invariant"; |
5313
1861a564d7e2
Constrains, Stable, Invariant...more of the substitution axiom, but Union
paulson
parents:
5253
diff
changeset
|
32 |
by (rtac InvariantI 1); |
5240
bbcd79ef7cf2
Constant "invariant" and new constrains_tac, ensures_tac
paulson
parents:
5232
diff
changeset
|
33 |
by Auto_tac; (*for the initial state; proof of stability remains*) |
5426
566f47250bd0
A new approach, using simp_of_act and simp_of_set to activate definitions when
paulson
parents:
5424
diff
changeset
|
34 |
by (constrains_tac 1); |
4776 | 35 |
by (blast_tac (claset() addIs [r_into_rtrancl,rtrancl_trans]) 1); |
5240
bbcd79ef7cf2
Constant "invariant" and new constrains_tac, ensures_tac
paulson
parents:
5232
diff
changeset
|
36 |
qed "reach_invariant"; |
4776 | 37 |
|
38 |
||
39 |
(*** Fixedpoint ***) |
|
40 |
||
41 |
(*If it reaches a fixedpoint, it has found a solution*) |
|
5426
566f47250bd0
A new approach, using simp_of_act and simp_of_set to activate definitions when
paulson
parents:
5424
diff
changeset
|
42 |
Goalw [fixedpoint_def] |
566f47250bd0
A new approach, using simp_of_act and simp_of_set to activate definitions when
paulson
parents:
5424
diff
changeset
|
43 |
"fixedpoint Int reach_invariant = { %v. (init, v) : edges^* }"; |
4776 | 44 |
by (rtac equalityI 1); |
5426
566f47250bd0
A new approach, using simp_of_act and simp_of_set to activate definitions when
paulson
parents:
5424
diff
changeset
|
45 |
by (auto_tac (claset() addSIs [ext], simpset())); |
4776 | 46 |
by (blast_tac (claset() addIs [r_into_rtrancl,rtrancl_trans]) 2); |
47 |
by (etac rtrancl_induct 1); |
|
48 |
by Auto_tac; |
|
49 |
qed "fixedpoint_invariant_correct"; |
|
50 |
||
5426
566f47250bd0
A new approach, using simp_of_act and simp_of_set to activate definitions when
paulson
parents:
5424
diff
changeset
|
51 |
Goalw [FP_def, fixedpoint_def, stable_def, constrains_def] |
566f47250bd0
A new approach, using simp_of_act and simp_of_set to activate definitions when
paulson
parents:
5424
diff
changeset
|
52 |
"FP (Acts Rprg) <= fixedpoint"; |
4776 | 53 |
by Auto_tac; |
54 |
by (asm_full_simp_tac (simpset() addsimps [Image_singleton, image_iff]) 1); |
|
55 |
by (dtac fun_cong 1); |
|
56 |
by Auto_tac; |
|
57 |
val lemma1 = result(); |
|
58 |
||
5426
566f47250bd0
A new approach, using simp_of_act and simp_of_set to activate definitions when
paulson
parents:
5424
diff
changeset
|
59 |
Goalw [FP_def, fixedpoint_def, stable_def, constrains_def] |
566f47250bd0
A new approach, using simp_of_act and simp_of_set to activate definitions when
paulson
parents:
5424
diff
changeset
|
60 |
"fixedpoint <= FP (Acts Rprg)"; |
566f47250bd0
A new approach, using simp_of_act and simp_of_set to activate definitions when
paulson
parents:
5424
diff
changeset
|
61 |
by (auto_tac (claset() addSIs [ext], simpset())); |
4776 | 62 |
val lemma2 = result(); |
63 |
||
5253 | 64 |
Goal "FP (Acts Rprg) = fixedpoint"; |
4776 | 65 |
by (rtac ([lemma1,lemma2] MRS equalityI) 1); |
66 |
qed "FP_fixedpoint"; |
|
67 |
||
68 |
||
69 |
(*If we haven't reached a fixedpoint then there is some edge for which u but |
|
70 |
not v holds. Progress will be proved via an ENSURES assertion that the |
|
71 |
metric will decrease for each suitable edge. A union over all edges proves |
|
72 |
a LEADSTO assertion that the metric decreases if we are not at a fixedpoint. |
|
73 |
*) |
|
74 |
||
5490 | 75 |
Goal "- fixedpoint = (UN (u,v): edges. {s. s u & ~ s v})"; |
4776 | 76 |
by (simp_tac (simpset() addsimps |
5426
566f47250bd0
A new approach, using simp_of_act and simp_of_set to activate definitions when
paulson
parents:
5424
diff
changeset
|
77 |
([Compl_FP, UN_UN_flatten, FP_fixedpoint RS sym])) 1); |
566f47250bd0
A new approach, using simp_of_act and simp_of_set to activate definitions when
paulson
parents:
5424
diff
changeset
|
78 |
by Auto_tac; |
5196 | 79 |
by (rtac fun_upd_idem 1); |
5521 | 80 |
by (auto_tac (claset(),simpset() addsimps [fun_upd_idem_iff])); |
4776 | 81 |
qed "Compl_fixedpoint"; |
82 |
||
5069 | 83 |
Goal "A - fixedpoint = (UN (u,v): edges. A Int {s. s u & ~ s v})"; |
4776 | 84 |
by (simp_tac (simpset() addsimps [Diff_eq, Compl_fixedpoint]) 1); |
85 |
by (Blast_tac 1); |
|
86 |
qed "Diff_fixedpoint"; |
|
87 |
||
88 |
||
89 |
(*** Progress ***) |
|
90 |
||
5111 | 91 |
Goalw [metric_def] "~ s x ==> Suc (metric (s(x:=True))) = metric s"; |
5071
548f398d770b
Consequences of the change from [ := ] to ( := ) in theory Update.
nipkow
parents:
5069
diff
changeset
|
92 |
by (subgoal_tac "{v. ~ (s(x:=True)) v} = {v. ~ s v} - {x}" 1); |
4776 | 93 |
by Auto_tac; |
94 |
by (asm_simp_tac (simpset() addsimps [card_Suc_Diff]) 1); |
|
95 |
qed "Suc_metric"; |
|
96 |
||
5111 | 97 |
Goal "~ s x ==> metric (s(x:=True)) < metric s"; |
4776 | 98 |
by (etac (Suc_metric RS subst) 1); |
99 |
by (Blast_tac 1); |
|
100 |
qed "metric_less"; |
|
101 |
AddSIs [metric_less]; |
|
102 |
||
5071
548f398d770b
Consequences of the change from [ := ] to ( := ) in theory Update.
nipkow
parents:
5069
diff
changeset
|
103 |
Goal "metric (s(y:=s x | s y)) <= metric s"; |
4776 | 104 |
by (case_tac "s x --> s y" 1); |
105 |
by (auto_tac (claset() addIs [less_imp_le], |
|
5196 | 106 |
simpset() addsimps [fun_upd_idem])); |
4776 | 107 |
qed "metric_le"; |
108 |
||
5313
1861a564d7e2
Constrains, Stable, Invariant...more of the substitution axiom, but Union
paulson
parents:
5253
diff
changeset
|
109 |
Goal "LeadsTo Rprg ((metric-``{m}) - fixedpoint) (metric-``(lessThan m))"; |
4776 | 110 |
by (simp_tac (simpset() addsimps [Diff_fixedpoint]) 1); |
5313
1861a564d7e2
Constrains, Stable, Invariant...more of the substitution axiom, but Union
paulson
parents:
5253
diff
changeset
|
111 |
by (rtac LeadsTo_UN 1); |
1861a564d7e2
Constrains, Stable, Invariant...more of the substitution axiom, but Union
paulson
parents:
5253
diff
changeset
|
112 |
by Auto_tac; |
5426
566f47250bd0
A new approach, using simp_of_act and simp_of_set to activate definitions when
paulson
parents:
5424
diff
changeset
|
113 |
by (ensures_tac "asgt a b" 1); |
5424
771a68a468cc
modified proofs for new constrains_tac and ensures_tac
paulson
parents:
5313
diff
changeset
|
114 |
by (Blast_tac 2); |
771a68a468cc
modified proofs for new constrains_tac and ensures_tac
paulson
parents:
5313
diff
changeset
|
115 |
by (full_simp_tac (simpset() addsimps [not_less_iff_le]) 1); |
771a68a468cc
modified proofs for new constrains_tac and ensures_tac
paulson
parents:
5313
diff
changeset
|
116 |
bd (metric_le RS le_anti_sym) 1; |
771a68a468cc
modified proofs for new constrains_tac and ensures_tac
paulson
parents:
5313
diff
changeset
|
117 |
by (auto_tac (claset() addEs [less_not_refl3 RSN (2, rev_notE)], |
771a68a468cc
modified proofs for new constrains_tac and ensures_tac
paulson
parents:
5313
diff
changeset
|
118 |
simpset())); |
5313
1861a564d7e2
Constrains, Stable, Invariant...more of the substitution axiom, but Union
paulson
parents:
5253
diff
changeset
|
119 |
qed "LeadsTo_Diff_fixedpoint"; |
4776 | 120 |
|
5313
1861a564d7e2
Constrains, Stable, Invariant...more of the substitution axiom, but Union
paulson
parents:
5253
diff
changeset
|
121 |
Goal "LeadsTo Rprg (metric-``{m}) (metric-``(lessThan m) Un fixedpoint)"; |
5426
566f47250bd0
A new approach, using simp_of_act and simp_of_set to activate definitions when
paulson
parents:
5424
diff
changeset
|
122 |
by (rtac ([LeadsTo_Diff_fixedpoint RS LeadsTo_weaken_R, |
566f47250bd0
A new approach, using simp_of_act and simp_of_set to activate definitions when
paulson
parents:
5424
diff
changeset
|
123 |
subset_imp_LeadsTo] MRS LeadsTo_Diff) 1); |
566f47250bd0
A new approach, using simp_of_act and simp_of_set to activate definitions when
paulson
parents:
5424
diff
changeset
|
124 |
by Auto_tac; |
5313
1861a564d7e2
Constrains, Stable, Invariant...more of the substitution axiom, but Union
paulson
parents:
5253
diff
changeset
|
125 |
qed "LeadsTo_Un_fixedpoint"; |
4776 | 126 |
|
127 |
||
128 |
(*Execution in any state leads to a fixedpoint (i.e. can terminate)*) |
|
5313
1861a564d7e2
Constrains, Stable, Invariant...more of the substitution axiom, but Union
paulson
parents:
5253
diff
changeset
|
129 |
Goal "LeadsTo Rprg UNIV fixedpoint"; |
1861a564d7e2
Constrains, Stable, Invariant...more of the substitution axiom, but Union
paulson
parents:
5253
diff
changeset
|
130 |
by (rtac LessThan_induct 1); |
4776 | 131 |
by Auto_tac; |
5313
1861a564d7e2
Constrains, Stable, Invariant...more of the substitution axiom, but Union
paulson
parents:
5253
diff
changeset
|
132 |
by (rtac LeadsTo_Un_fixedpoint 1); |
1861a564d7e2
Constrains, Stable, Invariant...more of the substitution axiom, but Union
paulson
parents:
5253
diff
changeset
|
133 |
qed "LeadsTo_fixedpoint"; |
4776 | 134 |
|
5253 | 135 |
Goal "LeadsTo Rprg UNIV { %v. (init, v) : edges^* }"; |
4776 | 136 |
by (stac (fixedpoint_invariant_correct RS sym) 1); |
5313
1861a564d7e2
Constrains, Stable, Invariant...more of the substitution axiom, but Union
paulson
parents:
5253
diff
changeset
|
137 |
by (rtac ([reach_invariant, LeadsTo_fixedpoint] |
1861a564d7e2
Constrains, Stable, Invariant...more of the substitution axiom, but Union
paulson
parents:
5253
diff
changeset
|
138 |
MRS Invariant_LeadsTo_weaken) 1); |
5240
bbcd79ef7cf2
Constant "invariant" and new constrains_tac, ensures_tac
paulson
parents:
5232
diff
changeset
|
139 |
by Auto_tac; |
4776 | 140 |
qed "LeadsTo_correct"; |