equal
deleted
inserted
replaced
1 (* Title: HOL/Semiring_Normalization.thy |
1 (* Title: HOL/Semiring_Normalization.thy |
2 Author: Amine Chaieb, TU Muenchen |
2 Author: Amine Chaieb, TU Muenchen |
3 *) |
3 *) |
4 |
4 |
5 section {* Semiring normalization *} |
5 section \<open>Semiring normalization\<close> |
6 |
6 |
7 theory Semiring_Normalization |
7 theory Semiring_Normalization |
8 imports Numeral_Simprocs Nat_Transfer |
8 imports Numeral_Simprocs Nat_Transfer |
9 begin |
9 begin |
10 |
10 |
11 text {* Prelude *} |
11 text \<open>Prelude\<close> |
12 |
12 |
13 class comm_semiring_1_cancel_crossproduct = comm_semiring_1_cancel + |
13 class comm_semiring_1_cancel_crossproduct = comm_semiring_1_cancel + |
14 assumes crossproduct_eq: "w * y + x * z = w * z + x * y \<longleftrightarrow> w = x \<or> y = z" |
14 assumes crossproduct_eq: "w * y + x * z = w * z + x * y \<longleftrightarrow> w = x \<or> y = z" |
15 begin |
15 begin |
16 |
16 |
55 proof - |
55 proof - |
56 fix y z :: nat |
56 fix y z :: nat |
57 assume "y < z" then have "\<exists>k. z = y + k \<and> k \<noteq> 0" by (intro exI [of _ "z - y"]) auto |
57 assume "y < z" then have "\<exists>k. z = y + k \<and> k \<noteq> 0" by (intro exI [of _ "z - y"]) auto |
58 then obtain k where "z = y + k" and "k \<noteq> 0" by blast |
58 then obtain k where "z = y + k" and "k \<noteq> 0" by blast |
59 assume "w * y + x * z = w * z + x * y" |
59 assume "w * y + x * z = w * z + x * y" |
60 then have "(w * y + x * y) + x * k = (w * y + x * y) + w * k" by (simp add: `z = y + k` algebra_simps) |
60 then have "(w * y + x * y) + x * k = (w * y + x * y) + w * k" by (simp add: \<open>z = y + k\<close> algebra_simps) |
61 then have "x * k = w * k" by simp |
61 then have "x * k = w * k" by simp |
62 then show "w = x" using `k \<noteq> 0` by simp |
62 then show "w = x" using \<open>k \<noteq> 0\<close> by simp |
63 qed |
63 qed |
64 show "w * y + x * z = w * z + x * y \<longleftrightarrow> w = x \<or> y = z" |
64 show "w * y + x * z = w * z + x * y \<longleftrightarrow> w = x \<or> y = z" |
65 by (auto simp add: neq_iff dest!: aux) |
65 by (auto simp add: neq_iff dest!: aux) |
66 qed |
66 qed |
67 |
67 |
68 text {* Semiring normalization proper *} |
68 text \<open>Semiring normalization proper\<close> |
69 |
69 |
70 ML_file "Tools/semiring_normalizer.ML" |
70 ML_file "Tools/semiring_normalizer.ML" |
71 |
71 |
72 context comm_semiring_1 |
72 context comm_semiring_1 |
73 begin |
73 begin |