1 (**************************************************************************)
4 (* ||A|| A project by Andrea Asperti *)
6 (* ||I|| Developers: *)
7 (* ||T|| A.Asperti, C.Sacerdoti Coen, *)
8 (* ||A|| E.Tassi, S.Zacchiroli *)
10 (* \ / This file is distributed under the terms of the *)
11 (* v GNU Lesser General Public License Version 2.1 *)
13 (**************************************************************************)
15 set "baseuri" "cic:/matita/datatypes/bool/".
17 include "logic/equality.ma".
18 include "higher_order_defs/functions.ma".
20 inductive bool : Set \def
24 theorem bool_elim: \forall P:bool \to Prop. \forall b:bool.
26 \to (b = false \to P false)
30 [ apply H; reflexivity
31 | apply H1; reflexivity
35 theorem not_eq_true_false : true \neq false.
39 [ true \Rightarrow False
40 | false \Rightarrow True].
41 rewrite > H.simplify.exact I.
44 definition notb : bool \to bool \def
47 [ true \Rightarrow false
48 | false \Rightarrow true ].
50 theorem notb_elim: \forall b:bool.\forall P:bool \to Prop.
52 [ true \Rightarrow P false
53 | false \Rightarrow P true] \to P (notb b).
54 intros 2.elim b.exact H. exact H.
57 theorem notb_notb: \forall b:bool. notb (notb b) = b.
62 theorem injective_notb: injective bool bool notb.
66 rewrite < (notb_notb y).
71 (*CSC: the URI must disappear: there is a bug now *)
72 interpretation "boolean not" 'not x = (cic:/matita/datatypes/bool/notb.con x).
74 definition andb : bool \to bool \to bool\def
78 | false \Rightarrow false ].
80 (*CSC: the URI must disappear: there is a bug now *)
81 interpretation "boolean and" 'and x y = (cic:/matita/datatypes/bool/andb.con x y).
83 theorem andb_elim: \forall b1,b2:bool. \forall P:bool \to Prop.
85 [ true \Rightarrow P b2
86 | false \Rightarrow P false] \to P (b1 \land b2).
87 intros 3.elim b1.exact H. exact H.
90 theorem and_true: \forall a,b:bool.
91 andb a b =true \to a =true \land b= true.
94 [reflexivity|assumption]
96 apply not_eq_true_false.
102 theorem andb_true_true: \forall b1,b2. (b1 \land b2) = true \to b1 = true.
108 theorem andb_true_true_r: \forall b1,b2. (b1 \land b2) = true \to b2 = true.
111 |apply False_ind.apply not_eq_true_false.
112 apply sym_eq.assumption
116 definition orb : bool \to bool \to bool\def
119 [ true \Rightarrow true
120 | false \Rightarrow b2].
122 theorem orb_elim: \forall b1,b2:bool. \forall P:bool \to Prop.
124 [ true \Rightarrow P true
125 | false \Rightarrow P b2] \to P (orb b1 b2).
126 intros 3.elim b1.exact H. exact H.
129 (*CSC: the URI must disappear: there is a bug now *)
130 interpretation "boolean or" 'or x y = (cic:/matita/datatypes/bool/orb.con x y).
132 definition if_then_else : bool \to Prop \to Prop \to Prop \def
133 \lambda b:bool.\lambda P,Q:Prop.
136 | false \Rightarrow Q].
138 (*CSC: missing notation for if_then_else *)
140 theorem bool_to_decidable_eq:
141 \forall b1,b2:bool. decidable (b1=b2).
147 right. exact not_eq_true_false.
149 right. unfold Not. intro.
150 apply not_eq_true_false.
155 theorem P_x_to_P_x_to_eq:
156 \forall A:Set. \forall P: A \to bool.
157 \forall x:A. \forall p1,p2:P x = true. p1 = p2.
159 apply eq_to_eq_to_eq_p_q.
160 exact bool_to_decidable_eq.
164 (* some basic properties of and - or*)
165 theorem andb_sym: \forall A,B:bool.
166 (A \land B) = (B \land A).
174 theorem andb_assoc: \forall A,B,C:bool.
175 (A \land (B \land C)) = ((A \land B) \land C).
184 theorem orb_sym: \forall A,B:bool.
185 (A \lor B) = (B \lor A).
193 theorem true_to_true_to_andb_true: \forall A,B:bool.
194 A = true \to B = true \to (A \land B) = true.