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