X-Git-Url: http://matita.cs.unibo.it/gitweb/?a=blobdiff_plain;ds=sidebyside;f=weblib%2Ftutorial%2Fchapter7.ma;h=e37ec25e6d3689c0be83211ace41b47a3bb320e8;hb=45e128062d4ad05b4dfa6e30b9b4d553315186ab;hp=b9a35a8ad93214da1f607dec2f9c2d1f9623bb0d;hpb=c65aeeb22bdc7bf289e5db108c358b199773c857;p=helm.git
diff --git a/weblib/tutorial/chapter7.ma b/weblib/tutorial/chapter7.ma
index b9a35a8ad..e37ec25e6 100644
--- a/weblib/tutorial/chapter7.ma
+++ b/weblib/tutorial/chapter7.ma
@@ -1,4 +1,5 @@
-(*
Regular Expressions
+(*
+h1Regular Expressions /h1
We shall apply all the previous machinery to the study of regular languages
and the constructions of the associated finite automata. *)
@@ -7,7 +8,7 @@ include "tutorial/chapter6.ma".
(* The type re of regular expressions over an alphabet $S$ is the smallest
collection of objects generated by the following constructors: *)
-inductive re (S: a href="cic:/matita/tutorial/chapter4/DeqSet.ind(1,0,0)"DeqSet/a) : Type[0] â
+img class="anchor" src="icons/tick.png" id="re"inductive re (S: a href="cic:/matita/tutorial/chapter4/DeqSet.ind(1,0,0)"DeqSet/a) : Type[0] â
z: re S (* empty: â
*)
| e: re S (* epsilon: ϵ *)
| s: S â re S (* symbol: a *)
@@ -30,24 +31,25 @@ interpretation "empty" 'empty = (z ?).
(* The language sem{e} associated with the regular expression e is inductively
defined by the following function: *)
-let rec in_l (S : a href="cic:/matita/tutorial/chapter4/DeqSet.ind(1,0,0)"DeqSet/aspan class="error" title="Parse error: RPAREN expected after [term] (in [arg])"/span) (r : a href="cic:/matita/tutorial/chapter7/re.ind(1,0,1)"re/a S) on r : a href="cic:/matita/tutorial/chapter6/word.def(3)"word/aspan class="error" title="Parse error: SYMBOL 'â' expected (in [let_defs])"/span S â Prop â
+img class="anchor" src="icons/tick.png" id="in_l"let rec in_l (S : a href="cic:/matita/tutorial/chapter4/DeqSet.ind(1,0,0)"DeqSet/aspan class="error" title="Parse error: RPAREN expected after [term] (in [arg])"/span) (r : a href="cic:/matita/tutorial/chapter7/re.ind(1,0,1)"re/a S) on r : a href="cic:/matita/tutorial/chapter6/word.def(3)"word/aspan class="error" title="Parse error: SYMBOL 'â' expected (in [let_defs])"/span S â Prop â
match r with
-[ z â a title="empty set" href="cic:/fakeuri.def(1)"â
/aspan class="error" title="Parse error: SYMBOL '|' or SYMBOL ']' expected (in [term])"/span
-| e â a title="singleton" href="cic:/fakeuri.def(1)"{/aa title="epsilon" href="cic:/fakeuri.def(1)"ϵ/a}
-| s x â a title="singleton" href="cic:/fakeuri.def(1)"{/aspan class="error" title="Parse error: [ident] or [term level 19] expected after [sym{] (in [term])"/spana title="cons" href="cic:/fakeuri.def(1)"[/aspan class="error" title="Parse error: [term] expected after [sym[] (in [term])"/spanx]}
+[ z â a title="empty set" href="cic:/fakeuri.def(1)"â
/a
+| e â a title="singleton" href="cic:/fakeuri.def(1)"{/aa title="epsilon" href="cic:/fakeuri.def(1)"ϵ/aa title="singleton" href="cic:/fakeuri.def(1)"}/a
+| s x â a title="singleton" href="cic:/fakeuri.def(1)"{/aspan class="error" title="Parse error: [ident] or [term level 19] expected after [sym{] (in [term])"/span (xa title="cons" href="cic:/fakeuri.def(1)":/aa title="cons" href="cic:/fakeuri.def(1)":/aa title="nil" href="cic:/fakeuri.def(1)"[/aa title="nil" href="cic:/fakeuri.def(1)"]/a) a title="singleton" href="cic:/fakeuri.def(1)"}/a
| c r1 r2 â (in_l ? r1) a title="cat lang" href="cic:/fakeuri.def(1)"·/a (in_l ? r2)
| o r1 r2 â (in_l ? r1) a title="union" href="cic:/fakeuri.def(1)"âª/a (in_l ? r2)
-| k r1 â (in_l ? r1) a title="star lang" href="cic:/fakeuri.def(1)"^/a*].
+| k r1 â (in_l ? r1) a title="star lang" href="cic:/fakeuri.def(1)"^/aa title="star lang" href="cic:/fakeuri.def(1)"*/a].
notation "\sem{term 19 E}" non associative with precedence 75 for @{'in_l $E}.
interpretation "in_l" 'in_l E = (in_l ? E).
interpretation "in_l mem" 'mem w l = (in_l ? l w).
-lemma rsem_star : âS.âr: a href="cic:/matita/tutorial/chapter7/re.ind(1,0,1)"re/a S. a title="in_l" href="cic:/fakeuri.def(1)"\sem/a{ra title="re star" href="cic:/fakeuri.def(1)"^/a*} a title="leibnitz's equality" href="cic:/fakeuri.def(1)"=/a a title="in_l" href="cic:/fakeuri.def(1)"\sem/a{r}a title="star lang" href="cic:/fakeuri.def(1)"^/a*.
+img class="anchor" src="icons/tick.png" id="rsem_star"lemma rsem_star : âS.âr: a href="cic:/matita/tutorial/chapter7/re.ind(1,0,1)"re/a S. a title="in_l" href="cic:/fakeuri.def(1)"\sem/a{ra title="re star" href="cic:/fakeuri.def(1)"^/aa title="re star" href="cic:/fakeuri.def(1)"*/aa title="in_l" href="cic:/fakeuri.def(1)"}/a a title="leibnitz's equality" href="cic:/fakeuri.def(1)"=/a a title="in_l" href="cic:/fakeuri.def(1)"\sem/a{ra title="in_l" href="cic:/fakeuri.def(1)"}/aa title="star lang" href="cic:/fakeuri.def(1)"^/aa title="star lang" href="cic:/fakeuri.def(1)"*/a.
// qed.
-(* Pointed Regular expressions
+(*
+h2Pointed Regular expressions /h2
We now introduce pointed regular expressions, that are the main tool we shall
use for the construction of the automaton.
A pointed regular expression is just a regular expression internally labelled
@@ -76,7 +78,7 @@ formalization of the metatheory of programming languages. For our purposes, it i
enough to mark positions preceding individual characters, so we shall have two kinds
of characters â¢a (pp a) and a (ps a) according to the case a is pointed or not. *)
-inductive pitem (S: a href="cic:/matita/tutorial/chapter4/DeqSet.ind(1,0,0)"DeqSet/a) : Type[0] â
+img class="anchor" src="icons/tick.png" id="pitem"inductive pitem (S: a href="cic:/matita/tutorial/chapter4/DeqSet.ind(1,0,0)"DeqSet/a) : Type[0] â
pz: pitem S (* empty *)
| pe: pitem S (* epsilon *)
| ps: S â pitem S (* symbol *)
@@ -91,7 +93,7 @@ the end of the expression. As we shall see, pointed regular expressions can be
understood as states of a DFA, and the boolean indicates if
the state is final or not. *)
-definition pre â λS.a href="cic:/matita/tutorial/chapter7/pitem.ind(1,0,1)"pitem/a S a title="Product" href="cic:/fakeuri.def(1)"Ã/a a href="cic:/matita/basics/bool/bool.ind(1,0,0)"bool/a.
+img class="anchor" src="icons/tick.png" id="pre"definition pre â λS.a href="cic:/matita/tutorial/chapter7/pitem.ind(1,0,1)"pitem/a S a title="Product" href="cic:/fakeuri.def(1)"Ã/a a href="cic:/matita/basics/bool/bool.ind(1,0,0)"bool/a.
interpretation "pitem star" 'star a = (pk ? a).
interpretation "pitem or" 'plus a b = (po ? a b).
@@ -107,153 +109,155 @@ interpretation "pitem empty" 'empty = (pz ?).
removing all the points. Similarly, the carrier of a pointed regular expression
is the carrier of its item. *)
-let rec forget (S: DeqSet) (l : pitem S) on l: re S â
+img class="anchor" src="icons/tick.png" id="forget"let rec forget (S: a href="cic:/matita/tutorial/chapter4/DeqSet.ind(1,0,0)"DeqSet/a) (l : a href="cic:/matita/tutorial/chapter7/pitem.ind(1,0,1)"pitem/a S) on l: a href="cic:/matita/tutorial/chapter7/re.ind(1,0,1)"re/a S â
match l with
- [ pz â `â
- | pe â ϵ
- | ps x â `x
- | pp x â `x
- | pc E1 E2 â (forget ? E1) · (forget ? E2)
- | po E1 E2 â (forget ? E1) + (forget ? E2)
- | pk E â (forget ? E)^* ].
+ [ pz â a href="cic:/matita/tutorial/chapter7/re.con(0,1,1)"z/a ? (* `â
*)
+ | pe â a title="re epsilon" href="cic:/fakeuri.def(1)"ϵ/a
+ | ps x â a title="atom" href="cic:/fakeuri.def(1)"`/ax
+ | pp x â a title="atom" href="cic:/fakeuri.def(1)"`/ax
+ | pc E1 E2 â (forget ? E1) a title="re cat" href="cic:/fakeuri.def(1)"·/a (forget ? E2)
+ | po E1 E2 â (forget ? E1) a title="re or" href="cic:/fakeuri.def(1)"+/aspan class="error" title="Parse error: [term] expected after [sym+] (in [term])"/span (forget ? E2)
+ | pk E â (forget ? E)a title="re star" href="cic:/fakeuri.def(1)"^/aa title="re star" href="cic:/fakeuri.def(1)"*/a ].
(* notation < "|term 19 e|" non associative with precedence 70 for @{'forget $e}.*)
interpretation "forget" 'norm a = (forget ? a).
-lemma erase_dot : âS.âe1,e2:pitem S. |e1 · e2| = c ? (|e1|) (|e2|).
+img class="anchor" src="icons/tick.png" id="erase_dot"lemma erase_dot : âS.âe1,e2:a href="cic:/matita/tutorial/chapter7/pitem.ind(1,0,1)"pitem/a S. a title="forget" href="cic:/fakeuri.def(1)"|/ae1 a title="pitem cat" href="cic:/fakeuri.def(1)"·/a e2a title="forget" href="cic:/fakeuri.def(1)"|/a a title="leibnitz's equality" href="cic:/fakeuri.def(1)"=/a a href="cic:/matita/tutorial/chapter7/re.con(0,4,1)"c/a ? (a title="forget" href="cic:/fakeuri.def(1)"|/ae1a title="forget" href="cic:/fakeuri.def(1)"|/a) (a title="forget" href="cic:/fakeuri.def(1)"|/ae2a title="forget" href="cic:/fakeuri.def(1)"|/a).
// qed.
-lemma erase_plus : âS.âi1,i2:pitem S.
- |i1 + i2| = |i1| + |i2|.
+img class="anchor" src="icons/tick.png" id="erase_plus"lemma erase_plus : âS.âi1,i2:a href="cic:/matita/tutorial/chapter7/pitem.ind(1,0,1)"pitem/a S.
+ a title="forget" href="cic:/fakeuri.def(1)"|/ai1 a title="pitem or" href="cic:/fakeuri.def(1)"+/a i2a title="forget" href="cic:/fakeuri.def(1)"|/a a title="leibnitz's equality" href="cic:/fakeuri.def(1)"=/a a title="forget" href="cic:/fakeuri.def(1)"|/ai1a title="forget" href="cic:/fakeuri.def(1)"|/a a title="re or" href="cic:/fakeuri.def(1)"+/a a title="forget" href="cic:/fakeuri.def(1)"|/ai2a title="forget" href="cic:/fakeuri.def(1)"|/a.
// qed.
-lemma erase_star : âS.âi:pitem S.|i^*| = |i|^*.
+img class="anchor" src="icons/tick.png" id="erase_star"lemma erase_star : âS.âi:a href="cic:/matita/tutorial/chapter7/pitem.ind(1,0,1)"pitem/a S.a title="forget" href="cic:/fakeuri.def(1)"|/aia title="pitem star" href="cic:/fakeuri.def(1)"^/aa title="pitem star" href="cic:/fakeuri.def(1)"*/aa title="forget" href="cic:/fakeuri.def(1)"|/a a title="leibnitz's equality" href="cic:/fakeuri.def(1)"=/a a title="forget" href="cic:/fakeuri.def(1)"|/aia title="forget" href="cic:/fakeuri.def(1)"|/aa title="re star" href="cic:/fakeuri.def(1)"^/aa title="re star" href="cic:/fakeuri.def(1)"*/a.
// qed.
-(* Comparing items and pres
+(*
+h2Comparing items and pres/h2
Items and pres are very concrete datatypes: they can be effectively compared,
and enumerated. In particular, we can define a boolean equality beqitem and a proof
beqitem_true that it refects propositional equality, enriching the set (pitem S)
to a DeqSet. *)
-let rec beqitem S (i1,i2: pitem S) on i1 â
+img class="anchor" src="icons/tick.png" id="beqitem"let rec beqitem S (i1,i2: a href="cic:/matita/tutorial/chapter7/pitem.ind(1,0,1)"pitem/a S) on i1 â
match i1 with
- [ pz â match i2 with [ pz â true | _ â false]
- | pe â match i2 with [ pe â true | _ â false]
- | ps y1 â match i2 with [ ps y2 â y1==y2 | _ â false]
- | pp y1 â match i2 with [ pp y2 â y1==y2 | _ â false]
+ [ pz â match i2 with [ pz â a href="cic:/matita/basics/bool/bool.con(0,1,0)"true/a | _ â a href="cic:/matita/basics/bool/bool.con(0,2,0)"false/a]
+ | pe â match i2 with [ pe â a href="cic:/matita/basics/bool/bool.con(0,1,0)"true/a | _ â a href="cic:/matita/basics/bool/bool.con(0,2,0)"false/a]
+ | ps y1 â match i2 with [ ps y2 â y1a title="eqb" href="cic:/fakeuri.def(1)"=/aa title="eqb" href="cic:/fakeuri.def(1)"=/ay2 | _ â a href="cic:/matita/basics/bool/bool.con(0,2,0)"false/a]
+ | pp y1 â match i2 with [ pp y2 â y1a title="eqb" href="cic:/fakeuri.def(1)"=/aa title="eqb" href="cic:/fakeuri.def(1)"=/ay2 | _ â a href="cic:/matita/basics/bool/bool.con(0,2,0)"false/a]
| po i11 i12 â match i2 with
- [ po i21 i22 â beqitem S i11 i21 ⧠beqitem S i12 i22
- | _ â false]
+ [ po i21 i22 â beqitem S i11 i21 a title="boolean and" href="cic:/fakeuri.def(1)"â§/a beqitem S i12 i22
+ | _ â a href="cic:/matita/basics/bool/bool.con(0,2,0)"false/aspan class="error" title="Parse error: SYMBOL '|' or SYMBOL ']' expected (in [term])"/span]
| pc i11 i12 â match i2 with
- [ pc i21 i22 â beqitem S i11 i21 ⧠beqitem S i12 i22
- | _ â false]
- | pk i11 â match i2 with [ pk i21 â beqitem S i11 i21 | _ â false]
+ [ pc i21 i22 â beqitem S i11 i21 a title="boolean and" href="cic:/fakeuri.def(1)"â§/a beqitem S i12 i22
+ | _ â a href="cic:/matita/basics/bool/bool.con(0,2,0)"false/a]
+ | pk i11 â match i2 with [ pk i21 â beqitem S i11 i21 | _ â a href="cic:/matita/basics/bool/bool.con(0,2,0)"false/a]
].
-lemma beqitem_true: âS,i1,i2. iff (beqitem S i1 i2 = true) (i1 = i2).
+img class="anchor" src="icons/tick.png" id="beqitem_true"lemma beqitem_true: âS,i1,i2. a href="cic:/matita/basics/logic/iff.def(1)"iff/a (a href="cic:/matita/tutorial/chapter7/beqitem.fix(0,1,4)"beqitem/a S i1 i2 a title="leibnitz's equality" href="cic:/fakeuri.def(1)"=/a a href="cic:/matita/basics/bool/bool.con(0,1,0)"true/a) (i1 a title="leibnitz's equality" href="cic:/fakeuri.def(1)"=/a i2).
#S #i1 elim i1
[#i2 cases i2 [||#a|#a|#i21 #i22| #i21 #i22|#i3] % // normalize #H destruct
|#i2 cases i2 [||#a|#a|#i21 #i22| #i21 #i22|#i3] % // normalize #H destruct
|#x #i2 cases i2 [||#a|#a|#i21 #i22| #i21 #i22|#i3] % normalize #H destruct
- [>(\P H) // | @(\b (refl â¦))]
+ [>(\P H) // | @(\b (a href="cic:/matita/basics/logic/eq.con(0,1,2)"refl/a â¦))]
|#x #i2 cases i2 [||#a|#a|#i21 #i22| #i21 #i22|#i3] % normalize #H destruct
- [>(\P H) // | @(\b (refl â¦))]
+ [>(\P H) // | @(\b (a href="cic:/matita/basics/logic/eq.con(0,1,2)"refl/a â¦))]
|#i11 #i12 #Hind1 #Hind2 #i2 cases i2 [||#a|#a|#i21 #i22| #i21 #i22|#i3] %
normalize #H destruct
- [cases (true_or_false (beqitem S i11 i21)) #H1
- [>(proj1 ⦠(Hind1 i21) H1) >(proj1 ⦠(Hind2 i22)) // >H1 in H; #H @H
- |>H1 in H; normalize #abs @False_ind /2/
+ [cases (a href="cic:/matita/basics/bool/true_or_false.def(1)"true_or_false/a (a href="cic:/matita/tutorial/chapter7/beqitem.fix(0,1,4)"beqitem/a S i11 i21)) #H1
+ [>(a href="cic:/matita/basics/logic/proj1.def(2)"proj1/a ⦠(Hind1 i21) H1) >(a href="cic:/matita/basics/logic/proj1.def(2)"proj1/a ⦠(Hind2 i22)) // >H1 in H; #H @H
+ |>H1 in 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/
]
- |>(proj2 ⦠(Hind1 i21) (refl â¦)) >(proj2 ⦠(Hind2 i22) (refl â¦)) //
+ |>(a href="cic:/matita/basics/logic/proj2.def(2)"proj2/a ⦠(Hind1 i21) (a href="cic:/matita/basics/logic/eq.con(0,1,2)"refl/a â¦)) >(a href="cic:/matita/basics/logic/proj2.def(2)"proj2/a ⦠(Hind2 i22) (a href="cic:/matita/basics/logic/eq.con(0,1,2)"refl/a â¦)) //
]
|#i11 #i12 #Hind1 #Hind2 #i2 cases i2 [||#a|#a|#i21 #i22| #i21 #i22|#i3] %
normalize #H destruct
- [cases (true_or_false (beqitem S i11 i21)) #H1
- [>(proj1 ⦠(Hind1 i21) H1) >(proj1 ⦠(Hind2 i22)) // >H1 in H; #H @H
- |>H1 in H; normalize #abs @False_ind /2/
+ [cases (a href="cic:/matita/basics/bool/true_or_false.def(1)"true_or_false/a (a href="cic:/matita/tutorial/chapter7/beqitem.fix(0,1,4)"beqitem/a S i11 i21)) #H1
+ [>(a href="cic:/matita/basics/logic/proj1.def(2)"proj1/a ⦠(Hind1 i21) H1) >(a href="cic:/matita/basics/logic/proj1.def(2)"proj1/a ⦠(Hind2 i22)) // >H1 in H; #H @H
+ |>H1 in 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/
]
- |>(proj2 ⦠(Hind1 i21) (refl â¦)) >(proj2 ⦠(Hind2 i22) (refl â¦)) //
+ |>(a href="cic:/matita/basics/logic/proj2.def(2)"proj2/a ⦠(Hind1 i21) (a href="cic:/matita/basics/logic/eq.con(0,1,2)"refl/a â¦)) >(a href="cic:/matita/basics/logic/proj2.def(2)"proj2/a ⦠(Hind2 i22) (a href="cic:/matita/basics/logic/eq.con(0,1,2)"refl/a â¦)) //
]
|#i3 #Hind #i2 cases i2 [||#a|#a|#i21 #i22| #i21 #i22|#i4] %
normalize #H destruct
- [>(proj1 ⦠(Hind i4) H) // |>(proj2 ⦠(Hind i4) (refl â¦)) //]
+ [>(a href="cic:/matita/basics/logic/proj1.def(2)"proj1/a ⦠(Hind i4) H) // |>(a href="cic:/matita/basics/logic/proj2.def(2)"proj2/a ⦠(Hind i4) (a href="cic:/matita/basics/logic/eq.con(0,1,2)"refl/a â¦)) //]
]
qed.
-definition DeqItem â λS.
- mk_DeqSet (pitem S) (beqitem S) (beqitem_true S).
+img class="anchor" src="icons/tick.png" id="DeqItem"definition DeqItem â λS.
+ a href="cic:/matita/tutorial/chapter4/DeqSet.con(0,1,0)"mk_DeqSet/a (a href="cic:/matita/tutorial/chapter7/pitem.ind(1,0,1)"pitem/a S) (a href="cic:/matita/tutorial/chapter7/beqitem.fix(0,1,4)"beqitem/a S) (a href="cic:/matita/tutorial/chapter7/beqitem_true.def(5)"beqitem_true/a S).
(* We also add a couple of unification hints to allow the type inference system
to look at (pitem S) as the carrier of a DeqSet, and at beqitem as if it was the
equality function of a DeqSet. *)
-unification hint 0 â S;
- X â mk_DeqSet (pitem S) (beqitem S) (beqitem_true S)
+unification hint 0 a href="cic:/fakeuri.def(1)" title="hint_decl_Type1"â/a S;
+ X â a href="cic:/matita/tutorial/chapter4/DeqSet.con(0,1,0)"mk_DeqSet/a (a href="cic:/matita/tutorial/chapter7/pitem.ind(1,0,1)"pitem/a S) (a href="cic:/matita/tutorial/chapter7/beqitem.fix(0,1,4)"beqitem/a S) (a href="cic:/matita/tutorial/chapter7/beqitem_true.def(5)"beqitem_true/a S)
(* ---------------------------------------- *) â¢
- pitem S â¡ carr X.
+ a href="cic:/matita/tutorial/chapter7/pitem.ind(1,0,1)"pitem/a S â¡ a href="cic:/matita/tutorial/chapter4/carr.fix(0,0,2)"carr/a X.
-unification hint 0 â S,i1,i2;
- X â mk_DeqSet (pitem S) (beqitem S) (beqitem_true S)
+unification hint 0 a href="cic:/fakeuri.def(1)" title="hint_decl_Type0"â/a S,i1,i2;
+ X â a href="cic:/matita/tutorial/chapter4/DeqSet.con(0,1,0)"mk_DeqSet/a (a href="cic:/matita/tutorial/chapter7/pitem.ind(1,0,1)"pitem/a S) (a href="cic:/matita/tutorial/chapter7/beqitem.fix(0,1,4)"beqitem/a S) (a href="cic:/matita/tutorial/chapter7/beqitem_true.def(5)"beqitem_true/a S)
(* ---------------------------------------- *) â¢
- beqitem S i1 i2 â¡ eqb X i1 i2.
+ a href="cic:/matita/tutorial/chapter7/beqitem.fix(0,1,4)"beqitem/a S i1 i2 â¡ a href="cic:/matita/tutorial/chapter4/eqb.fix(0,0,3)"eqb/a X i1 i2.
-(* Semantics of pointed regular expression
+(*
+h2Semantics of pointed regular expressions/h2
The intuitive semantic of a point is to mark the position where
we should start reading the regular expression. The language associated
to a pre is the union of the languages associated with its points. *)
-let rec in_pl (S : DeqSet) (r : pitem S) on r : word S â Prop â
+img class="anchor" src="icons/tick.png" id="in_pl"let rec in_pl (S : a href="cic:/matita/tutorial/chapter4/DeqSet.ind(1,0,0)"DeqSet/a) (r : a href="cic:/matita/tutorial/chapter7/pitem.ind(1,0,1)"pitem/a S) on r : a href="cic:/matita/tutorial/chapter6/word.def(3)"word/a S â Prop â
match r with
-[ pz â â
-| pe â â
-| ps _ â â
-| pp x â { [x] }
-| pc r1 r2 â (in_pl ? r1) · \sem{forget ? r2} ⪠(in_pl ? r2)
-| po r1 r2 â (in_pl ? r1) ⪠(in_pl ? r2)
-| pk r1 â (in_pl ? r1) · \sem{forget ? r1}^* ].
+[ pz â a title="empty set" href="cic:/fakeuri.def(1)"â
/a
+| pe â a title="empty set" href="cic:/fakeuri.def(1)"â
/a
+| ps _ â a title="empty set" href="cic:/fakeuri.def(1)"â
/a
+| pp x â a title="singleton" href="cic:/fakeuri.def(1)"{/a (xa title="cons" href="cic:/fakeuri.def(1)":/aa title="cons" href="cic:/fakeuri.def(1)":/aa title="nil" href="cic:/fakeuri.def(1)"[/aa title="nil" href="cic:/fakeuri.def(1)"]/a) a title="singleton" href="cic:/fakeuri.def(1)"}/a
+| pc r1 r2 â (in_pl ? r1) a title="cat lang" href="cic:/fakeuri.def(1)"·/a a title="in_l" href="cic:/fakeuri.def(1)"\sem/a{a href="cic:/matita/tutorial/chapter7/forget.fix(0,1,3)"forget/a ? r2a title="in_l" href="cic:/fakeuri.def(1)"}/a a title="union" href="cic:/fakeuri.def(1)"âª/aspan class="error" title="Parse error: [term] expected after [symâª] (in [term])"/span (in_pl ? r2)
+| po r1 r2 â (in_pl ? r1) a title="union" href="cic:/fakeuri.def(1)"âª/a (in_pl ? r2)
+| pk r1 â (in_pl ? r1) a title="cat lang" href="cic:/fakeuri.def(1)"·/a a title="in_l" href="cic:/fakeuri.def(1)"\sem/a{a href="cic:/matita/tutorial/chapter7/forget.fix(0,1,3)"forget/a ? r1a title="in_l" href="cic:/fakeuri.def(1)"}/aa title="star lang" href="cic:/fakeuri.def(1)"^/aa title="star lang" href="cic:/fakeuri.def(1)"*/a ].
interpretation "in_pl" 'in_l E = (in_pl ? E).
interpretation "in_pl mem" 'mem w l = (in_pl ? l w).
-definition in_prl â λS : DeqSet.λp:pre S.
- if (\snd p) then \sem{\fst p} ⪠{ϵ} else \sem{\fst p}.
+img class="anchor" src="icons/tick.png" id="in_prl"definition in_prl â λS : a href="cic:/matita/tutorial/chapter4/DeqSet.ind(1,0,0)"DeqSet/a.λp:a href="cic:/matita/tutorial/chapter7/pre.def(1)"pre/a S.
+ if (a title="pair pi2" href="cic:/fakeuri.def(1)"\snd/a p) then a title="in_pl" href="cic:/fakeuri.def(1)"\sem/a{a title="pair pi1" href="cic:/fakeuri.def(1)"\fst/a pa title="in_pl" href="cic:/fakeuri.def(1)"}/a a title="union" href="cic:/fakeuri.def(1)"âª/a a title="singleton" href="cic:/fakeuri.def(1)"{/aa title="epsilon" href="cic:/fakeuri.def(1)"ϵ/aa title="singleton" href="cic:/fakeuri.def(1)"}/a else a title="in_pl" href="cic:/fakeuri.def(1)"\sem/a{a title="pair pi1" href="cic:/fakeuri.def(1)"\fst/a pa title="in_pl" href="cic:/fakeuri.def(1)"}/a.
interpretation "in_prl mem" 'mem w l = (in_prl ? l w).
interpretation "in_prl" 'in_l E = (in_prl ? E).
(* The following, trivial lemmas are only meant for rewriting purposes. *)
-lemma sem_pre_true : âS.âi:pitem S.
- \sem{â©i,trueâª} = \sem{i} ⪠{ϵ}.
+img class="anchor" src="icons/tick.png" id="sem_pre_true"lemma sem_pre_true : âS.âi:a href="cic:/matita/tutorial/chapter7/pitem.ind(1,0,1)"pitem/a S.
+ a title="in_prl" href="cic:/fakeuri.def(1)"\sem/a{a title="Pair construction" href="cic:/fakeuri.def(1)"ã/ai,a href="cic:/matita/basics/bool/bool.con(0,1,0)"true/aa title="Pair construction" href="cic:/fakeuri.def(1)"ã/aa title="in_prl" href="cic:/fakeuri.def(1)"}/a a title="leibnitz's equality" href="cic:/fakeuri.def(1)"=/a a title="in_pl" href="cic:/fakeuri.def(1)"\sem/a{ia title="in_pl" href="cic:/fakeuri.def(1)"}/a a title="union" href="cic:/fakeuri.def(1)"âª/a a title="singleton" href="cic:/fakeuri.def(1)"{/aa title="epsilon" href="cic:/fakeuri.def(1)"ϵ/aa title="singleton" href="cic:/fakeuri.def(1)"}/a.
// qed.
-lemma sem_pre_false : âS.âi:pitem S.
- \sem{â©i,falseâª} = \sem{i}.
+img class="anchor" src="icons/tick.png" id="sem_pre_false"lemma sem_pre_false : âS.âi:a href="cic:/matita/tutorial/chapter7/pitem.ind(1,0,1)"pitem/a S.
+ a title="in_prl" href="cic:/fakeuri.def(1)"\sem/a{a title="Pair construction" href="cic:/fakeuri.def(1)"ã/ai,a href="cic:/matita/basics/bool/bool.con(0,2,0)"false/aa title="Pair construction" href="cic:/fakeuri.def(1)"ã/aa title="in_prl" href="cic:/fakeuri.def(1)"}/a a title="leibnitz's equality" href="cic:/fakeuri.def(1)"=/a a title="in_pl" href="cic:/fakeuri.def(1)"\sem/a{ia title="in_pl" href="cic:/fakeuri.def(1)"}/a.
// qed.
-lemma sem_cat: âS.âi1,i2:pitem S.
- \sem{i1 · i2} = \sem{i1} · \sem{|i2|} ⪠\sem{i2}.
+img class="anchor" src="icons/tick.png" id="sem_cat"lemma sem_cat: âS.âi1,i2:a href="cic:/matita/tutorial/chapter7/pitem.ind(1,0,1)"pitem/a S.
+ a title="in_pl" href="cic:/fakeuri.def(1)"\sem/a{i1 a title="pitem cat" href="cic:/fakeuri.def(1)"·/a i2a title="in_pl" href="cic:/fakeuri.def(1)"}/a a title="leibnitz's equality" href="cic:/fakeuri.def(1)"=/a a title="in_pl" href="cic:/fakeuri.def(1)"\sem/a{i1a title="in_pl" href="cic:/fakeuri.def(1)"}/a a title="cat lang" href="cic:/fakeuri.def(1)"·/a a title="in_l" href="cic:/fakeuri.def(1)"\sem/a{a title="forget" href="cic:/fakeuri.def(1)"|/ai2a title="forget" href="cic:/fakeuri.def(1)"|/aa title="in_l" href="cic:/fakeuri.def(1)"}/a a title="union" href="cic:/fakeuri.def(1)"âª/a a title="in_pl" href="cic:/fakeuri.def(1)"\sem/a{i2a title="in_pl" href="cic:/fakeuri.def(1)"}/a.
// qed.
-lemma sem_cat_w: âS.âi1,i2:pitem S.âw.
- \sem{i1 · i2} w = ((\sem{i1} · \sem{|i2|}) w ⨠\sem{i2} w).
+img class="anchor" src="icons/tick.png" id="sem_cat_w"lemma sem_cat_w: âS.âi1,i2:a href="cic:/matita/tutorial/chapter7/pitem.ind(1,0,1)"pitem/a S.âw.
+ a title="in_pl" href="cic:/fakeuri.def(1)"\sem/a{i1 a title="pitem cat" href="cic:/fakeuri.def(1)"·/a i2a title="in_pl" href="cic:/fakeuri.def(1)"}/a w a title="leibnitz's equality" href="cic:/fakeuri.def(1)"=/a ((a title="in_pl" href="cic:/fakeuri.def(1)"\sem/a{i1a title="in_pl" href="cic:/fakeuri.def(1)"}/a a title="cat lang" href="cic:/fakeuri.def(1)"·/a a title="in_l" href="cic:/fakeuri.def(1)"\sem/a{a title="forget" href="cic:/fakeuri.def(1)"|/ai2a title="forget" href="cic:/fakeuri.def(1)"|/aa title="in_l" href="cic:/fakeuri.def(1)"}/a) w a title="logical or" href="cic:/fakeuri.def(1)"â¨/a a title="in_pl" href="cic:/fakeuri.def(1)"\sem/a{i2a title="in_pl" href="cic:/fakeuri.def(1)"}/a w).
// qed.
-lemma sem_plus: âS.âi1,i2:pitem S.
- \sem{i1 + i2} = \sem{i1} ⪠\sem{i2}.
+img class="anchor" src="icons/tick.png" id="sem_plus"lemma sem_plus: âS.âi1,i2:a href="cic:/matita/tutorial/chapter7/pitem.ind(1,0,1)"pitem/a S.
+ a title="in_pl" href="cic:/fakeuri.def(1)"\sem/a{i1 a title="pitem or" href="cic:/fakeuri.def(1)"+/a i2a title="in_pl" href="cic:/fakeuri.def(1)"}/a a title="leibnitz's equality" href="cic:/fakeuri.def(1)"=/a a title="in_pl" href="cic:/fakeuri.def(1)"\sem/a{i1a title="in_pl" href="cic:/fakeuri.def(1)"}/a a title="union" href="cic:/fakeuri.def(1)"âª/a a title="in_pl" href="cic:/fakeuri.def(1)"\sem/a{i2a title="in_pl" href="cic:/fakeuri.def(1)"}/a.
// qed.
-lemma sem_plus_w: âS.âi1,i2:pitem S.âw.
- \sem{i1 + i2} w = (\sem{i1} w ⨠\sem{i2} w).
+img class="anchor" src="icons/tick.png" id="sem_plus_w"lemma sem_plus_w: âS.âi1,i2:a href="cic:/matita/tutorial/chapter7/pitem.ind(1,0,1)"pitem/a S.âw.
+ a title="in_pl" href="cic:/fakeuri.def(1)"\sem/a{i1 a title="pitem or" href="cic:/fakeuri.def(1)"+/a i2a title="in_pl" href="cic:/fakeuri.def(1)"}/a w a title="leibnitz's equality" href="cic:/fakeuri.def(1)"=/a (a title="in_pl" href="cic:/fakeuri.def(1)"\sem/a{i1a title="in_pl" href="cic:/fakeuri.def(1)"}/a w a title="logical or" href="cic:/fakeuri.def(1)"â¨/a a title="in_pl" href="cic:/fakeuri.def(1)"\sem/a{i2a title="in_pl" href="cic:/fakeuri.def(1)"}/a w).
// qed.
-lemma sem_star : âS.âi:pitem S.
- \sem{i^*} = \sem{i} · \sem{|i|}^*.
+img class="anchor" src="icons/tick.png" id="sem_star"lemma sem_star : âS.âi:a href="cic:/matita/tutorial/chapter7/pitem.ind(1,0,1)"pitem/a S.
+ a title="in_pl" href="cic:/fakeuri.def(1)"\sem/a{ia title="pitem star" href="cic:/fakeuri.def(1)"^/aa title="pitem star" href="cic:/fakeuri.def(1)"*/aa title="in_pl" href="cic:/fakeuri.def(1)"}/a a title="leibnitz's equality" href="cic:/fakeuri.def(1)"=/a a title="in_pl" href="cic:/fakeuri.def(1)"\sem/a{ia title="in_pl" href="cic:/fakeuri.def(1)"}/a a title="cat lang" href="cic:/fakeuri.def(1)"·/a a title="in_l" href="cic:/fakeuri.def(1)"\sem/a{a title="forget" href="cic:/fakeuri.def(1)"|/aia title="forget" href="cic:/fakeuri.def(1)"|/aa title="in_l" href="cic:/fakeuri.def(1)"}/aa title="star lang" href="cic:/fakeuri.def(1)"^/aa title="star lang" href="cic:/fakeuri.def(1)"*/a.
// qed.
-lemma sem_star_w : âS.âi:pitem S.âw.
- \sem{i^*} w = (âw1,w2.w1 @ w2 = w ⧠\sem{i} w1 ⧠\sem{|i|}^* w2).
+img class="anchor" src="icons/tick.png" id="sem_star_w"lemma sem_star_w : âS.âi:a href="cic:/matita/tutorial/chapter7/pitem.ind(1,0,1)"pitem/a S.âw.
+ a title="in_pl" href="cic:/fakeuri.def(1)"\sem/a{ia title="pitem star" href="cic:/fakeuri.def(1)"^/aa title="pitem star" href="cic:/fakeuri.def(1)"*/aa title="in_pl" href="cic:/fakeuri.def(1)"}/a w a title="leibnitz's equality" href="cic:/fakeuri.def(1)"=/a (a title="exists" href="cic:/fakeuri.def(1)"â/aw1,w2a title="exists" href="cic:/fakeuri.def(1)"./aw1 a title="append" href="cic:/fakeuri.def(1)"@/a w2 a title="leibnitz's equality" href="cic:/fakeuri.def(1)"=/a w a title="logical and" href="cic:/fakeuri.def(1)"â§/a a title="in_pl" href="cic:/fakeuri.def(1)"\sem/a{ia title="in_pl" href="cic:/fakeuri.def(1)"}/a w1 a title="logical and" href="cic:/fakeuri.def(1)"â§/a a title="in_l" href="cic:/fakeuri.def(1)"\sem/a{a title="forget" href="cic:/fakeuri.def(1)"|/aia title="forget" href="cic:/fakeuri.def(1)"|/aa title="in_l" href="cic:/fakeuri.def(1)"}/aa title="star lang" href="cic:/fakeuri.def(1)"^/aa title="star lang" href="cic:/fakeuri.def(1)"*/a w2).
// qed.
(* Below are a few, simple, semantic properties of items. In particular:
@@ -264,38 +268,37 @@ lemma sem_star_w : âS.âi:pitem S.âw.
The first property is proved by a simple induction on $i$; the other
results are easy corollaries. We need an auxiliary lemma first. *)
-lemma append_eq_nil : âS.âw1,w2:word S. w1 @ w2 = ϵ â w1 = ϵ.
+img class="anchor" src="icons/tick.png" id="append_eq_nil"lemma append_eq_nil : âS.âw1,w2:a href="cic:/matita/tutorial/chapter6/word.def(3)"word/a S. w1 a title="append" href="cic:/fakeuri.def(1)"@/a w2 a title="leibnitz's equality" href="cic:/fakeuri.def(1)"=/a a title="epsilon" href="cic:/fakeuri.def(1)"ϵ/a â w1 a title="leibnitz's equality" href="cic:/fakeuri.def(1)"=/a a title="epsilon" href="cic:/fakeuri.def(1)"ϵ/a.
#S #w1 #w2 cases w1 // #a #tl normalize #H destruct qed.
-lemma not_epsilon_lp : âS:DeqSet.âe:pitem S. ¬ (ϵ â e).
-#S #e elim e normalize /2/
- [#r1 #r2 * #n1 #n2 % * /2/ * #w1 * #w2 * * #H
- >(append_eq_nil â¦Hâ¦) /2/
- |#r1 #r2 #n1 #n2 % * /2/
- |#r #n % * #w1 * #w2 * * #H >(append_eq_nil â¦Hâ¦) /2/
+img class="anchor" src="icons/tick.png" id="not_epsilon_lp"lemma not_epsilon_lp : âS:a href="cic:/matita/tutorial/chapter4/DeqSet.ind(1,0,0)"DeqSet/a.âe:a href="cic:/matita/tutorial/chapter7/pitem.ind(1,0,1)"pitem/a S. a title="logical not" href="cic:/fakeuri.def(1)"¬/a (a title="epsilon" href="cic:/fakeuri.def(1)"ϵ/a a title="in_pl mem" href="cic:/fakeuri.def(1)"â/a e).
+#S #e elim e normalize /span class="autotactic"2span class="autotrace" trace a href="cic:/matita/basics/logic/Not.con(0,1,1)"nmk/a/span/span/
+ [#r1 #r2 * #n1 #n2 % * /span class="autotactic"2span class="autotrace" trace a href="cic:/matita/basics/logic/absurd.def(2)"absurd/a/span/span/ * #w1 * #w2 * * #H
+ >(a href="cic:/matita/tutorial/chapter7/append_eq_nil.def(4)"append_eq_nil/a â¦Hâ¦) /span class="autotactic"2span class="autotrace" trace /span/span/
+ |#r1 #r2 #n1 #n2 % * /span class="autotactic"2span class="autotrace" trace a href="cic:/matita/basics/logic/absurd.def(2)"absurd/a/span/span/
+ |#r #n % * #w1 * #w2 * * #H >(a href="cic:/matita/tutorial/chapter7/append_eq_nil.def(4)"append_eq_nil/a â¦Hâ¦) /span class="autotactic"2span class="autotrace" trace a href="cic:/matita/basics/logic/absurd.def(2)"absurd/a/span/span/
]
qed.
-lemma epsilon_to_true : âS.âe:pre S. ϵ â e â \snd e = true.
-#S * #i #b cases b // normalize #H @False_ind /2/
+img class="anchor" src="icons/tick.png" id="epsilon_to_true"lemma epsilon_to_true : âS.âe:a href="cic:/matita/tutorial/chapter7/pre.def(1)"pre/a S. a title="epsilon" href="cic:/fakeuri.def(1)"ϵ/a a title="in_prl mem" href="cic:/fakeuri.def(1)"â/a e â a title="pair pi2" href="cic:/fakeuri.def(1)"\snd/a e 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 * #i #b cases b // 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/
qed.
-lemma true_to_epsilon : âS.âe:pre S. \snd e = true â ϵ â e.
+img class="anchor" src="icons/tick.png" id="true_to_epsilon"lemma true_to_epsilon : âS.âe:a href="cic:/matita/tutorial/chapter7/pre.def(1)"pre/a S. a title="pair pi2" href="cic:/fakeuri.def(1)"\snd/a e 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="epsilon" href="cic:/fakeuri.def(1)"ϵ/a a title="in_prl mem" href="cic:/fakeuri.def(1)"â/a e.
#S * #i #b #btrue normalize in btrue; >btrue %2 //
qed.
-lemma minus_eps_item: âS.âi:pitem S. \sem{i} =1 \sem{i}-{[ ]}.
+img class="anchor" src="icons/tick.png" id="minus_eps_item"lemma minus_eps_item: âS.âi:a href="cic:/matita/tutorial/chapter7/pitem.ind(1,0,1)"pitem/a S. a title="in_pl" href="cic:/fakeuri.def(1)"\sem/a{ia title="in_pl" href="cic:/fakeuri.def(1)"}/a a title="extensional equality" href="cic:/fakeuri.def(1)"=/a1 a title="in_pl" href="cic:/fakeuri.def(1)"\sem/a{ia title="in_pl" href="cic:/fakeuri.def(1)"}/aa title="substraction" href="cic:/fakeuri.def(1)"-/aa title="singleton" href="cic:/fakeuri.def(1)"{/aa title="nil" href="cic:/fakeuri.def(1)"[/a a title="nil" href="cic:/fakeuri.def(1)"]/aa title="singleton" href="cic:/fakeuri.def(1)"}/a.
#S #i #w %
- [#H whd % // normalize @(not_to_not ⦠(not_epsilon_lp â¦i)) //
+ [#H whd % // normalize @(a href="cic:/matita/basics/logic/not_to_not.def(3)"not_to_not/a ⦠(a href="cic:/matita/tutorial/chapter7/not_epsilon_lp.def(8)"not_epsilon_lp/a â¦i)) //
|* //
]
qed.
-lemma minus_eps_pre: âS.âe:pre S. \sem{\fst e} =1 \sem{e}-{[ ]}.
+img class="anchor" src="icons/tick.png" id="minus_eps_pre"lemma minus_eps_pre: âS.âe:a href="cic:/matita/tutorial/chapter7/pre.def(1)"pre/a S. a title="in_pl" href="cic:/fakeuri.def(1)"\sem/aspan class="error" title="Parse error: [sym{] expected after [sym\sem ] (in [term])"/span{a title="pair pi1" href="cic:/fakeuri.def(1)"\fst/a ea title="in_pl" href="cic:/fakeuri.def(1)"}/a a title="extensional equality" href="cic:/fakeuri.def(1)"=/a1 a title="in_prl" href="cic:/fakeuri.def(1)"\sem/a{ea title="in_prl" href="cic:/fakeuri.def(1)"}/aa title="substraction" href="cic:/fakeuri.def(1)"-/aa title="singleton" href="cic:/fakeuri.def(1)"{/aa title="nil" href="cic:/fakeuri.def(1)"[/a a title="nil" href="cic:/fakeuri.def(1)"]/aa title="singleton" href="cic:/fakeuri.def(1)"}/a.
#S * #i *
- [>sem_pre_true normalize in ⢠(??%?); #w %
- [/3/ | * * // #H1 #H2 @False_ind @(absurd â¦H1 H2)]
- |>sem_pre_false normalize in ⢠(??%?); #w % [ /3/ | * // ]
+ [>a href="cic:/matita/tutorial/chapter7/sem_pre_true.def(9)"sem_pre_true/a normalize in ⢠(??%?); #w %
+ [/span class="autotactic"3span class="autotrace" trace a href="cic:/matita/basics/logic/Or.con(0,1,2)"or_introl/a, a href="cic:/matita/basics/logic/And.con(0,1,2)"conj/a, a href="cic:/matita/basics/logic/not_to_not.def(3)"not_to_not/a/span/span/ | * * // #H1 #H2 @a href="cic:/matita/basics/logic/False_ind.fix(0,1,1)"False_ind/a @(a href="cic:/matita/basics/logic/absurd.def(2)"absurd/a â¦H1 H2)]
+ |>a href="cic:/matita/tutorial/chapter7/sem_pre_false.def(9)"sem_pre_false/a normalize in ⢠(??%?); #w % [ /span class="autotactic"3span class="autotrace" trace a href="cic:/matita/basics/logic/And.con(0,1,2)"conj/a, a href="cic:/matita/basics/logic/not_to_not.def(3)"not_to_not/a/span/span/ | * // ]
]
-qed.
-
+qed.
\ No newline at end of file