author | paulson |
Fri, 07 Jan 2000 11:04:15 +0100 | |
changeset 8113 | 7110358acded |
parent 8074 | 36a6c38e0eca |
child 8128 | 3a5864b465e2 |
permissions | -rw-r--r-- |
6706 | 1 |
(* Title: HOL/UNITY/Follows |
2 |
ID: $Id$ |
|
3 |
Author: Lawrence C Paulson, Cambridge University Computer Laboratory |
|
4 |
Copyright 1998 University of Cambridge |
|
5 |
||
6 |
The Follows relation of Charpentier and Sivilotte |
|
7 |
*) |
|
8 |
||
9 |
(*Does this hold for "invariant"?*) |
|
10 |
Goal "mono h ==> Always {s. f s <= g s} <= Always {s. h (f s) <= h (g s)}"; |
|
11 |
by (asm_simp_tac (simpset() addsimps [Always_eq_includes_reachable]) 1); |
|
12 |
by (blast_tac (claset() addIs [monoD]) 1); |
|
13 |
qed "mono_Always_o"; |
|
14 |
||
7363 | 15 |
Goal "mono (h::'a::order => 'b::order) \ |
16 |
\ ==> (INT j. {s. j <= g s} LeadsTo {s. j <= f s}) <= \ |
|
17 |
\ (INT k. {s. k <= h (g s)} LeadsTo {s. k <= h (f s)})"; |
|
6706 | 18 |
by Auto_tac; |
19 |
by (rtac single_LeadsTo_I 1); |
|
20 |
by (dres_inst_tac [("x", "g s")] spec 1); |
|
21 |
by (etac LeadsTo_weaken 1); |
|
22 |
by (ALLGOALS (blast_tac (claset() addIs [monoD, order_trans]))); |
|
23 |
qed "mono_LeadsTo_o"; |
|
24 |
||
8074
36a6c38e0eca
Working version after a FAILED attempt to base Follows upon LeadsETo
paulson
parents:
7542
diff
changeset
|
25 |
(*NOT PROVABLE USING leadsETo because givenBy f <= givenBy (h o f) fails*) |
6809 | 26 |
Goalw [Follows_def] "mono h ==> f Fols g <= (h o f) Fols (h o g)"; |
6706 | 27 |
by (Clarify_tac 1); |
28 |
by (asm_full_simp_tac |
|
29 |
(simpset() addsimps [impOfSubs mono_Increasing_o, |
|
30 |
impOfSubs mono_Always_o, |
|
31 |
impOfSubs mono_LeadsTo_o RS INT_D]) 1); |
|
32 |
qed "mono_Follows_o"; |
|
33 |
||
8074
36a6c38e0eca
Working version after a FAILED attempt to base Follows upon LeadsETo
paulson
parents:
7542
diff
changeset
|
34 |
(*NOT PROVABLE USING leadsETo since it needs the previous thm*) |
7542 | 35 |
Goal "mono h ==> f Fols g <= (%x. h (f x)) Fols (%x. h (g x))"; |
36 |
by (dtac mono_Follows_o 1); |
|
37 |
by (force_tac (claset(), simpset() addsimps [o_def]) 1); |
|
38 |
qed "mono_Follows_apply"; |
|
39 |
||
8074
36a6c38e0eca
Working version after a FAILED attempt to base Follows upon LeadsETo
paulson
parents:
7542
diff
changeset
|
40 |
(*NOT PROVABLE USING leadsETo since givenBy g doesn't imply givenBy f*) |
6706 | 41 |
Goalw [Follows_def] |
6809 | 42 |
"[| F : f Fols g; F: g Fols h |] ==> F : f Fols h"; |
6706 | 43 |
by (asm_full_simp_tac (simpset() addsimps [Always_eq_includes_reachable]) 1); |
44 |
by (blast_tac (claset() addIs [order_trans, LeadsTo_Trans]) 1); |
|
45 |
qed "Follows_trans"; |
|
46 |
||
8074
36a6c38e0eca
Working version after a FAILED attempt to base Follows upon LeadsETo
paulson
parents:
7542
diff
changeset
|
47 |
(* |
36a6c38e0eca
Working version after a FAILED attempt to base Follows upon LeadsETo
paulson
parents:
7542
diff
changeset
|
48 |
try: |
36a6c38e0eca
Working version after a FAILED attempt to base Follows upon LeadsETo
paulson
parents:
7542
diff
changeset
|
49 |
by (asm_full_simp_tac (simpset() addsimps [Always_eq_includes_reachable]) 1); |
8113 | 50 |
by Auto_tac; |
8074
36a6c38e0eca
Working version after a FAILED attempt to base Follows upon LeadsETo
paulson
parents:
7542
diff
changeset
|
51 |
by (blast_tac (claset() addIs [order_trans, LeadsETo_Trans]) 1); |
8113 | 52 |
by (rtac LeadsETo_Trans 1); |
8074
36a6c38e0eca
Working version after a FAILED attempt to base Follows upon LeadsETo
paulson
parents:
7542
diff
changeset
|
53 |
by (Blast_tac 2); |
8113 | 54 |
by (dtac spec 1); |
55 |
by (etac LeadsETo_weaken 1); |
|
56 |
by Auto_tac; |
|
8074
36a6c38e0eca
Working version after a FAILED attempt to base Follows upon LeadsETo
paulson
parents:
7542
diff
changeset
|
57 |
by (thin_tac "All ?P" 1); |
36a6c38e0eca
Working version after a FAILED attempt to base Follows upon LeadsETo
paulson
parents:
7542
diff
changeset
|
58 |
by (full_simp_tac (simpset() addsimps [givenBy_eq_Collect]) 1); |
36a6c38e0eca
Working version after a FAILED attempt to base Follows upon LeadsETo
paulson
parents:
7542
diff
changeset
|
59 |
by Safe_tac; |
36a6c38e0eca
Working version after a FAILED attempt to base Follows upon LeadsETo
paulson
parents:
7542
diff
changeset
|
60 |
**) |
36a6c38e0eca
Working version after a FAILED attempt to base Follows upon LeadsETo
paulson
parents:
7542
diff
changeset
|
61 |
|
6706 | 62 |
|
7363 | 63 |
(** Destructiom rules **) |
64 |
||
65 |
Goalw [Follows_def] |
|
66 |
"F : f Fols g ==> F : Increasing f"; |
|
67 |
by (Blast_tac 1); |
|
68 |
qed "Follows_Increasing1"; |
|
69 |
||
70 |
Goalw [Follows_def] |
|
71 |
"F : f Fols g ==> F : Increasing g"; |
|
72 |
by (Blast_tac 1); |
|
73 |
qed "Follows_Increasing2"; |
|
74 |
||
75 |
Goalw [Follows_def] |
|
76 |
"F : f Fols g ==> F : Always {s. f s <= g s}"; |
|
77 |
by (Blast_tac 1); |
|
78 |
qed "Follows_Bounded"; |
|
79 |
||
80 |
Goalw [Follows_def] |
|
81 |
"F : f Fols g ==> F : {s. k <= g s} LeadsTo {s. k <= f s}"; |
|
82 |
by (Blast_tac 1); |
|
83 |
qed "Follows_LeadsTo"; |
|
84 |
||
85 |
||
6706 | 86 |
(*Can replace "Un" by any sup. But existing max only works for linorders.*) |
87 |
||
88 |
Goalw [increasing_def, stable_def, constrains_def] |
|
89 |
"[| F : increasing f; F: increasing g |] \ |
|
90 |
\ ==> F : increasing (%s. (f s) Un (g s))"; |
|
91 |
by Auto_tac; |
|
92 |
by (dres_inst_tac [("x","f xa")] spec 1); |
|
93 |
by (dres_inst_tac [("x","g xa")] spec 1); |
|
94 |
by (blast_tac (claset() addSDs [bspec]) 1); |
|
95 |
qed "increasing_Un"; |
|
96 |
||
97 |
Goalw [Increasing_def, Stable_def, Constrains_def, stable_def, constrains_def] |
|
98 |
"[| F : Increasing f; F: Increasing g |] \ |
|
99 |
\ ==> F : Increasing (%s. (f s) Un (g s))"; |
|
100 |
by Auto_tac; |
|
101 |
by (dres_inst_tac [("x","f xa")] spec 1); |
|
102 |
by (dres_inst_tac [("x","g xa")] spec 1); |
|
103 |
by (blast_tac (claset() addSDs [bspec]) 1); |
|
104 |
qed "Increasing_Un"; |
|
105 |
||
106 |
||
107 |
Goal "[| F : Always {s. f' s <= f s}; F : Always {s. g' s <= g s} |] \ |
|
108 |
\ ==> F : Always {s. f' s Un g' s <= f s Un g s}"; |
|
109 |
by (asm_full_simp_tac (simpset() addsimps [Always_eq_includes_reachable]) 1); |
|
110 |
by (Blast_tac 1); |
|
111 |
qed "Always_Un"; |
|
112 |
||
113 |
Goalw [Increasing_def] |
|
114 |
"F : Increasing f ==> F : Stable {s. x <= f s}"; |
|
115 |
by (Blast_tac 1); |
|
116 |
qed "IncreasingD"; |
|
117 |
||
118 |
(*Lemma to re-use the argument that one variable increases (progress) |
|
119 |
while the other variable doesn't decrease (safety)*) |
|
120 |
Goal "[| F : Increasing f; F : Increasing g; \ |
|
121 |
\ F : Increasing g'; F : Always {s. f' s <= f s};\ |
|
122 |
\ ALL k. F : {s. k <= f s} LeadsTo {s. k <= f' s} |]\ |
|
123 |
\ ==> F : {s. k <= f s Un g s} LeadsTo {s. k <= f' s Un g s}"; |
|
124 |
by (rtac single_LeadsTo_I 1); |
|
125 |
by (dres_inst_tac [("x", "f s")] IncreasingD 1); |
|
126 |
by (dres_inst_tac [("x", "g s")] IncreasingD 1); |
|
127 |
by (rtac LeadsTo_weaken 1); |
|
128 |
by (rtac PSP_Stable 1); |
|
129 |
by (eres_inst_tac [("x", "f s")] spec 1); |
|
130 |
by (etac Stable_Int 1); |
|
131 |
by (assume_tac 1); |
|
132 |
by (Blast_tac 1); |
|
133 |
by (Blast_tac 1); |
|
134 |
qed "Follows_Un_lemma"; |
|
135 |
||
136 |
Goalw [Follows_def] |
|
6809 | 137 |
"[| F : f' Fols f; F: g' Fols g |] \ |
138 |
\ ==> F : (%s. (f' s) Un (g' s)) Fols (%s. (f s) Un (g s))"; |
|
6706 | 139 |
by (asm_full_simp_tac (simpset() addsimps [Increasing_Un, Always_Un]) 1); |
140 |
by Auto_tac; |
|
141 |
by (rtac LeadsTo_Trans 1); |
|
142 |
by (blast_tac (claset() addIs [Follows_Un_lemma]) 1); |
|
143 |
(*Weakening is used to exchange Un's arguments*) |
|
144 |
by (blast_tac (claset() addIs [Follows_Un_lemma RS LeadsTo_weaken]) 1); |
|
145 |
qed "Follows_Un"; |
|
146 |