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.