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