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