src/HOL/MicroJava/BV/Semilat.thy
changeset 27681 8cedebf55539
parent 25592 e8ddaf6bf5df
equal deleted inserted replaced
27680:5a557a5afc48 27681:8cedebf55539
    69 "is_lub r x y u == is_ub r x y u & (!z. is_ub r x y z \<longrightarrow> r u z)"
    69 "is_lub r x y u == is_ub r x y u & (!z. is_ub r x y z \<longrightarrow> r u z)"
    70 
    70 
    71  some_lub :: "'a ord \<Rightarrow> 'a \<Rightarrow> 'a \<Rightarrow> 'a"
    71  some_lub :: "'a ord \<Rightarrow> 'a \<Rightarrow> 'a \<Rightarrow> 'a"
    72 "some_lub r x y == SOME z. is_lub r x y z";
    72 "some_lub r x y == SOME z. is_lub r x y z";
    73 
    73 
    74 locale (open) semilat =
    74 locale Semilat =
    75   fixes A :: "'a set"
    75   fixes A :: "'a set"
    76     and r :: "'a ord"
    76     and r :: "'a ord"
    77     and f :: "'a binop"
    77     and f :: "'a binop"
    78   assumes semilat: "semilat(A,r,f)"
    78   assumes semilat: "semilat(A,r,f)"
    79 
    79 
   120                  (!x:A. !y:A. !z:A. x <=_r z & y <=_r z \<longrightarrow> x +_f y <=_r z)"
   120                  (!x:A. !y:A. !z:A. x <=_r z & y <=_r z \<longrightarrow> x +_f y <=_r z)"
   121 apply (unfold semilat_def split_conv [THEN eq_reflection])
   121 apply (unfold semilat_def split_conv [THEN eq_reflection])
   122 apply (rule refl [THEN eq_reflection])
   122 apply (rule refl [THEN eq_reflection])
   123 done
   123 done
   124 
   124 
   125 lemma (in semilat) orderI [simp, intro]:
   125 lemma (in Semilat) orderI [simp, intro]:
   126   "order r"
   126   "order r"
   127   by (insert semilat) (simp add: semilat_Def)
   127   by (insert semilat) (simp add: semilat_Def)
   128 
   128 
   129 lemma (in semilat) closedI [simp, intro]:
   129 lemma (in Semilat) closedI [simp, intro]:
   130   "closed A f"
   130   "closed A f"
   131   by (insert semilat) (simp add: semilat_Def)
   131   by (insert semilat) (simp add: semilat_Def)
   132 
   132 
   133 lemma closedD:
   133 lemma closedD:
   134   "\<lbrakk> closed A f; x:A; y:A \<rbrakk> \<Longrightarrow> x +_f y : A"
   134   "\<lbrakk> closed A f; x:A; y:A \<rbrakk> \<Longrightarrow> x +_f y : A"
   136 
   136 
   137 lemma closed_UNIV [simp]: "closed UNIV f"
   137 lemma closed_UNIV [simp]: "closed UNIV f"
   138   by (simp add: closed_def)
   138   by (simp add: closed_def)
   139 
   139 
   140 
   140 
   141 lemma (in semilat) closed_f [simp, intro]:
   141 lemma (in Semilat) closed_f [simp, intro]:
   142   "\<lbrakk>x:A; y:A\<rbrakk>  \<Longrightarrow> x +_f y : A"
   142   "\<lbrakk>x:A; y:A\<rbrakk>  \<Longrightarrow> x +_f y : A"
   143   by (simp add: closedD [OF closedI])
   143   by (simp add: closedD [OF closedI])
   144 
   144 
   145 lemma (in semilat) refl_r [intro, simp]:
   145 lemma (in Semilat) refl_r [intro, simp]:
   146   "x <=_r x"
   146   "x <=_r x"
   147   by simp
   147   by simp
   148 
   148 
   149 lemma (in semilat) antisym_r [intro?]:
   149 lemma (in Semilat) antisym_r [intro?]:
   150   "\<lbrakk> x <=_r y; y <=_r x \<rbrakk> \<Longrightarrow> x = y"
   150   "\<lbrakk> x <=_r y; y <=_r x \<rbrakk> \<Longrightarrow> x = y"
   151   by (rule order_antisym) auto
   151   by (rule order_antisym) auto
   152   
   152   
   153 lemma (in semilat) trans_r [trans, intro?]:
   153 lemma (in Semilat) trans_r [trans, intro?]:
   154   "\<lbrakk>x <=_r y; y <=_r z\<rbrakk> \<Longrightarrow> x <=_r z"
   154   "\<lbrakk>x <=_r y; y <=_r z\<rbrakk> \<Longrightarrow> x <=_r z"
   155   by (auto intro: order_trans)    
   155   by (auto intro: order_trans)    
   156   
   156   
   157 
   157 
   158 lemma (in semilat) ub1 [simp, intro?]:
   158 lemma (in Semilat) ub1 [simp, intro?]:
   159   "\<lbrakk> x:A; y:A \<rbrakk> \<Longrightarrow> x <=_r x +_f y"
   159   "\<lbrakk> x:A; y:A \<rbrakk> \<Longrightarrow> x <=_r x +_f y"
   160   by (insert semilat) (unfold semilat_Def, simp)
   160   by (insert semilat) (unfold semilat_Def, simp)
   161 
   161 
   162 lemma (in semilat) ub2 [simp, intro?]:
   162 lemma (in Semilat) ub2 [simp, intro?]:
   163   "\<lbrakk> x:A; y:A \<rbrakk> \<Longrightarrow> y <=_r x +_f y"
   163   "\<lbrakk> x:A; y:A \<rbrakk> \<Longrightarrow> y <=_r x +_f y"
   164   by (insert semilat) (unfold semilat_Def, simp)
   164   by (insert semilat) (unfold semilat_Def, simp)
   165 
   165 
   166 lemma (in semilat) lub [simp, intro?]:
   166 lemma (in Semilat) lub [simp, intro?]:
   167  "\<lbrakk> x <=_r z; y <=_r z; x:A; y:A; z:A \<rbrakk> \<Longrightarrow> x +_f y <=_r z";
   167  "\<lbrakk> x <=_r z; y <=_r z; x:A; y:A; z:A \<rbrakk> \<Longrightarrow> x +_f y <=_r z";
   168   by (insert semilat) (unfold semilat_Def, simp)
   168   by (insert semilat) (unfold semilat_Def, simp)
   169 
   169 
   170 
   170 
   171 lemma (in semilat) plus_le_conv [simp]:
   171 lemma (in Semilat) plus_le_conv [simp]:
   172   "\<lbrakk> x:A; y:A; z:A \<rbrakk> \<Longrightarrow> (x +_f y <=_r z) = (x <=_r z & y <=_r z)"
   172   "\<lbrakk> x:A; y:A; z:A \<rbrakk> \<Longrightarrow> (x +_f y <=_r z) = (x <=_r z & y <=_r z)"
   173   by (blast intro: ub1 ub2 lub order_trans)
   173   by (blast intro: ub1 ub2 lub order_trans)
   174 
   174 
   175 lemma (in semilat) le_iff_plus_unchanged:
   175 lemma (in Semilat) le_iff_plus_unchanged:
   176   "\<lbrakk> x:A; y:A \<rbrakk> \<Longrightarrow> (x <=_r y) = (x +_f y = y)"
   176   "\<lbrakk> x:A; y:A \<rbrakk> \<Longrightarrow> (x <=_r y) = (x +_f y = y)"
   177 apply (rule iffI)
   177 apply (rule iffI)
   178  apply (blast intro: antisym_r refl_r lub ub2)
   178  apply (blast intro: antisym_r refl_r lub ub2)
   179 apply (erule subst)
   179 apply (erule subst)
   180 apply simp
   180 apply simp
   181 done
   181 done
   182 
   182 
   183 lemma (in semilat) le_iff_plus_unchanged2:
   183 lemma (in Semilat) le_iff_plus_unchanged2:
   184   "\<lbrakk> x:A; y:A \<rbrakk> \<Longrightarrow> (x <=_r y) = (y +_f x = y)"
   184   "\<lbrakk> x:A; y:A \<rbrakk> \<Longrightarrow> (x <=_r y) = (y +_f x = y)"
   185 apply (rule iffI)
   185 apply (rule iffI)
   186  apply (blast intro: order_antisym lub order_refl ub1)
   186  apply (blast intro: order_antisym lub order_refl ub1)
   187 apply (erule subst)
   187 apply (erule subst)
   188 apply simp
   188 apply simp
   189 done 
   189 done 
   190 
   190 
   191 
   191 
   192 lemma (in semilat) plus_assoc [simp]:
   192 lemma (in Semilat) plus_assoc [simp]:
   193   assumes a: "a \<in> A" and b: "b \<in> A" and c: "c \<in> A"
   193   assumes a: "a \<in> A" and b: "b \<in> A" and c: "c \<in> A"
   194   shows "a +_f (b +_f c) = a +_f b +_f c"
   194   shows "a +_f (b +_f c) = a +_f b +_f c"
   195 proof -
   195 proof -
   196   from a b have ab: "a +_f b \<in> A" ..
   196   from a b have ab: "a +_f b \<in> A" ..
   197   from this c have abc: "(a +_f b) +_f c \<in> A" ..
   197   from this c have abc: "(a +_f b) +_f c \<in> A" ..
   225       from this "c<" ab c abc' show ?thesis ..
   225       from this "c<" ab c abc' show ?thesis ..
   226     qed
   226     qed
   227   qed
   227   qed
   228 qed
   228 qed
   229 
   229 
   230 lemma (in semilat) plus_com_lemma:
   230 lemma (in Semilat) plus_com_lemma:
   231   "\<lbrakk>a \<in> A; b \<in> A\<rbrakk> \<Longrightarrow> a +_f b <=_r b +_f a"
   231   "\<lbrakk>a \<in> A; b \<in> A\<rbrakk> \<Longrightarrow> a +_f b <=_r b +_f a"
   232 proof -
   232 proof -
   233   assume a: "a \<in> A" and b: "b \<in> A"  
   233   assume a: "a \<in> A" and b: "b \<in> A"  
   234   from b a have "a <=_r b +_f a" .. 
   234   from b a have "a <=_r b +_f a" .. 
   235   moreover from b a have "b <=_r b +_f a" ..
   235   moreover from b a have "b <=_r b +_f a" ..
   236   moreover note a b
   236   moreover note a b
   237   moreover from b a have "b +_f a \<in> A" ..
   237   moreover from b a have "b +_f a \<in> A" ..
   238   ultimately show ?thesis ..
   238   ultimately show ?thesis ..
   239 qed
   239 qed
   240 
   240 
   241 lemma (in semilat) plus_commutative:
   241 lemma (in Semilat) plus_commutative:
   242   "\<lbrakk>a \<in> A; b \<in> A\<rbrakk> \<Longrightarrow> a +_f b = b +_f a"
   242   "\<lbrakk>a \<in> A; b \<in> A\<rbrakk> \<Longrightarrow> a +_f b = b +_f a"
   243 by(blast intro: order_antisym plus_com_lemma)
   243 by(blast intro: order_antisym plus_com_lemma)
   244 
   244 
   245 lemma is_lubD:
   245 lemma is_lubD:
   246   "is_lub r x y u \<Longrightarrow> is_ub r x y u & (!z. is_ub r x y z \<longrightarrow> r u z)"
   246   "is_lub r x y u \<Longrightarrow> is_ub r x y u & (!z. is_ub r x y z \<longrightarrow> r u z)"