From d07f4b413bf2f8fabe5e57869e3c6f35b3c4e262 Mon Sep 17 00:00:00 2001 From: matitaweb Date: Tue, 6 Mar 2012 18:24:11 +0000 Subject: [PATCH] commit by user andrea --- weblib/tutorial/chapter5.ma | 174 ++++++++++++++++++------------------ 1 file changed, 87 insertions(+), 87 deletions(-) diff --git a/weblib/tutorial/chapter5.ma b/weblib/tutorial/chapter5.ma index 8d4fc9f6c..014cb611f 100644 --- a/weblib/tutorial/chapter5.ma +++ b/weblib/tutorial/chapter5.ma @@ -11,10 +11,10 @@ include "tutorial/chapter4.ma". between an element x and a list l. Its definition is a straightforward recursion on l.*) -let rec memb (S:DeqSet) (x:S) (l: listspan class="error" title="Parse error: RPAREN expected after [term] (in [arg])"/span S) on l ≝ +let rec memb (S:a href="cic:/matita/tutorial/chapter4/DeqSet.ind(1,0,0)"DeqSet/a) (x:S) (l: a href="cic:/matita/basics/list/list.ind(1,0,1)"list/aspan class="error" title="Parse error: RPAREN expected after [term] (in [arg])"/span S) on l ≝ match l with - [ nil ⇒ false - | cons a tl ⇒ (x == a) ∨ memb S x tl + [ nil ⇒ a href="cic:/matita/basics/bool/bool.con(0,2,0)"false/a + | cons a tl ⇒ (x a title="eqb" href="cic:/fakeuri.def(1)"=/a= a) a title="boolean or" href="cic:/fakeuri.def(1)"∨/a memb S x tl ]span class="error" title="Parse error: NUMBER '1' or [term] or [sym=] expected after [sym=] (in [term])"/spanspan class="error" title="No choices for ID nil"/span. notation < "\memb x l" non associative with precedence 90 for @{'memb $x $l}. @@ -35,71 +35,71 @@ interpretation "boolean membership" 'memb a l = (memb ? a l). (op a b) is a member of (compose op l1 l2) *) -lemma memb_hd: ∀S,a,l. memb S a (a::l) = true. -#S #a #l normalize >(proj2 … (eqb_true S …) (refl S a)) // +lemma memb_hd: ∀S,a,l. a href="cic:/matita/tutorial/chapter5/memb.fix(0,2,4)"memb/a S a (aa title="cons" href="cic:/fakeuri.def(1)":/a:l) a title="leibnitz's equality" href="cic:/fakeuri.def(1)"=/a a href="cic:/matita/basics/bool/bool.con(0,1,0)"true/a. +#S #a #l normalize >(a href="cic:/matita/basics/logic/proj2.def(2)"proj2/a … (a href="cic:/matita/tutorial/chapter4/eqb_true.fix(0,0,4)"eqb_true/a S …) (a href="cic:/matita/basics/logic/eq.con(0,1,2)"refl/a S a)) // qed. lemma memb_cons: ∀S,a,b,l. - memb S a l = true → membspan class="error" title="Parse error: SYMBOL '.' expected after [grafite_ncommand] (in [executable])"/span S a (b::l) = true. -#S #a #b #l normalize cases (a==b) normalize // + a href="cic:/matita/tutorial/chapter5/memb.fix(0,2,4)"memb/a S a l a title="leibnitz's equality" href="cic:/fakeuri.def(1)"=/a a href="cic:/matita/basics/bool/bool.con(0,1,0)"true/a → a href="cic:/matita/tutorial/chapter5/memb.fix(0,2,4)"memb/aspan class="error" title="Parse error: SYMBOL '.' expected after [grafite_ncommand] (in [executable])"/span S a (ba title="cons" href="cic:/fakeuri.def(1)":/a:l) a title="leibnitz's equality" href="cic:/fakeuri.def(1)"=/a a href="cic:/matita/basics/bool/bool.con(0,1,0)"true/a. +#S #a #b #l normalize cases (aa title="eqb" href="cic:/fakeuri.def(1)"=/a=b) normalize // qed. -lemma memb_single: ∀S,a,x. memb S a (x::[]) = true → a = x. -#S #a #x normalize cases (true_or_false … (a==x)) #H - [#_ >(\P H) // |>H normalize #abs @False_ind /span class="autotactic"2span class="autotrace" trace absurd/span/span/] +lemma memb_single: ∀S,a,x. a href="cic:/matita/tutorial/chapter5/memb.fix(0,2,4)"memb/a S a (xa title="cons" href="cic:/fakeuri.def(1)":/a:a title="nil" href="cic:/fakeuri.def(1)"[/a]) a title="leibnitz's equality" href="cic:/fakeuri.def(1)"=/a a href="cic:/matita/basics/bool/bool.con(0,1,0)"true/a → a a title="leibnitz's equality" href="cic:/fakeuri.def(1)"=/a x. +#S #a #x normalize cases (a href="cic:/matita/basics/bool/true_or_false.def(1)"true_or_false/a … (aa title="eqb" href="cic:/fakeuri.def(1)"=/a=x)) #H + [#_ >(\P H) // |>H normalize #abs @a href="cic:/matita/basics/logic/False_ind.fix(0,1,1)"False_ind/a /span class="autotactic"2span class="autotrace" trace a href="cic:/matita/basics/logic/absurd.def(2)"absurd/a/span/span/] qed. lemma memb_append: ∀S,a,l1,l2. -memb S a (l1@span class="error" title="Parse error: [term level 46] expected after [sym@] (in [term])"/spanl2) = true → memb S a l1= true ∨ memb S a l2 = true. +a href="cic:/matita/tutorial/chapter5/memb.fix(0,2,4)"memb/a S a (l1a title="append" href="cic:/fakeuri.def(1)"@/aspan class="error" title="Parse error: [term level 46] expected after [sym@] (in [term])"/spanl2) a title="leibnitz's equality" href="cic:/fakeuri.def(1)"=/a a href="cic:/matita/basics/bool/bool.con(0,1,0)"true/a → a href="cic:/matita/tutorial/chapter5/memb.fix(0,2,4)"memb/a S a l1a title="leibnitz's equality" href="cic:/fakeuri.def(1)"=/a a href="cic:/matita/basics/bool/bool.con(0,1,0)"true/a a title="logical or" href="cic:/fakeuri.def(1)"∨/a a href="cic:/matita/tutorial/chapter5/memb.fix(0,2,4)"memb/a S a l2 a title="leibnitz's equality" href="cic:/fakeuri.def(1)"=/a a href="cic:/matita/basics/bool/bool.con(0,1,0)"true/a. #S #a #l1span class="error" title="Parse error: illegal begin of statement"/spanspan class="error" title="Parse error: illegal begin of statement"/span elim l1 normalize [#l2 #H %2 //] -#b #tl #Hind #l2 cases (a==b) normalize /span class="autotactic"2span class="autotrace" trace orb_true_l/span/span/ +#b #tl #Hind #l2 cases (aa title="eqb" href="cic:/fakeuri.def(1)"=/a=b) normalize /span class="autotactic"2span class="autotrace" trace a href="cic:/matita/basics/bool/orb_true_l.def(2)"orb_true_l/a/span/span/ qed. lemma memb_append_l1: ∀S,a,l1,l2. - memb S a l1= true → memb S a (l1@l2) = true. + a href="cic:/matita/tutorial/chapter5/memb.fix(0,2,4)"memb/a S a l1a title="leibnitz's equality" href="cic:/fakeuri.def(1)"=/a a href="cic:/matita/basics/bool/bool.con(0,1,0)"true/a → a href="cic:/matita/tutorial/chapter5/memb.fix(0,2,4)"memb/a S a (l1a title="append" href="cic:/fakeuri.def(1)"@/al2) a title="leibnitz's equality" href="cic:/fakeuri.def(1)"=/a a href="cic:/matita/basics/bool/bool.con(0,1,0)"true/a. #S #a #l1 elim l1 normalize - [normalize #le #abs @False_ind /span class="autotactic"2span class="autotrace" trace absurd/span/span/ - |#b #tl #Hind #l2 cases (a==b) normalize /span class="autotactic"2span class="autotrace" trace /span/span/ + [normalize #le #abs @a href="cic:/matita/basics/logic/False_ind.fix(0,1,1)"False_ind/a /span class="autotactic"2span class="autotrace" trace a href="cic:/matita/basics/logic/absurd.def(2)"absurd/a/span/span/ + |#b #tl #Hind #l2 cases (aa title="eqb" href="cic:/fakeuri.def(1)"=/a=b) normalize /span class="autotactic"2span class="autotrace" trace /span/span/ ] qed. lemma memb_append_l2: ∀S,a,l1,l2. - memb S a l2= true → memb S a (l1@l2) = true. + a href="cic:/matita/tutorial/chapter5/memb.fix(0,2,4)"memb/a S a l2a title="leibnitz's equality" href="cic:/fakeuri.def(1)"=/a a href="cic:/matita/basics/bool/bool.con(0,1,0)"true/a → a href="cic:/matita/tutorial/chapter5/memb.fix(0,2,4)"memb/a S a (l1a title="append" href="cic:/fakeuri.def(1)"@/al2) a title="leibnitz's equality" href="cic:/fakeuri.def(1)"=/a a href="cic:/matita/basics/bool/bool.con(0,1,0)"true/a. #S #a #l1 elim l1 normalize // -#b #tl #Hind #l2 cases (a==b) normalize /span class="autotactic"2span class="autotrace" trace /span/span/ +#b #tl #Hind #l2 cases (aa title="eqb" href="cic:/fakeuri.def(1)"=/a=b) normalize /span class="autotactic"2span class="autotrace" trace /span/span/ qed. -lemma memb_exists: ∀S,a,l.memb S a l = truespan class="error" title="Parse error: SYMBOL '.' expected after [grafite_ncommand] (in [executable])"/span → ∃l1,l2.l=l1@(a::l2). -#S #a #l elim l [normalize #abs @False_ind /span class="autotactic"2span class="autotrace" trace absurd/span/span/] -#b #tl #Hind #H cases (orb_true_l … H) - [#eqba @(ex_intro … (nil S)) @(ex_intro … tl) >(\P eqba) // +lemma memb_exists: ∀S,a,l.a href="cic:/matita/tutorial/chapter5/memb.fix(0,2,4)"memb/a S a l a title="leibnitz's equality" href="cic:/fakeuri.def(1)"=/a a href="cic:/matita/basics/bool/bool.con(0,1,0)"true/aspan class="error" title="Parse error: SYMBOL '.' expected after [grafite_ncommand] (in [executable])"/span → a title="exists" href="cic:/fakeuri.def(1)"∃/al1,l2.la title="leibnitz's equality" href="cic:/fakeuri.def(1)"=/al1a title="append" href="cic:/fakeuri.def(1)"@/a(aa title="cons" href="cic:/fakeuri.def(1)":/a:l2). +#S #a #l elim l [normalize #abs @a href="cic:/matita/basics/logic/False_ind.fix(0,1,1)"False_ind/a /span class="autotactic"2span class="autotrace" trace a href="cic:/matita/basics/logic/absurd.def(2)"absurd/a/span/span/] +#b #tl #Hind #H cases (a href="cic:/matita/basics/bool/orb_true_l.def(2)"orb_true_l/a … H) + [#eqba @(a href="cic:/matita/basics/logic/ex.con(0,1,2)"ex_intro/a … (a href="cic:/matita/basics/list/list.con(0,1,1)"nil/a S)) @(a href="cic:/matita/basics/logic/ex.con(0,1,2)"ex_intro/a … tl) >(\P eqba) // |#mem_tl cases (Hind mem_tl) #l1 * #l2 #eqtl - @(ex_intro … (b::l1)) @(ex_intro … l2) >eqtl // + @(a href="cic:/matita/basics/logic/ex.con(0,1,2)"ex_intro/a … (ba title="cons" href="cic:/fakeuri.def(1)":/a:l1)) @(a href="cic:/matita/basics/logic/ex.con(0,1,2)"ex_intro/a … l2) >eqtl // ] qed. lemma not_memb_to_not_eq: ∀S,a,b,l. - memb S a l = false → memb S b l = true → a==b = false. -#S #a #b #l cases (true_or_false (a==b)) // -#eqab >(\P eqab) #H >H #abs @False_ind /span class="autotactic"2span class="autotrace" trace absurd/span/span/ + a href="cic:/matita/tutorial/chapter5/memb.fix(0,2,4)"memb/a S a l a title="leibnitz's equality" href="cic:/fakeuri.def(1)"=/a a href="cic:/matita/basics/bool/bool.con(0,2,0)"false/a → a href="cic:/matita/tutorial/chapter5/memb.fix(0,2,4)"memb/a S b l a title="leibnitz's equality" href="cic:/fakeuri.def(1)"=/a a href="cic:/matita/basics/bool/bool.con(0,1,0)"true/a → aa title="eqb" href="cic:/fakeuri.def(1)"=/a=b a title="leibnitz's equality" href="cic:/fakeuri.def(1)"=/a a href="cic:/matita/basics/bool/bool.con(0,2,0)"false/a. +#S #a #b #l cases (a href="cic:/matita/basics/bool/true_or_false.def(1)"true_or_false/a (aa title="eqb" href="cic:/fakeuri.def(1)"=/a=b)) // +#eqab >(\P eqab) #H >H #abs @a href="cic:/matita/basics/logic/False_ind.fix(0,1,1)"False_ind/a /span class="autotactic"2span class="autotrace" trace a href="cic:/matita/basics/logic/absurd.def(2)"absurd/a/span/span/ qed. -lemma memb_map: ∀S1,S2,f,a,l. memb S1 a l= true → - memb S2 (f a) (map … f l) = true. +lemma memb_map: ∀S1,S2,f,a,l. a href="cic:/matita/tutorial/chapter5/memb.fix(0,2,4)"memb/a S1 a la title="leibnitz's equality" href="cic:/fakeuri.def(1)"=/a a href="cic:/matita/basics/bool/bool.con(0,1,0)"true/a → + a href="cic:/matita/tutorial/chapter5/memb.fix(0,2,4)"memb/a S2 (f a) (a href="cic:/matita/basics/list/map.fix(0,3,1)"map/a … f l) a title="leibnitz's equality" href="cic:/fakeuri.def(1)"=/a a href="cic:/matita/basics/bool/bool.con(0,1,0)"true/a. #S1 #S2 #f #a #l elim l normalize [//] -#x #tl #memba cases (true_or_false (a==x)) - [#eqx >eqx >(\P eqx) >(\b (refl … (f x))) normalize // - |#eqx >eqx cases (f a==f x) normalize /span class="autotactic"2span class="autotrace" trace /span/span/ +#x #tl #memba cases (a href="cic:/matita/basics/bool/true_or_false.def(1)"true_or_false/a (aa title="eqb" href="cic:/fakeuri.def(1)"=/a=x)) + [#eqx >eqx >(\P eqx) >(\b (a href="cic:/matita/basics/logic/eq.con(0,1,2)"refl/a … (f x))) normalize // + |#eqx >eqx cases (f aa title="eqb" href="cic:/fakeuri.def(1)"=/a=f x) normalize /span class="autotactic"2span class="autotrace" trace /span/span/ ] qed. lemma memb_compose: ∀S1,S2,S3,op,a1,a2,l1,l2. - memb S1 a1 l1 = true → memb S2 a2 l2 = true → - memb S3 (op a1 a2) (compose S1 S2 S3 op l1 l2) = true. + a href="cic:/matita/tutorial/chapter5/memb.fix(0,2,4)"memb/a S1 a1 l1 a title="leibnitz's equality" href="cic:/fakeuri.def(1)"=/a a href="cic:/matita/basics/bool/bool.con(0,1,0)"true/a → a href="cic:/matita/tutorial/chapter5/memb.fix(0,2,4)"memb/a S2 a2 l2 a title="leibnitz's equality" href="cic:/fakeuri.def(1)"=/a a href="cic:/matita/basics/bool/bool.con(0,1,0)"true/a → + a href="cic:/matita/tutorial/chapter5/memb.fix(0,2,4)"memb/a S3 (op a1 a2) (a href="cic:/matita/basics/list/compose.def(2)"compose/a S1 S2 S3 op l1 l2) a title="leibnitz's equality" href="cic:/fakeuri.def(1)"=/a a href="cic:/matita/basics/bool/bool.con(0,1,0)"true/a. #S1 #S2 #S3 #op #a1 #a2 #l1 elim l1 [normalize //] -#x #tl #Hind #l2 #memba1 #memba2 cases (orb_true_l … memba1) - [#eqa1 >(\P eqa1) @memb_append_l1 @memb_map // - |#membtl @memb_append_l2 @Hind // +#x #tl #Hind #l2 #memba1 #memba2 cases (a href="cic:/matita/basics/bool/orb_true_l.def(2)"orb_true_l/a … memba1) + [#eqa1 >(\P eqa1) @a href="cic:/matita/tutorial/chapter5/memb_append_l1.def(5)"memb_append_l1/a @a href="cic:/matita/tutorial/chapter5/memb_map.def(5)"memb_map/a // + |#membtl @a href="cic:/matita/tutorial/chapter5/memb_append_l2.def(5)"memb_append_l2/a @Hind // ] qed. @@ -108,84 +108,84 @@ to avoid duplications of elements. The following uniqueb check this property. *) (*************** unicity test *****************) -let rec uniqueb (S:DeqSet) l on l : bool ≝ +let rec uniqueb (S:a href="cic:/matita/tutorial/chapter4/DeqSet.ind(1,0,0)"DeqSet/a) l on l : a href="cic:/matita/basics/bool/bool.ind(1,0,0)"bool/a ≝ match l with - [ nil ⇒ true - | cons a tl ⇒ notb (memb S a tl) ∧ uniqueb S tl + [ nil ⇒ a href="cic:/matita/basics/bool/bool.con(0,1,0)"true/a + | cons a tl ⇒ a href="cic:/matita/basics/bool/notb.def(1)"notb/a (a href="cic:/matita/tutorial/chapter5/memb.fix(0,2,4)"memb/a S a tl) a title="boolean and" href="cic:/fakeuri.def(1)"∧/a uniqueb S tl ]. (* unique_append l1 l2 add l1 in fornt of l2, but preserving unicity *) -let rec unique_append (S:DeqSet) (l1,l2: list S) on l1 ≝ +let rec unique_append (S:a href="cic:/matita/tutorial/chapter4/DeqSet.ind(1,0,0)"DeqSet/a) (l1,l2: a href="cic:/matita/basics/list/list.ind(1,0,1)"list/a S) on l1 ≝ match l1 with [ nil ⇒ l2 | cons a tl ⇒ let r ≝ unique_append S tl l2 in - if memb S a r then r else a::r + if a href="cic:/matita/tutorial/chapter5/memb.fix(0,2,4)"memb/a S a r then r else aa title="cons" href="cic:/fakeuri.def(1)":/a:r ]. -axiom unique_append_elim: ∀S:DeqSet.∀P: S → Prop.∀l1,l2. -(∀x. memb S x l1 =span class="error" title="Parse error: NUMBER '1' or [term] or [sym=] expected after [sym=] (in [term])"/span true → P x) → (∀x. memb S x l2 = true → P x) → -∀x. memb S x (unique_append S l1 l2) = true → P x. +axiom unique_append_elim: ∀S:a href="cic:/matita/tutorial/chapter4/DeqSet.ind(1,0,0)"DeqSet/a.∀P: S → Prop.∀l1,l2. +(∀x. a href="cic:/matita/tutorial/chapter5/memb.fix(0,2,4)"memb/a S x l1 a title="leibnitz's equality" href="cic:/fakeuri.def(1)"=/aspan class="error" title="Parse error: NUMBER '1' or [term] or [sym=] expected after [sym=] (in [term])"/span a href="cic:/matita/basics/bool/bool.con(0,1,0)"true/a → P x) → (∀x. a href="cic:/matita/tutorial/chapter5/memb.fix(0,2,4)"memb/a S x l2 a title="leibnitz's equality" href="cic:/fakeuri.def(1)"=/a a href="cic:/matita/basics/bool/bool.con(0,1,0)"true/a → P x) → +∀x. a href="cic:/matita/tutorial/chapter5/memb.fix(0,2,4)"memb/a S x (a href="cic:/matita/tutorial/chapter5/unique_append.fix(0,1,5)"unique_append/a S l1 l2) a title="leibnitz's equality" href="cic:/fakeuri.def(1)"=/a a href="cic:/matita/basics/bool/bool.con(0,1,0)"true/a → P x. -lemma unique_append_unique: ∀S,l1,l2. uniqueb S l2 = true → - uniqueb S (unique_append S l1 l2) = true. +lemma unique_append_unique: ∀S,l1,l2. a href="cic:/matita/tutorial/chapter5/uniqueb.fix(0,1,5)"uniqueb/a S l2 a title="leibnitz's equality" href="cic:/fakeuri.def(1)"=/a a href="cic:/matita/basics/bool/bool.con(0,1,0)"true/a → + a href="cic:/matita/tutorial/chapter5/uniqueb.fix(0,1,5)"uniqueb/a S (a href="cic:/matita/tutorial/chapter5/unique_append.fix(0,1,5)"unique_append/a S l1 l2) a title="leibnitz's equality" href="cic:/fakeuri.def(1)"=/a a href="cic:/matita/basics/bool/bool.con(0,1,0)"true/a. #S #l1 elim l1 normalize // #a #tl #Hind #l2 #uniquel2 -cases (true_or_false … (memb S a (unique_append S tl l2))) +cases (a href="cic:/matita/basics/bool/true_or_false.def(1)"true_or_false/a … (a href="cic:/matita/tutorial/chapter5/memb.fix(0,2,4)"memb/a S a (a href="cic:/matita/tutorial/chapter5/unique_append.fix(0,1,5)"unique_append/a S tl l2))) #H >H normalize [@Hind //] >H normalize @Hind // qed. (******************* sublist *******************) definition sublist ≝ - λS,l1,l2.∀a. memb S a l1 = true → memb S a l2 = true. + λS,l1,l2.∀a. a href="cic:/matita/tutorial/chapter5/memb.fix(0,2,4)"memb/a S a l1 a title="leibnitz's equality" href="cic:/fakeuri.def(1)"=/a a href="cic:/matita/basics/bool/bool.con(0,1,0)"true/a → a href="cic:/matita/tutorial/chapter5/memb.fix(0,2,4)"memb/a S a l2 a title="leibnitz's equality" href="cic:/fakeuri.def(1)"=/a a href="cic:/matita/basics/bool/bool.con(0,1,0)"true/a. lemma sublist_length: ∀S,l1,l2. - uniqueb S l1 = true → sublist S l1 l2 → |l1| ≤ |l2|. + a href="cic:/matita/tutorial/chapter5/uniqueb.fix(0,1,5)"uniqueb/a S l1 a title="leibnitz's equality" href="cic:/fakeuri.def(1)"=/a a href="cic:/matita/basics/bool/bool.con(0,1,0)"true/a → a href="cic:/matita/tutorial/chapter5/sublist.def(5)"sublist/a S l1 l2 → a title="norm" href="cic:/fakeuri.def(1)"|/al1| a title="natural 'less or equal to'" href="cic:/fakeuri.def(1)"≤/a a title="norm" href="cic:/fakeuri.def(1)"|/al2|. #S #l1 elim l1 // #a #tl #Hind #l2 #unique #sub -cut (∃l3,l4.l2=l3@(a::l4)) [@memb_exists @sub //] -* #l3 * #l4 #eql2 >eql2 >length_append normalize -applyS le_S_S eql2 >a href="cic:/matita/basics/list/length_append.def(2)"length_append/a normalize +applyS a href="cic:/matita/arithmetics/nat/le_S_S.def(2)"le_S_S/a <a href="cic:/matita/basics/list/length_append.def(2)"length_append/a @Hind [@(a href="cic:/matita/basics/bool/andb_true_r.def(4)"andb_true_r/a … unique)] >eql2 in sub; #sub #x #membx -cases (memb_append … (sub x (orb_true_r2 … membx))) - [#membxl3 @memb_append_l1 // - |#membxal4 cases (orb_true_l … membxal4) - [#eqxa @False_ind lapply (andb_true_l … unique) - <(\P eqxa) >membx normalize /span class="autotactic"2span class="autotrace" trace absurd/span/span/ |#membxl4 @memb_append_l2 // +cases (a href="cic:/matita/tutorial/chapter5/memb_append.def(5)"memb_append/a … (sub x (a href="cic:/matita/basics/bool/orb_true_r2.def(3)"orb_true_r2/a … membx))) + [#membxl3 @a href="cic:/matita/tutorial/chapter5/memb_append_l1.def(5)"memb_append_l1/a // + |#membxal4 cases (a href="cic:/matita/basics/bool/orb_true_l.def(2)"orb_true_l/a … membxal4) + [#eqxa @a href="cic:/matita/basics/logic/False_ind.fix(0,1,1)"False_ind/a lapply (a href="cic:/matita/basics/bool/andb_true_l.def(4)"andb_true_l/a … unique) + <(\P eqxa) >membx normalize /span class="autotactic"2span class="autotrace" trace a href="cic:/matita/basics/logic/absurd.def(2)"absurd/a/span/span/ |#membxl4 @a href="cic:/matita/tutorial/chapter5/memb_append_l2.def(5)"memb_append_l2/a // ] ] qed. lemma sublist_unique_append_l1: - ∀S,l1,l2. sublist S l1 (unique_append S l1 l2). -#S #l1 elim l1 normalize [#l2 #S #abs @False_ind /span class="autotactic"2span class="autotrace" trace absurd/span/span/] + ∀S,l1,l2. a href="cic:/matita/tutorial/chapter5/sublist.def(5)"sublist/a S l1 (a href="cic:/matita/tutorial/chapter5/unique_append.fix(0,1,5)"unique_append/a S l1 l2). +#S #l1 elim l1 normalize [#l2 #S #abs @a href="cic:/matita/basics/logic/False_ind.fix(0,1,1)"False_ind/a /span class="autotactic"2span class="autotrace" trace a href="cic:/matita/basics/logic/absurd.def(2)"absurd/a/span/span/] #x #tl #Hind #l2 #a -normalize cases (true_or_false … (a==x)) #eqax >eqax -[<(\P eqax) cases (true_or_false (memb S a (unique_append S tl l2))) - [#H >H normalize // | #H >H normalize >(\b (refl … a)) //] -|cases (memb S x (unique_append S tl l2)) normalize +normalize cases (a href="cic:/matita/basics/bool/true_or_false.def(1)"true_or_false/a … (aa title="eqb" href="cic:/fakeuri.def(1)"=/a=x)) #eqax >eqax +[<(\P eqax) cases (a href="cic:/matita/basics/bool/true_or_false.def(1)"true_or_false/a (a href="cic:/matita/tutorial/chapter5/memb.fix(0,2,4)"memb/a S a (a href="cic:/matita/tutorial/chapter5/unique_append.fix(0,1,5)"unique_append/a S tl l2))) + [#H >H normalize // | #H >H normalize >(\b (a href="cic:/matita/basics/logic/eq.con(0,1,2)"refl/a … a)) //] +|cases (a href="cic:/matita/tutorial/chapter5/memb.fix(0,2,4)"memb/a S x (a href="cic:/matita/tutorial/chapter5/unique_append.fix(0,1,5)"unique_append/a S tl l2)) normalize [/span class="autotactic"2span class="autotrace" trace /span/span/ |>eqax normalize /span class="autotactic"2span class="autotrace" trace /span/span/] ] qed. lemma sublist_unique_append_l2: - ∀S,l1,l2. sublist S l2 (unique_append S l1 l2). + ∀S,l1,l2. a href="cic:/matita/tutorial/chapter5/sublist.def(5)"sublist/a S l2 (a href="cic:/matita/tutorial/chapter5/unique_append.fix(0,1,5)"unique_append/a S l1 l2). #S #l1 elim l1 [normalize //] #x #tl #Hind normalize -#l2 #a cases (memb S x (unique_append S tl l2)) normalize -[@Hind | cases (a==x) normalize // @Hind] +#l2 #a cases (a href="cic:/matita/tutorial/chapter5/memb.fix(0,2,4)"memb/a S x (a href="cic:/matita/tutorial/chapter5/unique_append.fix(0,1,5)"unique_append/a S tl l2)) normalize +[@Hind | cases (aa title="eqb" href="cic:/fakeuri.def(1)"=/a=x) normalize // @Hind] qed. lemma decidable_sublist:∀S,l1,l2. - (sublist S l1 l2) ∨ ¬(sublist S l1 l2). + (a href="cic:/matita/tutorial/chapter5/sublist.def(5)"sublist/a S l1 l2) a title="logical or" href="cic:/fakeuri.def(1)"∨/a a title="logical not" href="cic:/fakeuri.def(1)"¬/a(a href="cic:/matita/tutorial/chapter5/sublist.def(5)"sublist/a S l1 l2). #S #l1 #l2 elim l1 - [%1 #a normalize in ⊢ (%→?); #abs @False_ind /span class="autotactic"2span class="autotrace" trace absurd/span/span/ + [%1 #a normalize in ⊢ (%→?); #abs @a href="cic:/matita/basics/logic/False_ind.fix(0,1,1)"False_ind/a /span class="autotactic"2span class="autotrace" trace a href="cic:/matita/basics/logic/absurd.def(2)"absurd/a/span/span/ |#a #tl * #subtl - [cases (true_or_false (memb S a l2)) #memba - [%1 whd #x #membx cases (orb_true_l … membx) + [cases (a href="cic:/matita/basics/bool/true_or_false.def(1)"true_or_false/a (a href="cic:/matita/tutorial/chapter5/memb.fix(0,2,4)"memb/a S a l2)) #memba + [%1 whd #x #membx cases (a href="cic:/matita/basics/bool/orb_true_l.def(2)"orb_true_l/a … membx) [#eqax >(\P eqax) // |@subtl] - |%2 @(not_to_not … (eqnot_to_noteq … true memba)) #H1 @H1 @memb_hd + |%2 @(a href="cic:/matita/basics/logic/not_to_not.def(3)"not_to_not/a … (a href="cic:/matita/basics/bool/eqnot_to_noteq.def(4)"eqnot_to_noteq/a … a href="cic:/matita/basics/bool/bool.con(0,1,0)"true/a memba)) #H1 @H1 @a href="cic:/matita/tutorial/chapter5/memb_hd.def(5)"memb_hd/a ] - |%2 @(not_to_not … subtl) #H1 #x #H2 @H1 @memb_cons // + |%2 @(a href="cic:/matita/basics/logic/not_to_not.def(3)"not_to_not/a … subtl) #H1 #x #H2 @H1 @a href="cic:/matita/tutorial/chapter5/memb_cons.def(5)"memb_cons/a // ] ] qed. @@ -193,38 +193,38 @@ qed. (********************* filtering *****************) lemma filter_true: ∀S,f,a,l. - memb S a (filter S f l) = true → f a = true. -#S #f #a #l elim l [normalize #H @False_ind /span class="autotactic"2span class="autotrace" trace absurd/span/span/] -#b #tl #Hind cases (true_or_false (f b)) #H + a href="cic:/matita/tutorial/chapter5/memb.fix(0,2,4)"memb/a S a (a href="cic:/matita/basics/list/filter.def(2)"filter/a S f l) a title="leibnitz's equality" href="cic:/fakeuri.def(1)"=/a a href="cic:/matita/basics/bool/bool.con(0,1,0)"true/a → f a a title="leibnitz's equality" href="cic:/fakeuri.def(1)"=/a a href="cic:/matita/basics/bool/bool.con(0,1,0)"true/a. +#S #f #a #l elim l [normalize #H @a href="cic:/matita/basics/logic/False_ind.fix(0,1,1)"False_ind/a /span class="autotactic"2span class="autotrace" trace a href="cic:/matita/basics/logic/absurd.def(2)"absurd/a/span/span/] +#b #tl #Hind cases (a href="cic:/matita/basics/bool/true_or_false.def(1)"true_or_false/a (f b)) #H normalize >H normalize [2:@Hind] -cases (true_or_false (a==b)) #eqab +cases (a href="cic:/matita/basics/bool/true_or_false.def(1)"true_or_false/a (aa title="eqb" href="cic:/fakeuri.def(1)"=/a=b)) #eqab [#_ >(\P eqab) // | >eqab normalize @Hind] qed. lemma memb_filter_memb: ∀S,f,a,l. - memb S a (filter S f l) = true → memb S a l = true. + a href="cic:/matita/tutorial/chapter5/memb.fix(0,2,4)"memb/a S a (a href="cic:/matita/basics/list/filter.def(2)"filter/a S f l) a title="leibnitz's equality" href="cic:/fakeuri.def(1)"=/a a href="cic:/matita/basics/bool/bool.con(0,1,0)"true/a → a href="cic:/matita/tutorial/chapter5/memb.fix(0,2,4)"memb/a S a l a title="leibnitz's equality" href="cic:/fakeuri.def(1)"=/a a href="cic:/matita/basics/bool/bool.con(0,1,0)"true/a. #S #f #a #l elim l [normalize //] #b #tl #Hind normalize (cases (f b)) normalize -cases (a==b) normalize // @Hind +cases (aa title="eqb" href="cic:/fakeuri.def(1)"=/a=b) normalize // @Hind qed. -lemma memb_filter: ∀S,f,l,x. memb S x (filter ? f l) = true → -memb S x l = true ∧ (f x = true). -/span class="autotactic"3span class="autotrace" trace conj, memb_filter_memb, filter_truespan class="error" title="disambiguation error"/span/span/span/ qed. +lemma memb_filter: ∀S,f,l,x. a href="cic:/matita/tutorial/chapter5/memb.fix(0,2,4)"memb/a S x (a href="cic:/matita/basics/list/filter.def(2)"filter/a ? f l) a title="leibnitz's equality" href="cic:/fakeuri.def(1)"=/a a href="cic:/matita/basics/bool/bool.con(0,1,0)"true/a → +a href="cic:/matita/tutorial/chapter5/memb.fix(0,2,4)"memb/a S x l a title="leibnitz's equality" href="cic:/fakeuri.def(1)"=/a a href="cic:/matita/basics/bool/bool.con(0,1,0)"true/a a title="logical and" href="cic:/fakeuri.def(1)"∧/a (f x a title="leibnitz's equality" href="cic:/fakeuri.def(1)"=/a a href="cic:/matita/basics/bool/bool.con(0,1,0)"true/a). +/span class="autotactic"3span class="autotrace" trace a href="cic:/matita/basics/logic/And.con(0,1,2)"conj/a, a href="cic:/matita/tutorial/chapter5/memb_filter_memb.def(5)"memb_filter_memb/a, a href="cic:/matita/tutorial/chapter5/filter_true.def(5)"filter_true/a/span/span/ qed. -lemma memb_filter_l: ∀S,f,x,l. (f x = true) → memb S x l = true → -memb S x (filter ? f l) = true. +lemma memb_filter_l: ∀S,f,x,l. (f x a title="leibnitz's equality" href="cic:/fakeuri.def(1)"=/a a href="cic:/matita/basics/bool/bool.con(0,1,0)"true/a) → a href="cic:/matita/tutorial/chapter5/memb.fix(0,2,4)"memb/a S x l a title="leibnitz's equality" href="cic:/fakeuri.def(1)"=/a a href="cic:/matita/basics/bool/bool.con(0,1,0)"true/a → +a href="cic:/matita/tutorial/chapter5/memb.fix(0,2,4)"memb/a S x (a href="cic:/matita/basics/list/filter.def(2)"filter/a ? f l) a title="leibnitz's equality" href="cic:/fakeuri.def(1)"=/a a href="cic:/matita/basics/bool/bool.con(0,1,0)"true/a. #S #f #x #l #fx elim l normalize // -#b #tl #Hind cases (true_or_false (x==b)) #eqxb - [<(\P eqxb) >(\b (refl … x)) >fx normalize >(\b (refl … x)) normalize // +#b #tl #Hind cases (a href="cic:/matita/basics/bool/true_or_false.def(1)"true_or_false/a (xa title="eqb" href="cic:/fakeuri.def(1)"=/a=b)) #eqxb + [<(\P eqxb) >(\b (a href="cic:/matita/basics/logic/eq.con(0,1,2)"refl/a … x)) >fx normalize >(\b (a href="cic:/matita/basics/logic/eq.con(0,1,2)"refl/a … x)) normalize // |>eqxb cases (f b) normalize [>eqxb normalize @Hind| @Hind] ] qed. (********************* exists *****************) -let rec exists (A:Type[0]) (p:A → bool) (l:list A) on l : bool ≝ +let rec exists (A:Type[0]) (p:A → a href="cic:/matita/basics/bool/bool.ind(1,0,0)"bool/a) (l:a href="cic:/matita/basics/list/list.ind(1,0,1)"list/a A) on l : a href="cic:/matita/basics/bool/bool.ind(1,0,0)"bool/a ≝ match l with -[ nil ⇒ false -| cons h t ⇒ orb (p h) (exists A p t) +[ nil ⇒ a href="cic:/matita/basics/bool/bool.con(0,2,0)"false/a +| cons h t ⇒ a href="cic:/matita/basics/bool/orb.def(1)"orb/a (p h) (exists A p t) ]. \ No newline at end of file -- 2.39.2