src/HOL/Decision_Procs/MIR.thy
changeset 31952 40501bb2d57c
parent 31730 d74830dc3e4a
child 32960 69916a850301
equal deleted inserted replaced
31951:9787769764bb 31952:40501bb2d57c
  1058   { assume nnz: "n \<noteq> 0"
  1058   { assume nnz: "n \<noteq> 0"
  1059     {assume "\<not> ?g > 1" hence ?thesis by (simp add: Let_def simp_num_pair_def)}
  1059     {assume "\<not> ?g > 1" hence ?thesis by (simp add: Let_def simp_num_pair_def)}
  1060     moreover
  1060     moreover
  1061     {assume g1:"?g>1" hence g0: "?g > 0" by simp
  1061     {assume g1:"?g>1" hence g0: "?g > 0" by simp
  1062       from g1 nnz have gp0: "?g' \<noteq> 0" by simp
  1062       from g1 nnz have gp0: "?g' \<noteq> 0" by simp
  1063       hence g'p: "?g' > 0" using int_gcd_ge_0[where x="n" and y="numgcd ?t'"] by arith
  1063       hence g'p: "?g' > 0" using gcd_ge_0_int[where x="n" and y="numgcd ?t'"] by arith
  1064       hence "?g'= 1 \<or> ?g' > 1" by arith
  1064       hence "?g'= 1 \<or> ?g' > 1" by arith
  1065       moreover {assume "?g'=1" hence ?thesis by (simp add: Let_def simp_num_pair_def)}
  1065       moreover {assume "?g'=1" hence ?thesis by (simp add: Let_def simp_num_pair_def)}
  1066       moreover {assume g'1:"?g'>1"
  1066       moreover {assume g'1:"?g'>1"
  1067 	from dvdnumcoeff_aux2[OF g1] have th1:"dvdnumcoeff ?t' ?g" ..
  1067 	from dvdnumcoeff_aux2[OF g1] have th1:"dvdnumcoeff ?t' ?g" ..
  1068 	let ?tt = "reducecoeffh ?t' ?g'"
  1068 	let ?tt = "reducecoeffh ?t' ?g'"
  1094   { assume nnz: "n \<noteq> 0"
  1094   { assume nnz: "n \<noteq> 0"
  1095     {assume "\<not> ?g > 1" hence ?thesis  using prems by (auto simp add: Let_def simp_num_pair_def)}
  1095     {assume "\<not> ?g > 1" hence ?thesis  using prems by (auto simp add: Let_def simp_num_pair_def)}
  1096     moreover
  1096     moreover
  1097     {assume g1:"?g>1" hence g0: "?g > 0" by simp
  1097     {assume g1:"?g>1" hence g0: "?g > 0" by simp
  1098       from g1 nnz have gp0: "?g' \<noteq> 0" by simp
  1098       from g1 nnz have gp0: "?g' \<noteq> 0" by simp
  1099       hence g'p: "?g' > 0" using int_gcd_ge_0[where x="n" and y="numgcd ?t'"] by arith
  1099       hence g'p: "?g' > 0" using gcd_ge_0_int[where x="n" and y="numgcd ?t'"] by arith
  1100       hence "?g'= 1 \<or> ?g' > 1" by arith
  1100       hence "?g'= 1 \<or> ?g' > 1" by arith
  1101       moreover {assume "?g'=1" hence ?thesis using prems 
  1101       moreover {assume "?g'=1" hence ?thesis using prems 
  1102 	  by (auto simp add: Let_def simp_num_pair_def)}
  1102 	  by (auto simp add: Let_def simp_num_pair_def)}
  1103       moreover {assume g'1:"?g'>1"
  1103       moreover {assume g'1:"?g'>1"
  1104 	have gpdg: "?g' dvd ?g" by simp
  1104 	have gpdg: "?g' dvd ?g" by simp
  1231   let ?g' = "gcd d ?g"
  1231   let ?g' = "gcd d ?g"
  1232   {assume "\<not> ?g > 1" hence ?thesis by (simp add: Let_def simpdvd_def)}
  1232   {assume "\<not> ?g > 1" hence ?thesis by (simp add: Let_def simpdvd_def)}
  1233   moreover
  1233   moreover
  1234   {assume g1:"?g>1" hence g0: "?g > 0" by simp
  1234   {assume g1:"?g>1" hence g0: "?g > 0" by simp
  1235     from g1 dnz have gp0: "?g' \<noteq> 0" by simp
  1235     from g1 dnz have gp0: "?g' \<noteq> 0" by simp
  1236     hence g'p: "?g' > 0" using int_gcd_ge_0[where x="d" and y="numgcd t"] by arith
  1236     hence g'p: "?g' > 0" using gcd_ge_0_int[where x="d" and y="numgcd t"] by arith
  1237     hence "?g'= 1 \<or> ?g' > 1" by arith
  1237     hence "?g'= 1 \<or> ?g' > 1" by arith
  1238     moreover {assume "?g'=1" hence ?thesis by (simp add: Let_def simpdvd_def)}
  1238     moreover {assume "?g'=1" hence ?thesis by (simp add: Let_def simpdvd_def)}
  1239     moreover {assume g'1:"?g'>1"
  1239     moreover {assume g'1:"?g'>1"
  1240       from dvdnumcoeff_aux2[OF g1] have th1:"dvdnumcoeff t ?g" ..
  1240       from dvdnumcoeff_aux2[OF g1] have th1:"dvdnumcoeff t ?g" ..
  1241       let ?tt = "reducecoeffh t ?g'"
  1241       let ?tt = "reducecoeffh t ?g'"
  2124   shows "d\<delta> p (\<delta> p) \<and> \<delta> p >0"
  2124   shows "d\<delta> p (\<delta> p) \<and> \<delta> p >0"
  2125 using lin
  2125 using lin
  2126 proof (induct p rule: iszlfm.induct)
  2126 proof (induct p rule: iszlfm.induct)
  2127   case (1 p q) 
  2127   case (1 p q) 
  2128   let ?d = "\<delta> (And p q)"
  2128   let ?d = "\<delta> (And p q)"
  2129   from prems int_lcm_pos have dp: "?d >0" by simp
  2129   from prems lcm_pos_int have dp: "?d >0" by simp
  2130   have d1: "\<delta> p dvd \<delta> (And p q)" using prems by simp 
  2130   have d1: "\<delta> p dvd \<delta> (And p q)" using prems by simp 
  2131    hence th: "d\<delta> p ?d" 
  2131    hence th: "d\<delta> p ?d" 
  2132      using delta_mono prems by(simp only: iszlfm.simps) blast
  2132      using delta_mono prems by(simp only: iszlfm.simps) blast
  2133   have "\<delta> q dvd \<delta> (And p q)" using prems  by simp 
  2133   have "\<delta> q dvd \<delta> (And p q)" using prems  by simp 
  2134   hence th': "d\<delta> q ?d" using delta_mono prems by(simp only: iszlfm.simps) blast
  2134   hence th': "d\<delta> q ?d" using delta_mono prems by(simp only: iszlfm.simps) blast
  2135   from th th' dp show ?case by simp 
  2135   from th th' dp show ?case by simp 
  2136 next
  2136 next
  2137   case (2 p q)  
  2137   case (2 p q)  
  2138   let ?d = "\<delta> (And p q)"
  2138   let ?d = "\<delta> (And p q)"
  2139   from prems int_lcm_pos have dp: "?d >0" by simp
  2139   from prems lcm_pos_int have dp: "?d >0" by simp
  2140   have "\<delta> p dvd \<delta> (And p q)" using prems by simp hence th: "d\<delta> p ?d" using delta_mono prems 
  2140   have "\<delta> p dvd \<delta> (And p q)" using prems by simp hence th: "d\<delta> p ?d" using delta_mono prems 
  2141     by(simp only: iszlfm.simps) blast
  2141     by(simp only: iszlfm.simps) blast
  2142   have "\<delta> q dvd \<delta> (And p q)" using prems by simp hence th': "d\<delta> q ?d" using delta_mono prems by(simp only: iszlfm.simps) blast
  2142   have "\<delta> q dvd \<delta> (And p q)" using prems by simp hence th': "d\<delta> q ?d" using delta_mono prems by(simp only: iszlfm.simps) blast
  2143   from th th' dp show ?case by simp
  2143   from th th' dp show ?case by simp
  2144 qed simp_all
  2144 qed simp_all
  2512   case (1 p q)
  2512   case (1 p q)
  2513   from prems have dl1: "\<zeta> p dvd lcm (\<zeta> p) (\<zeta> q)" by simp
  2513   from prems have dl1: "\<zeta> p dvd lcm (\<zeta> p) (\<zeta> q)" by simp
  2514   from prems have dl2: "\<zeta> q dvd lcm (\<zeta> p) (\<zeta> q)" by simp
  2514   from prems have dl2: "\<zeta> q dvd lcm (\<zeta> p) (\<zeta> q)" by simp
  2515   from prems d\<beta>_mono[where p = "p" and l="\<zeta> p" and l'="lcm (\<zeta> p) (\<zeta> q)"] 
  2515   from prems d\<beta>_mono[where p = "p" and l="\<zeta> p" and l'="lcm (\<zeta> p) (\<zeta> q)"] 
  2516     d\<beta>_mono[where p = "q" and l="\<zeta> q" and l'="lcm (\<zeta> p) (\<zeta> q)"] 
  2516     d\<beta>_mono[where p = "q" and l="\<zeta> q" and l'="lcm (\<zeta> p) (\<zeta> q)"] 
  2517     dl1 dl2 show ?case by (auto simp add: int_lcm_pos)
  2517     dl1 dl2 show ?case by (auto simp add: lcm_pos_int)
  2518 next
  2518 next
  2519   case (2 p q)
  2519   case (2 p q)
  2520   from prems have dl1: "\<zeta> p dvd lcm (\<zeta> p) (\<zeta> q)" by simp
  2520   from prems have dl1: "\<zeta> p dvd lcm (\<zeta> p) (\<zeta> q)" by simp
  2521   from prems have dl2: "\<zeta> q dvd lcm (\<zeta> p) (\<zeta> q)" by simp
  2521   from prems have dl2: "\<zeta> q dvd lcm (\<zeta> p) (\<zeta> q)" by simp
  2522   from prems d\<beta>_mono[where p = "p" and l="\<zeta> p" and l'="lcm (\<zeta> p) (\<zeta> q)"] 
  2522   from prems d\<beta>_mono[where p = "p" and l="\<zeta> p" and l'="lcm (\<zeta> p) (\<zeta> q)"] 
  2523     d\<beta>_mono[where p = "q" and l="\<zeta> q" and l'="lcm (\<zeta> p) (\<zeta> q)"] 
  2523     d\<beta>_mono[where p = "q" and l="\<zeta> q" and l'="lcm (\<zeta> p) (\<zeta> q)"] 
  2524     dl1 dl2 show ?case by (auto simp add: int_lcm_pos)
  2524     dl1 dl2 show ?case by (auto simp add: lcm_pos_int)
  2525 qed (auto simp add: int_lcm_pos)
  2525 qed (auto simp add: lcm_pos_int)
  2526 
  2526 
  2527 lemma a\<beta>: assumes linp: "iszlfm p (a #bs)" and d: "d\<beta> p l" and lp: "l > 0"
  2527 lemma a\<beta>: assumes linp: "iszlfm p (a #bs)" and d: "d\<beta> p l" and lp: "l > 0"
  2528   shows "iszlfm (a\<beta> p l) (a #bs) \<and> d\<beta> (a\<beta> p l) 1 \<and> (Ifm (real (l * x) #bs) (a\<beta> p l) = Ifm ((real x)#bs) p)"
  2528   shows "iszlfm (a\<beta> p l) (a #bs) \<and> d\<beta> (a\<beta> p l) 1 \<and> (Ifm (real (l * x) #bs) (a\<beta> p l) = Ifm ((real x)#bs) p)"
  2529 using linp d
  2529 using linp d
  2530 proof (induct p rule: iszlfm.induct)
  2530 proof (induct p rule: iszlfm.induct)
  4173 
  4173 
  4174 lemma bound0at_l : "\<lbrakk>isatom p ; bound0 p\<rbrakk> \<Longrightarrow> isrlfm p"
  4174 lemma bound0at_l : "\<lbrakk>isatom p ; bound0 p\<rbrakk> \<Longrightarrow> isrlfm p"
  4175   by (induct p rule: isrlfm.induct, auto)
  4175   by (induct p rule: isrlfm.induct, auto)
  4176 lemma zgcd_le1: assumes ip: "(0::int) < i" shows "gcd i j \<le> i"
  4176 lemma zgcd_le1: assumes ip: "(0::int) < i" shows "gcd i j \<le> i"
  4177 proof-
  4177 proof-
  4178   from int_gcd_dvd1 have th: "gcd i j dvd i" by blast
  4178   from gcd_dvd1_int have th: "gcd i j dvd i" by blast
  4179   from zdvd_imp_le[OF th ip] show ?thesis .
  4179   from zdvd_imp_le[OF th ip] show ?thesis .
  4180 qed
  4180 qed
  4181 
  4181 
  4182 
  4182 
  4183 lemma simpfm_rl: "isrlfm p \<Longrightarrow> isrlfm (simpfm p)"
  4183 lemma simpfm_rl: "isrlfm p \<Longrightarrow> isrlfm (simpfm p)"