helm/software/matita/contribs/procedural/Coq/NArith/BinPos.mma

   1 (**************************************************************************)
   2 (*       ___                                                              *)
   3 (*      ||M||                                                             *)
   4 (*      ||A||       A project by Andrea Asperti                           *)
   5 (*      ||T||                                                             *)
   6 (*      ||I||       Developers:                                           *)
   7 (*      ||T||         The HELM team.                                      *)
   8 (*      ||A||         http://helm.cs.unibo.it                             *)
   9 (*      \   /                                                             *)
  10 (*       \ /        This file is distributed under the terms of the       *)
  11 (*        v         GNU General Public License Version 2                  *)
  12 (*                                                                        *)
  13 (**************************************************************************)
  14
  15 (* This file was automatically generated: do not edit *********************)
  16
  17 include "Coq.ma".
  18
  19 (*#**********************************************************************)
  20
  21 (*  v      *   The Coq Proof Assistant  /  The Coq Development Team    *)
  22
  23 (* <O___,, *        INRIA-Rocquencourt  &  LRI-CNRS-Orsay              *)
  24
  25 (*   \VV/  *************************************************************)
  26
  27 (*    //   *      This file is distributed under the terms of the      *)
  28
  29 (*         *       GNU Lesser General Public License Version 2.1       *)
  30
  31 (*#**********************************************************************)
  32
  33 (*i $Id: BinPos.v,v 1.7 2003/12/15 19:48:20 barras Exp $ i*)
  34
  35 (*#*********************************************************************)
  36
  37 (*#* Binary positive numbers *)
  38
  39 (*#* Original development by Pierre Crégut, CNET, Lannion, France *)
  40
  41 inline procedural "cic:/Coq/NArith/BinPos/positive.ind".
  42
  43 (*#* Declare binding key for scope positive_scope *)
  44
  45 (* UNEXPORTED
  46 Delimit Scope positive_scope with positive.
  47 *)
  48
  49 (*#* Automatically open scope positive_scope for type positive, xO and xI *)
  50
  51 (* UNEXPORTED
  52 Bind Scope positive_scope with positive.
  53 *)
  54
  55 (* UNEXPORTED
  56 Arguments Scope xO [positive_scope].
  57 *)
  58
  59 (* UNEXPORTED
  60 Arguments Scope xI [positive_scope].
  61 *)
  62
  63 (*#* Successor *)
  64
  65 inline procedural "cic:/Coq/NArith/BinPos/Psucc.con" as definition.
  66
  67 (*#* Addition *)
  68
  69 inline procedural "cic:/Coq/NArith/BinPos/Pplus.con" as definition.
  70
  71 (* NOTATION
  72 Infix "+" := Pplus : positive_scope.
  73 *)
  74
  75 (* UNEXPORTED
  76 Open Local Scope positive_scope.
  77 *)
  78
  79 (*#* From binary positive numbers to Peano natural numbers *)
  80
  81 inline procedural "cic:/Coq/NArith/BinPos/Pmult_nat.con" as definition.
  82
  83 inline procedural "cic:/Coq/NArith/BinPos/nat_of_P.con" as definition.
  84
  85 (*#* From Peano natural numbers to binary positive numbers *)
  86
  87 inline procedural "cic:/Coq/NArith/BinPos/P_of_succ_nat.con" as definition.
  88
  89 (*#* Operation x -> 2*x-1 *)
  90
  91 inline procedural "cic:/Coq/NArith/BinPos/Pdouble_minus_one.con" as definition.
  92
  93 (*#* Predecessor *)
  94
  95 inline procedural "cic:/Coq/NArith/BinPos/Ppred.con" as definition.
  96
  97 (*#* An auxiliary type for subtraction *)
  98
  99 inline procedural "cic:/Coq/NArith/BinPos/positive_mask.ind".
 100
 101 (*#* Operation x -> 2*x+1 *)
 102
 103 inline procedural "cic:/Coq/NArith/BinPos/Pdouble_plus_one_mask.con" as definition.
 104
 105 (*#* Operation x -> 2*x *)
 106
 107 inline procedural "cic:/Coq/NArith/BinPos/Pdouble_mask.con" as definition.
 108
 109 (*#* Operation x -> 2*x-2 *)
 110
 111 inline procedural "cic:/Coq/NArith/BinPos/Pdouble_minus_two.con" as definition.
 112
 113 (*#* Subtraction of binary positive numbers into a positive numbers mask *)
 114
 115 inline procedural "cic:/Coq/NArith/BinPos/Pminus_mask.con" as definition.
 116
 117 (*#* Subtraction of binary positive numbers x and y, returns 1 if x<=y *)
 118
 119 inline procedural "cic:/Coq/NArith/BinPos/Pminus.con" as definition.
 120
 121 (* NOTATION
 122 Infix "-" := Pminus : positive_scope.
 123 *)
 124
 125 (*#* Multiplication on binary positive numbers *)
 126
 127 inline procedural "cic:/Coq/NArith/BinPos/Pmult.con" as definition.
 128
 129 (* NOTATION
 130 Infix "*" := Pmult : positive_scope.
 131 *)
 132
 133 (*#* Division by 2 rounded below but for 1 *)
 134
 135 inline procedural "cic:/Coq/NArith/BinPos/Pdiv2.con" as definition.
 136
 137 (* NOTATION
 138 Infix "/" := Pdiv2 : positive_scope.
 139 *)
 140
 141 (*#* Comparison on binary positive numbers *)
 142
 143 inline procedural "cic:/Coq/NArith/BinPos/Pcompare.con" as definition.
 144
 145 (* NOTATION
 146 Infix "?=" := Pcompare (at level 70, no associativity) : positive_scope.
 147 *)
 148
 149 (*#*********************************************************************)
 150
 151 (*#* Miscellaneous properties of binary positive numbers *)
 152
 153 inline procedural "cic:/Coq/NArith/BinPos/ZL11.con" as lemma.
 154
 155 (*#*********************************************************************)
 156
 157 (*#* Properties of successor on binary positive numbers *)
 158
 159 (*#* Specification of [xI] in term of [Psucc] and [xO] *)
 160
 161 inline procedural "cic:/Coq/NArith/BinPos/xI_succ_xO.con" as lemma.
 162
 163 inline procedural "cic:/Coq/NArith/BinPos/Psucc_discr.con" as lemma.
 164
 165 (*#* Successor and double *)
 166
 167 inline procedural "cic:/Coq/NArith/BinPos/Psucc_o_double_minus_one_eq_xO.con" as lemma.
 168
 169 inline procedural "cic:/Coq/NArith/BinPos/Pdouble_minus_one_o_succ_eq_xI.con" as lemma.
 170
 171 inline procedural "cic:/Coq/NArith/BinPos/xO_succ_permute.con" as lemma.
 172
 173 inline procedural "cic:/Coq/NArith/BinPos/double_moins_un_xO_discr.con" as lemma.
 174
 175 (*#* Successor and predecessor *)
 176
 177 inline procedural "cic:/Coq/NArith/BinPos/Psucc_not_one.con" as lemma.
 178
 179 inline procedural "cic:/Coq/NArith/BinPos/Ppred_succ.con" as lemma.
 180
 181 inline procedural "cic:/Coq/NArith/BinPos/Psucc_pred.con" as lemma.
 182
 183 (*#* Injectivity of successor *)
 184
 185 inline procedural "cic:/Coq/NArith/BinPos/Psucc_inj.con" as lemma.
 186
 187 (*#*********************************************************************)
 188
 189 (*#* Properties of addition on binary positive numbers *)
 190
 191 (*#* Specification of [Psucc] in term of [Pplus] *)
 192
 193 inline procedural "cic:/Coq/NArith/BinPos/Pplus_one_succ_r.con" as lemma.
 194
 195 inline procedural "cic:/Coq/NArith/BinPos/Pplus_one_succ_l.con" as lemma.
 196
 197 (*#* Specification of [Pplus_carry] *)
 198
 199 inline procedural "cic:/Coq/NArith/BinPos/Pplus_carry_spec.con" as theorem.
 200
 201 (*#* Commutativity *)
 202
 203 inline procedural "cic:/Coq/NArith/BinPos/Pplus_comm.con" as theorem.
 204
 205 (*#* Permutation of [Pplus] and [Psucc] *)
 206
 207 inline procedural "cic:/Coq/NArith/BinPos/Pplus_succ_permute_r.con" as theorem.
 208
 209 inline procedural "cic:/Coq/NArith/BinPos/Pplus_succ_permute_l.con" as theorem.
 210
 211 inline procedural "cic:/Coq/NArith/BinPos/Pplus_carry_pred_eq_plus.con" as theorem.
 212
 213 (*#* No neutral for addition on strictly positive numbers *)
 214
 215 inline procedural "cic:/Coq/NArith/BinPos/Pplus_no_neutral.con" as lemma.
 216
 217 inline procedural "cic:/Coq/NArith/BinPos/Pplus_carry_no_neutral.con" as lemma.
 218
 219 (*#* Simplification *)
 220
 221 inline procedural "cic:/Coq/NArith/BinPos/Pplus_carry_plus.con" as lemma.
 222
 223 inline procedural "cic:/Coq/NArith/BinPos/Pplus_reg_r.con" as lemma.
 224
 225 inline procedural "cic:/Coq/NArith/BinPos/Pplus_reg_l.con" as lemma.
 226
 227 inline procedural "cic:/Coq/NArith/BinPos/Pplus_carry_reg_r.con" as lemma.
 228
 229 inline procedural "cic:/Coq/NArith/BinPos/Pplus_carry_reg_l.con" as lemma.
 230
 231 (*#* Addition on positive is associative *)
 232
 233 inline procedural "cic:/Coq/NArith/BinPos/Pplus_assoc.con" as theorem.
 234
 235 (*#* Commutation of addition with the double of a positive number *)
 236
 237 inline procedural "cic:/Coq/NArith/BinPos/Pplus_xI_double_minus_one.con" as lemma.
 238
 239 inline procedural "cic:/Coq/NArith/BinPos/Pplus_xO_double_minus_one.con" as lemma.
 240
 241 (*#* Misc *)
 242
 243 inline procedural "cic:/Coq/NArith/BinPos/Pplus_diag.con" as lemma.
 244
 245 (*#*********************************************************************)
 246
 247 (*#* Peano induction on binary positive positive numbers *)
 248
 249 inline procedural "cic:/Coq/NArith/BinPos/plus_iter.con" as definition.
 250
 251 inline procedural "cic:/Coq/NArith/BinPos/plus_iter_eq_plus.con" as lemma.
 252
 253 inline procedural "cic:/Coq/NArith/BinPos/plus_iter_xO.con" as lemma.
 254
 255 inline procedural "cic:/Coq/NArith/BinPos/plus_iter_xI.con" as lemma.
 256
 257 inline procedural "cic:/Coq/NArith/BinPos/iterate_add.con" as lemma.
 258
 259 (*#* Peano induction *)
 260
 261 inline procedural "cic:/Coq/NArith/BinPos/Pind.con" as theorem.
 262
 263 (*#* Peano recursion *)
 264
 265 inline procedural "cic:/Coq/NArith/BinPos/Prec.con" as definition.
 266
 267 (*#* Peano case analysis *)
 268
 269 inline procedural "cic:/Coq/NArith/BinPos/Pcase.con" as theorem.
 270
 271 (*
 272 Check
 273   (let fact := Prec positive xH (fun p r => Psucc p * r) in
 274    let seven := xI (xI xH) in
 275    let five_thousand_forty :=
 276      xO (xO (xO (xO (xI (xI (xO (xI (xI (xI (xO (xO xH))))))))))) in
 277    refl_equal _:fact seven = five_thousand_forty).
 278 *)
 279
 280 (*#*********************************************************************)
 281
 282 (*#* Properties of multiplication on binary positive numbers *)
 283
 284 (*#* One is right neutral for multiplication *)
 285
 286 inline procedural "cic:/Coq/NArith/BinPos/Pmult_1_r.con" as lemma.
 287
 288 (*#* Right reduction properties for multiplication *)
 289
 290 inline procedural "cic:/Coq/NArith/BinPos/Pmult_xO_permute_r.con" as lemma.
 291
 292 inline procedural "cic:/Coq/NArith/BinPos/Pmult_xI_permute_r.con" as lemma.
 293
 294 (*#* Commutativity of multiplication *)
 295
 296 inline procedural "cic:/Coq/NArith/BinPos/Pmult_comm.con" as theorem.
 297
 298 (*#* Distributivity of multiplication over addition *)
 299
 300 inline procedural "cic:/Coq/NArith/BinPos/Pmult_plus_distr_l.con" as theorem.
 301
 302 inline procedural "cic:/Coq/NArith/BinPos/Pmult_plus_distr_r.con" as theorem.
 303
 304 (*#* Associativity of multiplication *)
 305
 306 inline procedural "cic:/Coq/NArith/BinPos/Pmult_assoc.con" as theorem.
 307
 308 (*#* Parity properties of multiplication *)
 309
 310 inline procedural "cic:/Coq/NArith/BinPos/Pmult_xI_mult_xO_discr.con" as lemma.
 311
 312 inline procedural "cic:/Coq/NArith/BinPos/Pmult_xO_discr.con" as lemma.
 313
 314 (*#* Simplification properties of multiplication *)
 315
 316 inline procedural "cic:/Coq/NArith/BinPos/Pmult_reg_r.con" as theorem.
 317
 318 inline procedural "cic:/Coq/NArith/BinPos/Pmult_reg_l.con" as theorem.
 319
 320 (*#* Inversion of multiplication *)
 321
 322 inline procedural "cic:/Coq/NArith/BinPos/Pmult_1_inversion_l.con" as lemma.
 323
 324 (*#*********************************************************************)
 325
 326 (*#* Properties of comparison on binary positive numbers *)
 327
 328 inline procedural "cic:/Coq/NArith/BinPos/Pcompare_not_Eq.con" as theorem.
 329
 330 inline procedural "cic:/Coq/NArith/BinPos/Pcompare_Eq_eq.con" as theorem.
 331
 332 inline procedural "cic:/Coq/NArith/BinPos/Pcompare_Gt_Lt.con" as lemma.
 333
 334 inline procedural "cic:/Coq/NArith/BinPos/Pcompare_Lt_Gt.con" as lemma.
 335
 336 inline procedural "cic:/Coq/NArith/BinPos/Pcompare_Lt_Lt.con" as lemma.
 337
 338 inline procedural "cic:/Coq/NArith/BinPos/Pcompare_Gt_Gt.con" as lemma.
 339
 340 inline procedural "cic:/Coq/NArith/BinPos/Dcompare.con" as lemma.
 341
 342 (* UNEXPORTED
 343 Ltac ElimPcompare c1 c2 :=
 344   elim (Dcompare ((c1 ?= c2) Eq));
 345    [ idtac | let x := fresh "H" in
 346              (intro x; case x; clear x) ].
 347 *)
 348
 349 inline procedural "cic:/Coq/NArith/BinPos/Pcompare_refl.con" as theorem.
 350
 351 inline procedural "cic:/Coq/NArith/BinPos/Pcompare_antisym.con" as lemma.
 352
 353 inline procedural "cic:/Coq/NArith/BinPos/ZC1.con" as lemma.
 354
 355 inline procedural "cic:/Coq/NArith/BinPos/ZC2.con" as lemma.
 356
 357 inline procedural "cic:/Coq/NArith/BinPos/ZC3.con" as lemma.
 358
 359 inline procedural "cic:/Coq/NArith/BinPos/ZC4.con" as lemma.
 360
 361 (*#*********************************************************************)
 362
 363 (*#* Properties of subtraction on binary positive numbers *)
 364
 365 inline procedural "cic:/Coq/NArith/BinPos/double_eq_zero_inversion.con" as lemma.
 366
 367 inline procedural "cic:/Coq/NArith/BinPos/double_plus_one_zero_discr.con" as lemma.
 368
 369 inline procedural "cic:/Coq/NArith/BinPos/double_plus_one_eq_one_inversion.con" as lemma.
 370
 371 inline procedural "cic:/Coq/NArith/BinPos/double_eq_one_discr.con" as lemma.
 372
 373 inline procedural "cic:/Coq/NArith/BinPos/Pminus_mask_diag.con" as theorem.
 374
 375 inline procedural "cic:/Coq/NArith/BinPos/ZL10.con" as lemma.
 376
 377 (*#* Properties of subtraction valid only for x>y *)
 378
 379 inline procedural "cic:/Coq/NArith/BinPos/Pminus_mask_Gt.con" as lemma.
 380
 381 inline procedural "cic:/Coq/NArith/BinPos/Pplus_minus.con" as theorem.
 382