equal
deleted
inserted
replaced
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)" |