changeset 60592 | c9bd1d902f04 |
parent 60591 | e0b77517f9a9 |
child 66453 | cc19f7ca2ed6 |
60591:e0b77517f9a9 | 60592:c9bd1d902f04 |
---|---|
1 (* Title: HOL/TLA/Inc/Inc.thy |
1 (* Title: HOL/TLA/Inc/Inc.thy |
2 Author: Stephan Merz, University of Munich |
2 Author: Stephan Merz, University of Munich |
3 *) |
3 *) |
4 |
4 |
5 section {* Lamport's "increment" example *} |
5 section \<open>Lamport's "increment" example\<close> |
6 |
6 |
7 theory Inc |
7 theory Inc |
8 imports "../TLA" |
8 imports "../TLA" |
9 begin |
9 begin |
10 |
10 |
168 lemma g1_leadsto_a1: |
168 lemma g1_leadsto_a1: |
169 "\<turnstile> \<box>[(N1 \<or> N2) \<and> \<not>beta1]_(x,y,sem,pc1,pc2) \<and> SF(N1)_(x,y,sem,pc1,pc2) \<and> \<box>#True |
169 "\<turnstile> \<box>[(N1 \<or> N2) \<and> \<not>beta1]_(x,y,sem,pc1,pc2) \<and> SF(N1)_(x,y,sem,pc1,pc2) \<and> \<box>#True |
170 \<longrightarrow> (pc1 = #g \<leadsto> pc1 = #a)" |
170 \<longrightarrow> (pc1 = #g \<leadsto> pc1 = #a)" |
171 apply (rule SF1) |
171 apply (rule SF1) |
172 apply (tactic |
172 apply (tactic |
173 {* action_simp_tac (@{context} addsimps @{thms Psi_defs}) [] [@{thm squareE}] 1 *}) |
173 \<open>action_simp_tac (@{context} addsimps @{thms Psi_defs}) [] [@{thm squareE}] 1\<close>) |
174 apply (tactic |
174 apply (tactic |
175 {* action_simp_tac (@{context} addsimps @{thm angle_def} :: @{thms Psi_defs}) [] [] 1 *}) |
175 \<open>action_simp_tac (@{context} addsimps @{thm angle_def} :: @{thms Psi_defs}) [] [] 1\<close>) |
176 (* reduce \<turnstile> \<box>A \<longrightarrow> \<diamond>Enabled B to \<turnstile> A \<longrightarrow> Enabled B *) |
176 (* reduce \<turnstile> \<box>A \<longrightarrow> \<diamond>Enabled B to \<turnstile> A \<longrightarrow> Enabled B *) |
177 apply (auto intro!: InitDmd_gen [temp_use] N1_enabled_at_g [temp_use] |
177 apply (auto intro!: InitDmd_gen [temp_use] N1_enabled_at_g [temp_use] |
178 dest!: STL2_gen [temp_use] simp: Init_def) |
178 dest!: STL2_gen [temp_use] simp: Init_def) |
179 done |
179 done |
180 |
180 |
189 |
189 |
190 lemma g2_leadsto_a2: |
190 lemma g2_leadsto_a2: |
191 "\<turnstile> \<box>[(N1 \<or> N2) \<and> \<not>beta1]_(x,y,sem,pc1,pc2) \<and> SF(N2)_(x,y,sem,pc1,pc2) \<and> \<box>#True |
191 "\<turnstile> \<box>[(N1 \<or> N2) \<and> \<not>beta1]_(x,y,sem,pc1,pc2) \<and> SF(N2)_(x,y,sem,pc1,pc2) \<and> \<box>#True |
192 \<longrightarrow> (pc2 = #g \<leadsto> pc2 = #a)" |
192 \<longrightarrow> (pc2 = #g \<leadsto> pc2 = #a)" |
193 apply (rule SF1) |
193 apply (rule SF1) |
194 apply (tactic {* action_simp_tac (@{context} addsimps @{thms Psi_defs}) [] [@{thm squareE}] 1 *}) |
194 apply (tactic \<open>action_simp_tac (@{context} addsimps @{thms Psi_defs}) [] [@{thm squareE}] 1\<close>) |
195 apply (tactic {* action_simp_tac (@{context} addsimps @{thm angle_def} :: @{thms Psi_defs}) |
195 apply (tactic \<open>action_simp_tac (@{context} addsimps @{thm angle_def} :: @{thms Psi_defs}) |
196 [] [] 1 *}) |
196 [] [] 1\<close>) |
197 apply (auto intro!: InitDmd_gen [temp_use] N2_enabled_at_g [temp_use] |
197 apply (auto intro!: InitDmd_gen [temp_use] N2_enabled_at_g [temp_use] |
198 dest!: STL2_gen [temp_use] simp add: Init_def) |
198 dest!: STL2_gen [temp_use] simp add: Init_def) |
199 done |
199 done |
200 |
200 |
201 lemma N2_enabled_at_b: "\<turnstile> pc2 = #b \<longrightarrow> Enabled (<N2>_(x,y,sem,pc1,pc2))" |
201 lemma N2_enabled_at_b: "\<turnstile> pc2 = #b \<longrightarrow> Enabled (<N2>_(x,y,sem,pc1,pc2))" |
209 lemma b2_leadsto_g2: |
209 lemma b2_leadsto_g2: |
210 "\<turnstile> \<box>[(N1 \<or> N2) \<and> \<not>beta1]_(x,y,sem,pc1,pc2) \<and> SF(N2)_(x,y,sem,pc1,pc2) \<and> \<box>#True |
210 "\<turnstile> \<box>[(N1 \<or> N2) \<and> \<not>beta1]_(x,y,sem,pc1,pc2) \<and> SF(N2)_(x,y,sem,pc1,pc2) \<and> \<box>#True |
211 \<longrightarrow> (pc2 = #b \<leadsto> pc2 = #g)" |
211 \<longrightarrow> (pc2 = #b \<leadsto> pc2 = #g)" |
212 apply (rule SF1) |
212 apply (rule SF1) |
213 apply (tactic |
213 apply (tactic |
214 {* action_simp_tac (@{context} addsimps @{thms Psi_defs}) [] [@{thm squareE}] 1 *}) |
214 \<open>action_simp_tac (@{context} addsimps @{thms Psi_defs}) [] [@{thm squareE}] 1\<close>) |
215 apply (tactic |
215 apply (tactic |
216 {* action_simp_tac (@{context} addsimps @{thm angle_def} :: @{thms Psi_defs}) [] [] 1 *}) |
216 \<open>action_simp_tac (@{context} addsimps @{thm angle_def} :: @{thms Psi_defs}) [] [] 1\<close>) |
217 apply (auto intro!: InitDmd_gen [temp_use] N2_enabled_at_b [temp_use] |
217 apply (auto intro!: InitDmd_gen [temp_use] N2_enabled_at_b [temp_use] |
218 dest!: STL2_gen [temp_use] simp: Init_def) |
218 dest!: STL2_gen [temp_use] simp: Init_def) |
219 done |
219 done |
220 |
220 |
221 (* Combine above lemmas: the second component will eventually reach pc2 = a *) |
221 (* Combine above lemmas: the second component will eventually reach pc2 = a *) |
251 lemma a1_leadsto_b1: |
251 lemma a1_leadsto_b1: |
252 "\<turnstile> \<box>($PsiInv \<and> [(N1 \<or> N2) \<and> \<not>beta1]_(x,y,sem,pc1,pc2)) |
252 "\<turnstile> \<box>($PsiInv \<and> [(N1 \<or> N2) \<and> \<not>beta1]_(x,y,sem,pc1,pc2)) |
253 \<and> SF(N1)_(x,y,sem,pc1,pc2) \<and> \<box> SF(N2)_(x,y,sem,pc1,pc2) |
253 \<and> SF(N1)_(x,y,sem,pc1,pc2) \<and> \<box> SF(N2)_(x,y,sem,pc1,pc2) |
254 \<longrightarrow> (pc1 = #a \<leadsto> pc1 = #b)" |
254 \<longrightarrow> (pc1 = #a \<leadsto> pc1 = #b)" |
255 apply (rule SF1) |
255 apply (rule SF1) |
256 apply (tactic {* action_simp_tac (@{context} addsimps @{thms Psi_defs}) [] [@{thm squareE}] 1 *}) |
256 apply (tactic \<open>action_simp_tac (@{context} addsimps @{thms Psi_defs}) [] [@{thm squareE}] 1\<close>) |
257 apply (tactic |
257 apply (tactic |
258 {* action_simp_tac (@{context} addsimps (@{thm angle_def} :: @{thms Psi_defs})) [] [] 1 *}) |
258 \<open>action_simp_tac (@{context} addsimps (@{thm angle_def} :: @{thms Psi_defs})) [] [] 1\<close>) |
259 apply (clarsimp intro!: N1_enabled_at_both_a [THEN DmdImpl [temp_use]]) |
259 apply (clarsimp intro!: N1_enabled_at_both_a [THEN DmdImpl [temp_use]]) |
260 apply (auto intro!: BoxDmd2_simple [temp_use] N2_live [temp_use] |
260 apply (auto intro!: BoxDmd2_simple [temp_use] N2_live [temp_use] |
261 simp: split_box_conj more_temp_simps) |
261 simp: split_box_conj more_temp_simps) |
262 done |
262 done |
263 |
263 |