src/HOL/TLA/Inc/Inc.thy
changeset 60592 c9bd1d902f04
parent 60591 e0b77517f9a9
child 66453 cc19f7ca2ed6
equal deleted inserted replaced
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