src/HOL/Decision_Procs/MIR.thy
changeset 61610 4f54d2759a0b
parent 61609 77b453bd616f
parent 61586 5197a2ecb658
child 61649 268d88ec9087
equal deleted inserted replaced
61609:77b453bd616f 61610:4f54d2759a0b
     5 theory MIR
     5 theory MIR
     6 imports Complex_Main Dense_Linear_Order DP_Library
     6 imports Complex_Main Dense_Linear_Order DP_Library
     7   "~~/src/HOL/Library/Code_Target_Numeral" "~~/src/HOL/Library/Old_Recdef"
     7   "~~/src/HOL/Library/Code_Target_Numeral" "~~/src/HOL/Library/Old_Recdef"
     8 begin
     8 begin
     9 
     9 
    10 section \<open>Quantifier elimination for @{text "\<real> (0, 1, +, floor, <)"}\<close>
    10 section \<open>Quantifier elimination for \<open>\<real> (0, 1, +, floor, <)\<close>\<close>
    11 
    11 
    12 declare of_int_floor_cancel [simp del]
    12 declare of_int_floor_cancel [simp del]
    13 
    13 
    14 lemma myle:
    14 lemma myle:
    15   fixes a b :: "'a::{ordered_ab_group_add}"
    15   fixes a b :: "'a::{ordered_ab_group_add}"
  1426   shows "\<And> bs. qfree (qelim p qe) \<and> (Ifm bs (qelim p qe) = Ifm bs p)"
  1426   shows "\<And> bs. qfree (qelim p qe) \<and> (Ifm bs (qelim p qe) = Ifm bs p)"
  1427   using qe_inv DJ_qe[OF CJNB_qe[OF qe_inv]] 
  1427   using qe_inv DJ_qe[OF CJNB_qe[OF qe_inv]] 
  1428   by (induct p rule: qelim.induct) (auto simp del: simpfm.simps)
  1428   by (induct p rule: qelim.induct) (auto simp del: simpfm.simps)
  1429 
  1429 
  1430 
  1430 
  1431 text \<open>The @{text "\<int>"} Part\<close>
  1431 text \<open>The \<open>\<int>\<close> Part\<close>
  1432 text\<open>Linearity for fm where Bound 0 ranges over @{text "\<int>"}\<close>
  1432 text\<open>Linearity for fm where Bound 0 ranges over \<open>\<int>\<close>\<close>
  1433 
  1433 
  1434 function zsplit0 :: "num \<Rightarrow> int \<times> num" (* splits the bounded from the unbounded part*) where
  1434 function zsplit0 :: "num \<Rightarrow> int \<times> num" (* splits the bounded from the unbounded part*) where
  1435   "zsplit0 (C c) = (0,C c)"
  1435   "zsplit0 (C c) = (0,C c)"
  1436 | "zsplit0 (Bound n) = (if n=0 then (1, C 0) else (0,Bound n))"
  1436 | "zsplit0 (Bound n) = (if n=0 then (1, C 0) else (0,Bound n))"
  1437 | "zsplit0 (CN n c a) = zsplit0 (Add (Mul c (Bound n)) a)"
  1437 | "zsplit0 (CN n c a) = zsplit0 (Add (Mul c (Bound n)) a)"
  1931         del: of_int_mult) (auto simp add: ac_simps)
  1931         del: of_int_mult) (auto simp add: ac_simps)
  1932     finally have ?case using l jnz by blast }
  1932     finally have ?case using l jnz by blast }
  1933   ultimately show ?case by blast
  1933   ultimately show ?case by blast
  1934 qed auto
  1934 qed auto
  1935 
  1935 
  1936 text\<open>plusinf : Virtual substitution of @{text "+\<infinity>"}
  1936 text\<open>plusinf : Virtual substitution of \<open>+\<infinity>\<close>
  1937        minusinf: Virtual substitution of @{text "-\<infinity>"}
  1937        minusinf: Virtual substitution of \<open>-\<infinity>\<close>
  1938        @{text "\<delta>"} Compute lcm @{text "d| Dvd d  c*x+t \<in> p"}
  1938        \<open>\<delta>\<close> Compute lcm \<open>d| Dvd d  c*x+t \<in> p\<close>
  1939        @{text "d_\<delta>"} checks if a given l divides all the ds above\<close>
  1939        \<open>d_\<delta>\<close> checks if a given l divides all the ds above\<close>
  1940 
  1940 
  1941 fun minusinf:: "fm \<Rightarrow> fm" where
  1941 fun minusinf:: "fm \<Rightarrow> fm" where
  1942   "minusinf (And p q) = conj (minusinf p) (minusinf q)" 
  1942   "minusinf (And p q) = conj (minusinf p) (minusinf q)" 
  1943 | "minusinf (Or p q) = disj (minusinf p) (minusinf q)" 
  1943 | "minusinf (Or p q) = disj (minusinf p) (minusinf q)" 
  1944 | "minusinf (Eq  (CN 0 c e)) = F"
  1944 | "minusinf (Eq  (CN 0 c e)) = F"
  3268 lemma mirror_\<alpha>_\<rho>:   assumes lp: "iszlfm p (a#bs)"
  3268 lemma mirror_\<alpha>_\<rho>:   assumes lp: "iszlfm p (a#bs)"
  3269   shows "(\<lambda> (t,k). (Inum (a#bs) t, k)) ` set (\<alpha>_\<rho> p) = (\<lambda> (t,k). (Inum (a#bs) t,k)) ` set (\<rho> (mirror p))"
  3269   shows "(\<lambda> (t,k). (Inum (a#bs) t, k)) ` set (\<alpha>_\<rho> p) = (\<lambda> (t,k). (Inum (a#bs) t,k)) ` set (\<rho> (mirror p))"
  3270   using lp
  3270   using lp
  3271   by (induct p rule: mirror.induct) (simp_all add: split_def image_Un)
  3271   by (induct p rule: mirror.induct) (simp_all add: split_def image_Un)
  3272   
  3272   
  3273 text \<open>The @{text "\<real>"} part\<close>
  3273 text \<open>The \<open>\<real>\<close> part\<close>
  3274 
  3274 
  3275 text\<open>Linearity for fm where Bound 0 ranges over @{text "\<real>"}\<close>
  3275 text\<open>Linearity for fm where Bound 0 ranges over \<open>\<real>\<close>\<close>
  3276 consts
  3276 consts
  3277   isrlfm :: "fm \<Rightarrow> bool"   (* Linearity test for fm *)
  3277   isrlfm :: "fm \<Rightarrow> bool"   (* Linearity test for fm *)
  3278 recdef isrlfm "measure size"
  3278 recdef isrlfm "measure size"
  3279   "isrlfm (And p q) = (isrlfm p \<and> isrlfm q)" 
  3279   "isrlfm (And p q) = (isrlfm p \<and> isrlfm q)" 
  3280   "isrlfm (Or p q) = (isrlfm p \<and> isrlfm q)" 
  3280   "isrlfm (Or p q) = (isrlfm p \<and> isrlfm q)"