src/HOL/Decision_Procs/Cooper.thy
author wenzelm
Wed Dec 29 17:34:41 2010 +0100 (2010-12-29)
changeset 41413 64cd30d6b0b8
parent 39246 9e58f0499f57
child 41807 ab5d2d81f9fb
permissions -rw-r--r--
explicit file specifications -- avoid secondary load path;
hoelzl@30439
     1
(*  Title:      HOL/Decision_Procs/Cooper.thy
haftmann@27456
     2
    Author:     Amine Chaieb
haftmann@27456
     3
*)
haftmann@27456
     4
haftmann@29788
     5
theory Cooper
wenzelm@41413
     6
imports Complex_Main "~~/src/HOL/Library/Efficient_Nat"
haftmann@29788
     7
uses ("cooper_tac.ML")
nipkow@23477
     8
begin
chaieb@17378
     9
haftmann@29788
    10
function iupt :: "int \<Rightarrow> int \<Rightarrow> int list" where
haftmann@23689
    11
  "iupt i j = (if j < i then [] else i # iupt (i+1) j)"
haftmann@23689
    12
by pat_completeness auto
haftmann@23689
    13
termination by (relation "measure (\<lambda> (i, j). nat (j-i+1))") auto
chaieb@23274
    14
haftmann@23689
    15
lemma iupt_set: "set (iupt i j) = {i..j}"
haftmann@23689
    16
  by (induct rule: iupt.induct) (simp add: simp_from_to)
chaieb@17378
    17
chaieb@17378
    18
(* Periodicity of dvd *)
chaieb@23315
    19
chaieb@23274
    20
  (*********************************************************************************)
chaieb@23274
    21
  (****                            SHADOW SYNTAX AND SEMANTICS                  ****)
chaieb@23274
    22
  (*********************************************************************************)
chaieb@23274
    23
chaieb@23995
    24
datatype num = C int | Bound nat | CN nat int num | Neg num | Add num num| Sub num num 
chaieb@23274
    25
  | Mul int num
chaieb@23274
    26
chaieb@23274
    27
  (* A size for num to make inductive proofs simpler*)
haftmann@27456
    28
primrec num_size :: "num \<Rightarrow> nat" where
chaieb@23274
    29
  "num_size (C c) = 1"
haftmann@27456
    30
| "num_size (Bound n) = 1"
haftmann@27456
    31
| "num_size (Neg a) = 1 + num_size a"
haftmann@27456
    32
| "num_size (Add a b) = 1 + num_size a + num_size b"
haftmann@27456
    33
| "num_size (Sub a b) = 3 + num_size a + num_size b"
haftmann@27456
    34
| "num_size (CN n c a) = 4 + num_size a"
haftmann@27456
    35
| "num_size (Mul c a) = 1 + num_size a"
chaieb@17378
    36
haftmann@27456
    37
primrec Inum :: "int list \<Rightarrow> num \<Rightarrow> int" where
chaieb@23274
    38
  "Inum bs (C c) = c"
haftmann@27456
    39
| "Inum bs (Bound n) = bs!n"
haftmann@27456
    40
| "Inum bs (CN n c a) = c * (bs!n) + (Inum bs a)"
haftmann@27456
    41
| "Inum bs (Neg a) = -(Inum bs a)"
haftmann@27456
    42
| "Inum bs (Add a b) = Inum bs a + Inum bs b"
haftmann@27456
    43
| "Inum bs (Sub a b) = Inum bs a - Inum bs b"
haftmann@27456
    44
| "Inum bs (Mul c a) = c* Inum bs a"
chaieb@23274
    45
chaieb@23274
    46
datatype fm  = 
chaieb@23274
    47
  T| F| Lt num| Le num| Gt num| Ge num| Eq num| NEq num| Dvd int num| NDvd int num|
chaieb@23274
    48
  NOT fm| And fm fm|  Or fm fm| Imp fm fm| Iff fm fm| E fm| A fm 
chaieb@23274
    49
  | Closed nat | NClosed nat
chaieb@23274
    50
chaieb@23274
    51
chaieb@23274
    52
  (* A size for fm *)
chaieb@23274
    53
consts fmsize :: "fm \<Rightarrow> nat"
chaieb@23274
    54
recdef fmsize "measure size"
chaieb@23274
    55
  "fmsize (NOT p) = 1 + fmsize p"
chaieb@23274
    56
  "fmsize (And p q) = 1 + fmsize p + fmsize q"
chaieb@23274
    57
  "fmsize (Or p q) = 1 + fmsize p + fmsize q"
chaieb@23274
    58
  "fmsize (Imp p q) = 3 + fmsize p + fmsize q"
chaieb@23274
    59
  "fmsize (Iff p q) = 3 + 2*(fmsize p + fmsize q)"
chaieb@23274
    60
  "fmsize (E p) = 1 + fmsize p"
chaieb@23274
    61
  "fmsize (A p) = 4+ fmsize p"
chaieb@23274
    62
  "fmsize (Dvd i t) = 2"
chaieb@23274
    63
  "fmsize (NDvd i t) = 2"
chaieb@23274
    64
  "fmsize p = 1"
chaieb@23274
    65
  (* several lemmas about fmsize *)
wenzelm@32960
    66
lemma fmsize_pos: "fmsize p > 0"
wenzelm@32960
    67
  by (induct p rule: fmsize.induct) simp_all
chaieb@17378
    68
chaieb@23274
    69
  (* Semantics of formulae (fm) *)
haftmann@39246
    70
primrec Ifm ::"bool list \<Rightarrow> int list \<Rightarrow> fm \<Rightarrow> bool" where
chaieb@23274
    71
  "Ifm bbs bs T = True"
haftmann@39246
    72
| "Ifm bbs bs F = False"
haftmann@39246
    73
| "Ifm bbs bs (Lt a) = (Inum bs a < 0)"
haftmann@39246
    74
| "Ifm bbs bs (Gt a) = (Inum bs a > 0)"
haftmann@39246
    75
| "Ifm bbs bs (Le a) = (Inum bs a \<le> 0)"
haftmann@39246
    76
| "Ifm bbs bs (Ge a) = (Inum bs a \<ge> 0)"
haftmann@39246
    77
| "Ifm bbs bs (Eq a) = (Inum bs a = 0)"
haftmann@39246
    78
| "Ifm bbs bs (NEq a) = (Inum bs a \<noteq> 0)"
haftmann@39246
    79
| "Ifm bbs bs (Dvd i b) = (i dvd Inum bs b)"
haftmann@39246
    80
| "Ifm bbs bs (NDvd i b) = (\<not>(i dvd Inum bs b))"
haftmann@39246
    81
| "Ifm bbs bs (NOT p) = (\<not> (Ifm bbs bs p))"
haftmann@39246
    82
| "Ifm bbs bs (And p q) = (Ifm bbs bs p \<and> Ifm bbs bs q)"
haftmann@39246
    83
| "Ifm bbs bs (Or p q) = (Ifm bbs bs p \<or> Ifm bbs bs q)"
haftmann@39246
    84
| "Ifm bbs bs (Imp p q) = ((Ifm bbs bs p) \<longrightarrow> (Ifm bbs bs q))"
haftmann@39246
    85
| "Ifm bbs bs (Iff p q) = (Ifm bbs bs p = Ifm bbs bs q)"
haftmann@39246
    86
| "Ifm bbs bs (E p) = (\<exists> x. Ifm bbs (x#bs) p)"
haftmann@39246
    87
| "Ifm bbs bs (A p) = (\<forall> x. Ifm bbs (x#bs) p)"
haftmann@39246
    88
| "Ifm bbs bs (Closed n) = bbs!n"
haftmann@39246
    89
| "Ifm bbs bs (NClosed n) = (\<not> bbs!n)"
chaieb@23274
    90
chaieb@23274
    91
consts prep :: "fm \<Rightarrow> fm"
chaieb@23274
    92
recdef prep "measure fmsize"
chaieb@23274
    93
  "prep (E T) = T"
chaieb@23274
    94
  "prep (E F) = F"
chaieb@23274
    95
  "prep (E (Or p q)) = Or (prep (E p)) (prep (E q))"
chaieb@23274
    96
  "prep (E (Imp p q)) = Or (prep (E (NOT p))) (prep (E q))"
chaieb@23274
    97
  "prep (E (Iff p q)) = Or (prep (E (And p q))) (prep (E (And (NOT p) (NOT q))))" 
chaieb@23274
    98
  "prep (E (NOT (And p q))) = Or (prep (E (NOT p))) (prep (E(NOT q)))"
chaieb@23274
    99
  "prep (E (NOT (Imp p q))) = prep (E (And p (NOT q)))"
chaieb@23274
   100
  "prep (E (NOT (Iff p q))) = Or (prep (E (And p (NOT q)))) (prep (E(And (NOT p) q)))"
chaieb@23274
   101
  "prep (E p) = E (prep p)"
chaieb@23274
   102
  "prep (A (And p q)) = And (prep (A p)) (prep (A q))"
chaieb@23274
   103
  "prep (A p) = prep (NOT (E (NOT p)))"
chaieb@23274
   104
  "prep (NOT (NOT p)) = prep p"
chaieb@23274
   105
  "prep (NOT (And p q)) = Or (prep (NOT p)) (prep (NOT q))"
chaieb@23274
   106
  "prep (NOT (A p)) = prep (E (NOT p))"
chaieb@23274
   107
  "prep (NOT (Or p q)) = And (prep (NOT p)) (prep (NOT q))"
chaieb@23274
   108
  "prep (NOT (Imp p q)) = And (prep p) (prep (NOT q))"
chaieb@23274
   109
  "prep (NOT (Iff p q)) = Or (prep (And p (NOT q))) (prep (And (NOT p) q))"
chaieb@23274
   110
  "prep (NOT p) = NOT (prep p)"
chaieb@23274
   111
  "prep (Or p q) = Or (prep p) (prep q)"
chaieb@23274
   112
  "prep (And p q) = And (prep p) (prep q)"
chaieb@23274
   113
  "prep (Imp p q) = prep (Or (NOT p) q)"
chaieb@23274
   114
  "prep (Iff p q) = Or (prep (And p q)) (prep (And (NOT p) (NOT q)))"
chaieb@23274
   115
  "prep p = p"
nipkow@25162
   116
(hints simp add: fmsize_pos)
chaieb@23274
   117
lemma prep: "Ifm bbs bs (prep p) = Ifm bbs bs p"
chaieb@23274
   118
by (induct p arbitrary: bs rule: prep.induct, auto)
chaieb@23274
   119
chaieb@17378
   120
chaieb@23274
   121
  (* Quantifier freeness *)
chaieb@23274
   122
consts qfree:: "fm \<Rightarrow> bool"
chaieb@23274
   123
recdef qfree "measure size"
chaieb@23274
   124
  "qfree (E p) = False"
chaieb@23274
   125
  "qfree (A p) = False"
chaieb@23274
   126
  "qfree (NOT p) = qfree p" 
chaieb@23274
   127
  "qfree (And p q) = (qfree p \<and> qfree q)" 
chaieb@23274
   128
  "qfree (Or  p q) = (qfree p \<and> qfree q)" 
chaieb@23274
   129
  "qfree (Imp p q) = (qfree p \<and> qfree q)" 
chaieb@23274
   130
  "qfree (Iff p q) = (qfree p \<and> qfree q)"
chaieb@23274
   131
  "qfree p = True"
chaieb@23274
   132
chaieb@23274
   133
  (* Boundedness and substitution *)
haftmann@39246
   134
    
haftmann@39246
   135
primrec numbound0:: "num \<Rightarrow> bool" (* a num is INDEPENDENT of Bound 0 *) where
chaieb@23274
   136
  "numbound0 (C c) = True"
haftmann@39246
   137
| "numbound0 (Bound n) = (n>0)"
haftmann@39246
   138
| "numbound0 (CN n i a) = (n >0 \<and> numbound0 a)"
haftmann@39246
   139
| "numbound0 (Neg a) = numbound0 a"
haftmann@39246
   140
| "numbound0 (Add a b) = (numbound0 a \<and> numbound0 b)"
haftmann@39246
   141
| "numbound0 (Sub a b) = (numbound0 a \<and> numbound0 b)" 
haftmann@39246
   142
| "numbound0 (Mul i a) = numbound0 a"
chaieb@23274
   143
chaieb@23274
   144
lemma numbound0_I:
chaieb@23274
   145
  assumes nb: "numbound0 a"
chaieb@23274
   146
  shows "Inum (b#bs) a = Inum (b'#bs) a"
chaieb@23274
   147
using nb
haftmann@39246
   148
by (induct a rule: num.induct) (auto simp add: gr0_conv_Suc)
chaieb@17378
   149
haftmann@39246
   150
primrec bound0:: "fm \<Rightarrow> bool" (* A Formula is independent of Bound 0 *) where
chaieb@23274
   151
  "bound0 T = True"
haftmann@39246
   152
| "bound0 F = True"
haftmann@39246
   153
| "bound0 (Lt a) = numbound0 a"
haftmann@39246
   154
| "bound0 (Le a) = numbound0 a"
haftmann@39246
   155
| "bound0 (Gt a) = numbound0 a"
haftmann@39246
   156
| "bound0 (Ge a) = numbound0 a"
haftmann@39246
   157
| "bound0 (Eq a) = numbound0 a"
haftmann@39246
   158
| "bound0 (NEq a) = numbound0 a"
haftmann@39246
   159
| "bound0 (Dvd i a) = numbound0 a"
haftmann@39246
   160
| "bound0 (NDvd i a) = numbound0 a"
haftmann@39246
   161
| "bound0 (NOT p) = bound0 p"
haftmann@39246
   162
| "bound0 (And p q) = (bound0 p \<and> bound0 q)"
haftmann@39246
   163
| "bound0 (Or p q) = (bound0 p \<and> bound0 q)"
haftmann@39246
   164
| "bound0 (Imp p q) = ((bound0 p) \<and> (bound0 q))"
haftmann@39246
   165
| "bound0 (Iff p q) = (bound0 p \<and> bound0 q)"
haftmann@39246
   166
| "bound0 (E p) = False"
haftmann@39246
   167
| "bound0 (A p) = False"
haftmann@39246
   168
| "bound0 (Closed P) = True"
haftmann@39246
   169
| "bound0 (NClosed P) = True"
chaieb@23274
   170
lemma bound0_I:
chaieb@23274
   171
  assumes bp: "bound0 p"
chaieb@23274
   172
  shows "Ifm bbs (b#bs) p = Ifm bbs (b'#bs) p"
chaieb@23274
   173
using bp numbound0_I[where b="b" and bs="bs" and b'="b'"]
haftmann@39246
   174
by (induct p rule: fm.induct) (auto simp add: gr0_conv_Suc)
chaieb@23274
   175
haftmann@27456
   176
fun numsubst0:: "num \<Rightarrow> num \<Rightarrow> num" where
chaieb@23274
   177
  "numsubst0 t (C c) = (C c)"
chaieb@23995
   178
| "numsubst0 t (Bound n) = (if n=0 then t else Bound n)"
chaieb@23995
   179
| "numsubst0 t (CN 0 i a) = Add (Mul i t) (numsubst0 t a)"
chaieb@23995
   180
| "numsubst0 t (CN n i a) = CN n i (numsubst0 t a)"
chaieb@23995
   181
| "numsubst0 t (Neg a) = Neg (numsubst0 t a)"
chaieb@23995
   182
| "numsubst0 t (Add a b) = Add (numsubst0 t a) (numsubst0 t b)"
chaieb@23995
   183
| "numsubst0 t (Sub a b) = Sub (numsubst0 t a) (numsubst0 t b)" 
chaieb@23995
   184
| "numsubst0 t (Mul i a) = Mul i (numsubst0 t a)"
chaieb@23274
   185
chaieb@23274
   186
lemma numsubst0_I:
nipkow@25134
   187
  "Inum (b#bs) (numsubst0 a t) = Inum ((Inum (b#bs) a)#bs) t"
nipkow@25162
   188
by (induct t rule: numsubst0.induct,auto simp:nth_Cons')
chaieb@17378
   189
chaieb@23274
   190
lemma numsubst0_I':
nipkow@25134
   191
  "numbound0 a \<Longrightarrow> Inum (b#bs) (numsubst0 a t) = Inum ((Inum (b'#bs) a)#bs) t"
nipkow@25162
   192
by (induct t rule: numsubst0.induct, auto simp: nth_Cons' numbound0_I[where b="b" and b'="b'"])
chaieb@23274
   193
haftmann@39246
   194
primrec subst0:: "num \<Rightarrow> fm \<Rightarrow> fm" (* substitue a num into a formula for Bound 0 *) where
chaieb@23274
   195
  "subst0 t T = T"
haftmann@39246
   196
| "subst0 t F = F"
haftmann@39246
   197
| "subst0 t (Lt a) = Lt (numsubst0 t a)"
haftmann@39246
   198
| "subst0 t (Le a) = Le (numsubst0 t a)"
haftmann@39246
   199
| "subst0 t (Gt a) = Gt (numsubst0 t a)"
haftmann@39246
   200
| "subst0 t (Ge a) = Ge (numsubst0 t a)"
haftmann@39246
   201
| "subst0 t (Eq a) = Eq (numsubst0 t a)"
haftmann@39246
   202
| "subst0 t (NEq a) = NEq (numsubst0 t a)"
haftmann@39246
   203
| "subst0 t (Dvd i a) = Dvd i (numsubst0 t a)"
haftmann@39246
   204
| "subst0 t (NDvd i a) = NDvd i (numsubst0 t a)"
haftmann@39246
   205
| "subst0 t (NOT p) = NOT (subst0 t p)"
haftmann@39246
   206
| "subst0 t (And p q) = And (subst0 t p) (subst0 t q)"
haftmann@39246
   207
| "subst0 t (Or p q) = Or (subst0 t p) (subst0 t q)"
haftmann@39246
   208
| "subst0 t (Imp p q) = Imp (subst0 t p) (subst0 t q)"
haftmann@39246
   209
| "subst0 t (Iff p q) = Iff (subst0 t p) (subst0 t q)"
haftmann@39246
   210
| "subst0 t (Closed P) = (Closed P)"
haftmann@39246
   211
| "subst0 t (NClosed P) = (NClosed P)"
chaieb@23274
   212
chaieb@23274
   213
lemma subst0_I: assumes qfp: "qfree p"
chaieb@23274
   214
  shows "Ifm bbs (b#bs) (subst0 a p) = Ifm bbs ((Inum (b#bs) a)#bs) p"
chaieb@23274
   215
  using qfp numsubst0_I[where b="b" and bs="bs" and a="a"]
haftmann@23689
   216
  by (induct p) (simp_all add: gr0_conv_Suc)
chaieb@23274
   217
chaieb@23274
   218
chaieb@23274
   219
consts 
chaieb@23274
   220
  decrnum:: "num \<Rightarrow> num" 
chaieb@23274
   221
  decr :: "fm \<Rightarrow> fm"
chaieb@23274
   222
chaieb@23274
   223
recdef decrnum "measure size"
chaieb@23274
   224
  "decrnum (Bound n) = Bound (n - 1)"
chaieb@23274
   225
  "decrnum (Neg a) = Neg (decrnum a)"
chaieb@23274
   226
  "decrnum (Add a b) = Add (decrnum a) (decrnum b)"
chaieb@23274
   227
  "decrnum (Sub a b) = Sub (decrnum a) (decrnum b)"
chaieb@23274
   228
  "decrnum (Mul c a) = Mul c (decrnum a)"
chaieb@23995
   229
  "decrnum (CN n i a) = (CN (n - 1) i (decrnum a))"
chaieb@23274
   230
  "decrnum a = a"
chaieb@17378
   231
chaieb@23274
   232
recdef decr "measure size"
chaieb@23274
   233
  "decr (Lt a) = Lt (decrnum a)"
chaieb@23274
   234
  "decr (Le a) = Le (decrnum a)"
chaieb@23274
   235
  "decr (Gt a) = Gt (decrnum a)"
chaieb@23274
   236
  "decr (Ge a) = Ge (decrnum a)"
chaieb@23274
   237
  "decr (Eq a) = Eq (decrnum a)"
chaieb@23274
   238
  "decr (NEq a) = NEq (decrnum a)"
chaieb@23274
   239
  "decr (Dvd i a) = Dvd i (decrnum a)"
chaieb@23274
   240
  "decr (NDvd i a) = NDvd i (decrnum a)"
chaieb@23274
   241
  "decr (NOT p) = NOT (decr p)" 
chaieb@23274
   242
  "decr (And p q) = And (decr p) (decr q)"
chaieb@23274
   243
  "decr (Or p q) = Or (decr p) (decr q)"
chaieb@23274
   244
  "decr (Imp p q) = Imp (decr p) (decr q)"
chaieb@23274
   245
  "decr (Iff p q) = Iff (decr p) (decr q)"
chaieb@23274
   246
  "decr p = p"
chaieb@23274
   247
chaieb@23274
   248
lemma decrnum: assumes nb: "numbound0 t"
chaieb@23274
   249
  shows "Inum (x#bs) t = Inum bs (decrnum t)"
haftmann@23689
   250
  using nb by (induct t rule: decrnum.induct, auto simp add: gr0_conv_Suc)
chaieb@23274
   251
chaieb@23274
   252
lemma decr: assumes nb: "bound0 p"
chaieb@23274
   253
  shows "Ifm bbs (x#bs) p = Ifm bbs bs (decr p)"
chaieb@23274
   254
  using nb 
haftmann@23689
   255
  by (induct p rule: decr.induct, simp_all add: gr0_conv_Suc decrnum)
chaieb@23274
   256
chaieb@23274
   257
lemma decr_qf: "bound0 p \<Longrightarrow> qfree (decr p)"
chaieb@23274
   258
by (induct p, simp_all)
chaieb@23274
   259
chaieb@23274
   260
consts 
chaieb@23274
   261
  isatom :: "fm \<Rightarrow> bool" (* test for atomicity *)
chaieb@23274
   262
recdef isatom "measure size"
chaieb@23274
   263
  "isatom T = True"
chaieb@23274
   264
  "isatom F = True"
chaieb@23274
   265
  "isatom (Lt a) = True"
chaieb@23274
   266
  "isatom (Le a) = True"
chaieb@23274
   267
  "isatom (Gt a) = True"
chaieb@23274
   268
  "isatom (Ge a) = True"
chaieb@23274
   269
  "isatom (Eq a) = True"
chaieb@23274
   270
  "isatom (NEq a) = True"
chaieb@23274
   271
  "isatom (Dvd i b) = True"
chaieb@23274
   272
  "isatom (NDvd i b) = True"
chaieb@23274
   273
  "isatom (Closed P) = True"
chaieb@23274
   274
  "isatom (NClosed P) = True"
chaieb@23274
   275
  "isatom p = False"
chaieb@17378
   276
chaieb@23274
   277
lemma numsubst0_numbound0: assumes nb: "numbound0 t"
chaieb@23274
   278
  shows "numbound0 (numsubst0 t a)"
haftmann@39246
   279
using nb apply (induct a)
chaieb@23995
   280
apply simp_all
haftmann@39246
   281
apply (case_tac nat, simp_all)
chaieb@23995
   282
done
chaieb@23274
   283
chaieb@23274
   284
lemma subst0_bound0: assumes qf: "qfree p" and nb: "numbound0 t"
chaieb@23274
   285
  shows "bound0 (subst0 t p)"
haftmann@39246
   286
using qf numsubst0_numbound0[OF nb] by (induct p) auto
chaieb@23274
   287
chaieb@23274
   288
lemma bound0_qf: "bound0 p \<Longrightarrow> qfree p"
chaieb@23274
   289
by (induct p, simp_all)
chaieb@23274
   290
chaieb@23274
   291
haftmann@35416
   292
definition djf :: "('a \<Rightarrow> fm) \<Rightarrow> 'a \<Rightarrow> fm \<Rightarrow> fm" where
chaieb@23274
   293
  "djf f p q \<equiv> (if q=T then T else if q=F then f p else 
chaieb@23274
   294
  (let fp = f p in case fp of T \<Rightarrow> T | F \<Rightarrow> q | _ \<Rightarrow> Or (f p) q))"
haftmann@35416
   295
definition evaldjf :: "('a \<Rightarrow> fm) \<Rightarrow> 'a list \<Rightarrow> fm" where
chaieb@23274
   296
  "evaldjf f ps \<equiv> foldr (djf f) ps F"
chaieb@23274
   297
chaieb@23274
   298
lemma djf_Or: "Ifm bbs bs (djf f p q) = Ifm bbs bs (Or (f p) q)"
chaieb@23274
   299
by (cases "q=T", simp add: djf_def,cases "q=F",simp add: djf_def) 
chaieb@23274
   300
(cases "f p", simp_all add: Let_def djf_def) 
chaieb@23274
   301
chaieb@23274
   302
lemma evaldjf_ex: "Ifm bbs bs (evaldjf f ps) = (\<exists> p \<in> set ps. Ifm bbs bs (f p))"
chaieb@23274
   303
  by(induct ps, simp_all add: evaldjf_def djf_Or)
chaieb@17378
   304
chaieb@23274
   305
lemma evaldjf_bound0: 
chaieb@23274
   306
  assumes nb: "\<forall> x\<in> set xs. bound0 (f x)"
chaieb@23274
   307
  shows "bound0 (evaldjf f xs)"
chaieb@23274
   308
  using nb by (induct xs, auto simp add: evaldjf_def djf_def Let_def) (case_tac "f a", auto) 
chaieb@23274
   309
chaieb@23274
   310
lemma evaldjf_qf: 
chaieb@23274
   311
  assumes nb: "\<forall> x\<in> set xs. qfree (f x)"
chaieb@23274
   312
  shows "qfree (evaldjf f xs)"
chaieb@23274
   313
  using nb by (induct xs, auto simp add: evaldjf_def djf_def Let_def) (case_tac "f a", auto) 
chaieb@17378
   314
chaieb@23274
   315
consts disjuncts :: "fm \<Rightarrow> fm list"
chaieb@23274
   316
recdef disjuncts "measure size"
chaieb@23274
   317
  "disjuncts (Or p q) = (disjuncts p) @ (disjuncts q)"
chaieb@23274
   318
  "disjuncts F = []"
chaieb@23274
   319
  "disjuncts p = [p]"
chaieb@23274
   320
chaieb@23274
   321
lemma disjuncts: "(\<exists> q\<in> set (disjuncts p). Ifm bbs bs q) = Ifm bbs bs p"
chaieb@23274
   322
by(induct p rule: disjuncts.induct, auto)
chaieb@23274
   323
chaieb@23274
   324
lemma disjuncts_nb: "bound0 p \<Longrightarrow> \<forall> q\<in> set (disjuncts p). bound0 q"
chaieb@17378
   325
proof-
chaieb@23274
   326
  assume nb: "bound0 p"
chaieb@23274
   327
  hence "list_all bound0 (disjuncts p)" by (induct p rule:disjuncts.induct,auto)
chaieb@23274
   328
  thus ?thesis by (simp only: list_all_iff)
chaieb@17378
   329
qed
chaieb@17378
   330
chaieb@23274
   331
lemma disjuncts_qf: "qfree p \<Longrightarrow> \<forall> q\<in> set (disjuncts p). qfree q"
chaieb@23274
   332
proof-
chaieb@23274
   333
  assume qf: "qfree p"
chaieb@23274
   334
  hence "list_all qfree (disjuncts p)"
chaieb@23274
   335
    by (induct p rule: disjuncts.induct, auto)
chaieb@23274
   336
  thus ?thesis by (simp only: list_all_iff)
chaieb@23274
   337
qed
chaieb@17378
   338
haftmann@35416
   339
definition DJ :: "(fm \<Rightarrow> fm) \<Rightarrow> fm \<Rightarrow> fm" where
chaieb@23274
   340
  "DJ f p \<equiv> evaldjf f (disjuncts p)"
chaieb@17378
   341
chaieb@23274
   342
lemma DJ: assumes fdj: "\<forall> p q. f (Or p q) = Or (f p) (f q)"
chaieb@23274
   343
  and fF: "f F = F"
chaieb@23274
   344
  shows "Ifm bbs bs (DJ f p) = Ifm bbs bs (f p)"
chaieb@23274
   345
proof-
chaieb@23274
   346
  have "Ifm bbs bs (DJ f p) = (\<exists> q \<in> set (disjuncts p). Ifm bbs bs (f q))"
chaieb@23274
   347
    by (simp add: DJ_def evaldjf_ex) 
chaieb@23274
   348
  also have "\<dots> = Ifm bbs bs (f p)" using fdj fF by (induct p rule: disjuncts.induct, auto)
chaieb@23274
   349
  finally show ?thesis .
chaieb@23274
   350
qed
chaieb@17378
   351
chaieb@23274
   352
lemma DJ_qf: assumes 
chaieb@23274
   353
  fqf: "\<forall> p. qfree p \<longrightarrow> qfree (f p)"
chaieb@23274
   354
  shows "\<forall>p. qfree p \<longrightarrow> qfree (DJ f p) "
chaieb@23274
   355
proof(clarify)
chaieb@23274
   356
  fix  p assume qf: "qfree p"
chaieb@23274
   357
  have th: "DJ f p = evaldjf f (disjuncts p)" by (simp add: DJ_def)
chaieb@23274
   358
  from disjuncts_qf[OF qf] have "\<forall> q\<in> set (disjuncts p). qfree q" .
chaieb@23274
   359
  with fqf have th':"\<forall> q\<in> set (disjuncts p). qfree (f q)" by blast
chaieb@23274
   360
  
chaieb@23274
   361
  from evaldjf_qf[OF th'] th show "qfree (DJ f p)" by simp
chaieb@17378
   362
qed
chaieb@17378
   363
chaieb@23274
   364
lemma DJ_qe: assumes qe: "\<forall> bs p. qfree p \<longrightarrow> qfree (qe p) \<and> (Ifm bbs bs (qe p) = Ifm bbs bs (E p))"
chaieb@23274
   365
  shows "\<forall> bs p. qfree p \<longrightarrow> qfree (DJ qe p) \<and> (Ifm bbs bs ((DJ qe p)) = Ifm bbs bs (E p))"
chaieb@23274
   366
proof(clarify)
chaieb@23274
   367
  fix p::fm and bs
chaieb@23274
   368
  assume qf: "qfree p"
chaieb@23274
   369
  from qe have qth: "\<forall> p. qfree p \<longrightarrow> qfree (qe p)" by blast
chaieb@23274
   370
  from DJ_qf[OF qth] qf have qfth:"qfree (DJ qe p)" by auto
chaieb@23274
   371
  have "Ifm bbs bs (DJ qe p) = (\<exists> q\<in> set (disjuncts p). Ifm bbs bs (qe q))"
chaieb@23274
   372
    by (simp add: DJ_def evaldjf_ex)
chaieb@23274
   373
  also have "\<dots> = (\<exists> q \<in> set(disjuncts p). Ifm bbs bs (E q))" using qe disjuncts_qf[OF qf] by auto
chaieb@23274
   374
  also have "\<dots> = Ifm bbs bs (E p)" by (induct p rule: disjuncts.induct, auto)
chaieb@23274
   375
  finally show "qfree (DJ qe p) \<and> Ifm bbs bs (DJ qe p) = Ifm bbs bs (E p)" using qfth by blast
chaieb@23274
   376
qed
chaieb@23274
   377
  (* Simplification *)
chaieb@23274
   378
chaieb@23274
   379
  (* Algebraic simplifications for nums *)
chaieb@23274
   380
consts bnds:: "num \<Rightarrow> nat list"
chaieb@23274
   381
  lex_ns:: "nat list \<times> nat list \<Rightarrow> bool"
chaieb@23274
   382
recdef bnds "measure size"
chaieb@23274
   383
  "bnds (Bound n) = [n]"
chaieb@23995
   384
  "bnds (CN n c a) = n#(bnds a)"
chaieb@23274
   385
  "bnds (Neg a) = bnds a"
chaieb@23274
   386
  "bnds (Add a b) = (bnds a)@(bnds b)"
chaieb@23274
   387
  "bnds (Sub a b) = (bnds a)@(bnds b)"
chaieb@23274
   388
  "bnds (Mul i a) = bnds a"
chaieb@23274
   389
  "bnds a = []"
chaieb@23274
   390
recdef lex_ns "measure (\<lambda> (xs,ys). length xs + length ys)"
chaieb@23274
   391
  "lex_ns ([], ms) = True"
chaieb@23274
   392
  "lex_ns (ns, []) = False"
chaieb@23274
   393
  "lex_ns (n#ns, m#ms) = (n<m \<or> ((n = m) \<and> lex_ns (ns,ms))) "
haftmann@35416
   394
definition lex_bnd :: "num \<Rightarrow> num \<Rightarrow> bool" where
chaieb@23274
   395
  "lex_bnd t s \<equiv> lex_ns (bnds t, bnds s)"
chaieb@23274
   396
haftmann@23689
   397
consts
chaieb@23274
   398
  numadd:: "num \<times> num \<Rightarrow> num"
chaieb@23995
   399
recdef numadd "measure (\<lambda> (t,s). num_size t + num_size s)"
chaieb@23995
   400
  "numadd (CN n1 c1 r1 ,CN n2 c2 r2) =
chaieb@23274
   401
  (if n1=n2 then 
chaieb@23274
   402
  (let c = c1 + c2
chaieb@23995
   403
  in (if c=0 then numadd(r1,r2) else CN n1 c (numadd (r1,r2))))
chaieb@23995
   404
  else if n1 \<le> n2 then CN n1 c1 (numadd (r1,Add (Mul c2 (Bound n2)) r2))
chaieb@23995
   405
  else CN n2 c2 (numadd (Add (Mul c1 (Bound n1)) r1,r2)))"
chaieb@23995
   406
  "numadd (CN n1 c1 r1, t) = CN n1 c1 (numadd (r1, t))"  
chaieb@23995
   407
  "numadd (t,CN n2 c2 r2) = CN n2 c2 (numadd (t,r2))" 
chaieb@23274
   408
  "numadd (C b1, C b2) = C (b1+b2)"
chaieb@23274
   409
  "numadd (a,b) = Add a b"
chaieb@23274
   410
haftmann@23689
   411
(*function (sequential)
haftmann@23689
   412
  numadd :: "num \<Rightarrow> num \<Rightarrow> num"
haftmann@23689
   413
where
haftmann@23689
   414
  "numadd (Add (Mul c1 (Bound n1)) r1) (Add (Mul c2 (Bound n2)) r2) =
haftmann@23689
   415
      (if n1 = n2 then (let c = c1 + c2
haftmann@23689
   416
      in (if c = 0 then numadd r1 r2 else
haftmann@23689
   417
        Add (Mul c (Bound n1)) (numadd r1 r2)))
haftmann@23689
   418
      else if n1 \<le> n2 then
haftmann@23689
   419
        Add (Mul c1 (Bound n1)) (numadd r1 (Add (Mul c2 (Bound n2)) r2))
haftmann@23689
   420
      else
haftmann@23689
   421
        Add (Mul c2 (Bound n2)) (numadd (Add (Mul c1 (Bound n1)) r1) r2))"
haftmann@23689
   422
  | "numadd (Add (Mul c1 (Bound n1)) r1) t =
haftmann@23689
   423
      Add (Mul c1 (Bound n1)) (numadd r1 t)"  
haftmann@23689
   424
  | "numadd t (Add (Mul c2 (Bound n2)) r2) =
haftmann@23689
   425
      Add (Mul c2 (Bound n2)) (numadd t r2)" 
haftmann@23689
   426
  | "numadd (C b1) (C b2) = C (b1 + b2)"
haftmann@23689
   427
  | "numadd a b = Add a b"
haftmann@23689
   428
apply pat_completeness apply auto*)
haftmann@23689
   429
  
chaieb@23274
   430
lemma numadd: "Inum bs (numadd (t,s)) = Inum bs (Add t s)"
chaieb@23274
   431
apply (induct t s rule: numadd.induct, simp_all add: Let_def)
chaieb@23274
   432
apply (case_tac "c1+c2 = 0",case_tac "n1 \<le> n2", simp_all)
nipkow@23477
   433
 apply (case_tac "n1 = n2")
nipkow@29667
   434
  apply(simp_all add: algebra_simps)
nipkow@23477
   435
apply(simp add: left_distrib[symmetric])
nipkow@23477
   436
done
chaieb@23274
   437
chaieb@23274
   438
lemma numadd_nb: "\<lbrakk> numbound0 t ; numbound0 s\<rbrakk> \<Longrightarrow> numbound0 (numadd (t,s))"
chaieb@23274
   439
by (induct t s rule: numadd.induct, auto simp add: Let_def)
chaieb@23274
   440
haftmann@23689
   441
fun
haftmann@23689
   442
  nummul :: "int \<Rightarrow> num \<Rightarrow> num"
haftmann@23689
   443
where
haftmann@23689
   444
  "nummul i (C j) = C (i * j)"
chaieb@23995
   445
  | "nummul i (CN n c t) = CN n (c*i) (nummul i t)"
haftmann@23689
   446
  | "nummul i t = Mul i t"
chaieb@23274
   447
haftmann@23689
   448
lemma nummul: "\<And> i. Inum bs (nummul i t) = Inum bs (Mul i t)"
nipkow@29667
   449
by (induct t rule: nummul.induct, auto simp add: algebra_simps numadd)
chaieb@23274
   450
haftmann@23689
   451
lemma nummul_nb: "\<And> i. numbound0 t \<Longrightarrow> numbound0 (nummul i t)"
chaieb@23274
   452
by (induct t rule: nummul.induct, auto simp add: numadd_nb)
chaieb@23274
   453
haftmann@35416
   454
definition numneg :: "num \<Rightarrow> num" where
haftmann@23689
   455
  "numneg t \<equiv> nummul (- 1) t"
chaieb@23274
   456
haftmann@35416
   457
definition numsub :: "num \<Rightarrow> num \<Rightarrow> num" where
haftmann@23689
   458
  "numsub s t \<equiv> (if s = t then C 0 else numadd (s, numneg t))"
chaieb@23274
   459
chaieb@23274
   460
lemma numneg: "Inum bs (numneg t) = Inum bs (Neg t)"
chaieb@23274
   461
using numneg_def nummul by simp
chaieb@23274
   462
chaieb@23274
   463
lemma numneg_nb: "numbound0 t \<Longrightarrow> numbound0 (numneg t)"
chaieb@23274
   464
using numneg_def nummul_nb by simp
chaieb@23274
   465
chaieb@23274
   466
lemma numsub: "Inum bs (numsub a b) = Inum bs (Sub a b)"
chaieb@23274
   467
using numneg numadd numsub_def by simp
chaieb@23274
   468
chaieb@23274
   469
lemma numsub_nb: "\<lbrakk> numbound0 t ; numbound0 s\<rbrakk> \<Longrightarrow> numbound0 (numsub t s)"
chaieb@23274
   470
using numsub_def numadd_nb numneg_nb by simp
chaieb@23274
   471
haftmann@23689
   472
fun
haftmann@23689
   473
  simpnum :: "num \<Rightarrow> num"
haftmann@23689
   474
where
chaieb@23274
   475
  "simpnum (C j) = C j"
chaieb@23995
   476
  | "simpnum (Bound n) = CN n 1 (C 0)"
haftmann@23689
   477
  | "simpnum (Neg t) = numneg (simpnum t)"
haftmann@23689
   478
  | "simpnum (Add t s) = numadd (simpnum t, simpnum s)"
haftmann@23689
   479
  | "simpnum (Sub t s) = numsub (simpnum t) (simpnum s)"
haftmann@23689
   480
  | "simpnum (Mul i t) = (if i = 0 then C 0 else nummul i (simpnum t))"
haftmann@23689
   481
  | "simpnum t = t"
chaieb@23274
   482
chaieb@23274
   483
lemma simpnum_ci: "Inum bs (simpnum t) = Inum bs t"
chaieb@23274
   484
by (induct t rule: simpnum.induct, auto simp add: numneg numadd numsub nummul)
chaieb@23274
   485
chaieb@23274
   486
lemma simpnum_numbound0: 
chaieb@23274
   487
  "numbound0 t \<Longrightarrow> numbound0 (simpnum t)"
chaieb@23274
   488
by (induct t rule: simpnum.induct, auto simp add: numadd_nb numsub_nb nummul_nb numneg_nb)
chaieb@23274
   489
haftmann@23689
   490
fun
haftmann@23689
   491
  not :: "fm \<Rightarrow> fm"
haftmann@23689
   492
where
chaieb@23274
   493
  "not (NOT p) = p"
haftmann@23689
   494
  | "not T = F"
haftmann@23689
   495
  | "not F = T"
haftmann@23689
   496
  | "not p = NOT p"
chaieb@23274
   497
lemma not: "Ifm bbs bs (not p) = Ifm bbs bs (NOT p)"
chaieb@23274
   498
by (cases p) auto
chaieb@23274
   499
lemma not_qf: "qfree p \<Longrightarrow> qfree (not p)"
chaieb@23274
   500
by (cases p, auto)
chaieb@23274
   501
lemma not_bn: "bound0 p \<Longrightarrow> bound0 (not p)"
chaieb@23274
   502
by (cases p, auto)
chaieb@23274
   503
haftmann@35416
   504
definition conj :: "fm \<Rightarrow> fm \<Rightarrow> fm" where
chaieb@23274
   505
  "conj p q \<equiv> (if (p = F \<or> q=F) then F else if p=T then q else if q=T then p else And p q)"
chaieb@23274
   506
lemma conj: "Ifm bbs bs (conj p q) = Ifm bbs bs (And p q)"
chaieb@23274
   507
by (cases "p=F \<or> q=F",simp_all add: conj_def) (cases p,simp_all)
chaieb@23274
   508
chaieb@23274
   509
lemma conj_qf: "\<lbrakk>qfree p ; qfree q\<rbrakk> \<Longrightarrow> qfree (conj p q)"
chaieb@23274
   510
using conj_def by auto 
chaieb@23274
   511
lemma conj_nb: "\<lbrakk>bound0 p ; bound0 q\<rbrakk> \<Longrightarrow> bound0 (conj p q)"
chaieb@23274
   512
using conj_def by auto 
chaieb@23274
   513
haftmann@35416
   514
definition disj :: "fm \<Rightarrow> fm \<Rightarrow> fm" where
chaieb@23274
   515
  "disj p q \<equiv> (if (p = T \<or> q=T) then T else if p=F then q else if q=F then p else Or p q)"
chaieb@23274
   516
chaieb@23274
   517
lemma disj: "Ifm bbs bs (disj p q) = Ifm bbs bs (Or p q)"
chaieb@23274
   518
by (cases "p=T \<or> q=T",simp_all add: disj_def) (cases p,simp_all)
chaieb@23274
   519
lemma disj_qf: "\<lbrakk>qfree p ; qfree q\<rbrakk> \<Longrightarrow> qfree (disj p q)"
chaieb@23274
   520
using disj_def by auto 
chaieb@23274
   521
lemma disj_nb: "\<lbrakk>bound0 p ; bound0 q\<rbrakk> \<Longrightarrow> bound0 (disj p q)"
chaieb@23274
   522
using disj_def by auto 
chaieb@23274
   523
haftmann@35416
   524
definition imp :: "fm \<Rightarrow> fm \<Rightarrow> fm" where
chaieb@23274
   525
  "imp p q \<equiv> (if (p = F \<or> q=T) then T else if p=T then q else if q=F then not p else Imp p q)"
chaieb@23274
   526
lemma imp: "Ifm bbs bs (imp p q) = Ifm bbs bs (Imp p q)"
chaieb@23274
   527
by (cases "p=F \<or> q=T",simp_all add: imp_def,cases p) (simp_all add: not)
chaieb@23274
   528
lemma imp_qf: "\<lbrakk>qfree p ; qfree q\<rbrakk> \<Longrightarrow> qfree (imp p q)"
chaieb@23274
   529
using imp_def by (cases "p=F \<or> q=T",simp_all add: imp_def,cases p) (simp_all add: not_qf) 
chaieb@23274
   530
lemma imp_nb: "\<lbrakk>bound0 p ; bound0 q\<rbrakk> \<Longrightarrow> bound0 (imp p q)"
chaieb@23274
   531
using imp_def by (cases "p=F \<or> q=T",simp_all add: imp_def,cases p) simp_all
chaieb@23274
   532
haftmann@35416
   533
definition iff :: "fm \<Rightarrow> fm \<Rightarrow> fm" where
chaieb@23274
   534
  "iff p q \<equiv> (if (p = q) then T else if (p = not q \<or> not p = q) then F else 
chaieb@23274
   535
       if p=F then not q else if q=F then not p else if p=T then q else if q=T then p else 
chaieb@23274
   536
  Iff p q)"
chaieb@23274
   537
lemma iff: "Ifm bbs bs (iff p q) = Ifm bbs bs (Iff p q)"
chaieb@23274
   538
  by (unfold iff_def,cases "p=q", simp,cases "p=not q", simp add:not) 
chaieb@23274
   539
(cases "not p= q", auto simp add:not)
chaieb@23274
   540
lemma iff_qf: "\<lbrakk>qfree p ; qfree q\<rbrakk> \<Longrightarrow> qfree (iff p q)"
chaieb@23274
   541
  by (unfold iff_def,cases "p=q", auto simp add: not_qf)
chaieb@23274
   542
lemma iff_nb: "\<lbrakk>bound0 p ; bound0 q\<rbrakk> \<Longrightarrow> bound0 (iff p q)"
chaieb@23274
   543
using iff_def by (unfold iff_def,cases "p=q", auto simp add: not_bn)
chaieb@23274
   544
haftmann@23689
   545
function (sequential)
haftmann@23689
   546
  simpfm :: "fm \<Rightarrow> fm"
haftmann@23689
   547
where
chaieb@23274
   548
  "simpfm (And p q) = conj (simpfm p) (simpfm q)"
haftmann@23689
   549
  | "simpfm (Or p q) = disj (simpfm p) (simpfm q)"
haftmann@23689
   550
  | "simpfm (Imp p q) = imp (simpfm p) (simpfm q)"
haftmann@23689
   551
  | "simpfm (Iff p q) = iff (simpfm p) (simpfm q)"
haftmann@23689
   552
  | "simpfm (NOT p) = not (simpfm p)"
haftmann@23689
   553
  | "simpfm (Lt a) = (let a' = simpnum a in case a' of C v \<Rightarrow> if (v < 0) then T else F 
haftmann@23689
   554
      | _ \<Rightarrow> Lt a')"
haftmann@23689
   555
  | "simpfm (Le a) = (let a' = simpnum a in case a' of C v \<Rightarrow> if (v \<le> 0)  then T else F | _ \<Rightarrow> Le a')"
haftmann@23689
   556
  | "simpfm (Gt a) = (let a' = simpnum a in case a' of C v \<Rightarrow> if (v > 0)  then T else F | _ \<Rightarrow> Gt a')"
haftmann@23689
   557
  | "simpfm (Ge a) = (let a' = simpnum a in case a' of C v \<Rightarrow> if (v \<ge> 0)  then T else F | _ \<Rightarrow> Ge a')"
haftmann@23689
   558
  | "simpfm (Eq a) = (let a' = simpnum a in case a' of C v \<Rightarrow> if (v = 0)  then T else F | _ \<Rightarrow> Eq a')"
haftmann@23689
   559
  | "simpfm (NEq a) = (let a' = simpnum a in case a' of C v \<Rightarrow> if (v \<noteq> 0)  then T else F | _ \<Rightarrow> NEq a')"
haftmann@23689
   560
  | "simpfm (Dvd i a) = (if i=0 then simpfm (Eq a)
chaieb@23274
   561
             else if (abs i = 1) then T
chaieb@23274
   562
             else let a' = simpnum a in case a' of C v \<Rightarrow> if (i dvd v)  then T else F | _ \<Rightarrow> Dvd i a')"
haftmann@23689
   563
  | "simpfm (NDvd i a) = (if i=0 then simpfm (NEq a) 
chaieb@23274
   564
             else if (abs i = 1) then F
chaieb@23274
   565
             else let a' = simpnum a in case a' of C v \<Rightarrow> if (\<not>(i dvd v)) then T else F | _ \<Rightarrow> NDvd i a')"
haftmann@23689
   566
  | "simpfm p = p"
haftmann@23689
   567
by pat_completeness auto
haftmann@23689
   568
termination by (relation "measure fmsize") auto
haftmann@23689
   569
chaieb@23274
   570
lemma simpfm: "Ifm bbs bs (simpfm p) = Ifm bbs bs p"
chaieb@23274
   571
proof(induct p rule: simpfm.induct)
chaieb@23274
   572
  case (6 a) let ?sa = "simpnum a" from simpnum_ci have sa: "Inum bs ?sa = Inum bs a" by simp
chaieb@23274
   573
  {fix v assume "?sa = C v" hence ?case using sa by simp }
chaieb@23274
   574
  moreover {assume "\<not> (\<exists> v. ?sa = C v)" hence ?case using sa 
chaieb@23274
   575
      by (cases ?sa, simp_all add: Let_def)}
chaieb@23274
   576
  ultimately show ?case by blast
chaieb@17378
   577
next
chaieb@23274
   578
  case (7 a)  let ?sa = "simpnum a" 
chaieb@23274
   579
  from simpnum_ci have sa: "Inum bs ?sa = Inum bs a" by simp
chaieb@23274
   580
  {fix v assume "?sa = C v" hence ?case using sa by simp }
chaieb@23274
   581
  moreover {assume "\<not> (\<exists> v. ?sa = C v)" hence ?case using sa 
chaieb@23274
   582
      by (cases ?sa, simp_all add: Let_def)}
chaieb@23274
   583
  ultimately show ?case by blast
chaieb@23274
   584
next
chaieb@23274
   585
  case (8 a)  let ?sa = "simpnum a" 
chaieb@23274
   586
  from simpnum_ci have sa: "Inum bs ?sa = Inum bs a" by simp
chaieb@23274
   587
  {fix v assume "?sa = C v" hence ?case using sa by simp }
chaieb@23274
   588
  moreover {assume "\<not> (\<exists> v. ?sa = C v)" hence ?case using sa 
chaieb@23274
   589
      by (cases ?sa, simp_all add: Let_def)}
chaieb@23274
   590
  ultimately show ?case by blast
chaieb@23274
   591
next
chaieb@23274
   592
  case (9 a)  let ?sa = "simpnum a" 
chaieb@23274
   593
  from simpnum_ci have sa: "Inum bs ?sa = Inum bs a" by simp
chaieb@23274
   594
  {fix v assume "?sa = C v" hence ?case using sa by simp }
chaieb@23274
   595
  moreover {assume "\<not> (\<exists> v. ?sa = C v)" hence ?case using sa 
chaieb@23274
   596
      by (cases ?sa, simp_all add: Let_def)}
chaieb@23274
   597
  ultimately show ?case by blast
chaieb@23274
   598
next
chaieb@23274
   599
  case (10 a)  let ?sa = "simpnum a" 
chaieb@23274
   600
  from simpnum_ci have sa: "Inum bs ?sa = Inum bs a" by simp
chaieb@23274
   601
  {fix v assume "?sa = C v" hence ?case using sa by simp }
chaieb@23274
   602
  moreover {assume "\<not> (\<exists> v. ?sa = C v)" hence ?case using sa 
chaieb@23274
   603
      by (cases ?sa, simp_all add: Let_def)}
chaieb@23274
   604
  ultimately show ?case by blast
chaieb@23274
   605
next
chaieb@23274
   606
  case (11 a)  let ?sa = "simpnum a" 
chaieb@23274
   607
  from simpnum_ci have sa: "Inum bs ?sa = Inum bs a" by simp
chaieb@23274
   608
  {fix v assume "?sa = C v" hence ?case using sa by simp }
chaieb@23274
   609
  moreover {assume "\<not> (\<exists> v. ?sa = C v)" hence ?case using sa 
chaieb@23274
   610
      by (cases ?sa, simp_all add: Let_def)}
chaieb@23274
   611
  ultimately show ?case by blast
chaieb@23274
   612
next
chaieb@23274
   613
  case (12 i a)  let ?sa = "simpnum a" from simpnum_ci 
chaieb@23274
   614
  have sa: "Inum bs ?sa = Inum bs a" by simp
chaieb@23274
   615
  have "i=0 \<or> abs i = 1 \<or> (i\<noteq>0 \<and> (abs i \<noteq> 1))" by auto
chaieb@23274
   616
  {assume "i=0" hence ?case using "12.hyps" by (simp add: dvd_def Let_def)}
chaieb@23274
   617
  moreover 
chaieb@23274
   618
  {assume i1: "abs i = 1"
nipkow@30042
   619
      from one_dvd[of "Inum bs a"] uminus_dvd_conv[where d="1" and t="Inum bs a"]
chaieb@23315
   620
      have ?case using i1 apply (cases "i=0", simp_all add: Let_def) 
wenzelm@32960
   621
        by (cases "i > 0", simp_all)}
chaieb@23274
   622
  moreover   
chaieb@23274
   623
  {assume inz: "i\<noteq>0" and cond: "abs i \<noteq> 1"
chaieb@23274
   624
    {fix v assume "?sa = C v" hence ?case using sa[symmetric] inz cond
wenzelm@32960
   625
        by (cases "abs i = 1", auto) }
chaieb@23274
   626
    moreover {assume "\<not> (\<exists> v. ?sa = C v)" 
chaieb@23274
   627
      hence "simpfm (Dvd i a) = Dvd i ?sa" using inz cond 
wenzelm@32960
   628
        by (cases ?sa, auto simp add: Let_def)
chaieb@23274
   629
      hence ?case using sa by simp}
chaieb@23274
   630
    ultimately have ?case by blast}
chaieb@23274
   631
  ultimately show ?case by blast
chaieb@23274
   632
next
chaieb@23274
   633
  case (13 i a)  let ?sa = "simpnum a" from simpnum_ci 
chaieb@23274
   634
  have sa: "Inum bs ?sa = Inum bs a" by simp
chaieb@23274
   635
  have "i=0 \<or> abs i = 1 \<or> (i\<noteq>0 \<and> (abs i \<noteq> 1))" by auto
chaieb@23274
   636
  {assume "i=0" hence ?case using "13.hyps" by (simp add: dvd_def Let_def)}
chaieb@23274
   637
  moreover 
chaieb@23274
   638
  {assume i1: "abs i = 1"
nipkow@30042
   639
      from one_dvd[of "Inum bs a"] uminus_dvd_conv[where d="1" and t="Inum bs a"]
chaieb@23315
   640
      have ?case using i1 apply (cases "i=0", simp_all add: Let_def)
chaieb@23315
   641
      apply (cases "i > 0", simp_all) done}
chaieb@23274
   642
  moreover   
chaieb@23274
   643
  {assume inz: "i\<noteq>0" and cond: "abs i \<noteq> 1"
chaieb@23274
   644
    {fix v assume "?sa = C v" hence ?case using sa[symmetric] inz cond
wenzelm@32960
   645
        by (cases "abs i = 1", auto) }
chaieb@23274
   646
    moreover {assume "\<not> (\<exists> v. ?sa = C v)" 
chaieb@23274
   647
      hence "simpfm (NDvd i a) = NDvd i ?sa" using inz cond 
wenzelm@32960
   648
        by (cases ?sa, auto simp add: Let_def)
chaieb@23274
   649
      hence ?case using sa by simp}
chaieb@23274
   650
    ultimately have ?case by blast}
chaieb@23274
   651
  ultimately show ?case by blast
chaieb@23274
   652
qed (induct p rule: simpfm.induct, simp_all add: conj disj imp iff not)
chaieb@17378
   653
chaieb@23274
   654
lemma simpfm_bound0: "bound0 p \<Longrightarrow> bound0 (simpfm p)"
chaieb@23274
   655
proof(induct p rule: simpfm.induct)
chaieb@23274
   656
  case (6 a) hence nb: "numbound0 a" by simp
chaieb@23274
   657
  hence "numbound0 (simpnum a)" by (simp only: simpnum_numbound0[OF nb])
chaieb@23274
   658
  thus ?case by (cases "simpnum a", auto simp add: Let_def)
chaieb@23274
   659
next
chaieb@23274
   660
  case (7 a) hence nb: "numbound0 a" by simp
chaieb@23274
   661
  hence "numbound0 (simpnum a)" by (simp only: simpnum_numbound0[OF nb])
chaieb@23274
   662
  thus ?case by (cases "simpnum a", auto simp add: Let_def)
chaieb@23274
   663
next
chaieb@23274
   664
  case (8 a) hence nb: "numbound0 a" by simp
chaieb@23274
   665
  hence "numbound0 (simpnum a)" by (simp only: simpnum_numbound0[OF nb])
chaieb@23274
   666
  thus ?case by (cases "simpnum a", auto simp add: Let_def)
chaieb@23274
   667
next
chaieb@23274
   668
  case (9 a) hence nb: "numbound0 a" by simp
chaieb@23274
   669
  hence "numbound0 (simpnum a)" by (simp only: simpnum_numbound0[OF nb])
chaieb@23274
   670
  thus ?case by (cases "simpnum a", auto simp add: Let_def)
chaieb@23274
   671
next
chaieb@23274
   672
  case (10 a) hence nb: "numbound0 a" by simp
chaieb@23274
   673
  hence "numbound0 (simpnum a)" by (simp only: simpnum_numbound0[OF nb])
chaieb@23274
   674
  thus ?case by (cases "simpnum a", auto simp add: Let_def)
chaieb@23274
   675
next
chaieb@23274
   676
  case (11 a) hence nb: "numbound0 a" by simp
chaieb@23274
   677
  hence "numbound0 (simpnum a)" by (simp only: simpnum_numbound0[OF nb])
chaieb@23274
   678
  thus ?case by (cases "simpnum a", auto simp add: Let_def)
chaieb@23274
   679
next
chaieb@23274
   680
  case (12 i a) hence nb: "numbound0 a" by simp
chaieb@23274
   681
  hence "numbound0 (simpnum a)" by (simp only: simpnum_numbound0[OF nb])
chaieb@23274
   682
  thus ?case by (cases "simpnum a", auto simp add: Let_def)
chaieb@23274
   683
next
chaieb@23274
   684
  case (13 i a) hence nb: "numbound0 a" by simp
chaieb@23274
   685
  hence "numbound0 (simpnum a)" by (simp only: simpnum_numbound0[OF nb])
chaieb@23274
   686
  thus ?case by (cases "simpnum a", auto simp add: Let_def)
chaieb@23274
   687
qed(auto simp add: disj_def imp_def iff_def conj_def not_bn)
chaieb@17378
   688
chaieb@23274
   689
lemma simpfm_qf: "qfree p \<Longrightarrow> qfree (simpfm p)"
chaieb@23274
   690
by (induct p rule: simpfm.induct, auto simp add: disj_qf imp_qf iff_qf conj_qf not_qf Let_def)
chaieb@23274
   691
 (case_tac "simpnum a",auto)+
chaieb@23274
   692
chaieb@23274
   693
  (* Generic quantifier elimination *)
chaieb@23274
   694
consts qelim :: "fm \<Rightarrow> (fm \<Rightarrow> fm) \<Rightarrow> fm"
chaieb@23274
   695
recdef qelim "measure fmsize"
chaieb@23274
   696
  "qelim (E p) = (\<lambda> qe. DJ qe (qelim p qe))"
chaieb@23274
   697
  "qelim (A p) = (\<lambda> qe. not (qe ((qelim (NOT p) qe))))"
chaieb@23274
   698
  "qelim (NOT p) = (\<lambda> qe. not (qelim p qe))"
chaieb@23274
   699
  "qelim (And p q) = (\<lambda> qe. conj (qelim p qe) (qelim q qe))" 
chaieb@23274
   700
  "qelim (Or  p q) = (\<lambda> qe. disj (qelim p qe) (qelim q qe))" 
chaieb@23274
   701
  "qelim (Imp p q) = (\<lambda> qe. imp (qelim p qe) (qelim q qe))"
chaieb@23274
   702
  "qelim (Iff p q) = (\<lambda> qe. iff (qelim p qe) (qelim q qe))"
chaieb@23274
   703
  "qelim p = (\<lambda> y. simpfm p)"
chaieb@23274
   704
haftmann@23689
   705
(*function (sequential)
haftmann@23689
   706
  qelim :: "(fm \<Rightarrow> fm) \<Rightarrow> fm \<Rightarrow> fm"
haftmann@23689
   707
where
haftmann@23689
   708
  "qelim qe (E p) = DJ qe (qelim qe p)"
haftmann@23689
   709
  | "qelim qe (A p) = not (qe ((qelim qe (NOT p))))"
haftmann@23689
   710
  | "qelim qe (NOT p) = not (qelim qe p)"
haftmann@23689
   711
  | "qelim qe (And p q) = conj (qelim qe p) (qelim qe q)" 
haftmann@23689
   712
  | "qelim qe (Or  p q) = disj (qelim qe p) (qelim qe q)" 
haftmann@23689
   713
  | "qelim qe (Imp p q) = imp (qelim qe p) (qelim qe q)"
haftmann@23689
   714
  | "qelim qe (Iff p q) = iff (qelim qe p) (qelim qe q)"
haftmann@23689
   715
  | "qelim qe p = simpfm p"
haftmann@23689
   716
by pat_completeness auto
haftmann@23689
   717
termination by (relation "measure (fmsize o snd)") auto*)
haftmann@23689
   718
chaieb@23274
   719
lemma qelim_ci:
chaieb@23274
   720
  assumes qe_inv: "\<forall> bs p. qfree p \<longrightarrow> qfree (qe p) \<and> (Ifm bbs bs (qe p) = Ifm bbs bs (E p))"
chaieb@23274
   721
  shows "\<And> bs. qfree (qelim p qe) \<and> (Ifm bbs bs (qelim p qe) = Ifm bbs bs p)"
chaieb@23274
   722
using qe_inv DJ_qe[OF qe_inv] 
chaieb@23274
   723
by(induct p rule: qelim.induct) 
chaieb@23274
   724
(auto simp add: not disj conj iff imp not_qf disj_qf conj_qf imp_qf iff_qf 
chaieb@23274
   725
  simpfm simpfm_qf simp del: simpfm.simps)
chaieb@23274
   726
  (* Linearity for fm where Bound 0 ranges over \<int> *)
haftmann@23689
   727
haftmann@23689
   728
fun
chaieb@23274
   729
  zsplit0 :: "num \<Rightarrow> int \<times> num" (* splits the bounded from the unbounded part*)
haftmann@23689
   730
where
chaieb@23274
   731
  "zsplit0 (C c) = (0,C c)"
haftmann@23689
   732
  | "zsplit0 (Bound n) = (if n=0 then (1, C 0) else (0,Bound n))"
chaieb@23995
   733
  | "zsplit0 (CN n i a) = 
chaieb@23995
   734
      (let (i',a') =  zsplit0 a 
chaieb@23995
   735
       in if n=0 then (i+i', a') else (i',CN n i a'))"
haftmann@23689
   736
  | "zsplit0 (Neg a) = (let (i',a') =  zsplit0 a in (-i', Neg a'))"
haftmann@23689
   737
  | "zsplit0 (Add a b) = (let (ia,a') =  zsplit0 a ; 
chaieb@23274
   738
                            (ib,b') =  zsplit0 b 
chaieb@23274
   739
                            in (ia+ib, Add a' b'))"
haftmann@23689
   740
  | "zsplit0 (Sub a b) = (let (ia,a') =  zsplit0 a ; 
chaieb@23274
   741
                            (ib,b') =  zsplit0 b 
chaieb@23274
   742
                            in (ia-ib, Sub a' b'))"
haftmann@23689
   743
  | "zsplit0 (Mul i a) = (let (i',a') =  zsplit0 a in (i*i', Mul i a'))"
chaieb@23274
   744
chaieb@23274
   745
lemma zsplit0_I:
chaieb@23995
   746
  shows "\<And> n a. zsplit0 t = (n,a) \<Longrightarrow> (Inum ((x::int) #bs) (CN 0 n a) = Inum (x #bs) t) \<and> numbound0 a"
chaieb@23995
   747
  (is "\<And> n a. ?S t = (n,a) \<Longrightarrow> (?I x (CN 0 n a) = ?I x t) \<and> ?N a")
chaieb@23274
   748
proof(induct t rule: zsplit0.induct)
chaieb@23274
   749
  case (1 c n a) thus ?case by auto 
chaieb@23274
   750
next
chaieb@23274
   751
  case (2 m n a) thus ?case by (cases "m=0") auto
chaieb@23274
   752
next
chaieb@23995
   753
  case (3 m i a n a')
chaieb@23274
   754
  let ?j = "fst (zsplit0 a)"
chaieb@23274
   755
  let ?b = "snd (zsplit0 a)"
chaieb@23995
   756
  have abj: "zsplit0 a = (?j,?b)" by simp 
chaieb@23995
   757
  {assume "m\<noteq>0" 
chaieb@23995
   758
    with prems(1)[OF abj] prems(2) have ?case by (auto simp add: Let_def split_def)}
chaieb@23995
   759
  moreover
chaieb@23995
   760
  {assume m0: "m =0"
chaieb@23995
   761
    from abj have th: "a'=?b \<and> n=i+?j" using prems 
chaieb@23995
   762
      by (simp add: Let_def split_def)
chaieb@23995
   763
    from abj prems  have th2: "(?I x (CN 0 ?j ?b) = ?I x a) \<and> ?N ?b" by blast
chaieb@23995
   764
    from th have "?I x (CN 0 n a') = ?I x (CN 0 (i+?j) ?b)" by simp
chaieb@23995
   765
    also from th2 have "\<dots> = ?I x (CN 0 i (CN 0 ?j ?b))" by (simp add: left_distrib)
chaieb@23995
   766
  finally have "?I x (CN 0 n a') = ?I  x (CN 0 i a)" using th2 by simp
chaieb@23995
   767
  with th2 th have ?case using m0 by blast} 
chaieb@23995
   768
ultimately show ?case by blast
chaieb@23274
   769
next
chaieb@23274
   770
  case (4 t n a)
chaieb@23274
   771
  let ?nt = "fst (zsplit0 t)"
chaieb@23274
   772
  let ?at = "snd (zsplit0 t)"
chaieb@23274
   773
  have abj: "zsplit0 t = (?nt,?at)" by simp hence th: "a=Neg ?at \<and> n=-?nt" using prems 
chaieb@23274
   774
    by (simp add: Let_def split_def)
chaieb@23995
   775
  from abj prems  have th2: "(?I x (CN 0 ?nt ?at) = ?I x t) \<and> ?N ?at" by blast
chaieb@23274
   776
  from th2[simplified] th[simplified] show ?case by simp
chaieb@23274
   777
next
chaieb@23274
   778
  case (5 s t n a)
chaieb@23274
   779
  let ?ns = "fst (zsplit0 s)"
chaieb@23274
   780
  let ?as = "snd (zsplit0 s)"
chaieb@23274
   781
  let ?nt = "fst (zsplit0 t)"
chaieb@23274
   782
  let ?at = "snd (zsplit0 t)"
chaieb@23274
   783
  have abjs: "zsplit0 s = (?ns,?as)" by simp 
chaieb@23274
   784
  moreover have abjt:  "zsplit0 t = (?nt,?at)" by simp 
chaieb@23274
   785
  ultimately have th: "a=Add ?as ?at \<and> n=?ns + ?nt" using prems 
chaieb@23274
   786
    by (simp add: Let_def split_def)
chaieb@23274
   787
  from abjs[symmetric] have bluddy: "\<exists> x y. (x,y) = zsplit0 s" by blast
chaieb@23995
   788
  from prems have "(\<exists> x y. (x,y) = zsplit0 s) \<longrightarrow> (\<forall>xa xb. zsplit0 t = (xa, xb) \<longrightarrow> Inum (x # bs) (CN 0 xa xb) = Inum (x # bs) t \<and> numbound0 xb)" by auto
chaieb@23995
   789
  with bluddy abjt have th3: "(?I x (CN 0 ?nt ?at) = ?I x t) \<and> ?N ?at" by blast
chaieb@23995
   790
  from abjs prems  have th2: "(?I x (CN 0 ?ns ?as) = ?I x s) \<and> ?N ?as" by blast
chaieb@23274
   791
  from th3[simplified] th2[simplified] th[simplified] show ?case 
chaieb@23274
   792
    by (simp add: left_distrib)
chaieb@23274
   793
next
chaieb@23274
   794
  case (6 s t n a)
chaieb@23274
   795
  let ?ns = "fst (zsplit0 s)"
chaieb@23274
   796
  let ?as = "snd (zsplit0 s)"
chaieb@23274
   797
  let ?nt = "fst (zsplit0 t)"
chaieb@23274
   798
  let ?at = "snd (zsplit0 t)"
chaieb@23274
   799
  have abjs: "zsplit0 s = (?ns,?as)" by simp 
chaieb@23274
   800
  moreover have abjt:  "zsplit0 t = (?nt,?at)" by simp 
chaieb@23274
   801
  ultimately have th: "a=Sub ?as ?at \<and> n=?ns - ?nt" using prems 
chaieb@23274
   802
    by (simp add: Let_def split_def)
chaieb@23274
   803
  from abjs[symmetric] have bluddy: "\<exists> x y. (x,y) = zsplit0 s" by blast
chaieb@23995
   804
  from prems have "(\<exists> x y. (x,y) = zsplit0 s) \<longrightarrow> (\<forall>xa xb. zsplit0 t = (xa, xb) \<longrightarrow> Inum (x # bs) (CN 0 xa xb) = Inum (x # bs) t \<and> numbound0 xb)" by auto
chaieb@23995
   805
  with bluddy abjt have th3: "(?I x (CN 0 ?nt ?at) = ?I x t) \<and> ?N ?at" by blast
chaieb@23995
   806
  from abjs prems  have th2: "(?I x (CN 0 ?ns ?as) = ?I x s) \<and> ?N ?as" by blast
chaieb@23274
   807
  from th3[simplified] th2[simplified] th[simplified] show ?case 
chaieb@23274
   808
    by (simp add: left_diff_distrib)
chaieb@23274
   809
next
chaieb@23274
   810
  case (7 i t n a)
chaieb@23274
   811
  let ?nt = "fst (zsplit0 t)"
chaieb@23274
   812
  let ?at = "snd (zsplit0 t)"
chaieb@23274
   813
  have abj: "zsplit0 t = (?nt,?at)" by simp hence th: "a=Mul i ?at \<and> n=i*?nt" using prems 
chaieb@23274
   814
    by (simp add: Let_def split_def)
chaieb@23995
   815
  from abj prems  have th2: "(?I x (CN 0 ?nt ?at) = ?I x t) \<and> ?N ?at" by blast
chaieb@23995
   816
  hence " ?I x (Mul i t) = i * ?I x (CN 0 ?nt ?at)" by simp
chaieb@23995
   817
  also have "\<dots> = ?I x (CN 0 (i*?nt) (Mul i ?at))" by (simp add: right_distrib)
chaieb@23274
   818
  finally show ?case using th th2 by simp
chaieb@17378
   819
qed
chaieb@17378
   820
chaieb@23274
   821
consts
chaieb@23274
   822
  iszlfm :: "fm \<Rightarrow> bool"   (* Linearity test for fm *)
chaieb@23274
   823
recdef iszlfm "measure size"
chaieb@23274
   824
  "iszlfm (And p q) = (iszlfm p \<and> iszlfm q)" 
chaieb@23274
   825
  "iszlfm (Or p q) = (iszlfm p \<and> iszlfm q)" 
chaieb@23995
   826
  "iszlfm (Eq  (CN 0 c e)) = (c>0 \<and> numbound0 e)"
chaieb@23995
   827
  "iszlfm (NEq (CN 0 c e)) = (c>0 \<and> numbound0 e)"
chaieb@23995
   828
  "iszlfm (Lt  (CN 0 c e)) = (c>0 \<and> numbound0 e)"
chaieb@23995
   829
  "iszlfm (Le  (CN 0 c e)) = (c>0 \<and> numbound0 e)"
chaieb@23995
   830
  "iszlfm (Gt  (CN 0 c e)) = (c>0 \<and> numbound0 e)"
chaieb@23995
   831
  "iszlfm (Ge  (CN 0 c e)) = ( c>0 \<and> numbound0 e)"
chaieb@23995
   832
  "iszlfm (Dvd i (CN 0 c e)) = 
chaieb@23274
   833
                 (c>0 \<and> i>0 \<and> numbound0 e)"
chaieb@23995
   834
  "iszlfm (NDvd i (CN 0 c e))= 
chaieb@23274
   835
                 (c>0 \<and> i>0 \<and> numbound0 e)"
chaieb@23274
   836
  "iszlfm p = (isatom p \<and> (bound0 p))"
chaieb@17378
   837
chaieb@23274
   838
lemma zlin_qfree: "iszlfm p \<Longrightarrow> qfree p"
chaieb@23274
   839
  by (induct p rule: iszlfm.induct) auto
chaieb@17378
   840
haftmann@23689
   841
consts
haftmann@23689
   842
  zlfm :: "fm \<Rightarrow> fm"       (* Linearity transformation for fm *)
chaieb@23274
   843
recdef zlfm "measure fmsize"
chaieb@23274
   844
  "zlfm (And p q) = And (zlfm p) (zlfm q)"
chaieb@23274
   845
  "zlfm (Or p q) = Or (zlfm p) (zlfm q)"
chaieb@23274
   846
  "zlfm (Imp p q) = Or (zlfm (NOT p)) (zlfm q)"
chaieb@23274
   847
  "zlfm (Iff p q) = Or (And (zlfm p) (zlfm q)) (And (zlfm (NOT p)) (zlfm (NOT q)))"
chaieb@23274
   848
  "zlfm (Lt a) = (let (c,r) = zsplit0 a in 
chaieb@23274
   849
     if c=0 then Lt r else 
chaieb@23995
   850
     if c>0 then (Lt (CN 0 c r)) else (Gt (CN 0 (- c) (Neg r))))"
chaieb@23274
   851
  "zlfm (Le a) = (let (c,r) = zsplit0 a in 
chaieb@23274
   852
     if c=0 then Le r else 
chaieb@23995
   853
     if c>0 then (Le (CN 0 c r)) else (Ge (CN 0 (- c) (Neg r))))"
chaieb@23274
   854
  "zlfm (Gt a) = (let (c,r) = zsplit0 a in 
chaieb@23274
   855
     if c=0 then Gt r else 
chaieb@23995
   856
     if c>0 then (Gt (CN 0 c r)) else (Lt (CN 0 (- c) (Neg r))))"
chaieb@23274
   857
  "zlfm (Ge a) = (let (c,r) = zsplit0 a in 
chaieb@23274
   858
     if c=0 then Ge r else 
chaieb@23995
   859
     if c>0 then (Ge (CN 0 c r)) else (Le (CN 0 (- c) (Neg r))))"
chaieb@23274
   860
  "zlfm (Eq a) = (let (c,r) = zsplit0 a in 
chaieb@23274
   861
     if c=0 then Eq r else 
chaieb@23995
   862
     if c>0 then (Eq (CN 0 c r)) else (Eq (CN 0 (- c) (Neg r))))"
chaieb@23274
   863
  "zlfm (NEq a) = (let (c,r) = zsplit0 a in 
chaieb@23274
   864
     if c=0 then NEq r else 
chaieb@23995
   865
     if c>0 then (NEq (CN 0 c r)) else (NEq (CN 0 (- c) (Neg r))))"
chaieb@23274
   866
  "zlfm (Dvd i a) = (if i=0 then zlfm (Eq a) 
chaieb@23274
   867
        else (let (c,r) = zsplit0 a in 
chaieb@23274
   868
              if c=0 then (Dvd (abs i) r) else 
chaieb@23995
   869
      if c>0 then (Dvd (abs i) (CN 0 c r))
chaieb@23995
   870
      else (Dvd (abs i) (CN 0 (- c) (Neg r)))))"
chaieb@23274
   871
  "zlfm (NDvd i a) = (if i=0 then zlfm (NEq a) 
chaieb@23274
   872
        else (let (c,r) = zsplit0 a in 
chaieb@23274
   873
              if c=0 then (NDvd (abs i) r) else 
chaieb@23995
   874
      if c>0 then (NDvd (abs i) (CN 0 c r))
chaieb@23995
   875
      else (NDvd (abs i) (CN 0 (- c) (Neg r)))))"
chaieb@23274
   876
  "zlfm (NOT (And p q)) = Or (zlfm (NOT p)) (zlfm (NOT q))"
chaieb@23274
   877
  "zlfm (NOT (Or p q)) = And (zlfm (NOT p)) (zlfm (NOT q))"
chaieb@23274
   878
  "zlfm (NOT (Imp p q)) = And (zlfm p) (zlfm (NOT q))"
chaieb@23274
   879
  "zlfm (NOT (Iff p q)) = Or (And(zlfm p) (zlfm(NOT q))) (And (zlfm(NOT p)) (zlfm q))"
chaieb@23274
   880
  "zlfm (NOT (NOT p)) = zlfm p"
chaieb@23274
   881
  "zlfm (NOT T) = F"
chaieb@23274
   882
  "zlfm (NOT F) = T"
chaieb@23274
   883
  "zlfm (NOT (Lt a)) = zlfm (Ge a)"
chaieb@23274
   884
  "zlfm (NOT (Le a)) = zlfm (Gt a)"
chaieb@23274
   885
  "zlfm (NOT (Gt a)) = zlfm (Le a)"
chaieb@23274
   886
  "zlfm (NOT (Ge a)) = zlfm (Lt a)"
chaieb@23274
   887
  "zlfm (NOT (Eq a)) = zlfm (NEq a)"
chaieb@23274
   888
  "zlfm (NOT (NEq a)) = zlfm (Eq a)"
chaieb@23274
   889
  "zlfm (NOT (Dvd i a)) = zlfm (NDvd i a)"
chaieb@23274
   890
  "zlfm (NOT (NDvd i a)) = zlfm (Dvd i a)"
chaieb@23274
   891
  "zlfm (NOT (Closed P)) = NClosed P"
chaieb@23274
   892
  "zlfm (NOT (NClosed P)) = Closed P"
chaieb@23274
   893
  "zlfm p = p" (hints simp add: fmsize_pos)
chaieb@23274
   894
chaieb@23274
   895
lemma zlfm_I:
chaieb@23274
   896
  assumes qfp: "qfree p"
chaieb@23274
   897
  shows "(Ifm bbs (i#bs) (zlfm p) = Ifm bbs (i# bs) p) \<and> iszlfm (zlfm p)"
chaieb@23274
   898
  (is "(?I (?l p) = ?I p) \<and> ?L (?l p)")
chaieb@23274
   899
using qfp
chaieb@23274
   900
proof(induct p rule: zlfm.induct)
chaieb@23274
   901
  case (5 a) 
chaieb@23274
   902
  let ?c = "fst (zsplit0 a)"
chaieb@23274
   903
  let ?r = "snd (zsplit0 a)"
chaieb@23274
   904
  have spl: "zsplit0 a = (?c,?r)" by simp
chaieb@23274
   905
  from zsplit0_I[OF spl, where x="i" and bs="bs"] 
chaieb@23995
   906
  have Ia:"Inum (i # bs) a = Inum (i #bs) (CN 0 ?c ?r)" and nb: "numbound0 ?r" by auto 
chaieb@23274
   907
  let ?N = "\<lambda> t. Inum (i#bs) t"
chaieb@23274
   908
  from prems Ia nb  show ?case 
nipkow@29667
   909
    apply (auto simp add: Let_def split_def algebra_simps) 
chaieb@23995
   910
    apply (cases "?r",auto)
chaieb@23995
   911
    apply (case_tac nat, auto)
chaieb@23995
   912
    done
chaieb@23274
   913
next
chaieb@23274
   914
  case (6 a)  
chaieb@23274
   915
  let ?c = "fst (zsplit0 a)"
chaieb@23274
   916
  let ?r = "snd (zsplit0 a)"
chaieb@23274
   917
  have spl: "zsplit0 a = (?c,?r)" by simp
chaieb@23274
   918
  from zsplit0_I[OF spl, where x="i" and bs="bs"] 
chaieb@23995
   919
  have Ia:"Inum (i # bs) a = Inum (i #bs) (CN 0 ?c ?r)" and nb: "numbound0 ?r" by auto 
chaieb@23274
   920
  let ?N = "\<lambda> t. Inum (i#bs) t"
chaieb@23274
   921
  from prems Ia nb  show ?case 
nipkow@29667
   922
    apply (auto simp add: Let_def split_def algebra_simps) 
chaieb@23995
   923
    apply (cases "?r",auto)
chaieb@23995
   924
    apply (case_tac nat, auto)
chaieb@23995
   925
    done
chaieb@23274
   926
next
chaieb@23274
   927
  case (7 a)  
chaieb@23274
   928
  let ?c = "fst (zsplit0 a)"
chaieb@23274
   929
  let ?r = "snd (zsplit0 a)"
chaieb@23274
   930
  have spl: "zsplit0 a = (?c,?r)" by simp
chaieb@23274
   931
  from zsplit0_I[OF spl, where x="i" and bs="bs"] 
chaieb@23995
   932
  have Ia:"Inum (i # bs) a = Inum (i #bs) (CN 0 ?c ?r)" and nb: "numbound0 ?r" by auto 
chaieb@23274
   933
  let ?N = "\<lambda> t. Inum (i#bs) t"
chaieb@23274
   934
  from prems Ia nb  show ?case 
nipkow@29667
   935
    apply (auto simp add: Let_def split_def algebra_simps) 
chaieb@23995
   936
    apply (cases "?r",auto)
chaieb@23995
   937
    apply (case_tac nat, auto)
chaieb@23995
   938
    done
chaieb@23274
   939
next
chaieb@23274
   940
  case (8 a)  
chaieb@23274
   941
  let ?c = "fst (zsplit0 a)"
chaieb@23274
   942
  let ?r = "snd (zsplit0 a)"
chaieb@23274
   943
  have spl: "zsplit0 a = (?c,?r)" by simp
chaieb@23274
   944
  from zsplit0_I[OF spl, where x="i" and bs="bs"] 
chaieb@23995
   945
  have Ia:"Inum (i # bs) a = Inum (i #bs) (CN 0 ?c ?r)" and nb: "numbound0 ?r" by auto 
chaieb@23274
   946
  let ?N = "\<lambda> t. Inum (i#bs) t"
chaieb@23274
   947
  from prems Ia nb  show ?case 
nipkow@29667
   948
    apply (auto simp add: Let_def split_def algebra_simps) 
chaieb@23995
   949
    apply (cases "?r",auto)
chaieb@23995
   950
    apply (case_tac nat, auto)
chaieb@23995
   951
    done
chaieb@23274
   952
next
chaieb@23274
   953
  case (9 a)  
chaieb@23274
   954
  let ?c = "fst (zsplit0 a)"
chaieb@23274
   955
  let ?r = "snd (zsplit0 a)"
chaieb@23274
   956
  have spl: "zsplit0 a = (?c,?r)" by simp
chaieb@23274
   957
  from zsplit0_I[OF spl, where x="i" and bs="bs"] 
chaieb@23995
   958
  have Ia:"Inum (i # bs) a = Inum (i #bs) (CN 0 ?c ?r)" and nb: "numbound0 ?r" by auto 
chaieb@23274
   959
  let ?N = "\<lambda> t. Inum (i#bs) t"
chaieb@23274
   960
  from prems Ia nb  show ?case 
nipkow@29667
   961
    apply (auto simp add: Let_def split_def algebra_simps) 
chaieb@23995
   962
    apply (cases "?r",auto)
chaieb@23995
   963
    apply (case_tac nat, auto)
chaieb@23995
   964
    done
chaieb@23274
   965
next
chaieb@23274
   966
  case (10 a)  
chaieb@23274
   967
  let ?c = "fst (zsplit0 a)"
chaieb@23274
   968
  let ?r = "snd (zsplit0 a)"
chaieb@23274
   969
  have spl: "zsplit0 a = (?c,?r)" by simp
chaieb@23274
   970
  from zsplit0_I[OF spl, where x="i" and bs="bs"] 
chaieb@23995
   971
  have Ia:"Inum (i # bs) a = Inum (i #bs) (CN 0 ?c ?r)" and nb: "numbound0 ?r" by auto 
chaieb@23274
   972
  let ?N = "\<lambda> t. Inum (i#bs) t"
chaieb@23274
   973
  from prems Ia nb  show ?case 
nipkow@29667
   974
    apply (auto simp add: Let_def split_def algebra_simps) 
chaieb@23995
   975
    apply (cases "?r",auto)
chaieb@23995
   976
    apply (case_tac nat, auto)
chaieb@23995
   977
    done
chaieb@17378
   978
next
chaieb@23274
   979
  case (11 j a)  
chaieb@23274
   980
  let ?c = "fst (zsplit0 a)"
chaieb@23274
   981
  let ?r = "snd (zsplit0 a)"
chaieb@23274
   982
  have spl: "zsplit0 a = (?c,?r)" by simp
chaieb@23274
   983
  from zsplit0_I[OF spl, where x="i" and bs="bs"] 
chaieb@23995
   984
  have Ia:"Inum (i # bs) a = Inum (i #bs) (CN 0 ?c ?r)" and nb: "numbound0 ?r" by auto 
chaieb@23274
   985
  let ?N = "\<lambda> t. Inum (i#bs) t"
chaieb@23274
   986
  have "j=0 \<or> (j\<noteq>0 \<and> ?c = 0) \<or> (j\<noteq>0 \<and> ?c >0) \<or> (j\<noteq> 0 \<and> ?c<0)" by arith
chaieb@23274
   987
  moreover
chaieb@23274
   988
  {assume "j=0" hence z: "zlfm (Dvd j a) = (zlfm (Eq a))" by (simp add: Let_def) 
nipkow@30042
   989
    hence ?case using prems by (simp del: zlfm.simps)}
chaieb@23274
   990
  moreover
chaieb@23274
   991
  {assume "?c=0" and "j\<noteq>0" hence ?case 
nipkow@29700
   992
      using zsplit0_I[OF spl, where x="i" and bs="bs"]
nipkow@29667
   993
    apply (auto simp add: Let_def split_def algebra_simps) 
chaieb@23995
   994
    apply (cases "?r",auto)
chaieb@23995
   995
    apply (case_tac nat, auto)
chaieb@23995
   996
    done}
chaieb@23274
   997
  moreover
chaieb@23274
   998
  {assume cp: "?c > 0" and jnz: "j\<noteq>0" hence l: "?L (?l (Dvd j a))" 
chaieb@23274
   999
      by (simp add: nb Let_def split_def)
nipkow@29700
  1000
    hence ?case using Ia cp jnz by (simp add: Let_def split_def)}
chaieb@23274
  1001
  moreover
chaieb@23274
  1002
  {assume cn: "?c < 0" and jnz: "j\<noteq>0" hence l: "?L (?l (Dvd j a))" 
chaieb@23274
  1003
      by (simp add: nb Let_def split_def)
nipkow@30042
  1004
    hence ?case using Ia cn jnz dvd_minus_iff[of "abs j" "?c*i + ?N ?r" ]
nipkow@29700
  1005
      by (simp add: Let_def split_def) }
chaieb@23274
  1006
  ultimately show ?case by blast
chaieb@17378
  1007
next
chaieb@23274
  1008
  case (12 j a) 
chaieb@23274
  1009
  let ?c = "fst (zsplit0 a)"
chaieb@23274
  1010
  let ?r = "snd (zsplit0 a)"
chaieb@23274
  1011
  have spl: "zsplit0 a = (?c,?r)" by simp
chaieb@23274
  1012
  from zsplit0_I[OF spl, where x="i" and bs="bs"] 
chaieb@23995
  1013
  have Ia:"Inum (i # bs) a = Inum (i #bs) (CN 0 ?c ?r)" and nb: "numbound0 ?r" by auto 
chaieb@23274
  1014
  let ?N = "\<lambda> t. Inum (i#bs) t"
chaieb@23274
  1015
  have "j=0 \<or> (j\<noteq>0 \<and> ?c = 0) \<or> (j\<noteq>0 \<and> ?c >0) \<or> (j\<noteq> 0 \<and> ?c<0)" by arith
chaieb@23274
  1016
  moreover
chaieb@23274
  1017
  {assume "j=0" hence z: "zlfm (NDvd j a) = (zlfm (NEq a))" by (simp add: Let_def) 
nipkow@30042
  1018
    hence ?case using prems by (simp del: zlfm.simps)}
chaieb@23274
  1019
  moreover
chaieb@23274
  1020
  {assume "?c=0" and "j\<noteq>0" hence ?case 
nipkow@29700
  1021
      using zsplit0_I[OF spl, where x="i" and bs="bs"]
nipkow@29667
  1022
    apply (auto simp add: Let_def split_def algebra_simps) 
chaieb@23995
  1023
    apply (cases "?r",auto)
chaieb@23995
  1024
    apply (case_tac nat, auto)
chaieb@23995
  1025
    done}
chaieb@23274
  1026
  moreover
chaieb@23274
  1027
  {assume cp: "?c > 0" and jnz: "j\<noteq>0" hence l: "?L (?l (Dvd j a))" 
chaieb@23274
  1028
      by (simp add: nb Let_def split_def)
nipkow@29700
  1029
    hence ?case using Ia cp jnz by (simp add: Let_def split_def) }
chaieb@23274
  1030
  moreover
chaieb@23274
  1031
  {assume cn: "?c < 0" and jnz: "j\<noteq>0" hence l: "?L (?l (Dvd j a))" 
chaieb@23274
  1032
      by (simp add: nb Let_def split_def)
nipkow@30042
  1033
    hence ?case using Ia cn jnz dvd_minus_iff[of "abs j" "?c*i + ?N ?r"]
nipkow@29700
  1034
      by (simp add: Let_def split_def)}
chaieb@23274
  1035
  ultimately show ?case by blast
chaieb@23274
  1036
qed auto
chaieb@23274
  1037
chaieb@23274
  1038
consts 
chaieb@23274
  1039
  plusinf:: "fm \<Rightarrow> fm" (* Virtual substitution of +\<infinity>*)
chaieb@23274
  1040
  minusinf:: "fm \<Rightarrow> fm" (* Virtual substitution of -\<infinity>*)
nipkow@31952
  1041
  \<delta> :: "fm \<Rightarrow> int" (* Compute lcm {d| N\<^isup>? Dvd c*x+t \<in> p}*)
chaieb@23274
  1042
  d\<delta> :: "fm \<Rightarrow> int \<Rightarrow> bool" (* checks if a given l divides all the ds above*)
chaieb@23274
  1043
chaieb@23274
  1044
recdef minusinf "measure size"
chaieb@23274
  1045
  "minusinf (And p q) = And (minusinf p) (minusinf q)" 
chaieb@23274
  1046
  "minusinf (Or p q) = Or (minusinf p) (minusinf q)" 
chaieb@23995
  1047
  "minusinf (Eq  (CN 0 c e)) = F"
chaieb@23995
  1048
  "minusinf (NEq (CN 0 c e)) = T"
chaieb@23995
  1049
  "minusinf (Lt  (CN 0 c e)) = T"
chaieb@23995
  1050
  "minusinf (Le  (CN 0 c e)) = T"
chaieb@23995
  1051
  "minusinf (Gt  (CN 0 c e)) = F"
chaieb@23995
  1052
  "minusinf (Ge  (CN 0 c e)) = F"
chaieb@23274
  1053
  "minusinf p = p"
chaieb@23274
  1054
chaieb@23274
  1055
lemma minusinf_qfree: "qfree p \<Longrightarrow> qfree (minusinf p)"
chaieb@23274
  1056
  by (induct p rule: minusinf.induct, auto)
chaieb@23274
  1057
chaieb@23274
  1058
recdef plusinf "measure size"
chaieb@23274
  1059
  "plusinf (And p q) = And (plusinf p) (plusinf q)" 
chaieb@23274
  1060
  "plusinf (Or p q) = Or (plusinf p) (plusinf q)" 
chaieb@23995
  1061
  "plusinf (Eq  (CN 0 c e)) = F"
chaieb@23995
  1062
  "plusinf (NEq (CN 0 c e)) = T"
chaieb@23995
  1063
  "plusinf (Lt  (CN 0 c e)) = F"
chaieb@23995
  1064
  "plusinf (Le  (CN 0 c e)) = F"
chaieb@23995
  1065
  "plusinf (Gt  (CN 0 c e)) = T"
chaieb@23995
  1066
  "plusinf (Ge  (CN 0 c e)) = T"
chaieb@23274
  1067
  "plusinf p = p"
chaieb@23274
  1068
chaieb@23274
  1069
recdef \<delta> "measure size"
huffman@31715
  1070
  "\<delta> (And p q) = lcm (\<delta> p) (\<delta> q)" 
huffman@31715
  1071
  "\<delta> (Or p q) = lcm (\<delta> p) (\<delta> q)" 
chaieb@23995
  1072
  "\<delta> (Dvd i (CN 0 c e)) = i"
chaieb@23995
  1073
  "\<delta> (NDvd i (CN 0 c e)) = i"
chaieb@23274
  1074
  "\<delta> p = 1"
chaieb@23274
  1075
chaieb@23274
  1076
recdef d\<delta> "measure size"
chaieb@23274
  1077
  "d\<delta> (And p q) = (\<lambda> d. d\<delta> p d \<and> d\<delta> q d)" 
chaieb@23274
  1078
  "d\<delta> (Or p q) = (\<lambda> d. d\<delta> p d \<and> d\<delta> q d)" 
chaieb@23995
  1079
  "d\<delta> (Dvd i (CN 0 c e)) = (\<lambda> d. i dvd d)"
chaieb@23995
  1080
  "d\<delta> (NDvd i (CN 0 c e)) = (\<lambda> d. i dvd d)"
chaieb@23274
  1081
  "d\<delta> p = (\<lambda> d. True)"
chaieb@23274
  1082
chaieb@23274
  1083
lemma delta_mono: 
chaieb@23274
  1084
  assumes lin: "iszlfm p"
chaieb@23274
  1085
  and d: "d dvd d'"
chaieb@23274
  1086
  and ad: "d\<delta> p d"
chaieb@23274
  1087
  shows "d\<delta> p d'"
chaieb@23274
  1088
  using lin ad d
chaieb@23274
  1089
proof(induct p rule: iszlfm.induct)
chaieb@23274
  1090
  case (9 i c e)  thus ?case using d
nipkow@30042
  1091
    by (simp add: dvd_trans[of "i" "d" "d'"])
chaieb@17378
  1092
next
chaieb@23274
  1093
  case (10 i c e) thus ?case using d
nipkow@30042
  1094
    by (simp add: dvd_trans[of "i" "d" "d'"])
chaieb@23274
  1095
qed simp_all
chaieb@17378
  1096
chaieb@23274
  1097
lemma \<delta> : assumes lin:"iszlfm p"
chaieb@23274
  1098
  shows "d\<delta> p (\<delta> p) \<and> \<delta> p >0"
chaieb@23274
  1099
using lin
chaieb@23274
  1100
proof (induct p rule: iszlfm.induct)
chaieb@23274
  1101
  case (1 p q) 
chaieb@23274
  1102
  let ?d = "\<delta> (And p q)"
nipkow@31952
  1103
  from prems lcm_pos_int have dp: "?d >0" by simp
chaieb@23995
  1104
  have d1: "\<delta> p dvd \<delta> (And p q)" using prems by simp
nipkow@31730
  1105
  hence th: "d\<delta> p ?d" using delta_mono prems(3-4) by(simp only: iszlfm.simps)
chaieb@23995
  1106
  have "\<delta> q dvd \<delta> (And p q)" using prems by simp
nipkow@31730
  1107
  hence th': "d\<delta> q ?d" using delta_mono prems by(simp only: iszlfm.simps)
nipkow@23984
  1108
  from th th' dp show ?case by simp
chaieb@23274
  1109
next
chaieb@23274
  1110
  case (2 p q)  
chaieb@23274
  1111
  let ?d = "\<delta> (And p q)"
nipkow@31952
  1112
  from prems lcm_pos_int have dp: "?d >0" by simp
chaieb@23995
  1113
  have "\<delta> p dvd \<delta> (And p q)" using prems by simp
nipkow@31730
  1114
  hence th: "d\<delta> p ?d" using delta_mono prems by(simp only: iszlfm.simps)
chaieb@23995
  1115
  have "\<delta> q dvd \<delta> (And p q)" using prems by simp
nipkow@31730
  1116
  hence th': "d\<delta> q ?d" using delta_mono prems by(simp only: iszlfm.simps)
nipkow@23984
  1117
  from th th' dp show ?case by simp
chaieb@17378
  1118
qed simp_all
chaieb@17378
  1119
chaieb@17378
  1120
chaieb@23274
  1121
consts 
chaieb@23274
  1122
  a\<beta> :: "fm \<Rightarrow> int \<Rightarrow> fm" (* adjusts the coeffitients of a formula *)
chaieb@23274
  1123
  d\<beta> :: "fm \<Rightarrow> int \<Rightarrow> bool" (* tests if all coeffs c of c divide a given l*)
chaieb@23274
  1124
  \<zeta>  :: "fm \<Rightarrow> int" (* computes the lcm of all coefficients of x*)
chaieb@23274
  1125
  \<beta> :: "fm \<Rightarrow> num list"
chaieb@23274
  1126
  \<alpha> :: "fm \<Rightarrow> num list"
chaieb@17378
  1127
chaieb@23274
  1128
recdef a\<beta> "measure size"
chaieb@23274
  1129
  "a\<beta> (And p q) = (\<lambda> k. And (a\<beta> p k) (a\<beta> q k))" 
chaieb@23274
  1130
  "a\<beta> (Or p q) = (\<lambda> k. Or (a\<beta> p k) (a\<beta> q k))" 
chaieb@23995
  1131
  "a\<beta> (Eq  (CN 0 c e)) = (\<lambda> k. Eq (CN 0 1 (Mul (k div c) e)))"
chaieb@23995
  1132
  "a\<beta> (NEq (CN 0 c e)) = (\<lambda> k. NEq (CN 0 1 (Mul (k div c) e)))"
chaieb@23995
  1133
  "a\<beta> (Lt  (CN 0 c e)) = (\<lambda> k. Lt (CN 0 1 (Mul (k div c) e)))"
chaieb@23995
  1134
  "a\<beta> (Le  (CN 0 c e)) = (\<lambda> k. Le (CN 0 1 (Mul (k div c) e)))"
chaieb@23995
  1135
  "a\<beta> (Gt  (CN 0 c e)) = (\<lambda> k. Gt (CN 0 1 (Mul (k div c) e)))"
chaieb@23995
  1136
  "a\<beta> (Ge  (CN 0 c e)) = (\<lambda> k. Ge (CN 0 1 (Mul (k div c) e)))"
chaieb@23995
  1137
  "a\<beta> (Dvd i (CN 0 c e)) =(\<lambda> k. Dvd ((k div c)*i) (CN 0 1 (Mul (k div c) e)))"
chaieb@23995
  1138
  "a\<beta> (NDvd i (CN 0 c e))=(\<lambda> k. NDvd ((k div c)*i) (CN 0 1 (Mul (k div c) e)))"
chaieb@23274
  1139
  "a\<beta> p = (\<lambda> k. p)"
chaieb@17378
  1140
chaieb@23274
  1141
recdef d\<beta> "measure size"
chaieb@23274
  1142
  "d\<beta> (And p q) = (\<lambda> k. (d\<beta> p k) \<and> (d\<beta> q k))" 
chaieb@23274
  1143
  "d\<beta> (Or p q) = (\<lambda> k. (d\<beta> p k) \<and> (d\<beta> q k))" 
chaieb@23995
  1144
  "d\<beta> (Eq  (CN 0 c e)) = (\<lambda> k. c dvd k)"
chaieb@23995
  1145
  "d\<beta> (NEq (CN 0 c e)) = (\<lambda> k. c dvd k)"
chaieb@23995
  1146
  "d\<beta> (Lt  (CN 0 c e)) = (\<lambda> k. c dvd k)"
chaieb@23995
  1147
  "d\<beta> (Le  (CN 0 c e)) = (\<lambda> k. c dvd k)"
chaieb@23995
  1148
  "d\<beta> (Gt  (CN 0 c e)) = (\<lambda> k. c dvd k)"
chaieb@23995
  1149
  "d\<beta> (Ge  (CN 0 c e)) = (\<lambda> k. c dvd k)"
chaieb@23995
  1150
  "d\<beta> (Dvd i (CN 0 c e)) =(\<lambda> k. c dvd k)"
chaieb@23995
  1151
  "d\<beta> (NDvd i (CN 0 c e))=(\<lambda> k. c dvd k)"
chaieb@23274
  1152
  "d\<beta> p = (\<lambda> k. True)"
chaieb@17378
  1153
chaieb@23274
  1154
recdef \<zeta> "measure size"
huffman@31715
  1155
  "\<zeta> (And p q) = lcm (\<zeta> p) (\<zeta> q)" 
huffman@31715
  1156
  "\<zeta> (Or p q) = lcm (\<zeta> p) (\<zeta> q)" 
chaieb@23995
  1157
  "\<zeta> (Eq  (CN 0 c e)) = c"
chaieb@23995
  1158
  "\<zeta> (NEq (CN 0 c e)) = c"
chaieb@23995
  1159
  "\<zeta> (Lt  (CN 0 c e)) = c"
chaieb@23995
  1160
  "\<zeta> (Le  (CN 0 c e)) = c"
chaieb@23995
  1161
  "\<zeta> (Gt  (CN 0 c e)) = c"
chaieb@23995
  1162
  "\<zeta> (Ge  (CN 0 c e)) = c"
chaieb@23995
  1163
  "\<zeta> (Dvd i (CN 0 c e)) = c"
chaieb@23995
  1164
  "\<zeta> (NDvd i (CN 0 c e))= c"
chaieb@23274
  1165
  "\<zeta> p = 1"
chaieb@17378
  1166
chaieb@23274
  1167
recdef \<beta> "measure size"
chaieb@23274
  1168
  "\<beta> (And p q) = (\<beta> p @ \<beta> q)" 
chaieb@23274
  1169
  "\<beta> (Or p q) = (\<beta> p @ \<beta> q)" 
chaieb@23995
  1170
  "\<beta> (Eq  (CN 0 c e)) = [Sub (C -1) e]"
chaieb@23995
  1171
  "\<beta> (NEq (CN 0 c e)) = [Neg e]"
chaieb@23995
  1172
  "\<beta> (Lt  (CN 0 c e)) = []"
chaieb@23995
  1173
  "\<beta> (Le  (CN 0 c e)) = []"
chaieb@23995
  1174
  "\<beta> (Gt  (CN 0 c e)) = [Neg e]"
chaieb@23995
  1175
  "\<beta> (Ge  (CN 0 c e)) = [Sub (C -1) e]"
chaieb@23274
  1176
  "\<beta> p = []"
wenzelm@19736
  1177
chaieb@23274
  1178
recdef \<alpha> "measure size"
chaieb@23274
  1179
  "\<alpha> (And p q) = (\<alpha> p @ \<alpha> q)" 
chaieb@23274
  1180
  "\<alpha> (Or p q) = (\<alpha> p @ \<alpha> q)" 
chaieb@23995
  1181
  "\<alpha> (Eq  (CN 0 c e)) = [Add (C -1) e]"
chaieb@23995
  1182
  "\<alpha> (NEq (CN 0 c e)) = [e]"
chaieb@23995
  1183
  "\<alpha> (Lt  (CN 0 c e)) = [e]"
chaieb@23995
  1184
  "\<alpha> (Le  (CN 0 c e)) = [Add (C -1) e]"
chaieb@23995
  1185
  "\<alpha> (Gt  (CN 0 c e)) = []"
chaieb@23995
  1186
  "\<alpha> (Ge  (CN 0 c e)) = []"
chaieb@23274
  1187
  "\<alpha> p = []"
chaieb@23274
  1188
consts mirror :: "fm \<Rightarrow> fm"
chaieb@23274
  1189
recdef mirror "measure size"
chaieb@23274
  1190
  "mirror (And p q) = And (mirror p) (mirror q)" 
chaieb@23274
  1191
  "mirror (Or p q) = Or (mirror p) (mirror q)" 
chaieb@23995
  1192
  "mirror (Eq  (CN 0 c e)) = Eq (CN 0 c (Neg e))"
chaieb@23995
  1193
  "mirror (NEq (CN 0 c e)) = NEq (CN 0 c (Neg e))"
chaieb@23995
  1194
  "mirror (Lt  (CN 0 c e)) = Gt (CN 0 c (Neg e))"
chaieb@23995
  1195
  "mirror (Le  (CN 0 c e)) = Ge (CN 0 c (Neg e))"
chaieb@23995
  1196
  "mirror (Gt  (CN 0 c e)) = Lt (CN 0 c (Neg e))"
chaieb@23995
  1197
  "mirror (Ge  (CN 0 c e)) = Le (CN 0 c (Neg e))"
chaieb@23995
  1198
  "mirror (Dvd i (CN 0 c e)) = Dvd i (CN 0 c (Neg e))"
chaieb@23995
  1199
  "mirror (NDvd i (CN 0 c e)) = NDvd i (CN 0 c (Neg e))"
chaieb@23274
  1200
  "mirror p = p"
chaieb@23274
  1201
    (* Lemmas for the correctness of \<sigma>\<rho> *)
chaieb@23274
  1202
lemma dvd1_eq1: "x >0 \<Longrightarrow> (x::int) dvd 1 = (x = 1)"
nipkow@29700
  1203
by simp
chaieb@17378
  1204
chaieb@23274
  1205
lemma minusinf_inf:
chaieb@23274
  1206
  assumes linp: "iszlfm p"
chaieb@23274
  1207
  and u: "d\<beta> p 1"
chaieb@23274
  1208
  shows "\<exists> (z::int). \<forall> x < z. Ifm bbs (x#bs) (minusinf p) = Ifm bbs (x#bs) p"
chaieb@23274
  1209
  (is "?P p" is "\<exists> (z::int). \<forall> x < z. ?I x (?M p) = ?I x p")
chaieb@23274
  1210
using linp u
chaieb@23274
  1211
proof (induct p rule: minusinf.induct)
chaieb@23274
  1212
  case (1 p q) thus ?case 
nipkow@29700
  1213
    by auto (rule_tac x="min z za" in exI,simp)
chaieb@23274
  1214
next
chaieb@23274
  1215
  case (2 p q) thus ?case 
nipkow@29700
  1216
    by auto (rule_tac x="min z za" in exI,simp)
chaieb@17378
  1217
next
nipkow@29700
  1218
  case (3 c e) hence c1: "c=1" and nb: "numbound0 e" by simp+
wenzelm@26934
  1219
  fix a
wenzelm@26934
  1220
  from 3 have "\<forall> x<(- Inum (a#bs) e). c*x + Inum (x#bs) e \<noteq> 0"
chaieb@23274
  1221
  proof(clarsimp)
chaieb@23274
  1222
    fix x assume "x < (- Inum (a#bs) e)" and"x + Inum (x#bs) e = 0"
chaieb@23274
  1223
    with numbound0_I[OF nb, where bs="bs" and b="a" and b'="x"]
chaieb@23274
  1224
    show "False" by simp
chaieb@23274
  1225
  qed
chaieb@23274
  1226
  thus ?case by auto
chaieb@17378
  1227
next
nipkow@29700
  1228
  case (4 c e) hence c1: "c=1" and nb: "numbound0 e" by simp+
wenzelm@26934
  1229
  fix a
wenzelm@26934
  1230
  from 4 have "\<forall> x<(- Inum (a#bs) e). c*x + Inum (x#bs) e \<noteq> 0"
chaieb@23274
  1231
  proof(clarsimp)
chaieb@23274
  1232
    fix x assume "x < (- Inum (a#bs) e)" and"x + Inum (x#bs) e = 0"
chaieb@23274
  1233
    with numbound0_I[OF nb, where bs="bs" and b="a" and b'="x"]
chaieb@23274
  1234
    show "False" by simp
chaieb@23274
  1235
  qed
chaieb@23274
  1236
  thus ?case by auto
chaieb@17378
  1237
next
nipkow@29700
  1238
  case (5 c e) hence c1: "c=1" and nb: "numbound0 e" by simp+
wenzelm@26934
  1239
  fix a
wenzelm@26934
  1240
  from 5 have "\<forall> x<(- Inum (a#bs) e). c*x + Inum (x#bs) e < 0"
chaieb@23274
  1241
  proof(clarsimp)
chaieb@23274
  1242
    fix x assume "x < (- Inum (a#bs) e)" 
chaieb@23274
  1243
    with numbound0_I[OF nb, where bs="bs" and b="a" and b'="x"]
chaieb@23274
  1244
    show "x + Inum (x#bs) e < 0" by simp
chaieb@23274
  1245
  qed
chaieb@23274
  1246
  thus ?case by auto
chaieb@23274
  1247
next
nipkow@29700
  1248
  case (6 c e) hence c1: "c=1" and nb: "numbound0 e" by simp+
wenzelm@26934
  1249
  fix a
wenzelm@26934
  1250
  from 6 have "\<forall> x<(- Inum (a#bs) e). c*x + Inum (x#bs) e \<le> 0"
chaieb@23274
  1251
  proof(clarsimp)
chaieb@23274
  1252
    fix x assume "x < (- Inum (a#bs) e)" 
chaieb@23274
  1253
    with numbound0_I[OF nb, where bs="bs" and b="a" and b'="x"]
chaieb@23274
  1254
    show "x + Inum (x#bs) e \<le> 0" by simp
chaieb@23274
  1255
  qed
chaieb@23274
  1256
  thus ?case by auto
chaieb@23274
  1257
next
nipkow@29700
  1258
  case (7 c e) hence c1: "c=1" and nb: "numbound0 e" by simp+
wenzelm@26934
  1259
  fix a
wenzelm@26934
  1260
  from 7 have "\<forall> x<(- Inum (a#bs) e). \<not> (c*x + Inum (x#bs) e > 0)"
chaieb@23274
  1261
  proof(clarsimp)
chaieb@23274
  1262
    fix x assume "x < (- Inum (a#bs) e)" and"x + Inum (x#bs) e > 0"
chaieb@23274
  1263
    with numbound0_I[OF nb, where bs="bs" and b="a" and b'="x"]
chaieb@23274
  1264
    show "False" by simp
chaieb@23274
  1265
  qed
chaieb@23274
  1266
  thus ?case by auto
chaieb@23274
  1267
next
nipkow@29700
  1268
  case (8 c e) hence c1: "c=1" and nb: "numbound0 e" by simp+
wenzelm@26934
  1269
  fix a
wenzelm@26934
  1270
  from 8 have "\<forall> x<(- Inum (a#bs) e). \<not> (c*x + Inum (x#bs) e \<ge> 0)"
chaieb@23274
  1271
  proof(clarsimp)
chaieb@23274
  1272
    fix x assume "x < (- Inum (a#bs) e)" and"x + Inum (x#bs) e \<ge> 0"
chaieb@23274
  1273
    with numbound0_I[OF nb, where bs="bs" and b="a" and b'="x"]
chaieb@23274
  1274
    show "False" by simp
chaieb@23274
  1275
  qed
chaieb@23274
  1276
  thus ?case by auto
chaieb@23274
  1277
qed auto
chaieb@17378
  1278
chaieb@23274
  1279
lemma minusinf_repeats:
chaieb@23274
  1280
  assumes d: "d\<delta> p d" and linp: "iszlfm p"
chaieb@23274
  1281
  shows "Ifm bbs ((x - k*d)#bs) (minusinf p) = Ifm bbs (x #bs) (minusinf p)"
chaieb@23274
  1282
using linp d
chaieb@23274
  1283
proof(induct p rule: iszlfm.induct) 
chaieb@23274
  1284
  case (9 i c e) hence nbe: "numbound0 e"  and id: "i dvd d" by simp+
chaieb@23274
  1285
    hence "\<exists> k. d=i*k" by (simp add: dvd_def)
chaieb@23274
  1286
    then obtain "di" where di_def: "d=i*di" by blast
chaieb@23274
  1287
    show ?case 
chaieb@23274
  1288
    proof(simp add: numbound0_I[OF nbe,where bs="bs" and b="x - k * d" and b'="x"] right_diff_distrib, rule iffI)
chaieb@23274
  1289
      assume 
wenzelm@32960
  1290
        "i dvd c * x - c*(k*d) + Inum (x # bs) e"
chaieb@23274
  1291
      (is "?ri dvd ?rc*?rx - ?rc*(?rk*?rd) + ?I x e" is "?ri dvd ?rt")
chaieb@23274
  1292
      hence "\<exists> (l::int). ?rt = i * l" by (simp add: dvd_def)
chaieb@23274
  1293
      hence "\<exists> (l::int). c*x+ ?I x e = i*l+c*(k * i*di)" 
wenzelm@32960
  1294
        by (simp add: algebra_simps di_def)
chaieb@23274
  1295
      hence "\<exists> (l::int). c*x+ ?I x e = i*(l + c*k*di)"
wenzelm@32960
  1296
        by (simp add: algebra_simps)
chaieb@23274
  1297
      hence "\<exists> (l::int). c*x+ ?I x e = i*l" by blast
chaieb@23274
  1298
      thus "i dvd c*x + Inum (x # bs) e" by (simp add: dvd_def) 
chaieb@23274
  1299
    next
chaieb@23274
  1300
      assume 
wenzelm@32960
  1301
        "i dvd c*x + Inum (x # bs) e" (is "?ri dvd ?rc*?rx+?e")
chaieb@23274
  1302
      hence "\<exists> (l::int). c*x+?e = i*l" by (simp add: dvd_def)
chaieb@23274
  1303
      hence "\<exists> (l::int). c*x - c*(k*d) +?e = i*l - c*(k*d)" by simp
chaieb@23274
  1304
      hence "\<exists> (l::int). c*x - c*(k*d) +?e = i*l - c*(k*i*di)" by (simp add: di_def)
nipkow@29667
  1305
      hence "\<exists> (l::int). c*x - c*(k*d) +?e = i*((l - c*k*di))" by (simp add: algebra_simps)
chaieb@23274
  1306
      hence "\<exists> (l::int). c*x - c * (k*d) +?e = i*l"
wenzelm@32960
  1307
        by blast
chaieb@23274
  1308
      thus "i dvd c*x - c*(k*d) + Inum (x # bs) e" by (simp add: dvd_def)
chaieb@23274
  1309
    qed
chaieb@23274
  1310
next
chaieb@23274
  1311
  case (10 i c e)  hence nbe: "numbound0 e"  and id: "i dvd d" by simp+
chaieb@23274
  1312
    hence "\<exists> k. d=i*k" by (simp add: dvd_def)
chaieb@23274
  1313
    then obtain "di" where di_def: "d=i*di" by blast
chaieb@23274
  1314
    show ?case 
chaieb@23274
  1315
    proof(simp add: numbound0_I[OF nbe,where bs="bs" and b="x - k * d" and b'="x"] right_diff_distrib, rule iffI)
chaieb@23274
  1316
      assume 
wenzelm@32960
  1317
        "i dvd c * x - c*(k*d) + Inum (x # bs) e"
chaieb@23274
  1318
      (is "?ri dvd ?rc*?rx - ?rc*(?rk*?rd) + ?I x e" is "?ri dvd ?rt")
chaieb@23274
  1319
      hence "\<exists> (l::int). ?rt = i * l" by (simp add: dvd_def)
chaieb@23274
  1320
      hence "\<exists> (l::int). c*x+ ?I x e = i*l+c*(k * i*di)" 
wenzelm@32960
  1321
        by (simp add: algebra_simps di_def)
chaieb@23274
  1322
      hence "\<exists> (l::int). c*x+ ?I x e = i*(l + c*k*di)"
wenzelm@32960
  1323
        by (simp add: algebra_simps)
chaieb@23274
  1324
      hence "\<exists> (l::int). c*x+ ?I x e = i*l" by blast
chaieb@23274
  1325
      thus "i dvd c*x + Inum (x # bs) e" by (simp add: dvd_def) 
chaieb@23274
  1326
    next
chaieb@23274
  1327
      assume 
wenzelm@32960
  1328
        "i dvd c*x + Inum (x # bs) e" (is "?ri dvd ?rc*?rx+?e")
chaieb@23274
  1329
      hence "\<exists> (l::int). c*x+?e = i*l" by (simp add: dvd_def)
chaieb@23274
  1330
      hence "\<exists> (l::int). c*x - c*(k*d) +?e = i*l - c*(k*d)" by simp
chaieb@23274
  1331
      hence "\<exists> (l::int). c*x - c*(k*d) +?e = i*l - c*(k*i*di)" by (simp add: di_def)
nipkow@29667
  1332
      hence "\<exists> (l::int). c*x - c*(k*d) +?e = i*((l - c*k*di))" by (simp add: algebra_simps)
chaieb@23274
  1333
      hence "\<exists> (l::int). c*x - c * (k*d) +?e = i*l"
wenzelm@32960
  1334
        by blast
chaieb@23274
  1335
      thus "i dvd c*x - c*(k*d) + Inum (x # bs) e" by (simp add: dvd_def)
chaieb@23274
  1336
    qed
haftmann@23689
  1337
qed (auto simp add: gr0_conv_Suc numbound0_I[where bs="bs" and b="x - k*d" and b'="x"])
chaieb@17378
  1338
chaieb@23274
  1339
lemma mirror\<alpha>\<beta>:
chaieb@23274
  1340
  assumes lp: "iszlfm p"
chaieb@23274
  1341
  shows "(Inum (i#bs)) ` set (\<alpha> p) = (Inum (i#bs)) ` set (\<beta> (mirror p))"
chaieb@23274
  1342
using lp
chaieb@23274
  1343
by (induct p rule: mirror.induct, auto)
chaieb@17378
  1344
chaieb@23274
  1345
lemma mirror: 
chaieb@23274
  1346
  assumes lp: "iszlfm p"
chaieb@23274
  1347
  shows "Ifm bbs (x#bs) (mirror p) = Ifm bbs ((- x)#bs) p" 
chaieb@23274
  1348
using lp
chaieb@23274
  1349
proof(induct p rule: iszlfm.induct)
chaieb@23274
  1350
  case (9 j c e) hence nb: "numbound0 e" by simp
chaieb@23995
  1351
  have "Ifm bbs (x#bs) (mirror (Dvd j (CN 0 c e))) = (j dvd c*x - Inum (x#bs) e)" (is "_ = (j dvd c*x - ?e)") by simp
chaieb@23274
  1352
    also have "\<dots> = (j dvd (- (c*x - ?e)))"
nipkow@30042
  1353
    by (simp only: dvd_minus_iff)
chaieb@23274
  1354
  also have "\<dots> = (j dvd (c* (- x)) + ?e)"
haftmann@37887
  1355
    apply (simp only: minus_mult_right[symmetric] minus_mult_left[symmetric] diff_minus zadd_ac zminus_zadd_distrib)
nipkow@29667
  1356
    by (simp add: algebra_simps)
chaieb@23995
  1357
  also have "\<dots> = Ifm bbs ((- x)#bs) (Dvd j (CN 0 c e))"
chaieb@23274
  1358
    using numbound0_I[OF nb, where bs="bs" and b="x" and b'="- x"]
chaieb@23274
  1359
    by simp
chaieb@23274
  1360
  finally show ?case .
chaieb@23274
  1361
next
chaieb@23274
  1362
    case (10 j c e) hence nb: "numbound0 e" by simp
chaieb@23995
  1363
  have "Ifm bbs (x#bs) (mirror (Dvd j (CN 0 c e))) = (j dvd c*x - Inum (x#bs) e)" (is "_ = (j dvd c*x - ?e)") by simp
chaieb@23274
  1364
    also have "\<dots> = (j dvd (- (c*x - ?e)))"
nipkow@30042
  1365
    by (simp only: dvd_minus_iff)
chaieb@23274
  1366
  also have "\<dots> = (j dvd (c* (- x)) + ?e)"
haftmann@37887
  1367
    apply (simp only: minus_mult_right[symmetric] minus_mult_left[symmetric] diff_minus zadd_ac zminus_zadd_distrib)
nipkow@29667
  1368
    by (simp add: algebra_simps)
chaieb@23995
  1369
  also have "\<dots> = Ifm bbs ((- x)#bs) (Dvd j (CN 0 c e))"
chaieb@23274
  1370
    using numbound0_I[OF nb, where bs="bs" and b="x" and b'="- x"]
chaieb@23274
  1371
    by simp
chaieb@23274
  1372
  finally show ?case by simp
haftmann@23689
  1373
qed (auto simp add: numbound0_I[where bs="bs" and b="x" and b'="- x"] gr0_conv_Suc)
chaieb@17378
  1374
chaieb@23274
  1375
lemma mirror_l: "iszlfm p \<and> d\<beta> p 1 
chaieb@23274
  1376
  \<Longrightarrow> iszlfm (mirror p) \<and> d\<beta> (mirror p) 1"
chaieb@23274
  1377
by (induct p rule: mirror.induct, auto)
chaieb@17378
  1378
chaieb@23274
  1379
lemma mirror_\<delta>: "iszlfm p \<Longrightarrow> \<delta> (mirror p) = \<delta> p"
chaieb@23274
  1380
by (induct p rule: mirror.induct,auto)
chaieb@23274
  1381
chaieb@23274
  1382
lemma \<beta>_numbound0: assumes lp: "iszlfm p"
chaieb@23274
  1383
  shows "\<forall> b\<in> set (\<beta> p). numbound0 b"
chaieb@23274
  1384
  using lp by (induct p rule: \<beta>.induct,auto)
chaieb@17378
  1385
chaieb@23274
  1386
lemma d\<beta>_mono: 
chaieb@23274
  1387
  assumes linp: "iszlfm p"
chaieb@23274
  1388
  and dr: "d\<beta> p l"
chaieb@23274
  1389
  and d: "l dvd l'"
chaieb@23274
  1390
  shows "d\<beta> p l'"
nipkow@30042
  1391
using dr linp dvd_trans[of _ "l" "l'", simplified d]
chaieb@23274
  1392
by (induct p rule: iszlfm.induct) simp_all
chaieb@23274
  1393
chaieb@23274
  1394
lemma \<alpha>_l: assumes lp: "iszlfm p"
chaieb@23274
  1395
  shows "\<forall> b\<in> set (\<alpha> p). numbound0 b"
chaieb@23274
  1396
using lp
chaieb@23274
  1397
by(induct p rule: \<alpha>.induct, auto)
chaieb@17378
  1398
chaieb@23274
  1399
lemma \<zeta>: 
chaieb@23274
  1400
  assumes linp: "iszlfm p"
chaieb@23274
  1401
  shows "\<zeta> p > 0 \<and> d\<beta> p (\<zeta> p)"
chaieb@23274
  1402
using linp
chaieb@23274
  1403
proof(induct p rule: iszlfm.induct)
chaieb@23274
  1404
  case (1 p q)
huffman@31715
  1405
  from prems have dl1: "\<zeta> p dvd lcm (\<zeta> p) (\<zeta> q)" by simp
huffman@31715
  1406
  from prems have dl2: "\<zeta> q dvd lcm (\<zeta> p) (\<zeta> q)"  by simp
huffman@31715
  1407
  from prems d\<beta>_mono[where p = "p" and l="\<zeta> p" and l'="lcm (\<zeta> p) (\<zeta> q)"] 
huffman@31715
  1408
    d\<beta>_mono[where p = "q" and l="\<zeta> q" and l'="lcm (\<zeta> p) (\<zeta> q)"] 
nipkow@31952
  1409
    dl1 dl2 show ?case by (auto simp add: lcm_pos_int)
chaieb@17378
  1410
next
chaieb@23274
  1411
  case (2 p q)
huffman@31715
  1412
  from prems have dl1: "\<zeta> p dvd lcm (\<zeta> p) (\<zeta> q)" by simp
huffman@31715
  1413
  from prems have dl2: "\<zeta> q dvd lcm (\<zeta> p) (\<zeta> q)" by simp
huffman@31715
  1414
  from prems d\<beta>_mono[where p = "p" and l="\<zeta> p" and l'="lcm (\<zeta> p) (\<zeta> q)"] 
huffman@31715
  1415
    d\<beta>_mono[where p = "q" and l="\<zeta> q" and l'="lcm (\<zeta> p) (\<zeta> q)"] 
nipkow@31952
  1416
    dl1 dl2 show ?case by (auto simp add: lcm_pos_int)
nipkow@31952
  1417
qed (auto simp add: lcm_pos_int)
chaieb@17378
  1418
chaieb@23274
  1419
lemma a\<beta>: assumes linp: "iszlfm p" and d: "d\<beta> p l" and lp: "l > 0"
chaieb@23274
  1420
  shows "iszlfm (a\<beta> p l) \<and> d\<beta> (a\<beta> p l) 1 \<and> (Ifm bbs (l*x #bs) (a\<beta> p l) = Ifm bbs (x#bs) p)"
chaieb@23274
  1421
using linp d
chaieb@23274
  1422
proof (induct p rule: iszlfm.induct)
chaieb@23274
  1423
  case (5 c e) hence cp: "c>0" and be: "numbound0 e" and d': "c dvd l" by simp+
chaieb@23274
  1424
    from lp cp have clel: "c\<le>l" by (simp add: zdvd_imp_le [OF d' lp])
chaieb@23274
  1425
    from cp have cnz: "c \<noteq> 0" by simp
chaieb@23274
  1426
    have "c div c\<le> l div c"
chaieb@23274
  1427
      by (simp add: zdiv_mono1[OF clel cp])
chaieb@23274
  1428
    then have ldcp:"0 < l div c" 
chaieb@23274
  1429
      by (simp add: zdiv_self[OF cnz])
nipkow@30042
  1430
    have "c * (l div c) = c* (l div c) + l mod c" using d' dvd_eq_mod_eq_0[of "c" "l"] by simp
chaieb@23274
  1431
    hence cl:"c * (l div c) =l" using zmod_zdiv_equality[where a="l" and b="c", symmetric] 
chaieb@23274
  1432
      by simp
chaieb@23274
  1433
    hence "(l*x + (l div c) * Inum (x # bs) e < 0) =
chaieb@23274
  1434
          ((c * (l div c)) * x + (l div c) * Inum (x # bs) e < 0)"
chaieb@23274
  1435
      by simp
nipkow@29667
  1436
    also have "\<dots> = ((l div c) * (c*x + Inum (x # bs) e) < (l div c) * 0)" by (simp add: algebra_simps)
chaieb@23274
  1437
    also have "\<dots> = (c*x + Inum (x # bs) e < 0)"
chaieb@23274
  1438
    using mult_less_0_iff [where a="(l div c)" and b="c*x + Inum (x # bs) e"] ldcp by simp
chaieb@23274
  1439
  finally show ?case using numbound0_I[OF be,where b="l*x" and b'="x" and bs="bs"] be  by simp
chaieb@17378
  1440
next
chaieb@23274
  1441
  case (6 c e) hence cp: "c>0" and be: "numbound0 e" and d': "c dvd l" by simp+
chaieb@23274
  1442
    from lp cp have clel: "c\<le>l" by (simp add: zdvd_imp_le [OF d' lp])
chaieb@23274
  1443
    from cp have cnz: "c \<noteq> 0" by simp
chaieb@23274
  1444
    have "c div c\<le> l div c"
chaieb@23274
  1445
      by (simp add: zdiv_mono1[OF clel cp])
chaieb@23274
  1446
    then have ldcp:"0 < l div c" 
chaieb@23274
  1447
      by (simp add: zdiv_self[OF cnz])
nipkow@30042
  1448
    have "c * (l div c) = c* (l div c) + l mod c" using d' dvd_eq_mod_eq_0[of "c" "l"] by simp
chaieb@23274
  1449
    hence cl:"c * (l div c) =l" using zmod_zdiv_equality[where a="l" and b="c", symmetric] 
chaieb@17378
  1450
      by simp
chaieb@23274
  1451
    hence "(l*x + (l div c) * Inum (x# bs) e \<le> 0) =
chaieb@23274
  1452
          ((c * (l div c)) * x + (l div c) * Inum (x # bs) e \<le> 0)"
chaieb@23274
  1453
      by simp
nipkow@29667
  1454
    also have "\<dots> = ((l div c) * (c * x + Inum (x # bs) e) \<le> ((l div c)) * 0)" by (simp add: algebra_simps)
chaieb@23274
  1455
    also have "\<dots> = (c*x + Inum (x # bs) e \<le> 0)"
chaieb@23274
  1456
    using mult_le_0_iff [where a="(l div c)" and b="c*x + Inum (x # bs) e"] ldcp by simp
chaieb@23274
  1457
  finally show ?case using numbound0_I[OF be,where b="l*x" and b'="x" and bs="bs"]  be by simp
chaieb@17378
  1458
next
chaieb@23274
  1459
  case (7 c e) hence cp: "c>0" and be: "numbound0 e" and d': "c dvd l" by simp+
chaieb@23274
  1460
    from lp cp have clel: "c\<le>l" by (simp add: zdvd_imp_le [OF d' lp])
chaieb@23274
  1461
    from cp have cnz: "c \<noteq> 0" by simp
chaieb@23274
  1462
    have "c div c\<le> l div c"
chaieb@23274
  1463
      by (simp add: zdiv_mono1[OF clel cp])
chaieb@23274
  1464
    then have ldcp:"0 < l div c" 
chaieb@23274
  1465
      by (simp add: zdiv_self[OF cnz])
nipkow@30042
  1466
    have "c * (l div c) = c* (l div c) + l mod c" using d' dvd_eq_mod_eq_0[of "c" "l"] by simp
chaieb@23274
  1467
    hence cl:"c * (l div c) =l" using zmod_zdiv_equality[where a="l" and b="c", symmetric] 
chaieb@17378
  1468
      by simp
chaieb@23274
  1469
    hence "(l*x + (l div c)* Inum (x # bs) e > 0) =
chaieb@23274
  1470
          ((c * (l div c)) * x + (l div c) * Inum (x # bs) e > 0)"
chaieb@17378
  1471
      by simp
nipkow@29667
  1472
    also have "\<dots> = ((l div c) * (c * x + Inum (x # bs) e) > ((l div c)) * 0)" by (simp add: algebra_simps)
chaieb@23274
  1473
    also have "\<dots> = (c * x + Inum (x # bs) e > 0)"
chaieb@23274
  1474
    using zero_less_mult_iff [where a="(l div c)" and b="c * x + Inum (x # bs) e"] ldcp by simp
chaieb@23274
  1475
  finally show ?case using numbound0_I[OF be,where b="(l * x)" and b'="x" and bs="bs"]  be  by simp
chaieb@17378
  1476
next
chaieb@23274
  1477
  case (8 c e) hence cp: "c>0" and be: "numbound0 e" and d': "c dvd l" by simp+
chaieb@23274
  1478
    from lp cp have clel: "c\<le>l" by (simp add: zdvd_imp_le [OF d' lp])
chaieb@23274
  1479
    from cp have cnz: "c \<noteq> 0" by simp
chaieb@23274
  1480
    have "c div c\<le> l div c"
chaieb@23274
  1481
      by (simp add: zdiv_mono1[OF clel cp])
chaieb@23274
  1482
    then have ldcp:"0 < l div c" 
chaieb@23274
  1483
      by (simp add: zdiv_self[OF cnz])
nipkow@30042
  1484
    have "c * (l div c) = c* (l div c) + l mod c" using d' dvd_eq_mod_eq_0[of "c" "l"] by simp
chaieb@23274
  1485
    hence cl:"c * (l div c) =l" using zmod_zdiv_equality[where a="l" and b="c", symmetric] 
chaieb@17378
  1486
      by simp
chaieb@23274
  1487
    hence "(l*x + (l div c)* Inum (x # bs) e \<ge> 0) =
chaieb@23274
  1488
          ((c*(l div c))*x + (l div c)* Inum (x # bs) e \<ge> 0)"
chaieb@23274
  1489
      by simp
chaieb@23274
  1490
    also have "\<dots> = ((l div c)*(c*x + Inum (x # bs) e) \<ge> ((l div c)) * 0)" 
nipkow@29667
  1491
      by (simp add: algebra_simps)
chaieb@23274
  1492
    also have "\<dots> = (c*x + Inum (x # bs) e \<ge> 0)" using ldcp 
chaieb@23274
  1493
      zero_le_mult_iff [where a="l div c" and b="c*x + Inum (x # bs) e"] by simp
chaieb@23274
  1494
  finally show ?case using be numbound0_I[OF be,where b="l*x" and b'="x" and bs="bs"]  
chaieb@23274
  1495
    by simp
chaieb@17378
  1496
next
chaieb@23274
  1497
  case (3 c e) hence cp: "c>0" and be: "numbound0 e" and d': "c dvd l" by simp+
chaieb@23274
  1498
    from lp cp have clel: "c\<le>l" by (simp add: zdvd_imp_le [OF d' lp])
chaieb@23274
  1499
    from cp have cnz: "c \<noteq> 0" by simp
chaieb@23274
  1500
    have "c div c\<le> l div c"
chaieb@23274
  1501
      by (simp add: zdiv_mono1[OF clel cp])
chaieb@23274
  1502
    then have ldcp:"0 < l div c" 
chaieb@23274
  1503
      by (simp add: zdiv_self[OF cnz])
nipkow@30042
  1504
    have "c * (l div c) = c* (l div c) + l mod c" using d' dvd_eq_mod_eq_0[of "c" "l"] by simp
chaieb@23274
  1505
    hence cl:"c * (l div c) =l" using zmod_zdiv_equality[where a="l" and b="c", symmetric] 
chaieb@17378
  1506
      by simp
chaieb@23274
  1507
    hence "(l * x + (l div c) * Inum (x # bs) e = 0) =
chaieb@23274
  1508
          ((c * (l div c)) * x + (l div c) * Inum (x # bs) e = 0)"
chaieb@23274
  1509
      by simp
nipkow@29667
  1510
    also have "\<dots> = ((l div c) * (c * x + Inum (x # bs) e) = ((l div c)) * 0)" by (simp add: algebra_simps)
chaieb@23274
  1511
    also have "\<dots> = (c * x + Inum (x # bs) e = 0)"
chaieb@23274
  1512
    using mult_eq_0_iff [where a="(l div c)" and b="c * x + Inum (x # bs) e"] ldcp by simp
chaieb@23274
  1513
  finally show ?case using numbound0_I[OF be,where b="(l * x)" and b'="x" and bs="bs"]  be  by simp
chaieb@17378
  1514
next
chaieb@23274
  1515
  case (4 c e) hence cp: "c>0" and be: "numbound0 e" and d': "c dvd l" by simp+
chaieb@23274
  1516
    from lp cp have clel: "c\<le>l" by (simp add: zdvd_imp_le [OF d' lp])
chaieb@23274
  1517
    from cp have cnz: "c \<noteq> 0" by simp
chaieb@23274
  1518
    have "c div c\<le> l div c"
chaieb@23274
  1519
      by (simp add: zdiv_mono1[OF clel cp])
chaieb@23274
  1520
    then have ldcp:"0 < l div c" 
chaieb@23274
  1521
      by (simp add: zdiv_self[OF cnz])
nipkow@30042
  1522
    have "c * (l div c) = c* (l div c) + l mod c" using d' dvd_eq_mod_eq_0[of "c" "l"] by simp
chaieb@23274
  1523
    hence cl:"c * (l div c) =l" using zmod_zdiv_equality[where a="l" and b="c", symmetric] 
chaieb@23274
  1524
      by simp
chaieb@23274
  1525
    hence "(l * x + (l div c) * Inum (x # bs) e \<noteq> 0) =
chaieb@23274
  1526
          ((c * (l div c)) * x + (l div c) * Inum (x # bs) e \<noteq> 0)"
chaieb@23274
  1527
      by simp
nipkow@29667
  1528
    also have "\<dots> = ((l div c) * (c * x + Inum (x # bs) e) \<noteq> ((l div c)) * 0)" by (simp add: algebra_simps)
chaieb@23274
  1529
    also have "\<dots> = (c * x + Inum (x # bs) e \<noteq> 0)"
chaieb@23274
  1530
    using zero_le_mult_iff [where a="(l div c)" and b="c * x + Inum (x # bs) e"] ldcp by simp
chaieb@23274
  1531
  finally show ?case using numbound0_I[OF be,where b="(l * x)" and b'="x" and bs="bs"]  be  by simp
chaieb@17378
  1532
next
chaieb@23274
  1533
  case (9 j c e) hence cp: "c>0" and be: "numbound0 e" and jp: "j > 0" and d': "c dvd l" by simp+
chaieb@23274
  1534
    from lp cp have clel: "c\<le>l" by (simp add: zdvd_imp_le [OF d' lp])
chaieb@23274
  1535
    from cp have cnz: "c \<noteq> 0" by simp
chaieb@23274
  1536
    have "c div c\<le> l div c"
chaieb@23274
  1537
      by (simp add: zdiv_mono1[OF clel cp])
chaieb@23274
  1538
    then have ldcp:"0 < l div c" 
chaieb@23274
  1539
      by (simp add: zdiv_self[OF cnz])
nipkow@30042
  1540
    have "c * (l div c) = c* (l div c) + l mod c" using d' dvd_eq_mod_eq_0[of "c" "l"] by simp
chaieb@23274
  1541
    hence cl:"c * (l div c) =l" using zmod_zdiv_equality[where a="l" and b="c", symmetric] 
chaieb@23274
  1542
      by simp
chaieb@23274
  1543
    hence "(\<exists> (k::int). l * x + (l div c) * Inum (x # bs) e = ((l div c) * j) * k) = (\<exists> (k::int). (c * (l div c)) * x + (l div c) * Inum (x # bs) e = ((l div c) * j) * k)"  by simp
nipkow@29667
  1544
    also have "\<dots> = (\<exists> (k::int). (l div c) * (c * x + Inum (x # bs) e - j * k) = (l div c)*0)" by (simp add: algebra_simps)
wenzelm@26934
  1545
    also fix k have "\<dots> = (\<exists> (k::int). c * x + Inum (x # bs) e - j * k = 0)"
chaieb@23274
  1546
    using zero_le_mult_iff [where a="(l div c)" and b="c * x + Inum (x # bs) e - j * k"] ldcp by simp
chaieb@23274
  1547
  also have "\<dots> = (\<exists> (k::int). c * x + Inum (x # bs) e = j * k)" by simp
chaieb@23274
  1548
  finally show ?case using numbound0_I[OF be,where b="(l * x)" and b'="x" and bs="bs"] be  mult_strict_mono[OF ldcp jp ldcp ] by (simp add: dvd_def)
chaieb@17378
  1549
next
chaieb@23274
  1550
  case (10 j c e) hence cp: "c>0" and be: "numbound0 e" and jp: "j > 0" and d': "c dvd l" by simp+
chaieb@23274
  1551
    from lp cp have clel: "c\<le>l" by (simp add: zdvd_imp_le [OF d' lp])
chaieb@23274
  1552
    from cp have cnz: "c \<noteq> 0" by simp
chaieb@23274
  1553
    have "c div c\<le> l div c"
chaieb@23274
  1554
      by (simp add: zdiv_mono1[OF clel cp])
chaieb@23274
  1555
    then have ldcp:"0 < l div c" 
chaieb@23274
  1556
      by (simp add: zdiv_self[OF cnz])
nipkow@30042
  1557
    have "c * (l div c) = c* (l div c) + l mod c" using d' dvd_eq_mod_eq_0[of "c" "l"] by simp
chaieb@23274
  1558
    hence cl:"c * (l div c) =l" using zmod_zdiv_equality[where a="l" and b="c", symmetric] 
chaieb@23274
  1559
      by simp
chaieb@23274
  1560
    hence "(\<exists> (k::int). l * x + (l div c) * Inum (x # bs) e = ((l div c) * j) * k) = (\<exists> (k::int). (c * (l div c)) * x + (l div c) * Inum (x # bs) e = ((l div c) * j) * k)"  by simp
nipkow@29667
  1561
    also have "\<dots> = (\<exists> (k::int). (l div c) * (c * x + Inum (x # bs) e - j * k) = (l div c)*0)" by (simp add: algebra_simps)
wenzelm@26934
  1562
    also fix k have "\<dots> = (\<exists> (k::int). c * x + Inum (x # bs) e - j * k = 0)"
chaieb@23274
  1563
    using zero_le_mult_iff [where a="(l div c)" and b="c * x + Inum (x # bs) e - j * k"] ldcp by simp
chaieb@23274
  1564
  also have "\<dots> = (\<exists> (k::int). c * x + Inum (x # bs) e = j * k)" by simp
chaieb@23274
  1565
  finally show ?case using numbound0_I[OF be,where b="(l * x)" and b'="x" and bs="bs"] be  mult_strict_mono[OF ldcp jp ldcp ] by (simp add: dvd_def)
haftmann@23689
  1566
qed (auto simp add: gr0_conv_Suc numbound0_I[where bs="bs" and b="(l * x)" and b'="x"])
chaieb@17378
  1567
chaieb@23274
  1568
lemma a\<beta>_ex: assumes linp: "iszlfm p" and d: "d\<beta> p l" and lp: "l>0"
chaieb@23274
  1569
  shows "(\<exists> x. l dvd x \<and> Ifm bbs (x #bs) (a\<beta> p l)) = (\<exists> (x::int). Ifm bbs (x#bs) p)"
chaieb@23274
  1570
  (is "(\<exists> x. l dvd x \<and> ?P x) = (\<exists> x. ?P' x)")
chaieb@23274
  1571
proof-
chaieb@23274
  1572
  have "(\<exists> x. l dvd x \<and> ?P x) = (\<exists> (x::int). ?P (l*x))"
chaieb@23274
  1573
    using unity_coeff_ex[where l="l" and P="?P", simplified] by simp
chaieb@23274
  1574
  also have "\<dots> = (\<exists> (x::int). ?P' x)" using a\<beta>[OF linp d lp] by simp
chaieb@23274
  1575
  finally show ?thesis  . 
chaieb@17378
  1576
qed
chaieb@17378
  1577
chaieb@23274
  1578
lemma \<beta>:
chaieb@23274
  1579
  assumes lp: "iszlfm p"
chaieb@23274
  1580
  and u: "d\<beta> p 1"
chaieb@23274
  1581
  and d: "d\<delta> p d"
chaieb@23274
  1582
  and dp: "d > 0"
chaieb@23274
  1583
  and nob: "\<not>(\<exists>(j::int) \<in> {1 .. d}. \<exists> b\<in> (Inum (a#bs)) ` set(\<beta> p). x = b + j)"
chaieb@23274
  1584
  and p: "Ifm bbs (x#bs) p" (is "?P x")
chaieb@23274
  1585
  shows "?P (x - d)"
chaieb@23274
  1586
using lp u d dp nob p
chaieb@23274
  1587
proof(induct p rule: iszlfm.induct)
nipkow@29700
  1588
  case (5 c e) hence c1: "c=1" and  bn:"numbound0 e" by simp+
chaieb@23274
  1589
    with dp p c1 numbound0_I[OF bn,where b="(x-d)" and b'="x" and bs="bs"] prems
chaieb@23274
  1590
    show ?case by simp
chaieb@23274
  1591
next
nipkow@29700
  1592
  case (6 c e)  hence c1: "c=1" and  bn:"numbound0 e" by simp+
chaieb@23274
  1593
    with dp p c1 numbound0_I[OF bn,where b="(x-d)" and b'="x" and bs="bs"] prems
chaieb@23274
  1594
    show ?case by simp
chaieb@23274
  1595
next
nipkow@29700
  1596
  case (7 c e) hence p: "Ifm bbs (x #bs) (Gt (CN 0 c e))" and c1: "c=1" and bn:"numbound0 e" by simp+
chaieb@23274
  1597
    let ?e = "Inum (x # bs) e"
chaieb@23274
  1598
    {assume "(x-d) +?e > 0" hence ?case using c1 
chaieb@23274
  1599
      numbound0_I[OF bn,where b="(x-d)" and b'="x" and bs="bs"] by simp}
chaieb@23274
  1600
    moreover
chaieb@23274
  1601
    {assume H: "\<not> (x-d) + ?e > 0" 
chaieb@23274
  1602
      let ?v="Neg e"
chaieb@23995
  1603
      have vb: "?v \<in> set (\<beta> (Gt (CN 0 c e)))" by simp
chaieb@23274
  1604
      from prems(11)[simplified simp_thms Inum.simps \<beta>.simps set.simps bex_simps numbound0_I[OF bn,where b="a" and b'="x" and bs="bs"]] 
chaieb@23274
  1605
      have nob: "\<not> (\<exists> j\<in> {1 ..d}. x =  - ?e + j)" by auto 
chaieb@23274
  1606
      from H p have "x + ?e > 0 \<and> x + ?e \<le> d" by (simp add: c1)
chaieb@23274
  1607
      hence "x + ?e \<ge> 1 \<and> x + ?e \<le> d"  by simp
chaieb@23274
  1608
      hence "\<exists> (j::int) \<in> {1 .. d}. j = x + ?e" by simp
chaieb@23274
  1609
      hence "\<exists> (j::int) \<in> {1 .. d}. x = (- ?e + j)" 
wenzelm@32960
  1610
        by (simp add: algebra_simps)
chaieb@23274
  1611
      with nob have ?case by auto}
chaieb@23274
  1612
    ultimately show ?case by blast
chaieb@23274
  1613
next
chaieb@23995
  1614
  case (8 c e) hence p: "Ifm bbs (x #bs) (Ge (CN 0 c e))" and c1: "c=1" and bn:"numbound0 e" 
nipkow@29700
  1615
    by simp+
chaieb@23274
  1616
    let ?e = "Inum (x # bs) e"
chaieb@23274
  1617
    {assume "(x-d) +?e \<ge> 0" hence ?case using  c1 
chaieb@23274
  1618
      numbound0_I[OF bn,where b="(x-d)" and b'="x" and bs="bs"]
wenzelm@32960
  1619
        by simp}
chaieb@23274
  1620
    moreover
chaieb@23274
  1621
    {assume H: "\<not> (x-d) + ?e \<ge> 0" 
chaieb@23274
  1622
      let ?v="Sub (C -1) e"
chaieb@23995
  1623
      have vb: "?v \<in> set (\<beta> (Ge (CN 0 c e)))" by simp
chaieb@23274
  1624
      from prems(11)[simplified simp_thms Inum.simps \<beta>.simps set.simps bex_simps numbound0_I[OF bn,where b="a" and b'="x" and bs="bs"]] 
chaieb@23274
  1625
      have nob: "\<not> (\<exists> j\<in> {1 ..d}. x =  - ?e - 1 + j)" by auto 
chaieb@23274
  1626
      from H p have "x + ?e \<ge> 0 \<and> x + ?e < d" by (simp add: c1)
chaieb@23274
  1627
      hence "x + ?e +1 \<ge> 1 \<and> x + ?e + 1 \<le> d"  by simp
chaieb@23274
  1628
      hence "\<exists> (j::int) \<in> {1 .. d}. j = x + ?e + 1" by simp
nipkow@29667
  1629
      hence "\<exists> (j::int) \<in> {1 .. d}. x= - ?e - 1 + j" by (simp add: algebra_simps)
chaieb@23274
  1630
      with nob have ?case by simp }
chaieb@23274
  1631
    ultimately show ?case by blast
chaieb@23274
  1632
next
nipkow@29700
  1633
  case (3 c e) hence p: "Ifm bbs (x #bs) (Eq (CN 0 c e))" (is "?p x") and c1: "c=1" and bn:"numbound0 e" by simp+
chaieb@23274
  1634
    let ?e = "Inum (x # bs) e"
chaieb@23274
  1635
    let ?v="(Sub (C -1) e)"
chaieb@23995
  1636
    have vb: "?v \<in> set (\<beta> (Eq (CN 0 c e)))" by simp
chaieb@23274
  1637
    from p have "x= - ?e" by (simp add: c1) with prems(11) show ?case using dp
chaieb@23274
  1638
      by simp (erule ballE[where x="1"],
wenzelm@32960
  1639
        simp_all add:algebra_simps numbound0_I[OF bn,where b="x"and b'="a"and bs="bs"])
chaieb@23274
  1640
next
nipkow@29700
  1641
  case (4 c e)hence p: "Ifm bbs (x #bs) (NEq (CN 0 c e))" (is "?p x") and c1: "c=1" and bn:"numbound0 e" by simp+
chaieb@23274
  1642
    let ?e = "Inum (x # bs) e"
chaieb@23274
  1643
    let ?v="Neg e"
chaieb@23995
  1644
    have vb: "?v \<in> set (\<beta> (NEq (CN 0 c e)))" by simp
chaieb@23274
  1645
    {assume "x - d + Inum (((x -d)) # bs) e \<noteq> 0" 
chaieb@23274
  1646
      hence ?case by (simp add: c1)}
chaieb@23274
  1647
    moreover
chaieb@23274
  1648
    {assume H: "x - d + Inum (((x -d)) # bs) e = 0"
chaieb@23274
  1649
      hence "x = - Inum (((x -d)) # bs) e + d" by simp
chaieb@23274
  1650
      hence "x = - Inum (a # bs) e + d"
wenzelm@32960
  1651
        by (simp add: numbound0_I[OF bn,where b="x - d"and b'="a"and bs="bs"])
chaieb@23274
  1652
       with prems(11) have ?case using dp by simp}
chaieb@23274
  1653
  ultimately show ?case by blast
chaieb@23274
  1654
next 
nipkow@29700
  1655
  case (9 j c e) hence p: "Ifm bbs (x #bs) (Dvd j (CN 0 c e))" (is "?p x") and c1: "c=1" and bn:"numbound0 e" by simp+
chaieb@23274
  1656
    let ?e = "Inum (x # bs) e"
chaieb@23274
  1657
    from prems have id: "j dvd d" by simp
chaieb@23274
  1658
    from c1 have "?p x = (j dvd (x+ ?e))" by simp
chaieb@23274
  1659
    also have "\<dots> = (j dvd x - d + ?e)" 
haftmann@23689
  1660
      using zdvd_period[OF id, where x="x" and c="-1" and t="?e"] by simp
chaieb@23274
  1661
    finally show ?case 
chaieb@23274
  1662
      using numbound0_I[OF bn,where b="(x-d)" and b'="x" and bs="bs"] c1 p by simp
chaieb@23274
  1663
next
nipkow@29700
  1664
  case (10 j c e) hence p: "Ifm bbs (x #bs) (NDvd j (CN 0 c e))" (is "?p x") and c1: "c=1" and bn:"numbound0 e" by simp+
chaieb@23274
  1665
    let ?e = "Inum (x # bs) e"
chaieb@23274
  1666
    from prems have id: "j dvd d" by simp
chaieb@23274
  1667
    from c1 have "?p x = (\<not> j dvd (x+ ?e))" by simp
chaieb@23274
  1668
    also have "\<dots> = (\<not> j dvd x - d + ?e)" 
haftmann@23689
  1669
      using zdvd_period[OF id, where x="x" and c="-1" and t="?e"] by simp
chaieb@23274
  1670
    finally show ?case using numbound0_I[OF bn,where b="(x-d)" and b'="x" and bs="bs"] c1 p by simp
haftmann@23689
  1671
qed (auto simp add: numbound0_I[where bs="bs" and b="(x - d)" and b'="x"] gr0_conv_Suc)
chaieb@17378
  1672
chaieb@23274
  1673
lemma \<beta>':   
chaieb@23274
  1674
  assumes lp: "iszlfm p"
chaieb@23274
  1675
  and u: "d\<beta> p 1"
chaieb@23274
  1676
  and d: "d\<delta> p d"
chaieb@23274
  1677
  and dp: "d > 0"
chaieb@23274
  1678
  shows "\<forall> x. \<not>(\<exists>(j::int) \<in> {1 .. d}. \<exists> b\<in> set(\<beta> p). Ifm bbs ((Inum (a#bs) b + j) #bs) p) \<longrightarrow> Ifm bbs (x#bs) p \<longrightarrow> Ifm bbs ((x - d)#bs) p" (is "\<forall> x. ?b \<longrightarrow> ?P x \<longrightarrow> ?P (x - d)")
chaieb@23274
  1679
proof(clarify)
chaieb@23274
  1680
  fix x 
chaieb@23274
  1681
  assume nb:"?b" and px: "?P x" 
chaieb@23274
  1682
  hence nb2: "\<not>(\<exists>(j::int) \<in> {1 .. d}. \<exists> b\<in> (Inum (a#bs)) ` set(\<beta> p). x = b + j)"
chaieb@23274
  1683
    by auto
chaieb@23274
  1684
  from  \<beta>[OF lp u d dp nb2 px] show "?P (x -d )" .
chaieb@17378
  1685
qed
chaieb@23315
  1686
lemma cpmi_eq: "0 < D \<Longrightarrow> (EX z::int. ALL x. x < z --> (P x = P1 x))
chaieb@23315
  1687
==> ALL x.~(EX (j::int) : {1..D}. EX (b::int) : B. P(b+j)) --> P (x) --> P (x - D) 
chaieb@23315
  1688
==> (ALL (x::int). ALL (k::int). ((P1 x)= (P1 (x-k*D))))
chaieb@23315
  1689
==> (EX (x::int). P(x)) = ((EX (j::int) : {1..D} . (P1(j))) | (EX (j::int) : {1..D}. EX (b::int) : B. P (b+j)))"
chaieb@23315
  1690
apply(rule iffI)
chaieb@23315
  1691
prefer 2
chaieb@23315
  1692
apply(drule minusinfinity)
chaieb@23315
  1693
apply assumption+
chaieb@23315
  1694
apply(fastsimp)
chaieb@23315
  1695
apply clarsimp
chaieb@23315
  1696
apply(subgoal_tac "!!k. 0<=k \<Longrightarrow> !x. P x \<longrightarrow> P (x - k*D)")
chaieb@23315
  1697
apply(frule_tac x = x and z=z in decr_lemma)
chaieb@23315
  1698
apply(subgoal_tac "P1(x - (\<bar>x - z\<bar> + 1) * D)")
chaieb@23315
  1699
prefer 2
chaieb@23315
  1700
apply(subgoal_tac "0 <= (\<bar>x - z\<bar> + 1)")
chaieb@23315
  1701
prefer 2 apply arith
chaieb@23315
  1702
 apply fastsimp
chaieb@23315
  1703
apply(drule (1)  periodic_finite_ex)
chaieb@23315
  1704
apply blast
chaieb@23315
  1705
apply(blast dest:decr_mult_lemma)
chaieb@23315
  1706
done
chaieb@17378
  1707
chaieb@23274
  1708
theorem cp_thm:
chaieb@23274
  1709
  assumes lp: "iszlfm p"
chaieb@23274
  1710
  and u: "d\<beta> p 1"
chaieb@23274
  1711
  and d: "d\<delta> p d"
chaieb@23274
  1712
  and dp: "d > 0"
chaieb@23274
  1713
  shows "(\<exists> (x::int). Ifm bbs (x #bs) p) = (\<exists> j\<in> {1.. d}. Ifm bbs (j #bs) (minusinf p) \<or> (\<exists> b \<in> set (\<beta> p). Ifm bbs ((Inum (i#bs) b + j) #bs) p))"
chaieb@23274
  1714
  (is "(\<exists> (x::int). ?P (x)) = (\<exists> j\<in> ?D. ?M j \<or> (\<exists> b\<in> ?B. ?P (?I b + j)))")
chaieb@17378
  1715
proof-
chaieb@23274
  1716
  from minusinf_inf[OF lp u] 
chaieb@23274
  1717
  have th: "\<exists>(z::int). \<forall>x<z. ?P (x) = ?M x" by blast
chaieb@23274
  1718
  let ?B' = "{?I b | b. b\<in> ?B}"
chaieb@23274
  1719
  have BB': "(\<exists>j\<in>?D. \<exists>b\<in> ?B. ?P (?I b +j)) = (\<exists> j \<in> ?D. \<exists> b \<in> ?B'. ?P (b + j))" by auto
chaieb@23274
  1720
  hence th2: "\<forall> x. \<not> (\<exists> j \<in> ?D. \<exists> b \<in> ?B'. ?P ((b + j))) \<longrightarrow> ?P (x) \<longrightarrow> ?P ((x - d))" 
chaieb@23274
  1721
    using \<beta>'[OF lp u d dp, where a="i" and bbs = "bbs"] by blast
chaieb@23274
  1722
  from minusinf_repeats[OF d lp]
chaieb@23274
  1723
  have th3: "\<forall> x k. ?M x = ?M (x-k*d)" by simp
chaieb@23274
  1724
  from cpmi_eq[OF dp th th2 th3] BB' show ?thesis by blast
chaieb@17378
  1725
qed
chaieb@17378
  1726
chaieb@23274
  1727
    (* Implement the right hand sides of Cooper's theorem and Ferrante and Rackoff. *)
chaieb@23274
  1728
lemma mirror_ex: 
chaieb@23274
  1729
  assumes lp: "iszlfm p"
chaieb@23274
  1730
  shows "(\<exists> x. Ifm bbs (x#bs) (mirror p)) = (\<exists> x. Ifm bbs (x#bs) p)"
chaieb@23274
  1731
  (is "(\<exists> x. ?I x ?mp) = (\<exists> x. ?I x p)")
chaieb@23274
  1732
proof(auto)
chaieb@23274
  1733
  fix x assume "?I x ?mp" hence "?I (- x) p" using mirror[OF lp] by blast
chaieb@23274
  1734
  thus "\<exists> x. ?I x p" by blast
chaieb@23274
  1735
next
chaieb@23274
  1736
  fix x assume "?I x p" hence "?I (- x) ?mp" 
chaieb@23274
  1737
    using mirror[OF lp, where x="- x", symmetric] by auto
chaieb@23274
  1738
  thus "\<exists> x. ?I x ?mp" by blast
chaieb@23274
  1739
qed
nipkow@24349
  1740
nipkow@24349
  1741
chaieb@23274
  1742
lemma cp_thm': 
chaieb@23274
  1743
  assumes lp: "iszlfm p"
chaieb@23274
  1744
  and up: "d\<beta> p 1" and dd: "d\<delta> p d" and dp: "d > 0"
chaieb@23274
  1745
  shows "(\<exists> x. Ifm bbs (x#bs) p) = ((\<exists> j\<in> {1 .. d}. Ifm bbs (j#bs) (minusinf p)) \<or> (\<exists> j\<in> {1.. d}. \<exists> b\<in> (Inum (i#bs)) ` set (\<beta> p). Ifm bbs ((b+j)#bs) p))"
chaieb@23274
  1746
  using cp_thm[OF lp up dd dp,where i="i"] by auto
chaieb@17378
  1747
haftmann@35416
  1748
definition unit :: "fm \<Rightarrow> fm \<times> num list \<times> int" where
chaieb@23995
  1749
  "unit p \<equiv> (let p' = zlfm p ; l = \<zeta> p' ; q = And (Dvd l (CN 0 1 (C 0))) (a\<beta> p' l); d = \<delta> q;
chaieb@23274
  1750
             B = remdups (map simpnum (\<beta> q)) ; a = remdups (map simpnum (\<alpha> q))
chaieb@23274
  1751
             in if length B \<le> length a then (q,B,d) else (mirror q, a,d))"
chaieb@17378
  1752
chaieb@23274
  1753
lemma unit: assumes qf: "qfree p"
chaieb@23274
  1754
  shows "\<And> q B d. unit p = (q,B,d) \<Longrightarrow> ((\<exists> x. Ifm bbs (x#bs) p) = (\<exists> x. Ifm bbs (x#bs) q)) \<and> (Inum (i#bs)) ` set B = (Inum (i#bs)) ` set (\<beta> q) \<and> d\<beta> q 1 \<and> d\<delta> q d \<and> d >0 \<and> iszlfm q \<and> (\<forall> b\<in> set B. numbound0 b)"
chaieb@23274
  1755
proof-
chaieb@23274
  1756
  fix q B d 
chaieb@23274
  1757
  assume qBd: "unit p = (q,B,d)"
chaieb@23274
  1758
  let ?thes = "((\<exists> x. Ifm bbs (x#bs) p) = (\<exists> x. Ifm bbs (x#bs) q)) \<and>
chaieb@23274
  1759
    Inum (i#bs) ` set B = Inum (i#bs) ` set (\<beta> q) \<and>
chaieb@23274
  1760
    d\<beta> q 1 \<and> d\<delta> q d \<and> 0 < d \<and> iszlfm q \<and> (\<forall> b\<in> set B. numbound0 b)"
chaieb@23274
  1761
  let ?I = "\<lambda> x p. Ifm bbs (x#bs) p"
chaieb@23274
  1762
  let ?p' = "zlfm p"
chaieb@23274
  1763
  let ?l = "\<zeta> ?p'"
chaieb@23995
  1764
  let ?q = "And (Dvd ?l (CN 0 1 (C 0))) (a\<beta> ?p' ?l)"
chaieb@23274
  1765
  let ?d = "\<delta> ?q"
chaieb@23274
  1766
  let ?B = "set (\<beta> ?q)"
chaieb@23274
  1767
  let ?B'= "remdups (map simpnum (\<beta> ?q))"
chaieb@23274
  1768
  let ?A = "set (\<alpha> ?q)"
chaieb@23274
  1769
  let ?A'= "remdups (map simpnum (\<alpha> ?q))"
chaieb@23274
  1770
  from conjunct1[OF zlfm_I[OF qf, where bs="bs"]] 
chaieb@23274
  1771
  have pp': "\<forall> i. ?I i ?p' = ?I i p" by auto
chaieb@23274
  1772
  from conjunct2[OF zlfm_I[OF qf, where bs="bs" and i="i"]]
chaieb@23274
  1773
  have lp': "iszlfm ?p'" . 
chaieb@23274
  1774
  from lp' \<zeta>[where p="?p'"] have lp: "?l >0" and dl: "d\<beta> ?p' ?l" by auto
chaieb@23274
  1775
  from a\<beta>_ex[where p="?p'" and l="?l" and bs="bs", OF lp' dl lp] pp'
chaieb@23274
  1776
  have pq_ex:"(\<exists> (x::int). ?I x p) = (\<exists> x. ?I x ?q)" by simp 
chaieb@23274
  1777
  from lp' lp a\<beta>[OF lp' dl lp] have lq:"iszlfm ?q" and uq: "d\<beta> ?q 1"  by auto
chaieb@23274
  1778
  from \<delta>[OF lq] have dp:"?d >0" and dd: "d\<delta> ?q ?d" by blast+
chaieb@23274
  1779
  let ?N = "\<lambda> t. Inum (i#bs) t"
chaieb@23274
  1780
  have "?N ` set ?B' = ((?N o simpnum) ` ?B)" by auto 
chaieb@23274
  1781
  also have "\<dots> = ?N ` ?B" using simpnum_ci[where bs="i#bs"] by auto
chaieb@23274
  1782
  finally have BB': "?N ` set ?B' = ?N ` ?B" .
chaieb@23274
  1783
  have "?N ` set ?A' = ((?N o simpnum) ` ?A)" by auto 
chaieb@23274
  1784
  also have "\<dots> = ?N ` ?A" using simpnum_ci[where bs="i#bs"] by auto
chaieb@23274
  1785
  finally have AA': "?N ` set ?A' = ?N ` ?A" .
chaieb@23274
  1786
  from \<beta>_numbound0[OF lq] have B_nb:"\<forall> b\<in> set ?B'. numbound0 b"
chaieb@23274
  1787
    by (simp add: simpnum_numbound0)
chaieb@23274
  1788
  from \<alpha>_l[OF lq] have A_nb: "\<forall> b\<in> set ?A'. numbound0 b"
chaieb@23274
  1789
    by (simp add: simpnum_numbound0)
chaieb@23274
  1790
    {assume "length ?B' \<le> length ?A'"
chaieb@23274
  1791
    hence q:"q=?q" and "B = ?B'" and d:"d = ?d"
chaieb@23274
  1792
      using qBd by (auto simp add: Let_def unit_def)
chaieb@23274
  1793
    with BB' B_nb have b: "?N ` (set B) = ?N ` set (\<beta> q)" 
chaieb@23274
  1794
      and bn: "\<forall>b\<in> set B. numbound0 b" by simp+ 
chaieb@23274
  1795
  with pq_ex dp uq dd lq q d have ?thes by simp}
chaieb@23274
  1796
  moreover 
chaieb@23274
  1797
  {assume "\<not> (length ?B' \<le> length ?A')"
chaieb@23274
  1798
    hence q:"q=mirror ?q" and "B = ?A'" and d:"d = ?d"
chaieb@23274
  1799
      using qBd by (auto simp add: Let_def unit_def)
chaieb@23274
  1800
    with AA' mirror\<alpha>\<beta>[OF lq] A_nb have b:"?N ` (set B) = ?N ` set (\<beta> q)" 
chaieb@23274
  1801
      and bn: "\<forall>b\<in> set B. numbound0 b" by simp+
chaieb@23274
  1802
    from mirror_ex[OF lq] pq_ex q 
chaieb@23274
  1803
    have pqm_eq:"(\<exists> (x::int). ?I x p) = (\<exists> (x::int). ?I x q)" by simp
chaieb@23274
  1804
    from lq uq q mirror_l[where p="?q"]
chaieb@23274
  1805
    have lq': "iszlfm q" and uq: "d\<beta> q 1" by auto
chaieb@23274
  1806
    from \<delta>[OF lq'] mirror_\<delta>[OF lq] q d have dq:"d\<delta> q d " by auto
chaieb@23274
  1807
    from pqm_eq b bn uq lq' dp dq q dp d have ?thes by simp
chaieb@23274
  1808
  }
chaieb@23274
  1809
  ultimately show ?thes by blast
chaieb@23274
  1810
qed
chaieb@23274
  1811
    (* Cooper's Algorithm *)
chaieb@17378
  1812
haftmann@35416
  1813
definition cooper :: "fm \<Rightarrow> fm" where
chaieb@23274
  1814
  "cooper p \<equiv> 
haftmann@23689
  1815
  (let (q,B,d) = unit p; js = iupt 1 d;
chaieb@23274
  1816
       mq = simpfm (minusinf q);
chaieb@23274
  1817
       md = evaldjf (\<lambda> j. simpfm (subst0 (C j) mq)) js
chaieb@23274
  1818
   in if md = T then T else
chaieb@23274
  1819
    (let qd = evaldjf (\<lambda> (b,j). simpfm (subst0 (Add b (C j)) q)) 
nipkow@24336
  1820
                               [(b,j). b\<leftarrow>B,j\<leftarrow>js]
chaieb@23274
  1821
     in decr (disj md qd)))"
chaieb@23274
  1822
lemma cooper: assumes qf: "qfree p"
chaieb@23274
  1823
  shows "((\<exists> x. Ifm bbs (x#bs) p) = (Ifm bbs bs (cooper p))) \<and> qfree (cooper p)" 
chaieb@23274
  1824
  (is "(?lhs = ?rhs) \<and> _")
chaieb@23274
  1825
proof-
chaieb@23274
  1826
  let ?I = "\<lambda> x p. Ifm bbs (x#bs) p"
chaieb@23274
  1827
  let ?q = "fst (unit p)"
chaieb@23274
  1828
  let ?B = "fst (snd(unit p))"
chaieb@23274
  1829
  let ?d = "snd (snd (unit p))"
haftmann@23689
  1830
  let ?js = "iupt 1 ?d"
chaieb@23274
  1831
  let ?mq = "minusinf ?q"
chaieb@23274
  1832
  let ?smq = "simpfm ?mq"
chaieb@23274
  1833
  let ?md = "evaldjf (\<lambda> j. simpfm (subst0 (C j) ?smq)) ?js"
wenzelm@26934
  1834
  fix i
chaieb@23274
  1835
  let ?N = "\<lambda> t. Inum (i#bs) t"
nipkow@24336
  1836
  let ?Bjs = "[(b,j). b\<leftarrow>?B,j\<leftarrow>?js]"
nipkow@24336
  1837
  let ?qd = "evaldjf (\<lambda> (b,j). simpfm (subst0 (Add b (C j)) ?q)) ?Bjs"
chaieb@23274
  1838
  have qbf:"unit p = (?q,?B,?d)" by simp
chaieb@23274
  1839
  from unit[OF qf qbf] have pq_ex: "(\<exists>(x::int). ?I x p) = (\<exists> (x::int). ?I x ?q)" and 
chaieb@23274
  1840
    B:"?N ` set ?B = ?N ` set (\<beta> ?q)" and 
chaieb@23274
  1841
    uq:"d\<beta> ?q 1" and dd: "d\<delta> ?q ?d" and dp: "?d > 0" and 
chaieb@23274
  1842
    lq: "iszlfm ?q" and 
chaieb@23274
  1843
    Bn: "\<forall> b\<in> set ?B. numbound0 b" by auto
chaieb@23274
  1844
  from zlin_qfree[OF lq] have qfq: "qfree ?q" .
chaieb@23274
  1845
  from simpfm_qf[OF minusinf_qfree[OF qfq]] have qfmq: "qfree ?smq".
chaieb@23274
  1846
  have jsnb: "\<forall> j \<in> set ?js. numbound0 (C j)" by simp
chaieb@23274
  1847
  hence "\<forall> j\<in> set ?js. bound0 (subst0 (C j) ?smq)" 
chaieb@23274
  1848
    by (auto simp only: subst0_bound0[OF qfmq])
chaieb@23274
  1849
  hence th: "\<forall> j\<in> set ?js. bound0 (simpfm (subst0 (C j) ?smq))"
chaieb@23274
  1850
    by (auto simp add: simpfm_bound0)
chaieb@23274
  1851
  from evaldjf_bound0[OF th] have mdb: "bound0 ?md" by simp 
nipkow@24336
  1852
  from Bn jsnb have "\<forall> (b,j) \<in> set ?Bjs. numbound0 (Add b (C j))"
haftmann@23689
  1853
    by simp
nipkow@24336
  1854
  hence "\<forall> (b,j) \<in> set ?Bjs. bound0 (subst0 (Add b (C j)) ?q)"
chaieb@23274
  1855
    using subst0_bound0[OF qfq] by blast
nipkow@24336
  1856
  hence "\<forall> (b,j) \<in> set ?Bjs. bound0 (simpfm (subst0 (Add b (C j)) ?q))"
chaieb@23274
  1857
    using simpfm_bound0  by blast
nipkow@24336
  1858
  hence th': "\<forall> x \<in> set ?Bjs. bound0 ((\<lambda> (b,j). simpfm (subst0 (Add b (C j)) ?q)) x)"
chaieb@23274
  1859
    by auto 
chaieb@23274
  1860
  from evaldjf_bound0 [OF th'] have qdb: "bound0 ?qd" by simp
chaieb@23274
  1861
  from mdb qdb 
chaieb@23274
  1862
  have mdqdb: "bound0 (disj ?md ?qd)" by (simp only: disj_def, cases "?md=T \<or> ?qd=T", simp_all)
chaieb@23274
  1863
  from trans [OF pq_ex cp_thm'[OF lq uq dd dp,where i="i"]] B
chaieb@23274
  1864
  have "?lhs = (\<exists> j\<in> {1.. ?d}. ?I j ?mq \<or> (\<exists> b\<in> ?N ` set ?B. Ifm bbs ((b+ j)#bs) ?q))" by auto
chaieb@23274
  1865
  also have "\<dots> = (\<exists> j\<in> {1.. ?d}. ?I j ?mq \<or> (\<exists> b\<in> set ?B. Ifm bbs ((?N b+ j)#bs) ?q))" by simp
chaieb@23274
  1866
  also have "\<dots> = ((\<exists> j\<in> {1.. ?d}. ?I j ?mq ) \<or> (\<exists> j\<in> {1.. ?d}. \<exists> b\<in> set ?B. Ifm bbs ((?N (Add b (C j)))#bs) ?q))" by (simp only: Inum.simps) blast
chaieb@23274
  1867
  also have "\<dots> = ((\<exists> j\<in> {1.. ?d}. ?I j ?smq ) \<or> (\<exists> j\<in> {1.. ?d}. \<exists> b\<in> set ?B. Ifm bbs ((?N (Add b (C j)))#bs) ?q))" by (simp add: simpfm) 
chaieb@23274
  1868
  also have "\<dots> = ((\<exists> j\<in> set ?js. (\<lambda> j. ?I i (simpfm (subst0 (C j) ?smq))) j) \<or> (\<exists> j\<in> set ?js. \<exists> b\<in> set ?B. Ifm bbs ((?N (Add b (C j)))#bs) ?q))"
chaieb@23274
  1869
    by (simp only: simpfm subst0_I[OF qfmq] iupt_set) auto
chaieb@23274
  1870
  also have "\<dots> = (?I i (evaldjf (\<lambda> j. simpfm (subst0 (C j) ?smq)) ?js) \<or> (\<exists> j\<in> set ?js. \<exists> b\<in> set ?B. ?I i (subst0 (Add b (C j)) ?q)))" 
chaieb@23274
  1871
   by (simp only: evaldjf_ex subst0_I[OF qfq])
nipkow@24336
  1872
 also have "\<dots>= (?I i ?md \<or> (\<exists> (b,j) \<in> set ?Bjs. (\<lambda> (b,j). ?I i (simpfm (subst0 (Add b (C j)) ?q))) (b,j)))"
nipkow@24349
  1873
   by (simp only: simpfm set_concat set_map concat_map_singleton UN_simps) blast
nipkow@24336
  1874
 also have "\<dots> = (?I i ?md \<or> (?I i (evaldjf (\<lambda> (b,j). simpfm (subst0 (Add b (C j)) ?q)) ?Bjs)))"
nipkow@24336
  1875
   by (simp only: evaldjf_ex[where bs="i#bs" and f="\<lambda> (b,j). simpfm (subst0 (Add b (C j)) ?q)" and ps="?Bjs"]) (auto simp add: split_def)
chaieb@23274
  1876
 finally have mdqd: "?lhs = (?I i ?md \<or> ?I i ?qd)" by simp  
chaieb@23274
  1877
  also have "\<dots> = (?I i (disj ?md ?qd))" by (simp add: disj)
chaieb@23274
  1878
  also have "\<dots> = (Ifm bbs bs (decr (disj ?md ?qd)))" by (simp only: decr [OF mdqdb]) 
chaieb@23274
  1879
  finally have mdqd2: "?lhs = (Ifm bbs bs (decr (disj ?md ?qd)))" . 
chaieb@23274
  1880
  {assume mdT: "?md = T"
chaieb@23274
  1881
    hence cT:"cooper p = T" 
chaieb@23274
  1882
      by (simp only: cooper_def unit_def split_def Let_def if_True) simp
chaieb@23274
  1883
    from mdT have lhs:"?lhs" using mdqd by simp 
chaieb@23274
  1884
    from mdT have "?rhs" by (simp add: cooper_def unit_def split_def)
chaieb@23274
  1885
    with lhs cT have ?thesis by simp }
chaieb@17378
  1886
  moreover
chaieb@23274
  1887
  {assume mdT: "?md \<noteq> T" hence "cooper p = decr (disj ?md ?qd)" 
chaieb@23274
  1888
      by (simp only: cooper_def unit_def split_def Let_def if_False) 
chaieb@23274
  1889
    with mdqd2 decr_qf[OF mdqdb] have ?thesis by simp }
chaieb@17378
  1890
  ultimately show ?thesis by blast
chaieb@17378
  1891
qed
chaieb@17378
  1892
haftmann@27456
  1893
definition pa :: "fm \<Rightarrow> fm" where
haftmann@27456
  1894
  "pa p = qelim (prep p) cooper"
chaieb@17378
  1895
chaieb@23274
  1896
theorem mirqe: "(Ifm bbs bs (pa p) = Ifm bbs bs p) \<and> qfree (pa p)"
chaieb@23274
  1897
  using qelim_ci cooper prep by (auto simp add: pa_def)
chaieb@17378
  1898
haftmann@23515
  1899
definition
haftmann@23515
  1900
  cooper_test :: "unit \<Rightarrow> fm"
haftmann@23515
  1901
where
haftmann@23515
  1902
  "cooper_test u = pa (E (A (Imp (Ge (Sub (Bound 0) (Bound 1)))
haftmann@23515
  1903
    (E (E (Eq (Sub (Add (Mul 3 (Bound 1)) (Mul 5 (Bound 0)))
haftmann@23515
  1904
      (Bound 2))))))))"
chaieb@17378
  1905
haftmann@27456
  1906
ML {* @{code cooper_test} () *}
haftmann@27456
  1907
haftmann@36608
  1908
(*
haftmann@36798
  1909
code_reflect Cooper_Procedure
haftmann@36526
  1910
  functions pa
haftmann@36526
  1911
  file "~~/src/HOL/Tools/Qelim/generated_cooper.ML"
haftmann@36608
  1912
*)
haftmann@27456
  1913
wenzelm@28290
  1914
oracle linzqe_oracle = {*
haftmann@27456
  1915
let
haftmann@27456
  1916
haftmann@27456
  1917
fun num_of_term vs (t as Free (xn, xT)) = (case AList.lookup (op =) vs t
haftmann@27456
  1918
     of NONE => error "Variable not found in the list!"
haftmann@27456
  1919
      | SOME n => @{code Bound} n)
haftmann@27456
  1920
  | num_of_term vs @{term "0::int"} = @{code C} 0
haftmann@27456
  1921
  | num_of_term vs @{term "1::int"} = @{code C} 1
haftmann@27456
  1922
  | num_of_term vs (@{term "number_of :: int \<Rightarrow> int"} $ t) = @{code C} (HOLogic.dest_numeral t)
haftmann@27456
  1923
  | num_of_term vs (Bound i) = @{code Bound} i
haftmann@27456
  1924
  | num_of_term vs (@{term "uminus :: int \<Rightarrow> int"} $ t') = @{code Neg} (num_of_term vs t')
haftmann@27456
  1925
  | num_of_term vs (@{term "op + :: int \<Rightarrow> int \<Rightarrow> int"} $ t1 $ t2) =
haftmann@27456
  1926
      @{code Add} (num_of_term vs t1, num_of_term vs t2)
haftmann@27456
  1927
  | num_of_term vs (@{term "op - :: int \<Rightarrow> int \<Rightarrow> int"} $ t1 $ t2) =
haftmann@27456
  1928
      @{code Sub} (num_of_term vs t1, num_of_term vs t2)
haftmann@27456
  1929
  | num_of_term vs (@{term "op * :: int \<Rightarrow> int \<Rightarrow> int"} $ t1 $ t2) =
haftmann@27456
  1930
      (case try HOLogic.dest_number t1
haftmann@27456
  1931
       of SOME (_, i) => @{code Mul} (i, num_of_term vs t2)
haftmann@27456
  1932
        | NONE => (case try HOLogic.dest_number t2
haftmann@27456
  1933
                of SOME (_, i) => @{code Mul} (i, num_of_term vs t1)
haftmann@27456
  1934
                 | NONE => error "num_of_term: unsupported multiplication"))
wenzelm@28264
  1935
  | num_of_term vs t = error ("num_of_term: unknown term " ^ Syntax.string_of_term @{context} t);
haftmann@27456
  1936
haftmann@27456
  1937
fun fm_of_term ps vs @{term True} = @{code T}
haftmann@27456
  1938
  | fm_of_term ps vs @{term False} = @{code F}
haftmann@27456
  1939
  | fm_of_term ps vs (@{term "op < :: int \<Rightarrow> int \<Rightarrow> bool"} $ t1 $ t2) =
haftmann@27456
  1940
      @{code Lt} (@{code Sub} (num_of_term vs t1, num_of_term vs t2))
haftmann@27456
  1941
  | fm_of_term ps vs (@{term "op \<le> :: int \<Rightarrow> int \<Rightarrow> bool"} $ t1 $ t2) =
haftmann@27456
  1942
      @{code Le} (@{code Sub} (num_of_term vs t1, num_of_term vs t2))
haftmann@27456
  1943
  | fm_of_term ps vs (@{term "op = :: int \<Rightarrow> int \<Rightarrow> bool"} $ t1 $ t2) =
haftmann@27456
  1944
      @{code Eq} (@{code Sub} (num_of_term vs t1, num_of_term vs t2)) 
haftmann@27456
  1945
  | fm_of_term ps vs (@{term "op dvd :: int \<Rightarrow> int \<Rightarrow> bool"} $ t1 $ t2) =
haftmann@27456
  1946
      (case try HOLogic.dest_number t1
haftmann@27456
  1947
       of SOME (_, i) => @{code Dvd} (i, num_of_term vs t2)
haftmann@27456
  1948
        | NONE => error "num_of_term: unsupported dvd")
haftmann@27456
  1949
  | fm_of_term ps vs (@{term "op = :: bool \<Rightarrow> bool \<Rightarrow> bool"} $ t1 $ t2) =
haftmann@27456
  1950
      @{code Iff} (fm_of_term ps vs t1, fm_of_term ps vs t2)
haftmann@38795
  1951
  | fm_of_term ps vs (@{term HOL.conj} $ t1 $ t2) =
haftmann@27456
  1952
      @{code And} (fm_of_term ps vs t1, fm_of_term ps vs t2)
haftmann@38795
  1953
  | fm_of_term ps vs (@{term HOL.disj} $ t1 $ t2) =
haftmann@27456
  1954
      @{code Or} (fm_of_term ps vs t1, fm_of_term ps vs t2)
haftmann@38786
  1955
  | fm_of_term ps vs (@{term HOL.implies} $ t1 $ t2) =
haftmann@27456
  1956
      @{code Imp} (fm_of_term ps vs t1, fm_of_term ps vs t2)
haftmann@27456
  1957
  | fm_of_term ps vs (@{term "Not"} $ t') =
haftmann@27456
  1958
      @{code NOT} (fm_of_term ps vs t')
haftmann@38558
  1959
  | fm_of_term ps vs (Const (@{const_name Ex}, _) $ Abs (xn, xT, p)) =
haftmann@27456
  1960
      let
haftmann@27456
  1961
        val (xn', p') = variant_abs (xn, xT, p);
haftmann@27456
  1962
        val vs' = (Free (xn', xT), 0) :: map (fn (v, n) => (v, n + 1)) vs;
haftmann@27456
  1963
      in @{code E} (fm_of_term ps vs' p) end
haftmann@38558
  1964
  | fm_of_term ps vs (Const (@{const_name All}, _) $ Abs (xn, xT, p)) =
haftmann@27456
  1965
      let
haftmann@27456
  1966
        val (xn', p') = variant_abs (xn, xT, p);
haftmann@27456
  1967
        val vs' = (Free (xn', xT), 0) :: map (fn (v, n) => (v, n + 1)) vs;
haftmann@27456
  1968
      in @{code A} (fm_of_term ps vs' p) end
wenzelm@28264
  1969
  | fm_of_term ps vs t = error ("fm_of_term : unknown term " ^ Syntax.string_of_term @{context} t);
haftmann@23515
  1970
haftmann@27456
  1971
fun term_of_num vs (@{code C} i) = HOLogic.mk_number HOLogic.intT i
haftmann@27456
  1972
  | term_of_num vs (@{code Bound} n) = fst (the (find_first (fn (_, m) => n = m) vs))
haftmann@27456
  1973
  | term_of_num vs (@{code Neg} t') = @{term "uminus :: int \<Rightarrow> int"} $ term_of_num vs t'
haftmann@27456
  1974
  | term_of_num vs (@{code Add} (t1, t2)) = @{term "op + :: int \<Rightarrow> int \<Rightarrow> int"} $
haftmann@27456
  1975
      term_of_num vs t1 $ term_of_num vs t2
haftmann@27456
  1976
  | term_of_num vs (@{code Sub} (t1, t2)) = @{term "op - :: int \<Rightarrow> int \<Rightarrow> int"} $
haftmann@27456
  1977
      term_of_num vs t1 $ term_of_num vs t2
haftmann@27456
  1978
  | term_of_num vs (@{code Mul} (i, t2)) = @{term "op * :: int \<Rightarrow> int \<Rightarrow> int"} $
haftmann@27456
  1979
      term_of_num vs (@{code C} i) $ term_of_num vs t2
haftmann@29788
  1980
  | term_of_num vs (@{code CN} (n, i, t)) = term_of_num vs (@{code Add} (@{code Mul} (i, @{code Bound} n), t));
haftmann@27456
  1981
haftmann@27456
  1982
fun term_of_fm ps vs @{code T} = HOLogic.true_const 
haftmann@27456
  1983
  | term_of_fm ps vs @{code F} = HOLogic.false_const
haftmann@27456
  1984
  | term_of_fm ps vs (@{code Lt} t) =
haftmann@27456
  1985
      @{term "op < :: int \<Rightarrow> int \<Rightarrow> bool"} $ term_of_num vs t $ @{term "0::int"}
haftmann@27456
  1986
  | term_of_fm ps vs (@{code Le} t) =
haftmann@27456
  1987
      @{term "op \<le> :: int \<Rightarrow> int \<Rightarrow> bool"} $ term_of_num vs t $ @{term "0::int"}
haftmann@27456
  1988
  | term_of_fm ps vs (@{code Gt} t) =
haftmann@27456
  1989
      @{term "op < :: int \<Rightarrow> int \<Rightarrow> bool"} $ @{term "0::int"} $ term_of_num vs t
haftmann@27456
  1990
  | term_of_fm ps vs (@{code Ge} t) =
haftmann@27456
  1991
      @{term "op \<le> :: int \<Rightarrow> int \<Rightarrow> bool"} $ @{term "0::int"} $ term_of_num vs t
haftmann@27456
  1992
  | term_of_fm ps vs (@{code Eq} t) =
haftmann@27456
  1993
      @{term "op = :: int \<Rightarrow> int \<Rightarrow> bool"} $ term_of_num vs t $ @{term "0::int"}
haftmann@27456
  1994
  | term_of_fm ps vs (@{code NEq} t) =
haftmann@27456
  1995
      term_of_fm ps vs (@{code NOT} (@{code Eq} t))
haftmann@27456
  1996
  | term_of_fm ps vs (@{code Dvd} (i, t)) =
haftmann@27456
  1997
      @{term "op dvd :: int \<Rightarrow> int \<Rightarrow> bool"} $ term_of_num vs (@{code C} i) $ term_of_num vs t
haftmann@27456
  1998
  | term_of_fm ps vs (@{code NDvd} (i, t)) =
haftmann@27456
  1999
      term_of_fm ps vs (@{code NOT} (@{code Dvd} (i, t)))
haftmann@27456
  2000
  | term_of_fm ps vs (@{code NOT} t') =
haftmann@27456
  2001
      HOLogic.Not $ term_of_fm ps vs t'
haftmann@27456
  2002
  | term_of_fm ps vs (@{code And} (t1, t2)) =
haftmann@27456
  2003
      HOLogic.conj $ term_of_fm ps vs t1 $ term_of_fm ps vs t2
haftmann@27456
  2004
  | term_of_fm ps vs (@{code Or} (t1, t2)) =
haftmann@27456
  2005
      HOLogic.disj $ term_of_fm ps vs t1 $ term_of_fm ps vs t2
haftmann@27456
  2006
  | term_of_fm ps vs (@{code Imp} (t1, t2)) =
haftmann@27456
  2007
      HOLogic.imp $ term_of_fm ps vs t1 $ term_of_fm ps vs t2
haftmann@27456
  2008
  | term_of_fm ps vs (@{code Iff} (t1, t2)) =
haftmann@27456
  2009
      @{term "op = :: bool \<Rightarrow> bool \<Rightarrow> bool"} $ term_of_fm ps vs t1 $ term_of_fm ps vs t2
haftmann@27456
  2010
  | term_of_fm ps vs (@{code Closed} n) = (fst o the) (find_first (fn (_, m) => m = n) ps)
haftmann@29788
  2011
  | term_of_fm ps vs (@{code NClosed} n) = term_of_fm ps vs (@{code NOT} (@{code Closed} n));
haftmann@27456
  2012
haftmann@27456
  2013
fun term_bools acc t =
haftmann@27456
  2014
  let
haftmann@38795
  2015
    val is_op = member (op =) [@{term HOL.conj}, @{term HOL.disj}, @{term HOL.implies}, @{term "op = :: bool => _"},
haftmann@27456
  2016
      @{term "op = :: int => _"}, @{term "op < :: int => _"},
haftmann@27456
  2017
      @{term "op <= :: int => _"}, @{term "Not"}, @{term "All :: (int => _) => _"},
haftmann@27456
  2018
      @{term "Ex :: (int => _) => _"}, @{term "True"}, @{term "False"}]
haftmann@27456
  2019
    fun is_ty t = not (fastype_of t = HOLogic.boolT) 
haftmann@27456
  2020
  in case t
haftmann@27456
  2021
   of (l as f $ a) $ b => if is_ty t orelse is_op t then term_bools (term_bools acc l)b 
haftmann@27456
  2022
        else insert (op aconv) t acc
haftmann@27456
  2023
    | f $ a => if is_ty t orelse is_op t then term_bools (term_bools acc f) a  
haftmann@27456
  2024
        else insert (op aconv) t acc
haftmann@27456
  2025
    | Abs p => term_bools acc (snd (variant_abs p))
haftmann@27456
  2026
    | _ => if is_ty t orelse is_op t then acc else insert (op aconv) t acc
haftmann@27456
  2027
  end;
haftmann@27456
  2028
wenzelm@28290
  2029
in fn ct =>
wenzelm@28290
  2030
  let
wenzelm@28290
  2031
    val thy = Thm.theory_of_cterm ct;
wenzelm@28290
  2032
    val t = Thm.term_of ct;
wenzelm@29265
  2033
    val fs = OldTerm.term_frees t;
haftmann@27456
  2034
    val bs = term_bools [] t;
haftmann@33063
  2035
    val vs = map_index swap fs;
haftmann@33063
  2036
    val ps = map_index swap bs;
haftmann@27456
  2037
    val t' = (term_of_fm ps vs o @{code pa} o fm_of_term ps vs) t;
wenzelm@28290
  2038
  in (Thm.cterm_of thy o HOLogic.mk_Trueprop o HOLogic.mk_eq) (t, t') end
haftmann@27456
  2039
end;
haftmann@27456
  2040
*}
haftmann@27456
  2041
haftmann@29788
  2042
use "cooper_tac.ML"
haftmann@29788
  2043
setup "Cooper_Tac.setup"
chaieb@17378
  2044
haftmann@27456
  2045
text {* Tests *}
haftmann@27456
  2046
chaieb@23274
  2047
lemma "\<exists> (j::int). \<forall> x\<ge>j. (\<exists> a b. x = 3*a+5*b)"
haftmann@27456
  2048
  by cooper
chaieb@17378
  2049
haftmann@27456
  2050
lemma "ALL (x::int) >=8. EX i j. 5*i + 3*j = x"
haftmann@27456
  2051
  by cooper
haftmann@27456
  2052
chaieb@23274
  2053
theorem "(\<forall>(y::int). 3 dvd y) ==> \<forall>(x::int). b < x --> a \<le> x"
chaieb@23274
  2054
  by cooper
chaieb@17378
  2055
chaieb@23274
  2056
theorem "!! (y::int) (z::int) (n::int). 3 dvd z ==> 2 dvd (y::int) ==>
chaieb@23274
  2057
  (\<exists>(x::int).  2*x =  y) & (\<exists>(k::int). 3*k = z)"
chaieb@23274
  2058
  by cooper
chaieb@23274
  2059
chaieb@23274
  2060
theorem "!! (y::int) (z::int) n. Suc(n::nat) < 6 ==>  3 dvd z ==>
chaieb@23274
  2061
  2 dvd (y::int) ==> (\<exists>(x::int).  2*x =  y) & (\<exists>(k::int). 3*k = z)"
chaieb@23274
  2062
  by cooper
chaieb@23274
  2063
chaieb@23274
  2064
theorem "\<forall>(x::nat). \<exists>(y::nat). (0::nat) \<le> 5 --> y = 5 + x "
chaieb@23274
  2065
  by cooper
chaieb@17378
  2066
haftmann@27456
  2067
lemma "ALL (x::int) >=8. EX i j. 5*i + 3*j = x"
haftmann@27456
  2068
  by cooper 
haftmann@27456
  2069
haftmann@27456
  2070
lemma "ALL (y::int) (z::int) (n::int). 3 dvd z --> 2 dvd (y::int) --> (EX (x::int).  2*x =  y) & (EX (k::int). 3*k = z)"
haftmann@27456
  2071
  by cooper
haftmann@27456
  2072
haftmann@27456
  2073
lemma "ALL(x::int) y. x < y --> 2 * x + 1 < 2 * y"
haftmann@27456
  2074
  by cooper
haftmann@27456
  2075
haftmann@27456
  2076
lemma "ALL(x::int) y. 2 * x + 1 ~= 2 * y"
haftmann@27456
  2077
  by cooper
haftmann@27456
  2078
haftmann@27456
  2079
lemma "EX(x::int) y. 0 < x  & 0 <= y  & 3 * x - 5 * y = 1"
haftmann@27456
  2080
  by cooper
haftmann@27456
  2081
haftmann@27456
  2082
lemma "~ (EX(x::int) (y::int) (z::int). 4*x + (-6::int)*y = 1)"
haftmann@27456
  2083
  by cooper
haftmann@27456
  2084
haftmann@27456
  2085
lemma "ALL(x::int). (2 dvd x) --> (EX(y::int). x = 2*y)"
haftmann@27456
  2086
  by cooper
haftmann@27456
  2087
haftmann@27456
  2088
lemma "ALL(x::int). (2 dvd x) = (EX(y::int). x = 2*y)"
haftmann@27456
  2089
  by cooper
haftmann@27456
  2090
haftmann@27456
  2091
lemma "ALL(x::int). ((2 dvd x) = (ALL(y::int). x ~= 2*y + 1))"
haftmann@27456
  2092
  by cooper
haftmann@27456
  2093
haftmann@27456
  2094
lemma "~ (ALL(x::int). ((2 dvd x) = (ALL(y::int). x ~= 2*y+1) | (EX(q::int) (u::int) i. 3*i + 2*q - u < 17) --> 0 < x | ((~ 3 dvd x) &(x + 8 = 0))))"
haftmann@27456
  2095
  by cooper
haftmann@27456
  2096
chaieb@23274
  2097
lemma "~ (ALL(i::int). 4 <= i --> (EX x y. 0 <= x & 0 <= y & 3 * x + 5 * y = i))" 
chaieb@23274
  2098
  by cooper
haftmann@27456
  2099
haftmann@27456
  2100
lemma "EX j. ALL (x::int) >= j. EX i j. 5*i + 3*j = x"
haftmann@27456
  2101
  by cooper
chaieb@17378
  2102
chaieb@23274
  2103
theorem "(\<forall>(y::int). 3 dvd y) ==> \<forall>(x::int). b < x --> a \<le> x"
chaieb@23274
  2104
  by cooper
chaieb@17378
  2105
chaieb@23274
  2106
theorem "!! (y::int) (z::int) (n::int). 3 dvd z ==> 2 dvd (y::int) ==>
chaieb@23274
  2107
  (\<exists>(x::int).  2*x =  y) & (\<exists>(k::int). 3*k = z)"
chaieb@23274
  2108
  by cooper
chaieb@17378
  2109
chaieb@23274
  2110
theorem "!! (y::int) (z::int) n. Suc(n::nat) < 6 ==>  3 dvd z ==>
chaieb@23274
  2111
  2 dvd (y::int) ==> (\<exists>(x::int).  2*x =  y) & (\<exists>(k::int). 3*k = z)"
chaieb@23274
  2112
  by cooper
chaieb@17378
  2113
chaieb@23274
  2114
theorem "\<forall>(x::nat). \<exists>(y::nat). (0::nat) \<le> 5 --> y = 5 + x "
chaieb@23274
  2115
  by cooper
chaieb@17378
  2116
chaieb@23274
  2117
theorem "\<forall>(x::nat). \<exists>(y::nat). y = 5 + x | x div 6 + 1= 2"
chaieb@23274
  2118
  by cooper
chaieb@17378
  2119
chaieb@23274
  2120
theorem "\<exists>(x::int). 0 < x"
chaieb@23274
  2121
  by cooper
chaieb@17378
  2122
chaieb@23274
  2123
theorem "\<forall>(x::int) y. x < y --> 2 * x + 1 < 2 * y"
chaieb@23274
  2124
  by cooper
chaieb@23274
  2125
 
chaieb@23274
  2126
theorem "\<forall>(x::int) y. 2 * x + 1 \<noteq> 2 * y"
chaieb@23274
  2127
  by cooper
chaieb@23274
  2128
 
chaieb@23274
  2129
theorem "\<exists>(x::int) y. 0 < x  & 0 \<le> y  & 3 * x - 5 * y = 1"
chaieb@23274
  2130
  by cooper
chaieb@17378
  2131
chaieb@23274
  2132
theorem "~ (\<exists>(x::int) (y::int) (z::int). 4*x + (-6::int)*y = 1)"
chaieb@23274
  2133
  by cooper
chaieb@17378
  2134
chaieb@23274
  2135
theorem "~ (\<exists>(x::int). False)"
chaieb@23274
  2136
  by cooper
chaieb@17378
  2137
chaieb@23274
  2138
theorem "\<forall>(x::int). (2 dvd x) --> (\<exists>(y::int). x = 2*y)"
chaieb@23274
  2139
  by cooper 
chaieb@23274
  2140
chaieb@23274
  2141
theorem "\<forall>(x::int). (2 dvd x) --> (\<exists>(y::int). x = 2*y)"
chaieb@23274
  2142
  by cooper 
chaieb@17378
  2143
chaieb@23274
  2144
theorem "\<forall>(x::int). (2 dvd x) = (\<exists>(y::int). x = 2*y)"
chaieb@23274
  2145
  by cooper 
chaieb@17378
  2146
chaieb@23274
  2147
theorem "\<forall>(x::int). ((2 dvd x) = (\<forall>(y::int). x \<noteq> 2*y + 1))"
chaieb@23274
  2148
  by cooper 
chaieb@17378
  2149
chaieb@23274
  2150
theorem "~ (\<forall>(x::int). 
chaieb@23274
  2151
            ((2 dvd x) = (\<forall>(y::int). x \<noteq> 2*y+1) | 
chaieb@23274
  2152
             (\<exists>(q::int) (u::int) i. 3*i + 2*q - u < 17)
chaieb@23274
  2153
             --> 0 < x | ((~ 3 dvd x) &(x + 8 = 0))))"
chaieb@23274
  2154
  by cooper
chaieb@23274
  2155
 
chaieb@23274
  2156
theorem "~ (\<forall>(i::int). 4 \<le> i --> (\<exists>x y. 0 \<le> x & 0 \<le> y & 3 * x + 5 * y = i))"
chaieb@23274
  2157
  by cooper
chaieb@17378
  2158
chaieb@23274
  2159
theorem "\<forall>(i::int). 8 \<le> i --> (\<exists>x y. 0 \<le> x & 0 \<le> y & 3 * x + 5 * y = i)"
chaieb@23274
  2160
  by cooper
chaieb@17378
  2161
chaieb@23274
  2162
theorem "\<exists>(j::int). \<forall>i. j \<le> i --> (\<exists>x y. 0 \<le> x & 0 \<le> y & 3 * x + 5 * y = i)"
chaieb@23274
  2163
  by cooper
chaieb@17378
  2164
chaieb@23274
  2165
theorem "~ (\<forall>j (i::int). j \<le> i --> (\<exists>x y. 0 \<le> x & 0 \<le> y & 3 * x + 5 * y = i))"
chaieb@23274
  2166
  by cooper
chaieb@17378
  2167
chaieb@23274
  2168
theorem "(\<exists>m::nat. n = 2 * m) --> (n + 1) div 2 = n div 2"
chaieb@23274
  2169
  by cooper
wenzelm@17388
  2170
chaieb@17378
  2171
end