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