helm/software/matita/contribs/ng_assembly/num/bool_lemmas.ma

   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 (* ********************************************************************** *)
  16 (*                          Progetto FreeScale                            *)
  17 (*                                                                        *)
  18 (*   Sviluppato da: Ing. Cosimo Oliboni, oliboni@cs.unibo.it              *)
  19 (*   Ultima modifica: 05/08/2009                                          *)
  20 (*                                                                        *)
  21 (* ********************************************************************** *)
  22
  23 include "num/bool.ma".
  24
  25 (* ******** *)
  26 (* BOOLEANI *)
  27 (* ******** *)
  28
  29 ndefinition bool_destruct_aux ≝
  30 Πb1,b2:bool.ΠP:Prop.b1 = b2 →
  31  match b1 with
  32   [ true ⇒ match b2 with [ true ⇒ P → P | false ⇒ P ]
  33   | false ⇒ match b2 with [ true ⇒ P | false ⇒ P → P ]
  34   ].
  35
  36 ndefinition bool_destruct : bool_destruct_aux.
  37  #b1; #b2; #P;
  38  nelim b1;
  39  nelim b2;
  40  nnormalize;
  41  #H;
  42  ##[ ##2: napply False_ind;
  43           nchange with (match true with [ true ⇒ False | false ⇒ True]);
  44           nrewrite > H;
  45           nnormalize;
  46           napply I
  47  ##| ##3: napply False_ind;
  48           nchange with (match true with [ true ⇒ False | false ⇒ True]);
  49           nrewrite < H;
  50           nnormalize;
  51           napply I
  52  ##| ##1,4: napply (λx:P.x)
  53  ##]
  54 nqed.
  55
  56 nlemma symmetric_eqbool : symmetricT bool bool eq_bool.
  57  #b1; #b2;
  58  nelim b1;
  59  nelim b2;
  60  nnormalize;
  61  napply refl_eq.
  62 nqed.
  63
  64 nlemma symmetric_andbool : symmetricT bool bool and_bool.
  65  #b1; #b2;
  66  nelim b1;
  67  nelim b2;
  68  nnormalize;
  69  napply refl_eq.
  70 nqed.
  71
  72 nlemma associative_andbool : ∀b1,b2,b3.((b1 ⊗ b2) ⊗ b3) = (b1 ⊗ (b2 ⊗ b3)).
  73  #b1; #b2; #b3;
  74  nelim b1;
  75  nelim b2;
  76  nelim b3;
  77  nnormalize;
  78  napply refl_eq.
  79 nqed.
  80
  81 nlemma symmetric_orbool : symmetricT bool bool or_bool.
  82  #b1; #b2;
  83  nelim b1;
  84  nelim b2;
  85  nnormalize;
  86  napply refl_eq.
  87 nqed.
  88
  89 nlemma associative_orbool : ∀b1,b2,b3.((b1 ⊕ b2) ⊕ b3) = (b1 ⊕ (b2 ⊕ b3)).
  90  #b1; #b2; #b3;
  91  nelim b1;
  92  nelim b2;
  93  nelim b3;
  94  nnormalize;
  95  napply refl_eq.
  96 nqed.
  97
  98 nlemma symmetric_xorbool : symmetricT bool bool xor_bool.
  99  #b1; #b2;
 100  nelim b1;
 101  nelim b2;
 102  nnormalize;
 103  napply refl_eq.
 104 nqed.
 105
 106 nlemma associative_xorbool : ∀b1,b2,b3.((b1 ⊙ b2) ⊙ b3) = (b1 ⊙ (b2 ⊙ b3)).
 107  #b1; #b2; #b3;
 108  nelim b1;
 109  nelim b2;
 110  nelim b3;
 111  nnormalize;
 112  napply refl_eq.
 113 nqed.
 114
 115 nlemma eqbool_to_eq : ∀b1,b2:bool.(eq_bool b1 b2 = true) → (b1 = b2).
 116  #b1; #b2;
 117  ncases b1;
 118  ncases b2;
 119  nnormalize;
 120  ##[ ##1,4: #H; napply refl_eq
 121  ##| ##*: #H; napply (bool_destruct … H)
 122  ##]
 123 nqed.
 124
 125 nlemma eq_to_eqbool : ∀b1,b2.b1 = b2 → eq_bool b1 b2 = true.
 126  #b1; #b2;
 127  ncases b1;
 128  ncases b2;
 129  nnormalize;
 130  ##[ ##1,4: #H; napply refl_eq
 131  ##| ##*: #H; napply (bool_destruct … H)
 132  ##]
 133 nqed.
 134
 135 nlemma decidable_bool : ∀x,y:bool.decidable (x = y).
 136  #x; #y;
 137  nnormalize;
 138  nelim x;
 139  nelim y;
 140  ##[ ##1,4: napply (or2_intro1 (? = ?) (? ≠ ?) …); napply refl_eq
 141  ##| ##*: napply (or2_intro2 (? = ?) (? ≠ ?) …); nnormalize; #H; napply False_ind; napply (bool_destruct … H)
 142  ##]
 143 nqed.
 144
 145 nlemma neqbool_to_neq : ∀b1,b2:bool.(eq_bool b1 b2 = false) → (b1 ≠ b2).
 146  #b1; #b2;
 147  ncases b1;
 148  ncases b2;
 149  nnormalize;
 150  ##[ ##1,4: #H; napply (bool_destruct … H)
 151  ##| ##*: #H; #H1; napply (bool_destruct … H1)
 152  ##]
 153 nqed.
 154
 155 nlemma neq_to_neqbool : ∀b1,b2.b1 ≠ b2 → eq_bool b1 b2 = false.
 156  #b1; #b2;
 157  ncases b1;
 158  ncases b2;
 159  nnormalize;
 160  ##[ ##1,4: #H; nelim (H (refl_eq …))
 161  ##| ##*: #H; napply refl_eq
 162  ##]
 163 nqed.
 164
 165 nlemma andb_true_true_l: ∀b1,b2.(b1 ⊗ b2) = true → b1 = true.
 166  #b1; #b2;
 167  ncases b1;
 168  ncases b2;
 169  nnormalize;
 170  ##[ ##1,2: #H; napply refl_eq
 171  ##| ##*: #H; napply (bool_destruct … H)
 172  ##]
 173 nqed.
 174
 175 nlemma andb_true_true_r: ∀b1,b2.(b1 ⊗ b2) = true → b2 = true.
 176  #b1; #b2;
 177  ncases b1;
 178  ncases b2;
 179  nnormalize;
 180  ##[ ##1,3: #H; napply refl_eq
 181  ##| ##*: #H; napply (bool_destruct … H)
 182  ##]
 183 nqed.
 184
 185 nlemma andb_false2
 186  : ∀b1,b2.(b1 ⊗ b2) = false →
 187    (b1 = false) ∨ (b2 = false).
 188  #b1; #b2;
 189  ncases b1;
 190  ncases b2;
 191  nnormalize;
 192  ##[ ##1: #H; napply (bool_destruct … H)
 193  ##| ##2,4: #H; napply (or2_intro2 … H)
 194  ##| ##3: #H; napply (or2_intro1 … H)
 195  ##]
 196 nqed.
 197
 198 nlemma andb_false3
 199  : ∀b1,b2,b3.(b1 ⊗ b2 ⊗ b3) = false →
 200    Or3 (b1 = false) (b2 = false) (b3 = false).
 201  #b1; #b2; #b3;
 202  ncases b1;
 203  ncases b2;
 204  ncases b3;
 205  nnormalize;
 206  ##[ ##1: #H; napply (bool_destruct … H)
 207  ##| ##5,6,7,8: #H; napply (or3_intro1 … H)
 208  ##| ##2,4: #H; napply (or3_intro3 … H)
 209  ##| ##3: #H; napply (or3_intro2 … H)
 210  ##]
 211 nqed.
 212
 213 nlemma andb_false4
 214  : ∀b1,b2,b3,b4.(b1 ⊗ b2 ⊗ b3 ⊗ b4) = false →
 215    Or4 (b1 = false) (b2 = false) (b3 = false) (b4 = false).
 216  #b1; #b2; #b3; #b4;
 217  ncases b1;
 218  ncases b2;
 219  ncases b3;
 220  ncases b4;
 221  nnormalize;
 222  ##[ ##1: #H; napply (bool_destruct … H)
 223  ##| ##9,10,11,12,13,14,15,16: #H; napply (or4_intro1 … H)
 224  ##| ##5,6,7,8: #H; napply (or4_intro2 … H)
 225  ##| ##3,4: #H; napply (or4_intro3 … H)
 226  ##| ##2: #H; napply (or4_intro4 … H)
 227  ##]
 228 nqed.
 229
 230 nlemma andb_false5
 231  : ∀b1,b2,b3,b4,b5.(b1 ⊗ b2 ⊗ b3 ⊗ b4 ⊗ b5) = false →
 232    Or5 (b1 = false) (b2 = false) (b3 = false) (b4 = false) (b5 = false).
 233  #b1; #b2; #b3; #b4; #b5;
 234  ncases b1;
 235  ncases b2;
 236  ncases b3;
 237  ncases b4;
 238  ncases b5;
 239  nnormalize;
 240  ##[ ##1: #H; napply (bool_destruct … H)
 241  ##| ##17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32: #H; napply (or5_intro1 … H)
 242  ##| ##9,10,11,12,13,14,15,16: #H; napply (or5_intro2 … H)
 243  ##| ##5,6,7,8: #H; napply (or5_intro3 … H)
 244  ##| ##3,4: #H; napply (or5_intro4 … H)
 245  ##| ##2: #H; napply (or5_intro5 … H)
 246  ##]
 247 nqed.
 248
 249 nlemma andb_false2_1 : ∀b.(false ⊗ b) = false.
 250  #b; nnormalize; napply refl_eq. nqed.
 251 nlemma andb_false2_2 : ∀b.(b ⊗ false) = false.
 252  #b; nelim b; nnormalize; napply refl_eq. nqed.
 253
 254 nlemma andb_false3_1 : ∀b1,b2.(false ⊗ b1 ⊗ b2) = false.
 255  #b1; #b2; nnormalize; napply refl_eq. nqed.
 256 nlemma andb_false3_2 : ∀b1,b2.(b1 ⊗ false ⊗ b2) = false.
 257  #b1; #b2; nelim b1; nnormalize; napply refl_eq. nqed.
 258 nlemma andb_false3_3 : ∀b1,b2.(b1 ⊗ b2 ⊗ false) = false.
 259  #b1; #b2; nelim b1; nelim b2; nnormalize; napply refl_eq. nqed.
 260
 261 nlemma andb_false4_1 : ∀b1,b2,b3.(false ⊗ b1 ⊗ b2 ⊗ b3) = false.
 262  #b1; #b2; #b3; nnormalize; napply refl_eq. nqed.
 263 nlemma andb_false4_2 : ∀b1,b2,b3.(b1 ⊗ false ⊗ b2 ⊗ b3) = false.
 264  #b1; #b2; #b3; nelim b1; nnormalize; napply refl_eq. nqed.
 265 nlemma andb_false4_3 : ∀b1,b2,b3.(b1 ⊗ b2 ⊗ false ⊗ b3) = false.
 266  #b1; #b2; #b3; nelim b1; nelim b2; nnormalize; napply refl_eq. nqed.
 267 nlemma andb_false4_4 : ∀b1,b2,b3.(b1 ⊗ b2 ⊗ b3 ⊗ false) = false.
 268  #b1; #b2; #b3; nelim b1; nelim b2; nelim b3; nnormalize; napply refl_eq. nqed.
 269
 270 nlemma andb_false5_1 : ∀b1,b2,b3,b4.(false ⊗ b1 ⊗ b2 ⊗ b3 ⊗ b4) = false.
 271  #b1; #b2; #b3; #b4; nnormalize; napply refl_eq. nqed.
 272 nlemma andb_false5_2 : ∀b1,b2,b3,b4.(b1 ⊗ false ⊗ b2 ⊗ b3 ⊗ b4) = false.
 273  #b1; #b2; #b3; #b4; nelim b1; nnormalize; napply refl_eq. nqed.
 274 nlemma andb_false5_3 : ∀b1,b2,b3,b4.(b1 ⊗ b2 ⊗ false ⊗ b3 ⊗ b4) = false.
 275  #b1; #b2; #b3; #b4; nelim b1; nelim b2; nnormalize; napply refl_eq. nqed.
 276 nlemma andb_false5_4 : ∀b1,b2,b3,b4.(b1 ⊗ b2 ⊗ b3 ⊗ false ⊗ b4) = false.
 277  #b1; #b2; #b3; #b4; nelim b1; nelim b2; nelim b3; nnormalize; napply refl_eq. nqed.
 278 nlemma andb_false5_5 : ∀b1,b2,b3,b4.(b1 ⊗ b2 ⊗ b3 ⊗ b4 ⊗ false) = false.
 279  #b1; #b2; #b3; #b4; nelim b1; nelim b2; nelim b3; nelim b4; nnormalize; napply refl_eq. nqed.
 280
 281 nlemma orb_false_false_l : ∀b1,b2:bool.(b1 ⊕ b2) = false → b1 = false.
 282  #b1; #b2;
 283  ncases b1;
 284  ncases b2;
 285  nnormalize;
 286  ##[ ##4: #H; napply refl_eq
 287  ##| ##*: #H; napply (bool_destruct … H)
 288  ##]
 289 nqed.
 290
 291 nlemma orb_false_false_r : ∀b1,b2:bool.(b1 ⊕ b2) = false → b2 = false.
 292  #b1; #b2;
 293  ncases b1;
 294  ncases b2;
 295  nnormalize;
 296  ##[ ##4: #H; napply refl_eq
 297  ##| ##*: #H; napply (bool_destruct … H)
 298  ##]
 299 nqed.