X-Git-Url: http://matita.cs.unibo.it/gitweb/?a=blobdiff_plain;ds=sidebyside;f=helm%2Fmatita%2Flibrary%2Fnat%2Fminimization.ma;h=72812cb651ecf447983be299aa9e94d00794af64;hb=24320a56c9cc9e92c0a03475e529b4a54f5d4e14;hp=748399fbcc699f20c308228bc8e600e64fc2a4d5;hpb=78044035b4419e569df0d7f6a7f96fa32d21a19d;p=helm.git diff --git a/helm/matita/library/nat/minimization.ma b/helm/matita/library/nat/minimization.ma index 748399fbc..72812cb65 100644 --- a/helm/matita/library/nat/minimization.ma +++ b/helm/matita/library/nat/minimization.ma @@ -72,12 +72,13 @@ intro.simplify.rewrite < H3. rewrite > H2.simplify.apply le_n. qed. + definition max_spec \def \lambda f:nat \to bool.\lambda n: nat. -ex nat (\lambda i:nat. (le i n) \land (f i = true)) \to +\exists i. (le i n) \land (f i = true) \to (f n) = true \land (\forall i. i < n \to (f i = false)). theorem f_max_true : \forall f:nat \to bool. \forall n:nat. -ex nat (\lambda i:nat. (le i n) \land (f i = true)) \to f (max n f) = true. +(\exists i:nat. le i n \land f i = true) \to f (max n f) = true. intros 2. elim n.elim H.elim H1.generalize in match H3. apply le_n_O_elim a H2.intro.simplify.rewrite > H4. @@ -86,7 +87,7 @@ simplify. apply bool_ind (\lambda b:bool. (f (S n1) = b) \to (f ([\lambda b:bool.nat] match b in bool with [ true \Rightarrow (S n1) -| false \Rightarrow (max n1 f)])) = true) ? ? ?. +| false \Rightarrow (max n1 f)])) = true). simplify.intro.assumption. simplify.intro.apply H. elim H1.elim H3.generalize in match H5. @@ -94,7 +95,7 @@ apply le_n_Sm_elim a n1 H4. intros. apply ex_intro nat ? a. split.apply le_S_S_to_le.assumption.assumption. -intros.apply False_ind.apply not_eq_true_false ?. +intros.apply False_ind.apply not_eq_true_false. rewrite < H2.rewrite < H7.rewrite > H6. reflexivity. reflexivity. qed. @@ -106,7 +107,6 @@ elim n.absurd le m O.assumption. cut O < m.apply lt_O_n_elim m Hcut.exact not_le_Sn_O. rewrite < max_O_f f.assumption. generalize in match H1. -(* ?? non posso generalizzare su un goal implicativo ?? *) elim max_S_max f n1. elim H3. absurd m \le S n1.assumption. @@ -152,7 +152,7 @@ simplify.right.split.reflexivity.reflexivity. qed. theorem f_min_aux_true: \forall f:nat \to bool. \forall off,m:nat. -ex nat (\lambda i:nat. (le (m-off) i) \land (le i m) \land (f i = true)) \to +(\exists i. le (m-off) i \land le i m \land f i = true) \to f (min_aux off m f) = true. intros 2. elim off.elim H.elim H1.elim H2. @@ -163,7 +163,7 @@ simplify. apply bool_ind (\lambda b:bool. (f (m-(S n)) = b) \to (f ([\lambda b:bool.nat] match b in bool with [ true \Rightarrow m-(S n) -| false \Rightarrow (min_aux n m f)])) = true) ? ? ?. +| false \Rightarrow (min_aux n m f)])) = true). simplify.intro.assumption. simplify.intro.apply H. elim H1.elim H3.elim H4. @@ -204,7 +204,7 @@ rewrite > min_aux_O_f f n.apply le_n. elim min_aux_S f n1 n. elim H1.rewrite > H3.apply le_n. elim H1.rewrite > H3. -apply trans_le (n-(S n1)) (n-n1) ?. +apply trans_le (n-(S n1)) (n-n1). apply monotonic_le_minus_r. apply le_n_Sn. assumption.