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