X-Git-Url: http://matita.cs.unibo.it/gitweb/?a=blobdiff_plain;f=weblib%2Ftutorial%2Fchapter1.ma;h=4cf145d60f53f72c70b08846444700cd9b1afc7e;hb=1c8e230b1d81491b38126900d76201fb84303ced;hp=b21fd3e1787add792e06acdb24dbf62c14dba2b0;hpb=1e304931d5cb935c91402a5160c2150aeca0ea2b;p=helm.git diff --git a/weblib/tutorial/chapter1.ma b/weblib/tutorial/chapter1.ma index b21fd3e17..4cf145d60 100644 --- a/weblib/tutorial/chapter1.ma +++ b/weblib/tutorial/chapter1.ma @@ -1,4 +1,5 @@ -(* +(* +h1Matita Interactive Tutorial/h1 This is an interactive tutorial. To let you interact on line with the system, you must first of all register yourself. @@ -15,15 +16,19 @@ a file. The play button is meant to process the script up to a position previously selected by the user; the bottom button execute the whole script. That's it: we arespan style="font-family: Verdana,sans-serif;" /spannow ready to start. -The first thing to say is that in a system like Matita's very few things are -built-in: not even booleans or logical connectives. The main philosophy of the -system is to let you define your own data-types and functions using a powerful -computational mechanism based on the declaration of inductive types. +h2 class="section"Data types, functions and theorems/h2 +Matita is both a programming language and a theorem proving environment: +you define datatypes and programs, and then prove properties on them. +Very few things are built-in: not even booleans or logical connectives +(but you may of course use libraries, as in normal programming languages). +The main philosophy of the system is to let you define your own data-types +and functions using a powerful computational mechanism based on the +declaration of inductive types. Let us start this tutorial with a simple example based on the following well known problem. -h2 class="section"The goat, the wolf and the cabbage/h2 +bThe goat, the wolf and the cabbage/b A farmer need to transfer a goat, a wolf and a cabbage across a river, but there is only one place available on his boat. Furthermore, the goat will eat the cabbage if they are left alone on the same bank, and similarly the wolf will eat @@ -39,14 +44,14 @@ few preliminary notions not worth discussing for the moment. include "basics/logic.ma". -inductive bank: Type[0] ≝ +img class="anchor" src="icons/tick.png" id="bank"inductive bank: Type[0] ≝ | east : bank | west : bank. (* We can now define a simple function computing, for each bank of the river, the opposite one. *) -definition opposite ≝ λs. +img class="anchor" src="icons/tick.png" id="opposite"definition opposite ≝ λs. match s with [ east ⇒ a href="cic:/matita/tutorial/chapter1/bank.con(0,2,0)"west/a | west ⇒ a href="cic:/matita/tutorial/chapter1/bank.con(0,1,0)"east/a @@ -56,9 +61,11 @@ match s with us state the property that the opposite bank of east is west; every lemma needs a name for further reference, and we call it "east_to_west". *) -lemma east_to_west : a href="cic:/matita/tutorial/chapter1/opposite.def(1)"opposite/a a href="cic:/matita/tutorial/chapter1/bank.con(0,1,0)"east/a a title="leibnitz's equality" href="cic:/fakeuri.def(1)"=/a a href="cic:/matita/tutorial/chapter1/bank.con(0,2,0)"west/a. +img class="anchor" src="icons/tick.png" id="east_to_west"lemma east_to_west : a href="cic:/matita/tutorial/chapter1/opposite.def(1)"opposite/a a href="cic:/matita/tutorial/chapter1/bank.con(0,1,0)"east/a a title="leibnitz's equality" href="cic:/fakeuri.def(1)"=/a a href="cic:/matita/tutorial/chapter1/bank.con(0,2,0)"west/a. -(* If you stop the execution here you will see a new window on the right side +(* +h2 class="section"The goal window/h2 +If you stop the execution here you will see a new window on the right side of the screen: it is the goal window, providing a sequent like representation of the form @@ -95,13 +102,14 @@ lemma performing some book-keeping operations. In this case, we avoid the unnecessary simplification step: // will take care of it. *) -lemma west_to_east : a href="cic:/matita/tutorial/chapter1/opposite.def(1)"opposite/a a href="cic:/matita/tutorial/chapter1/bank.con(0,2,0)"west/a a title="leibnitz's equality" href="cic:/fakeuri.def(1)"=/a a href="cic:/matita/tutorial/chapter1/bank.con(0,1,0)"east/a. +img class="anchor" src="icons/tick.png" id="west_to_east"lemma west_to_east : a href="cic:/matita/tutorial/chapter1/opposite.def(1)"opposite/a a href="cic:/matita/tutorial/chapter1/bank.con(0,2,0)"west/a a title="leibnitz's equality" href="cic:/fakeuri.def(1)"=/a a href="cic:/matita/tutorial/chapter1/bank.con(0,1,0)"east/a. // qed. -(* A slightly more complex problem consists in proving that opposite is -idempotent *) +(* +h2 class="section"Introduction/h2 +A slightly more complex problem consists in proving that opposite is idempotent *) -lemma idempotent_opposite : ∀x. a href="cic:/matita/tutorial/chapter1/opposite.def(1)"opposite/a (a href="cic:/matita/tutorial/chapter1/opposite.def(1)"opposite/a x) a title="leibnitz's equality" href="cic:/fakeuri.def(1)"=/a x. +img class="anchor" src="icons/tick.png" id="idempotent_opposite"lemma idempotent_opposite : ∀x. a href="cic:/matita/tutorial/chapter1/opposite.def(1)"opposite/a (a href="cic:/matita/tutorial/chapter1/opposite.def(1)"opposite/a x) a title="leibnitz's equality" href="cic:/fakeuri.def(1)"=/a x. (* we start the proof moving x from the conclusion into the context, that is a (backward) introduction step. Matita syntax for an introduction step is simply @@ -114,7 +122,10 @@ wish to rename x into b (since it is a bank), we just type #b. *) (* See the effect of the execution in the goal window on the right: b has been added to the context (replacing x in the conclusion); moreover its implicit type "bank" has been made explicit. +*) +(* +h2 class="section"Case analysis/h2 But how are we supposed to proceed, now? Simplification cannot help us, since b is a variable: just try to call normalize and you will see that it has no effect. The point is that we must proceed by cases according to the possible values of b, @@ -135,14 +146,16 @@ them in turn, in a way that will be described at the end of this section. // qed. -(* Instead of working with functions, it is sometimes convenient to work with +(* +h2 class="section"Predicates/h2 +Instead of working with functions, it is sometimes convenient to work with predicates. For instance, instead of defining a function computing the opposite bank, we could declare a predicate stating when two banks are opposite to each other. Only two cases are possible, leading naturally to the following definition: *) -inductive opp : a href="cic:/matita/tutorial/chapter1/bank.ind(1,0,0)"bank/a → a href="cic:/matita/tutorial/chapter1/bank.ind(1,0,0)"bank/a → Prop ≝ +img class="anchor" src="icons/tick.png" id="opp"inductive opp : a href="cic:/matita/tutorial/chapter1/bank.ind(1,0,0)"bank/a → a href="cic:/matita/tutorial/chapter1/bank.ind(1,0,0)"bank/a → Prop ≝ | east_west : opp a href="cic:/matita/tutorial/chapter1/bank.con(0,1,0)"east/a a href="cic:/matita/tutorial/chapter1/bank.con(0,2,0)"west/a | west_east : opp a href="cic:/matita/tutorial/chapter1/bank.con(0,2,0)"west/a a href="cic:/matita/tutorial/chapter1/bank.con(0,1,0)"east/a. @@ -156,7 +169,7 @@ Between opp and opposite we have the following relation: opp a b iff a = opposite b Let us prove it, starting from the left to right implication, first *) -lemma opp_to_opposite: ∀a,b. a href="cic:/matita/tutorial/chapter1/opp.ind(1,0,0)"opp/a a b → a a title="leibnitz's equality" href="cic:/fakeuri.def(1)"=/a a href="cic:/matita/tutorial/chapter1/opposite.def(1)"opposite/a b. +img class="anchor" src="icons/tick.png" id="opp_to_opposite"lemma opp_to_opposite: ∀a,b. a href="cic:/matita/tutorial/chapter1/opp.ind(1,0,0)"opp/a a b → a a title="leibnitz's equality" href="cic:/fakeuri.def(1)"=/a a href="cic:/matita/tutorial/chapter1/opposite.def(1)"opposite/a b. (* We start the proof introducing a, b and the hypothesis opp a b, that we call oppab. *) @@ -169,9 +182,11 @@ automation *) cases oppab // qed. -(* Let us come to the opposite direction. *) +(* +h2 class="section"Rewriting/h2 +Let us come to the opposite direction. *) -lemma opposite_to_opp: ∀a,b. a a title="leibnitz's equality" href="cic:/fakeuri.def(1)"=/a a href="cic:/matita/tutorial/chapter1/opposite.def(1)"opposite/a b → a href="cic:/matita/tutorial/chapter1/opp.ind(1,0,0)"opp/a a b. +img class="anchor" src="icons/tick.png" id="opposite_to_opp"lemma opposite_to_opp: ∀a,b. a a title="leibnitz's equality" href="cic:/fakeuri.def(1)"=/a a href="cic:/matita/tutorial/chapter1/opposite.def(1)"opposite/a b → a href="cic:/matita/tutorial/chapter1/opp.ind(1,0,0)"opp/a a b. (* As usual, we start introducing a, b and the hypothesis (a = opposite b), that we call eqa. *) @@ -189,13 +204,14 @@ opposite b into a, we would have typed "