]> matita.cs.unibo.it Git - helm.git/blob - helm/software/matita/library/datatypes/bool.ma
c9a86165a24f1aaea48b235d4f5b140df29a97db
[helm.git] / helm / software / matita / library / datatypes / bool.ma
1 (**************************************************************************)
2 (*       ___                                                                *)
3 (*      ||M||                                                             *)
4 (*      ||A||       A project by Andrea Asperti                           *)
5 (*      ||T||                                                             *)
6 (*      ||I||       Developers:                                           *)
7 (*      ||T||       A.Asperti, C.Sacerdoti Coen,                          *)
8 (*      ||A||       E.Tassi, S.Zacchiroli                                 *)
9 (*      \   /                                                             *)
10 (*       \ /        This file is distributed under the terms of the       *)
11 (*        v         GNU Lesser General Public License Version 2.1         *)
12 (*                                                                        *)
13 (**************************************************************************)
14
15 include "logic/equality.ma".
16 include "higher_order_defs/functions.ma".
17
18 inductive bool : Set \def 
19   | true : bool
20   | false : bool.
21
22 theorem bool_elim: \forall P:bool \to Prop. \forall b:bool.
23   (b = true \to P true)
24   \to (b = false \to P false)
25   \to P b.
26   intros 2 (P b).
27   elim b;
28   [ apply H; reflexivity
29   | apply H1; reflexivity
30   ]
31 qed.
32
33 theorem not_eq_true_false : true \neq false.
34 unfold Not.intro.
35 change with 
36 match true with
37 [ true \Rightarrow False
38 | false \Rightarrow True].
39 rewrite > H.simplify.exact I.
40 qed.
41
42 definition notb : bool \to bool \def
43 \lambda b:bool. 
44  match b with 
45  [ true \Rightarrow false
46  | false \Rightarrow true ].
47  
48 theorem notb_elim: \forall b:bool.\forall P:bool \to Prop.
49 match b with
50 [ true \Rightarrow P false
51 | false \Rightarrow P true] \to P (notb b).
52 intros 2.elim b.exact H. exact H.
53 qed.
54
55 theorem notb_notb: \forall b:bool. notb (notb b) = b.
56 intros.
57 elim b;reflexivity.
58 qed.
59
60 theorem injective_notb: injective bool bool notb.
61 unfold injective.
62 intros.
63 rewrite < notb_notb.
64 rewrite < (notb_notb y).
65 apply eq_f.
66 assumption.
67 qed.
68
69 (*CSC: the URI must disappear: there is a bug now *)
70 interpretation "boolean not" 'not x = (cic:/matita/datatypes/bool/notb.con x).
71
72 definition andb : bool \to bool \to bool\def
73 \lambda b1,b2:bool. 
74  match b1 with 
75  [ true \Rightarrow b2
76  | false \Rightarrow false ].
77
78 (*CSC: the URI must disappear: there is a bug now *)
79 interpretation "boolean and" 'and x y = (cic:/matita/datatypes/bool/andb.con x y).
80
81 theorem andb_elim: \forall b1,b2:bool. \forall P:bool \to Prop.
82 match b1 with
83 [ true \Rightarrow P b2
84 | false \Rightarrow P false] \to P (b1 \land b2).
85 intros 3.elim b1.exact H. exact H.
86 qed.
87
88 theorem and_true: \forall a,b:bool. 
89 andb a b =true \to a =true \land b= true.
90 intro.elim a
91   [split
92     [reflexivity|assumption]
93   |apply False_ind.
94    apply not_eq_true_false.
95    apply sym_eq.
96    assumption
97   ]
98 qed.
99
100 theorem andb_true_true: \forall b1,b2. (b1 \land b2) = true \to b1 = true.
101 intro. elim b1.
102 reflexivity.
103 assumption.
104 qed.
105
106 theorem andb_true_true_r: \forall b1,b2. (b1 \land b2) = true \to b2 = true.
107 intro. elim b1
108   [assumption
109   |apply False_ind.apply not_eq_true_false.
110    apply sym_eq.assumption
111   ]
112 qed.
113
114 definition orb : bool \to bool \to bool\def
115 \lambda b1,b2:bool. 
116  match b1 with 
117  [ true \Rightarrow true
118  | false \Rightarrow b2].
119
120 theorem orb_elim: \forall b1,b2:bool. \forall P:bool \to Prop.
121 match b1 with
122 [ true \Rightarrow P true
123 | false \Rightarrow P b2] \to P (orb b1 b2).
124 intros 3.elim b1.exact H. exact H.
125 qed.
126
127 (*CSC: the URI must disappear: there is a bug now *)
128 interpretation "boolean or" 'or x y = (cic:/matita/datatypes/bool/orb.con x y).
129
130 definition if_then_else : bool \to Prop \to Prop \to Prop \def 
131 \lambda b:bool.\lambda P,Q:Prop.
132 match b with
133 [ true \Rightarrow P
134 | false  \Rightarrow Q].
135
136 (*CSC: missing notation for if_then_else *)
137
138 theorem bool_to_decidable_eq:
139  \forall b1,b2:bool. decidable (b1=b2).
140  intros.
141  unfold decidable.
142  elim b1.
143   elim b2.
144    left. reflexivity.
145    right. exact not_eq_true_false.
146   elim b2.
147    right. unfold Not. intro.
148    apply not_eq_true_false.
149    symmetry. exact H.
150    left. reflexivity.
151 qed.
152
153 theorem P_x_to_P_x_to_eq:
154  \forall A:Set. \forall P: A \to bool.
155   \forall x:A. \forall p1,p2:P x = true. p1 = p2.
156  intros.
157  apply eq_to_eq_to_eq_p_q.
158  exact bool_to_decidable_eq.
159 qed.
160
161
162 (* some basic properties of and - or*)
163 theorem andb_sym: \forall A,B:bool.
164 (A \land B) = (B \land A).
165 intros.
166 elim A;
167   elim B;
168     simplify;
169     reflexivity.
170 qed.
171
172 theorem andb_assoc: \forall A,B,C:bool.
173 (A \land (B \land C)) = ((A \land B) \land C).
174 intros.
175 elim A;
176   elim B;
177     elim C;
178       simplify;
179       reflexivity.
180 qed.
181
182 theorem orb_sym: \forall A,B:bool.
183 (A \lor B) = (B \lor A).
184 intros.
185 elim A;
186   elim B;
187     simplify;
188     reflexivity.
189 qed.
190
191 theorem true_to_true_to_andb_true: \forall A,B:bool.
192 A = true \to B = true \to (A \land B) = true.
193 intros.
194 rewrite > H.
195 rewrite > H1.
196 reflexivity.
197 qed.