src/HOL/ex/Simproc_Tests.thy
author huffman
Wed Nov 16 15:20:27 2011 +0100 (2011-11-16)
changeset 45530 0c4853bb77bf
parent 45464 5a5a6e6c6789
child 46240 933f35c4e126
permissions -rw-r--r--
rewrite integer numeral div/mod simprocs to not return conditional rewrites; add regression tests
huffman@45224
     1
(*  Title:      HOL/ex/Simproc_Tests.thy
huffman@45224
     2
    Author:     Brian Huffman
huffman@45224
     3
*)
huffman@45224
     4
huffman@45224
     5
header {* Testing of arithmetic simprocs *}
huffman@45224
     6
huffman@45224
     7
theory Simproc_Tests
huffman@45462
     8
imports Main
huffman@45224
     9
begin
huffman@45224
    10
huffman@45224
    11
text {*
huffman@45224
    12
  This theory tests the various simprocs defined in
huffman@45224
    13
  @{file "~~/src/HOL/Numeral_Simprocs.thy"}. Many of the tests
huffman@45224
    14
  are derived from commented-out code originally found in
huffman@45224
    15
  @{file "~~/src/HOL/Tools/numeral_simprocs.ML"}.
huffman@45224
    16
*}
huffman@45224
    17
huffman@45224
    18
subsection {* ML bindings *}
huffman@45224
    19
huffman@45224
    20
ML {*
huffman@45224
    21
  fun test ps = CHANGED (asm_simp_tac (HOL_basic_ss addsimprocs ps) 1)
huffman@45224
    22
*}
huffman@45224
    23
huffman@45464
    24
subsection {* Abelian group cancellation simprocs *}
huffman@45464
    25
huffman@45464
    26
notepad begin
huffman@45464
    27
  fix a b c u :: "'a::ab_group_add"
huffman@45464
    28
  {
huffman@45464
    29
    assume "(a + 0) - (b + 0) = u" have "(a + c) - (b + c) = u"
huffman@45464
    30
      by (tactic {* test [@{simproc abel_cancel_sum}] *}) fact
huffman@45464
    31
  next
huffman@45464
    32
    assume "a + 0 = b + 0" have "a + c = b + c"
huffman@45464
    33
      by (tactic {* test [@{simproc abel_cancel_relation}] *}) fact
huffman@45464
    34
  }
huffman@45464
    35
end
huffman@45464
    36
(* TODO: more tests for Groups.abel_cancel_{sum,relation} *)
huffman@45224
    37
huffman@45224
    38
subsection {* @{text int_combine_numerals} *}
huffman@45224
    39
huffman@45464
    40
(* FIXME: int_combine_numerals often unnecessarily regroups addition
huffman@45464
    41
and rewrites subtraction to negation. Ideally it should behave more
huffman@45464
    42
like Groups.abel_cancel_sum, preserving the shape of terms as much as
huffman@45464
    43
possible. *)
huffman@45464
    44
huffman@45435
    45
notepad begin
huffman@45435
    46
  fix a b c d oo uu i j k l u v w x y z :: "'a::number_ring"
huffman@45435
    47
  {
huffman@45464
    48
    assume "a + - b = u" have "(a + c) - (b + c) = u"
huffman@45464
    49
      by (tactic {* test [@{simproc int_combine_numerals}] *}) fact
huffman@45464
    50
  next
huffman@45435
    51
    assume "10 + (2 * l + oo) = uu"
huffman@45435
    52
    have "l + 2 + 2 + 2 + (l + 2) + (oo + 2) = uu"
huffman@45435
    53
      by (tactic {* test [@{simproc int_combine_numerals}] *}) fact
huffman@45435
    54
  next
huffman@45435
    55
    assume "-3 + (i + (j + k)) = y"
huffman@45435
    56
    have "(i + j + 12 + k) - 15 = y"
huffman@45435
    57
      by (tactic {* test [@{simproc int_combine_numerals}] *}) fact
huffman@45435
    58
  next
huffman@45435
    59
    assume "7 + (i + (j + k)) = y"
huffman@45435
    60
    have "(i + j + 12 + k) - 5 = y"
huffman@45435
    61
      by (tactic {* test [@{simproc int_combine_numerals}] *}) fact
huffman@45435
    62
  next
huffman@45435
    63
    assume "-4 * (u * v) + (2 * x + y) = w"
huffman@45435
    64
    have "(2*x - (u*v) + y) - v*3*u = w"
huffman@45435
    65
      by (tactic {* test [@{simproc int_combine_numerals}] *}) fact
huffman@45435
    66
  next
huffman@45437
    67
    assume "2 * x * u * v + y = w"
huffman@45435
    68
    have "(2*x*u*v + (u*v)*4 + y) - v*u*4 = w"
huffman@45435
    69
      by (tactic {* test [@{simproc int_combine_numerals}] *}) fact
huffman@45435
    70
  next
huffman@45435
    71
    assume "3 * (u * v) + (2 * x * u * v + y) = w"
huffman@45435
    72
    have "(2*x*u*v + (u*v)*4 + y) - v*u = w"
huffman@45435
    73
      by (tactic {* test [@{simproc int_combine_numerals}] *}) fact
huffman@45435
    74
  next
huffman@45435
    75
    assume "-3 * (u * v) + (- (x * u * v) + - y) = w"
huffman@45435
    76
    have "u*v - (x*u*v + (u*v)*4 + y) = w"
huffman@45435
    77
      by (tactic {* test [@{simproc int_combine_numerals}] *}) fact
huffman@45435
    78
  next
huffman@45437
    79
    assume "a + - c = d"
huffman@45435
    80
    have "a + -(b+c) + b = d"
huffman@45435
    81
      apply (simp only: minus_add_distrib)
huffman@45435
    82
      by (tactic {* test [@{simproc int_combine_numerals}] *}) fact
huffman@45435
    83
  next
huffman@45435
    84
    assume "-2 * b + (a + - c) = d"
huffman@45435
    85
    have "a + -(b+c) - b = d"
huffman@45435
    86
      apply (simp only: minus_add_distrib)
huffman@45435
    87
      by (tactic {* test [@{simproc int_combine_numerals}] *}) fact
huffman@45435
    88
  next
huffman@45435
    89
    assume "-7 + (i + (j + (k + (- u + - y)))) = z"
huffman@45435
    90
    have "(i + j + -2 + k) - (u + 5 + y) = z"
huffman@45435
    91
      by (tactic {* test [@{simproc int_combine_numerals}] *}) fact
huffman@45435
    92
  next
huffman@45435
    93
    assume "-27 + (i + (j + k)) = y"
huffman@45435
    94
    have "(i + j + -12 + k) - 15 = y"
huffman@45435
    95
      by (tactic {* test [@{simproc int_combine_numerals}] *}) fact
huffman@45435
    96
  next
huffman@45435
    97
    assume "27 + (i + (j + k)) = y"
huffman@45435
    98
    have "(i + j + 12 + k) - -15 = y"
huffman@45435
    99
      by (tactic {* test [@{simproc int_combine_numerals}] *}) fact
huffman@45435
   100
  next
huffman@45435
   101
    assume "3 + (i + (j + k)) = y"
huffman@45435
   102
    have "(i + j + -12 + k) - -15 = y"
huffman@45435
   103
      by (tactic {* test [@{simproc int_combine_numerals}] *}) fact
huffman@45435
   104
  }
huffman@45435
   105
end
huffman@45224
   106
huffman@45224
   107
subsection {* @{text inteq_cancel_numerals} *}
huffman@45224
   108
huffman@45435
   109
notepad begin
huffman@45435
   110
  fix i j k u vv w y z w' y' z' :: "'a::number_ring"
huffman@45435
   111
  {
huffman@45437
   112
    assume "u = 0" have "2*u = u"
huffman@45435
   113
      by (tactic {* test [@{simproc inteq_cancel_numerals}] *}) fact
huffman@45224
   114
(* conclusion matches Rings.ring_1_no_zero_divisors_class.mult_cancel_right2 *)
huffman@45435
   115
  next
huffman@45435
   116
    assume "i + (j + k) = 3 + (u + y)"
huffman@45435
   117
    have "(i + j + 12 + k) = u + 15 + y"
huffman@45435
   118
      by (tactic {* test [@{simproc inteq_cancel_numerals}] *}) fact
huffman@45435
   119
  next
huffman@45435
   120
    assume "7 + (j + (i + k)) = y"
huffman@45435
   121
    have "(i + j*2 + 12 + k) = j + 5 + y"
huffman@45435
   122
      by (tactic {* test [@{simproc inteq_cancel_numerals}] *}) fact
huffman@45435
   123
  next
huffman@45435
   124
    assume "u + (6*z + (4*y + 6*w)) = 6*z' + (4*y' + (6*w' + vv))"
huffman@45435
   125
    have "2*y + 3*z + 6*w + 2*y + 3*z + 2*u = 2*y' + 3*z' + 6*w' + 2*y' + 3*z' + u + vv"
huffman@45435
   126
      by (tactic {* test [@{simproc int_combine_numerals}, @{simproc inteq_cancel_numerals}] *}) fact
huffman@45435
   127
  }
huffman@45435
   128
end
huffman@45224
   129
huffman@45224
   130
subsection {* @{text intless_cancel_numerals} *}
huffman@45224
   131
huffman@45435
   132
notepad begin
huffman@45435
   133
  fix b c i j k u y :: "'a::{linordered_idom,number_ring}"
huffman@45435
   134
  {
huffman@45435
   135
    assume "y < 2 * b" have "y - b < b"
huffman@45435
   136
      by (tactic {* test [@{simproc intless_cancel_numerals}] *}) fact
huffman@45435
   137
  next
huffman@45435
   138
    assume "c + y < 4 * b" have "y - (3*b + c) < b - 2*c"
huffman@45435
   139
      by (tactic {* test [@{simproc intless_cancel_numerals}] *}) fact
huffman@45435
   140
  next
huffman@45435
   141
    assume "i + (j + k) < 8 + (u + y)"
huffman@45435
   142
    have "(i + j + -3 + k) < u + 5 + y"
huffman@45435
   143
      by (tactic {* test [@{simproc intless_cancel_numerals}] *}) fact
huffman@45435
   144
  next
huffman@45435
   145
    assume "9 + (i + (j + k)) < u + y"
huffman@45435
   146
    have "(i + j + 3 + k) < u + -6 + y"
huffman@45435
   147
      by (tactic {* test [@{simproc intless_cancel_numerals}] *}) fact
huffman@45435
   148
  }
huffman@45435
   149
end
huffman@45224
   150
huffman@45224
   151
subsection {* @{text ring_eq_cancel_numeral_factor} *}
huffman@45224
   152
huffman@45435
   153
notepad begin
huffman@45435
   154
  fix x y :: "'a::{idom,ring_char_0,number_ring}"
huffman@45435
   155
  {
huffman@45435
   156
    assume "3*x = 4*y" have "9*x = 12 * y"
huffman@45435
   157
      by (tactic {* test [@{simproc ring_eq_cancel_numeral_factor}] *}) fact
huffman@45435
   158
  next
huffman@45435
   159
    assume "-3*x = 4*y" have "-99*x = 132 * y"
huffman@45435
   160
      by (tactic {* test [@{simproc ring_eq_cancel_numeral_factor}] *}) fact
huffman@45435
   161
  next
huffman@45435
   162
    assume "111*x = -44*y" have "999*x = -396 * y"
huffman@45435
   163
      by (tactic {* test [@{simproc ring_eq_cancel_numeral_factor}] *}) fact
huffman@45435
   164
  next
huffman@45435
   165
    assume "11*x = 9*y" have "-99*x = -81 * y"
huffman@45435
   166
      by (tactic {* test [@{simproc ring_eq_cancel_numeral_factor}] *}) fact
huffman@45435
   167
  next
huffman@45437
   168
    assume "2*x = y" have "-2 * x = -1 * y"
huffman@45435
   169
      by (tactic {* test [@{simproc ring_eq_cancel_numeral_factor}] *}) fact
huffman@45435
   170
  next
huffman@45437
   171
    assume "2*x = y" have "-2 * x = -y"
huffman@45435
   172
      by (tactic {* test [@{simproc ring_eq_cancel_numeral_factor}] *}) fact
huffman@45435
   173
  }
huffman@45435
   174
end
huffman@45224
   175
huffman@45224
   176
subsection {* @{text int_div_cancel_numeral_factors} *}
huffman@45224
   177
huffman@45435
   178
notepad begin
huffman@45435
   179
  fix x y z :: "'a::{semiring_div,ring_char_0,number_ring}"
huffman@45435
   180
  {
huffman@45435
   181
    assume "(3*x) div (4*y) = z" have "(9*x) div (12*y) = z"
huffman@45435
   182
      by (tactic {* test [@{simproc int_div_cancel_numeral_factors}] *}) fact
huffman@45435
   183
  next
huffman@45435
   184
    assume "(-3*x) div (4*y) = z" have "(-99*x) div (132*y) = z"
huffman@45435
   185
      by (tactic {* test [@{simproc int_div_cancel_numeral_factors}] *}) fact
huffman@45435
   186
  next
huffman@45435
   187
    assume "(111*x) div (-44*y) = z" have "(999*x) div (-396*y) = z"
huffman@45435
   188
      by (tactic {* test [@{simproc int_div_cancel_numeral_factors}] *}) fact
huffman@45435
   189
  next
huffman@45435
   190
    assume "(11*x) div (9*y) = z" have "(-99*x) div (-81*y) = z"
huffman@45435
   191
      by (tactic {* test [@{simproc int_div_cancel_numeral_factors}] *}) fact
huffman@45435
   192
  next
huffman@45437
   193
    assume "(2*x) div y = z"
huffman@45435
   194
    have "(-2 * x) div (-1 * y) = z"
huffman@45435
   195
      by (tactic {* test [@{simproc int_div_cancel_numeral_factors}] *}) fact
huffman@45435
   196
  }
huffman@45435
   197
end
huffman@45224
   198
huffman@45224
   199
subsection {* @{text ring_less_cancel_numeral_factor} *}
huffman@45224
   200
huffman@45435
   201
notepad begin
huffman@45435
   202
  fix x y :: "'a::{linordered_idom,number_ring}"
huffman@45435
   203
  {
huffman@45435
   204
    assume "3*x < 4*y" have "9*x < 12 * y"
huffman@45435
   205
      by (tactic {* test [@{simproc ring_less_cancel_numeral_factor}] *}) fact
huffman@45435
   206
  next
huffman@45435
   207
    assume "-3*x < 4*y" have "-99*x < 132 * y"
huffman@45435
   208
      by (tactic {* test [@{simproc ring_less_cancel_numeral_factor}] *}) fact
huffman@45435
   209
  next
huffman@45435
   210
    assume "111*x < -44*y" have "999*x < -396 * y"
huffman@45435
   211
      by (tactic {* test [@{simproc ring_less_cancel_numeral_factor}] *}) fact
huffman@45435
   212
  next
huffman@45435
   213
    assume "9*y < 11*x" have "-99*x < -81 * y"
huffman@45435
   214
      by (tactic {* test [@{simproc ring_less_cancel_numeral_factor}] *}) fact
huffman@45435
   215
  next
huffman@45437
   216
    assume "y < 2*x" have "-2 * x < -y"
huffman@45435
   217
      by (tactic {* test [@{simproc ring_less_cancel_numeral_factor}] *}) fact
huffman@45435
   218
  next
huffman@45437
   219
    assume "23*y < x" have "-x < -23 * y"
huffman@45435
   220
      by (tactic {* test [@{simproc ring_less_cancel_numeral_factor}] *}) fact
huffman@45435
   221
  }
huffman@45435
   222
end
huffman@45224
   223
huffman@45224
   224
subsection {* @{text ring_le_cancel_numeral_factor} *}
huffman@45224
   225
huffman@45435
   226
notepad begin
huffman@45435
   227
  fix x y :: "'a::{linordered_idom,number_ring}"
huffman@45435
   228
  {
huffman@45435
   229
    assume "3*x \<le> 4*y" have "9*x \<le> 12 * y"
huffman@45435
   230
      by (tactic {* test [@{simproc ring_le_cancel_numeral_factor}] *}) fact
huffman@45435
   231
  next
huffman@45435
   232
    assume "-3*x \<le> 4*y" have "-99*x \<le> 132 * y"
huffman@45435
   233
      by (tactic {* test [@{simproc ring_le_cancel_numeral_factor}] *}) fact
huffman@45435
   234
  next
huffman@45435
   235
    assume "111*x \<le> -44*y" have "999*x \<le> -396 * y"
huffman@45435
   236
      by (tactic {* test [@{simproc ring_le_cancel_numeral_factor}] *}) fact
huffman@45435
   237
  next
huffman@45435
   238
    assume "9*y \<le> 11*x" have "-99*x \<le> -81 * y"
huffman@45435
   239
      by (tactic {* test [@{simproc ring_le_cancel_numeral_factor}] *}) fact
huffman@45435
   240
  next
huffman@45437
   241
    assume "y \<le> 2*x" have "-2 * x \<le> -1 * y"
huffman@45435
   242
      by (tactic {* test [@{simproc ring_le_cancel_numeral_factor}] *}) fact
huffman@45435
   243
  next
huffman@45437
   244
    assume "23*y \<le> x" have "-x \<le> -23 * y"
huffman@45435
   245
      by (tactic {* test [@{simproc ring_le_cancel_numeral_factor}] *}) fact
huffman@45435
   246
  next
huffman@45437
   247
    assume "y \<le> 0" have "0 \<le> y * -2"
huffman@45435
   248
      by (tactic {* test [@{simproc ring_le_cancel_numeral_factor}] *}) fact
huffman@45435
   249
  next
huffman@45437
   250
    assume "- x \<le> y" have "- (2 * x) \<le> 2*y"
huffman@45435
   251
      by (tactic {* test [@{simproc ring_le_cancel_numeral_factor}] *}) fact
huffman@45435
   252
  }
huffman@45435
   253
end
huffman@45224
   254
huffman@45285
   255
subsection {* @{text divide_cancel_numeral_factor} *}
huffman@45224
   256
huffman@45435
   257
notepad begin
huffman@45435
   258
  fix x y z :: "'a::{field_inverse_zero,ring_char_0,number_ring}"
huffman@45435
   259
  {
huffman@45435
   260
    assume "(3*x) / (4*y) = z" have "(9*x) / (12 * y) = z"
huffman@45435
   261
      by (tactic {* test [@{simproc divide_cancel_numeral_factor}] *}) fact
huffman@45435
   262
  next
huffman@45435
   263
    assume "(-3*x) / (4*y) = z" have "(-99*x) / (132 * y) = z"
huffman@45435
   264
      by (tactic {* test [@{simproc divide_cancel_numeral_factor}] *}) fact
huffman@45435
   265
  next
huffman@45435
   266
    assume "(111*x) / (-44*y) = z" have "(999*x) / (-396 * y) = z"
huffman@45435
   267
      by (tactic {* test [@{simproc divide_cancel_numeral_factor}] *}) fact
huffman@45435
   268
  next
huffman@45435
   269
    assume "(11*x) / (9*y) = z" have "(-99*x) / (-81 * y) = z"
huffman@45435
   270
      by (tactic {* test [@{simproc divide_cancel_numeral_factor}] *}) fact
huffman@45435
   271
  next
huffman@45437
   272
    assume "(2*x) / y = z" have "(-2 * x) / (-1 * y) = z"
huffman@45435
   273
      by (tactic {* test [@{simproc divide_cancel_numeral_factor}] *}) fact
huffman@45435
   274
  }
huffman@45435
   275
end
huffman@45224
   276
huffman@45224
   277
subsection {* @{text ring_eq_cancel_factor} *}
huffman@45224
   278
huffman@45435
   279
notepad begin
huffman@45435
   280
  fix a b c d k x y :: "'a::idom"
huffman@45435
   281
  {
huffman@45435
   282
    assume "k = 0 \<or> x = y" have "x*k = k*y"
huffman@45435
   283
      by (tactic {* test [@{simproc ring_eq_cancel_factor}] *}) fact
huffman@45435
   284
  next
huffman@45435
   285
    assume "k = 0 \<or> 1 = y" have "k = k*y"
huffman@45435
   286
      by (tactic {* test [@{simproc ring_eq_cancel_factor}] *}) fact
huffman@45435
   287
  next
huffman@45435
   288
    assume "b = 0 \<or> a*c = 1" have "a*(b*c) = b"
huffman@45435
   289
      by (tactic {* test [@{simproc ring_eq_cancel_factor}] *}) fact
huffman@45435
   290
  next
huffman@45435
   291
    assume "a = 0 \<or> b = 0 \<or> c = d*x" have "a*(b*c) = d*b*(x*a)"
huffman@45435
   292
      by (tactic {* test [@{simproc ring_eq_cancel_factor}] *}) fact
huffman@45435
   293
  next
huffman@45435
   294
    assume "k = 0 \<or> x = y" have "x*k = k*y"
huffman@45435
   295
      by (tactic {* test [@{simproc ring_eq_cancel_factor}] *}) fact
huffman@45435
   296
  next
huffman@45435
   297
    assume "k = 0 \<or> 1 = y" have "k = k*y"
huffman@45435
   298
      by (tactic {* test [@{simproc ring_eq_cancel_factor}] *}) fact
huffman@45435
   299
  }
huffman@45435
   300
end
huffman@45224
   301
huffman@45224
   302
subsection {* @{text int_div_cancel_factor} *}
huffman@45224
   303
huffman@45435
   304
notepad begin
huffman@45435
   305
  fix a b c d k uu x y :: "'a::semiring_div"
huffman@45435
   306
  {
huffman@45435
   307
    assume "(if k = 0 then 0 else x div y) = uu"
huffman@45435
   308
    have "(x*k) div (k*y) = uu"
huffman@45435
   309
      by (tactic {* test [@{simproc int_div_cancel_factor}] *}) fact
huffman@45435
   310
  next
huffman@45435
   311
    assume "(if k = 0 then 0 else 1 div y) = uu"
huffman@45435
   312
    have "(k) div (k*y) = uu"
huffman@45435
   313
      by (tactic {* test [@{simproc int_div_cancel_factor}] *}) fact
huffman@45435
   314
  next
huffman@45435
   315
    assume "(if b = 0 then 0 else a * c) = uu"
huffman@45435
   316
    have "(a*(b*c)) div b = uu"
huffman@45435
   317
      by (tactic {* test [@{simproc int_div_cancel_factor}] *}) fact
huffman@45435
   318
  next
huffman@45435
   319
    assume "(if a = 0 then 0 else if b = 0 then 0 else c div (d * x)) = uu"
huffman@45435
   320
    have "(a*(b*c)) div (d*b*(x*a)) = uu"
huffman@45435
   321
      by (tactic {* test [@{simproc int_div_cancel_factor}] *}) fact
huffman@45435
   322
  }
huffman@45435
   323
end
huffman@45224
   324
huffman@45224
   325
subsection {* @{text divide_cancel_factor} *}
huffman@45224
   326
huffman@45435
   327
notepad begin
huffman@45435
   328
  fix a b c d k uu x y :: "'a::field_inverse_zero"
huffman@45435
   329
  {
huffman@45435
   330
    assume "(if k = 0 then 0 else x / y) = uu"
huffman@45435
   331
    have "(x*k) / (k*y) = uu"
huffman@45435
   332
      by (tactic {* test [@{simproc divide_cancel_factor}] *}) fact
huffman@45435
   333
  next
huffman@45435
   334
    assume "(if k = 0 then 0 else 1 / y) = uu"
huffman@45435
   335
    have "(k) / (k*y) = uu"
huffman@45435
   336
      by (tactic {* test [@{simproc divide_cancel_factor}] *}) fact
huffman@45435
   337
  next
huffman@45435
   338
    assume "(if b = 0 then 0 else a * c / 1) = uu"
huffman@45435
   339
    have "(a*(b*c)) / b = uu"
huffman@45435
   340
      by (tactic {* test [@{simproc divide_cancel_factor}] *}) fact
huffman@45435
   341
  next
huffman@45435
   342
    assume "(if a = 0 then 0 else if b = 0 then 0 else c / (d * x)) = uu"
huffman@45435
   343
    have "(a*(b*c)) / (d*b*(x*a)) = uu"
huffman@45435
   344
      by (tactic {* test [@{simproc divide_cancel_factor}] *}) fact
huffman@45435
   345
  }
huffman@45435
   346
end
huffman@45224
   347
huffman@45462
   348
lemma
huffman@45462
   349
  fixes a b c d x y z :: "'a::linordered_field_inverse_zero"
huffman@45462
   350
  shows "a*(b*c)/(y*z) = d*(b)*(x*a)/z"
huffman@45224
   351
oops -- "FIXME: need simproc to cover this case"
huffman@45224
   352
huffman@45224
   353
subsection {* @{text linordered_ring_less_cancel_factor} *}
huffman@45224
   354
huffman@45435
   355
notepad begin
huffman@45435
   356
  fix x y z :: "'a::linordered_idom"
huffman@45435
   357
  {
huffman@45435
   358
    assume "0 < z \<Longrightarrow> x < y" have "0 < z \<Longrightarrow> x*z < y*z"
huffman@45435
   359
      by (tactic {* test [@{simproc linordered_ring_less_cancel_factor}] *}) fact
huffman@45435
   360
  next
huffman@45435
   361
    assume "0 < z \<Longrightarrow> x < y" have "0 < z \<Longrightarrow> x*z < z*y"
huffman@45435
   362
      by (tactic {* test [@{simproc linordered_ring_less_cancel_factor}] *}) fact
huffman@45435
   363
  next
huffman@45435
   364
    assume "0 < z \<Longrightarrow> x < y" have "0 < z \<Longrightarrow> z*x < y*z"
huffman@45435
   365
      by (tactic {* test [@{simproc linordered_ring_less_cancel_factor}] *}) fact
huffman@45435
   366
  next
huffman@45435
   367
    assume "0 < z \<Longrightarrow> x < y" have "0 < z \<Longrightarrow> z*x < z*y"
huffman@45435
   368
      by (tactic {* test [@{simproc linordered_ring_less_cancel_factor}] *}) fact
huffman@45435
   369
  }
huffman@45435
   370
end
huffman@45224
   371
huffman@45224
   372
subsection {* @{text linordered_ring_le_cancel_factor} *}
huffman@45224
   373
huffman@45435
   374
notepad begin
huffman@45435
   375
  fix x y z :: "'a::linordered_idom"
huffman@45435
   376
  {
huffman@45435
   377
    assume "0 < z \<Longrightarrow> x \<le> y" have "0 < z \<Longrightarrow> x*z \<le> y*z"
huffman@45435
   378
      by (tactic {* test [@{simproc linordered_ring_le_cancel_factor}] *}) fact
huffman@45435
   379
  next
huffman@45435
   380
    assume "0 < z \<Longrightarrow> x \<le> y" have "0 < z \<Longrightarrow> z*x \<le> z*y"
huffman@45435
   381
      by (tactic {* test [@{simproc linordered_ring_le_cancel_factor}] *}) fact
huffman@45435
   382
  }
huffman@45435
   383
end
huffman@45224
   384
huffman@45224
   385
subsection {* @{text field_combine_numerals} *}
huffman@45224
   386
huffman@45435
   387
notepad begin
huffman@45437
   388
  fix x y z uu :: "'a::{field_inverse_zero,ring_char_0,number_ring}"
huffman@45435
   389
  {
huffman@45435
   390
    assume "5 / 6 * x = uu" have "x / 2 + x / 3 = uu"
huffman@45435
   391
      by (tactic {* test [@{simproc field_combine_numerals}] *}) fact
huffman@45435
   392
  next
huffman@45435
   393
    assume "6 / 9 * x + y = uu" have "x / 3 + y + x / 3 = uu"
huffman@45435
   394
      by (tactic {* test [@{simproc field_combine_numerals}] *}) fact
huffman@45435
   395
  next
huffman@45435
   396
    assume "9 / 9 * x = uu" have "2 * x / 3 + x / 3 = uu"
huffman@45435
   397
      by (tactic {* test [@{simproc field_combine_numerals}] *}) fact
huffman@45437
   398
  next
huffman@45437
   399
    assume "y + z = uu"
huffman@45437
   400
    have "x / 2 + y - 3 * x / 6 + z = uu"
huffman@45437
   401
      by (tactic {* test [@{simproc field_combine_numerals}] *}) fact
huffman@45437
   402
  next
huffman@45437
   403
    assume "1 / 15 * x + y = uu"
huffman@45437
   404
    have "7 * x / 5 + y - 4 * x / 3 = uu"
huffman@45437
   405
      by (tactic {* test [@{simproc field_combine_numerals}] *}) fact
huffman@45435
   406
  }
huffman@45435
   407
end
huffman@45224
   408
huffman@45462
   409
lemma
huffman@45462
   410
  fixes x :: "'a::{linordered_field_inverse_zero,number_ring}"
huffman@45462
   411
  shows "2/3 * x + x / 3 = uu"
huffman@45284
   412
apply (tactic {* test [@{simproc field_combine_numerals}] *})?
huffman@45224
   413
oops -- "FIXME: test fails"
huffman@45224
   414
huffman@45462
   415
subsection {* @{text nat_combine_numerals} *}
huffman@45462
   416
huffman@45462
   417
notepad begin
huffman@45462
   418
  fix i j k m n u :: nat
huffman@45462
   419
  {
huffman@45462
   420
    assume "4*k = u" have "k + 3*k = u"
huffman@45462
   421
      by (tactic {* test [@{simproc nat_combine_numerals}] *}) fact
huffman@45462
   422
  next
huffman@45530
   423
    (* FIXME "Suc (i + 3) \<equiv> i + 4" *)
huffman@45462
   424
    assume "4 * Suc 0 + i = u" have "Suc (i + 3) = u"
huffman@45462
   425
      by (tactic {* test [@{simproc nat_combine_numerals}] *}) fact
huffman@45462
   426
  next
huffman@45530
   427
    (* FIXME "Suc (i + j + 3 + k) \<equiv> i + j + 4 + k" *)
huffman@45462
   428
    assume "4 * Suc 0 + (i + (j + k)) = u" have "Suc (i + j + 3 + k) = u"
huffman@45462
   429
      by (tactic {* test [@{simproc nat_combine_numerals}] *}) fact
huffman@45462
   430
  next
huffman@45462
   431
    assume "2 * j + 4 * k = u" have "k + j + 3*k + j = u"
huffman@45462
   432
      by (tactic {* test [@{simproc nat_combine_numerals}] *}) fact
huffman@45462
   433
  next
huffman@45462
   434
    assume "6 * Suc 0 + (5 * (i * j) + (4 * k + i)) = u"
huffman@45462
   435
    have "Suc (j*i + i + k + 5 + 3*k + i*j*4) = u"
huffman@45462
   436
      by (tactic {* test [@{simproc nat_combine_numerals}] *}) fact
huffman@45462
   437
  next
huffman@45462
   438
    assume "5 * (m * n) = u" have "(2*n*m) + (3*(m*n)) = u"
huffman@45462
   439
      by (tactic {* test [@{simproc nat_combine_numerals}] *}) fact
huffman@45462
   440
  }
huffman@45462
   441
end
huffman@45462
   442
huffman@45462
   443
(*negative numerals: FAIL*)
huffman@45462
   444
lemma "Suc (i + j + -3 + k) = u"
huffman@45462
   445
apply (tactic {* test [@{simproc nat_combine_numerals}] *})?
huffman@45462
   446
oops
huffman@45462
   447
huffman@45436
   448
subsection {* @{text nateq_cancel_numerals} *}
huffman@45436
   449
huffman@45436
   450
notepad begin
huffman@45436
   451
  fix i j k l oo u uu vv w y z w' y' z' :: "nat"
huffman@45436
   452
  {
huffman@45462
   453
    assume "Suc 0 * u = 0" have "2*u = u"
huffman@45436
   454
      by (tactic {* test [@{simproc nateq_cancel_numerals}] *}) fact
huffman@45436
   455
  next
huffman@45436
   456
    assume "Suc 0 * u = Suc 0" have "2*u = Suc (u)"
huffman@45436
   457
      by (tactic {* test [@{simproc nateq_cancel_numerals}] *}) fact
huffman@45436
   458
  next
huffman@45436
   459
    assume "i + (j + k) = 3 * Suc 0 + (u + y)"
huffman@45436
   460
    have "(i + j + 12 + k) = u + 15 + y"
huffman@45436
   461
      by (tactic {* test [@{simproc nateq_cancel_numerals}] *}) fact
huffman@45436
   462
  next
huffman@45436
   463
    assume "7 * Suc 0 + (i + (j + k)) = u + y"
huffman@45436
   464
    have "(i + j + 12 + k) = u + 5 + y"
huffman@45436
   465
      by (tactic {* test [@{simproc nateq_cancel_numerals}] *}) fact
huffman@45436
   466
  next
huffman@45436
   467
    assume "11 * Suc 0 + (i + (j + k)) = u + y"
huffman@45436
   468
    have "(i + j + 12 + k) = Suc (u + y)"
huffman@45436
   469
      by (tactic {* test [@{simproc nateq_cancel_numerals}] *}) fact
huffman@45436
   470
  next
huffman@45436
   471
    assume "i + (j + k) = 2 * Suc 0 + (u + y)"
huffman@45436
   472
    have "(i + j + 5 + k) = Suc (Suc (Suc (Suc (Suc (Suc (Suc (u + y)))))))"
huffman@45436
   473
      by (tactic {* test [@{simproc nateq_cancel_numerals}] *}) fact
huffman@45436
   474
  next
huffman@45436
   475
    assume "Suc 0 * u + (2 * y + 3 * z) = Suc 0"
huffman@45436
   476
    have "2*y + 3*z + 2*u = Suc (u)"
huffman@45436
   477
      by (tactic {* test [@{simproc nateq_cancel_numerals}] *}) fact
huffman@45436
   478
  next
huffman@45436
   479
    assume "Suc 0 * u + (2 * y + (3 * z + (6 * w + (2 * y + 3 * z)))) = Suc 0"
huffman@45436
   480
    have "2*y + 3*z + 6*w + 2*y + 3*z + 2*u = Suc (u)"
huffman@45436
   481
      by (tactic {* test [@{simproc nateq_cancel_numerals}] *}) fact
huffman@45436
   482
  next
huffman@45436
   483
    assume "Suc 0 * u + (2 * y + (3 * z + (6 * w + (2 * y + 3 * z)))) =
huffman@45436
   484
      2 * y' + (3 * z' + (6 * w' + (2 * y' + (3 * z' + vv))))"
huffman@45436
   485
    have "2*y + 3*z + 6*w + 2*y + 3*z + 2*u =
huffman@45436
   486
      2*y' + 3*z' + 6*w' + 2*y' + 3*z' + u + vv"
huffman@45436
   487
      by (tactic {* test [@{simproc nateq_cancel_numerals}] *}) fact
huffman@45436
   488
  next
huffman@45436
   489
    assume "2 * u + (2 * z + (5 * Suc 0 + 2 * y)) = vv"
huffman@45436
   490
    have "6 + 2*y + 3*z + 4*u = Suc (vv + 2*u + z)"
huffman@45436
   491
      by (tactic {* test [@{simproc nateq_cancel_numerals}] *}) fact
huffman@45436
   492
  }
huffman@45224
   493
end
huffman@45436
   494
huffman@45436
   495
subsection {* @{text natless_cancel_numerals} *}
huffman@45436
   496
huffman@45436
   497
notepad begin
huffman@45436
   498
  fix length :: "'a \<Rightarrow> nat" and l1 l2 xs :: "'a" and f :: "nat \<Rightarrow> 'a"
huffman@45436
   499
  fix c i j k l oo u uu vv w y z w' y' z' :: "nat"
huffman@45436
   500
  {
huffman@45436
   501
    assume "0 < j" have "(2*length xs < 2*length xs + j)"
huffman@45436
   502
      by (tactic {* test [@{simproc natless_cancel_numerals}] *}) fact
huffman@45436
   503
  next
huffman@45436
   504
    assume "0 < j" have "(2*length xs < length xs * 2 + j)"
huffman@45436
   505
      by (tactic {* test [@{simproc natless_cancel_numerals}] *}) fact
huffman@45436
   506
  next
huffman@45436
   507
    assume "i + (j + k) < u + y"
huffman@45436
   508
    have "(i + j + 5 + k) < Suc (Suc (Suc (Suc (Suc (u + y)))))"
huffman@45436
   509
      by (tactic {* test [@{simproc natless_cancel_numerals}] *}) fact
huffman@45436
   510
  next
huffman@45436
   511
    assume "0 < Suc 0 * (m * n) + u" have "(2*n*m) < (3*(m*n)) + u"
huffman@45436
   512
      by (tactic {* test [@{simproc natless_cancel_numerals}] *}) fact
huffman@45436
   513
  next
huffman@45436
   514
    (* FIXME: negative numerals fail
huffman@45436
   515
    have "(i + j + -23 + (k::nat)) < u + 15 + y"
huffman@45436
   516
      apply (tactic {* test [@{simproc natless_cancel_numerals}] *})?
huffman@45436
   517
      sorry
huffman@45436
   518
    have "(i + j + 3 + (k::nat)) < u + -15 + y"
huffman@45436
   519
      apply (tactic {* test [@{simproc natless_cancel_numerals}] *})?
huffman@45436
   520
      sorry*)
huffman@45436
   521
  }
huffman@45436
   522
end
huffman@45436
   523
huffman@45436
   524
subsection {* @{text natle_cancel_numerals} *}
huffman@45436
   525
huffman@45436
   526
notepad begin
huffman@45436
   527
  fix length :: "'a \<Rightarrow> nat" and l2 l3 :: "'a" and f :: "nat \<Rightarrow> 'a"
huffman@45436
   528
  fix c e i j k l oo u uu vv w y z w' y' z' :: "nat"
huffman@45436
   529
  {
huffman@45436
   530
    assume "u + y \<le> 36 * Suc 0 + (i + (j + k))"
huffman@45436
   531
    have "Suc (Suc (Suc (Suc (Suc (u + y))))) \<le> ((i + j) + 41 + k)"
huffman@45436
   532
      by (tactic {* test [@{simproc natle_cancel_numerals}] *}) fact
huffman@45436
   533
  next
huffman@45436
   534
    assume "5 * Suc 0 + (case length (f c) of 0 \<Rightarrow> 0 | Suc k \<Rightarrow> k) = 0"
huffman@45436
   535
    have "(Suc (Suc (Suc (Suc (Suc (Suc (case length (f c) of 0 => 0 | Suc k => k)))))) \<le> Suc 0)"
huffman@45436
   536
      by (tactic {* test [@{simproc natle_cancel_numerals}] *}) fact
huffman@45436
   537
  next
huffman@45436
   538
    assume "6 + length l2 = 0" have "Suc (Suc (Suc (Suc (Suc (Suc (length l1 + length l2)))))) \<le> length l1"
huffman@45436
   539
      by (tactic {* test [@{simproc natle_cancel_numerals}] *}) fact
huffman@45436
   540
  next
huffman@45436
   541
    assume "5 + length l3 = 0"
huffman@45436
   542
    have "( (Suc (Suc (Suc (Suc (Suc (length (compT P E A ST mxr e) + length l3)))))) \<le> length (compT P E A ST mxr e))"
huffman@45436
   543
      by (tactic {* test [@{simproc natle_cancel_numerals}] *}) fact
huffman@45436
   544
  next
huffman@45436
   545
    assume "5 + length (compT P E (A \<union> A' e) ST mxr c) = 0"
huffman@45436
   546
    have "( (Suc (Suc (Suc (Suc (Suc (length (compT P E A ST mxr e) + length (compT P E (A Un A' e) ST mxr c))))))) \<le> length (compT P E A ST mxr e))"
huffman@45436
   547
      by (tactic {* test [@{simproc natle_cancel_numerals}] *}) fact
huffman@45436
   548
  }
huffman@45436
   549
end
huffman@45436
   550
huffman@45436
   551
subsection {* @{text natdiff_cancel_numerals} *}
huffman@45436
   552
huffman@45436
   553
notepad begin
huffman@45436
   554
  fix length :: "'a \<Rightarrow> nat" and l2 l3 :: "'a" and f :: "nat \<Rightarrow> 'a"
huffman@45436
   555
  fix c e i j k l oo u uu vv v w x y z zz w' y' z' :: "nat"
huffman@45436
   556
  {
huffman@45436
   557
    assume "i + (j + k) - 3 * Suc 0 = y" have "(i + j + 12 + k) - 15 = y"
huffman@45436
   558
      by (tactic {* test [@{simproc natdiff_cancel_numerals}] *}) fact
huffman@45436
   559
  next
huffman@45436
   560
    assume "7 * Suc 0 + (i + (j + k)) - 0 = y" have "(i + j + 12 + k) - 5 = y"
huffman@45436
   561
      by (tactic {* test [@{simproc natdiff_cancel_numerals}] *}) fact
huffman@45436
   562
  next
huffman@45436
   563
    assume "u - Suc 0 * Suc 0 = y" have "Suc u - 2 = y"
huffman@45436
   564
      by (tactic {* test [@{simproc natdiff_cancel_numerals}] *}) fact
huffman@45436
   565
  next
huffman@45436
   566
    assume "Suc 0 * Suc 0 + u - 0 = y" have "Suc (Suc (Suc u)) - 2 = y"
huffman@45436
   567
      by (tactic {* test [@{simproc natdiff_cancel_numerals}] *}) fact
huffman@45436
   568
  next
huffman@45436
   569
    assume "Suc 0 * Suc 0 + (i + (j + k)) - 0 = y"
huffman@45436
   570
    have "(i + j + 2 + k) - 1 = y"
huffman@45436
   571
      by (tactic {* test [@{simproc natdiff_cancel_numerals}] *}) fact
huffman@45436
   572
  next
huffman@45436
   573
    assume "i + (j + k) - Suc 0 * Suc 0 = y"
huffman@45436
   574
    have "(i + j + 1 + k) - 2 = y"
huffman@45436
   575
      by (tactic {* test [@{simproc natdiff_cancel_numerals}] *}) fact
huffman@45436
   576
  next
huffman@45436
   577
    assume "2 * x + y - 2 * (u * v) = w"
huffman@45436
   578
    have "(2*x + (u*v) + y) - v*3*u = w"
huffman@45436
   579
      by (tactic {* test [@{simproc natdiff_cancel_numerals}] *}) fact
huffman@45436
   580
  next
huffman@45436
   581
    assume "2 * x * u * v + (5 + y) - 0 = w"
huffman@45436
   582
    have "(2*x*u*v + 5 + (u*v)*4 + y) - v*u*4 = w"
huffman@45436
   583
      by (tactic {* test [@{simproc natdiff_cancel_numerals}] *}) fact
huffman@45436
   584
  next
huffman@45436
   585
    assume "3 * (u * v) + (2 * x * u * v + y) - 0 = w"
huffman@45436
   586
    have "(2*x*u*v + (u*v)*4 + y) - v*u = w"
huffman@45436
   587
      by (tactic {* test [@{simproc natdiff_cancel_numerals}] *}) fact
huffman@45436
   588
  next
huffman@45436
   589
    assume "3 * u + (2 + (2 * x * u * v + y)) - 0 = w"
huffman@45436
   590
    have "Suc (Suc (2*x*u*v + u*4 + y)) - u = w"
huffman@45436
   591
      by (tactic {* test [@{simproc natdiff_cancel_numerals}] *}) fact
huffman@45436
   592
  next
huffman@45436
   593
    assume "Suc (Suc 0 * (u * v)) - 0 = w"
huffman@45436
   594
    have "Suc ((u*v)*4) - v*3*u = w"
huffman@45436
   595
      by (tactic {* test [@{simproc natdiff_cancel_numerals}] *}) fact
huffman@45436
   596
  next
huffman@45436
   597
    assume "2 - 0 = w" have "Suc (Suc ((u*v)*3)) - v*3*u = w"
huffman@45436
   598
      by (tactic {* test [@{simproc natdiff_cancel_numerals}] *}) fact
huffman@45436
   599
  next
huffman@45436
   600
    assume "17 * Suc 0 + (i + (j + k)) - (u + y) = zz"
huffman@45436
   601
    have "(i + j + 32 + k) - (u + 15 + y) = zz"
huffman@45436
   602
      by (tactic {* test [@{simproc natdiff_cancel_numerals}] *}) fact
huffman@45436
   603
  next
huffman@45436
   604
    assume "u + y - 0 = v" have "Suc (Suc (Suc (Suc (Suc (u + y))))) - 5 = v"
huffman@45436
   605
      by (tactic {* test [@{simproc natdiff_cancel_numerals}] *}) fact
huffman@45436
   606
  next
huffman@45436
   607
    (* FIXME: negative numerals fail
huffman@45436
   608
    have "(i + j + -12 + k) - 15 = y"
huffman@45436
   609
      apply (tactic {* test [@{simproc natdiff_cancel_numerals}] *})?
huffman@45436
   610
      sorry
huffman@45436
   611
    have "(i + j + 12 + k) - -15 = y"
huffman@45436
   612
      apply (tactic {* test [@{simproc natdiff_cancel_numerals}] *})?
huffman@45436
   613
      sorry
huffman@45436
   614
    have "(i + j + -12 + k) - -15 = y"
huffman@45436
   615
      apply (tactic {* test [@{simproc natdiff_cancel_numerals}] *})?
huffman@45436
   616
      sorry*)
huffman@45436
   617
  }
huffman@45436
   618
end
huffman@45436
   619
huffman@45462
   620
subsection {* Factor-cancellation simprocs for type @{typ nat} *}
huffman@45462
   621
huffman@45462
   622
text {* @{text nat_eq_cancel_factor}, @{text nat_less_cancel_factor},
huffman@45462
   623
@{text nat_le_cancel_factor}, @{text nat_divide_cancel_factor}, and
huffman@45462
   624
@{text nat_dvd_cancel_factor}. *}
huffman@45462
   625
huffman@45462
   626
notepad begin
huffman@45462
   627
  fix a b c d k x y uu :: nat
huffman@45462
   628
  {
huffman@45462
   629
    assume "k = 0 \<or> x = y" have "x*k = k*y"
huffman@45462
   630
      by (tactic {* test [@{simproc nat_eq_cancel_factor}] *}) fact
huffman@45462
   631
  next
huffman@45462
   632
    assume "k = 0 \<or> Suc 0 = y" have "k = k*y"
huffman@45462
   633
      by (tactic {* test [@{simproc nat_eq_cancel_factor}] *}) fact
huffman@45462
   634
  next
huffman@45462
   635
    assume "b = 0 \<or> a * c = Suc 0" have "a*(b*c) = b"
huffman@45462
   636
      by (tactic {* test [@{simproc nat_eq_cancel_factor}] *}) fact
huffman@45462
   637
  next
huffman@45462
   638
    assume "a = 0 \<or> b = 0 \<or> c = d * x" have "a*(b*c) = d*b*(x*a)"
huffman@45462
   639
      by (tactic {* test [@{simproc nat_eq_cancel_factor}] *}) fact
huffman@45462
   640
  next
huffman@45462
   641
    assume "0 < k \<and> x < y" have "x*k < k*y"
huffman@45462
   642
      by (tactic {* test [@{simproc nat_less_cancel_factor}] *}) fact
huffman@45462
   643
  next
huffman@45462
   644
    assume "0 < k \<and> Suc 0 < y" have "k < k*y"
huffman@45462
   645
      by (tactic {* test [@{simproc nat_less_cancel_factor}] *}) fact
huffman@45462
   646
  next
huffman@45462
   647
    assume "0 < b \<and> a * c < Suc 0" have "a*(b*c) < b"
huffman@45462
   648
      by (tactic {* test [@{simproc nat_less_cancel_factor}] *}) fact
huffman@45462
   649
  next
huffman@45462
   650
    assume "0 < a \<and> 0 < b \<and> c < d * x" have "a*(b*c) < d*b*(x*a)"
huffman@45462
   651
      by (tactic {* test [@{simproc nat_less_cancel_factor}] *}) fact
huffman@45462
   652
  next
huffman@45462
   653
    assume "0 < k \<longrightarrow> x \<le> y" have "x*k \<le> k*y"
huffman@45462
   654
      by (tactic {* test [@{simproc nat_le_cancel_factor}] *}) fact
huffman@45462
   655
  next
huffman@45462
   656
    assume "0 < k \<longrightarrow> Suc 0 \<le> y" have "k \<le> k*y"
huffman@45462
   657
      by (tactic {* test [@{simproc nat_le_cancel_factor}] *}) fact
huffman@45462
   658
  next
huffman@45462
   659
    assume "0 < b \<longrightarrow> a * c \<le> Suc 0" have "a*(b*c) \<le> b"
huffman@45462
   660
      by (tactic {* test [@{simproc nat_le_cancel_factor}] *}) fact
huffman@45462
   661
  next
huffman@45462
   662
    assume "0 < a \<longrightarrow> 0 < b \<longrightarrow> c \<le> d * x" have "a*(b*c) \<le> d*b*(x*a)"
huffman@45462
   663
      by (tactic {* test [@{simproc nat_le_cancel_factor}] *}) fact
huffman@45462
   664
  next
huffman@45462
   665
    assume "(if k = 0 then 0 else x div y) = uu" have "(x*k) div (k*y) = uu"
huffman@45463
   666
      by (tactic {* test [@{simproc nat_div_cancel_factor}] *}) fact
huffman@45462
   667
  next
huffman@45462
   668
    assume "(if k = 0 then 0 else Suc 0 div y) = uu" have "k div (k*y) = uu"
huffman@45463
   669
      by (tactic {* test [@{simproc nat_div_cancel_factor}] *}) fact
huffman@45462
   670
  next
huffman@45462
   671
    assume "(if b = 0 then 0 else a * c) = uu" have "(a*(b*c)) div (b) = uu"
huffman@45463
   672
      by (tactic {* test [@{simproc nat_div_cancel_factor}] *}) fact
huffman@45462
   673
  next
huffman@45462
   674
    assume "(if a = 0 then 0 else if b = 0 then 0 else c div (d * x)) = uu"
huffman@45462
   675
    have "(a*(b*c)) div (d*b*(x*a)) = uu"
huffman@45463
   676
      by (tactic {* test [@{simproc nat_div_cancel_factor}] *}) fact
huffman@45462
   677
  next
huffman@45462
   678
    assume "k = 0 \<or> x dvd y" have "(x*k) dvd (k*y)"
huffman@45462
   679
      by (tactic {* test [@{simproc nat_dvd_cancel_factor}] *}) fact
huffman@45462
   680
  next
huffman@45462
   681
    assume "k = 0 \<or> Suc 0 dvd y" have "k dvd (k*y)"
huffman@45462
   682
      by (tactic {* test [@{simproc nat_dvd_cancel_factor}] *}) fact
huffman@45462
   683
  next
huffman@45462
   684
    assume "b = 0 \<or> a * c dvd Suc 0" have "(a*(b*c)) dvd (b)"
huffman@45462
   685
      by (tactic {* test [@{simproc nat_dvd_cancel_factor}] *}) fact
huffman@45462
   686
  next
huffman@45462
   687
    assume "b = 0 \<or> Suc 0 dvd a * c" have "b dvd (a*(b*c))"
huffman@45462
   688
      by (tactic {* test [@{simproc nat_dvd_cancel_factor}] *}) fact
huffman@45462
   689
  next
huffman@45462
   690
    assume "a = 0 \<or> b = 0 \<or> c dvd d * x" have "(a*(b*c)) dvd (d*b*(x*a))"
huffman@45462
   691
      by (tactic {* test [@{simproc nat_dvd_cancel_factor}] *}) fact
huffman@45462
   692
  }
huffman@45436
   693
end
huffman@45462
   694
huffman@45463
   695
subsection {* Numeral-cancellation simprocs for type @{typ nat} *}
huffman@45463
   696
huffman@45463
   697
notepad begin
huffman@45463
   698
  fix x y z :: nat
huffman@45463
   699
  {
huffman@45463
   700
    assume "3 * x = 4 * y" have "9*x = 12 * y"
huffman@45463
   701
      by (tactic {* test [@{simproc nat_eq_cancel_numeral_factor}] *}) fact
huffman@45463
   702
  next
huffman@45463
   703
    assume "3 * x < 4 * y" have "9*x < 12 * y"
huffman@45463
   704
      by (tactic {* test [@{simproc nat_less_cancel_numeral_factor}] *}) fact
huffman@45463
   705
  next
huffman@45463
   706
    assume "3 * x \<le> 4 * y" have "9*x \<le> 12 * y"
huffman@45463
   707
      by (tactic {* test [@{simproc nat_le_cancel_numeral_factor}] *}) fact
huffman@45463
   708
  next
huffman@45463
   709
    assume "(3 * x) div (4 * y) = z" have "(9*x) div (12 * y) = z"
huffman@45463
   710
      by (tactic {* test [@{simproc nat_div_cancel_numeral_factor}] *}) fact
huffman@45463
   711
  next
huffman@45463
   712
    assume "(3 * x) dvd (4 * y)" have "(9*x) dvd (12 * y)"
huffman@45463
   713
      by (tactic {* test [@{simproc nat_dvd_cancel_numeral_factor}] *}) fact
huffman@45463
   714
  }
huffman@45462
   715
end
huffman@45463
   716
huffman@45530
   717
subsection {* Integer numeral div/mod simprocs *}
huffman@45530
   718
huffman@45530
   719
notepad begin
huffman@45530
   720
  have "(10::int) div 3 = 3"
huffman@45530
   721
    by (tactic {* test [@{simproc binary_int_div}] *})
huffman@45530
   722
  have "(10::int) mod 3 = 1"
huffman@45530
   723
    by (tactic {* test [@{simproc binary_int_mod}] *})
huffman@45530
   724
  have "(10::int) div -3 = -4"
huffman@45530
   725
    by (tactic {* test [@{simproc binary_int_div}] *})
huffman@45530
   726
  have "(10::int) mod -3 = -2"
huffman@45530
   727
    by (tactic {* test [@{simproc binary_int_mod}] *})
huffman@45530
   728
  have "(-10::int) div 3 = -4"
huffman@45530
   729
    by (tactic {* test [@{simproc binary_int_div}] *})
huffman@45530
   730
  have "(-10::int) mod 3 = 2"
huffman@45530
   731
    by (tactic {* test [@{simproc binary_int_mod}] *})
huffman@45530
   732
  have "(-10::int) div -3 = 3"
huffman@45530
   733
    by (tactic {* test [@{simproc binary_int_div}] *})
huffman@45530
   734
  have "(-10::int) mod -3 = -1"
huffman@45530
   735
    by (tactic {* test [@{simproc binary_int_mod}] *})
huffman@45530
   736
  have "(8452::int) mod 3 = 1"
huffman@45530
   737
    by (tactic {* test [@{simproc binary_int_mod}] *})
huffman@45530
   738
  have "(59485::int) div 434 = 137"
huffman@45530
   739
    by (tactic {* test [@{simproc binary_int_div}] *})
huffman@45530
   740
  have "(1000006::int) mod 10 = 6"
huffman@45530
   741
    by (tactic {* test [@{simproc binary_int_mod}] *})
huffman@45530
   742
  have "10000000 div 2 = (5000000::int)"
huffman@45530
   743
    by (tactic {* test [@{simproc binary_int_div}] *})
huffman@45530
   744
  have "10000001 mod 2 = (1::int)"
huffman@45530
   745
    by (tactic {* test [@{simproc binary_int_mod}] *})
huffman@45530
   746
  have "10000055 div 32 = (312501::int)"
huffman@45530
   747
    by (tactic {* test [@{simproc binary_int_div}] *})
huffman@45530
   748
  have "10000055 mod 32 = (23::int)"
huffman@45530
   749
    by (tactic {* test [@{simproc binary_int_mod}] *})
huffman@45530
   750
  have "100094 div 144 = (695::int)"
huffman@45530
   751
    by (tactic {* test [@{simproc binary_int_div}] *})
huffman@45530
   752
  have "100094 mod 144 = (14::int)"
huffman@45530
   753
    by (tactic {* test [@{simproc binary_int_mod}] *})
huffman@45463
   754
end
huffman@45530
   755
huffman@45530
   756
end