]> matita.cs.unibo.it Git - helm.git/blob - matita/matita/contribs/ng_assembly/num/bool_lemmas.ma
update in delayed_updating
[helm.git] / matita / 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.