-(*
+(*
+\ 5h1\ 6Matita Interactive Tutorial\ 5/h1\ 6
This is an interactive tutorial. To let you interact on line with the system,
you must first of all register yourself.
previously selected by the user; the bottom button execute the whole script.
That's it: we are\ 5span style="font-family: Verdana,sans-serif;"\ 6 \ 5/span\ 6now 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.
+\ 5h2 class="section"\ 6Data types, functions and theorems\ 5/h2\ 6
+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.
-\ 5h2 class="section"\ 6The goat, the wolf and the cabbage\ 5/h2\ 6
+\ 5b\ 6The goat, the wolf and the cabbage\ 5/b\ 6
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
lemma west_to_east : \ 5a href="cic:/matita/tutorial/chapter1/opposite.def(1)"\ 6opposite\ 5/a\ 6 \ 5a href="cic:/matita/tutorial/chapter1/bank.con(0,2,0)"\ 6west\ 5/a\ 6 \ 5a title="leibnitz's equality" href="cic:/fakeuri.def(1)"\ 6=\ 5/a\ 6 \ 5a href="cic:/matita/tutorial/chapter1/bank.con(0,1,0)"\ 6east\ 5/a\ 6.
// qed.
-(* A slightly more complex problem consists in proving that opposite is
-idempotent *)
+(*
+\ 5h2 class="section"\ 6Case analysis\ 5/h2\ 6
+A slightly more complex problem consists in proving that opposite is idempotent *)
lemma idempotent_opposite : ∀x. \ 5a href="cic:/matita/tutorial/chapter1/opposite.def(1)"\ 6opposite\ 5/a\ 6 (\ 5a href="cic:/matita/tutorial/chapter1/opposite.def(1)"\ 6opposite\ 5/a\ 6 x) \ 5a title="leibnitz's equality" href="cic:/fakeuri.def(1)"\ 6=\ 5/a\ 6 x.
// qed.
-(* Instead of working with functions, it is sometimes convenient to work with
+(*
+\ 5h2 class="section"\ 6Predicates\ 5/h2\ 6
+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
cases oppab // qed.
-(* Let us come to the opposite direction. *)
+(*
+\ 5h2 class="section"\ 6Rewriting\ 5/h2\ 6
+Let us come to the opposite direction. *)
lemma opposite_to_opp: ∀a,b. a \ 5a title="leibnitz's equality" href="cic:/fakeuri.def(1)"\ 6=\ 5/a\ 6 \ 5a href="cic:/matita/tutorial/chapter1/opposite.def(1)"\ 6opposite\ 5/a\ 6 b → \ 5a href="cic:/matita/tutorial/chapter1/opp.ind(1,0,0)"\ 6opp\ 5/a\ 6 a b.
cases b // qed.
(*
+\ 5h2 class="section"\ 6Records\ 5/h2\ 6
It is time to proceed with our formalization of the farmer's problem.
A state of the system is defined by the position of four item: the goat, the
wolf, the cabbage, and the boat. The simplest way to declare such a data type
| one : ∀x,y.\ 5a href="cic:/matita/tutorial/chapter1/move.ind(1,0,0)"\ 6move\ 5/a\ 6 x y → reachable x y
| more : ∀x,z,y. \ 5span style="text-decoration: underline;"\ 6\ 5/span\ 6reachable x z → \ 5a href="cic:/matita/tutorial/chapter1/safe_state.ind(1,0,0)"\ 6safe_state\ 5/a\ 6 z → \ 5span style="text-decoration: underline;"\ 6\ 5/span\ 6\ 5a href="cic:/matita/tutorial/chapter1/move.ind(1,0,0)"\ 6move\ 5/a\ 6 z y → reachable x y.
-(* Remarkably, Matita is now able to solve the problem by itslef, provided
+(*
+\ 5h2 class="section"\ 6Automation\ 5/h2\ 6
+Remarkably, Matita is now able to solve the problem by itslef, provided
you allow automation to exploit more resources. The command /n/ is similar to
//, where n is a measure of this complexity: in particular it is a bound to
the depth of the expected proof tree (more precisely, to the number of nested
lemma problem: \ 5a href="cic:/matita/tutorial/chapter1/reachable.ind(1,0,0)"\ 6reachable\ 5/a\ 6 \ 5a href="cic:/matita/tutorial/chapter1/start.def(1)"\ 6start\ 5/a\ 6 \ 5a href="cic:/matita/tutorial/chapter1/end.def(1)"\ 6end\ 5/a\ 6.
normalize /\ 5span class="autotactic"\ 69\ 5span class="autotrace"\ 6 trace \ 5a href="cic:/matita/tutorial/chapter1/reachable.con(0,1,0)"\ 6one\ 5/a\ 6, \ 5a href="cic:/matita/tutorial/chapter1/reachable.con(0,2,0)"\ 6more\ 5/a\ 6, \ 5a href="cic:/matita/tutorial/chapter1/safe_state.con(0,1,0)"\ 6with_boat\ 5/a\ 6, \ 5a href="cic:/matita/tutorial/chapter1/safe_state.con(0,2,0)"\ 6opposite_side\ 5/a\ 6, \ 5a href="cic:/matita/tutorial/chapter1/move.con(0,1,0)"\ 6move_goat\ 5/a\ 6, \ 5a href="cic:/matita/tutorial/chapter1/move.con(0,2,0)"\ 6move_wolf\ 5/a\ 6, \ 5a href="cic:/matita/tutorial/chapter1/move.con(0,3,0)"\ 6move_cabbage\ 5/a\ 6, \ 5a href="cic:/matita/tutorial/chapter1/move.con(0,4,0)"\ 6move_boat\ 5/a\ 6, \ 5a href="cic:/matita/tutorial/chapter1/opp.con(0,1,0)"\ 6east_west\ 5/a\ 6, \ 5a href="cic:/matita/tutorial/chapter1/opp.con(0,2,0)"\ 6west_east\ 5/a\ 6\ 5/span\ 6\ 5/span\ 6/ qed.
-(* Let us now try to derive the proof in a more interactive way. Of course, we
+(*
+\ 5h2 class="section"\ 6Application\ 5/h2\ 6
+Let us now try to derive the proof in a more interactive way. Of course, we
expect to need several moves to transfer all items from a bank to the other, so
-we should start our proof by applying "more".
+we should start our proof by applying "more". Matita syntax for invoking the
+application of a property named foo is to write "@foo". In general, the philosophy
+of Matita is to describe each proof of a property P as a structured collection of
+results required for proving P, prefixed by simple modalities (<,@,...) explaining
+the way the result is used (e.g. for rewriting, in an applicative step, and so on).
*)
lemma problem1: \ 5a href="cic:/matita/tutorial/chapter1/reachable.ind(1,0,0)"\ 6reachable\ 5/a\ 6 \ 5a href="cic:/matita/tutorial/chapter1/start.def(1)"\ 6start\ 5/a\ 6 \ 5a href="cic:/matita/tutorial/chapter1/end.def(1)"\ 6end\ 5/a\ 6.
normalize @\ 5a href="cic:/matita/tutorial/chapter1/reachable.con(0,2,0)"\ 6more\ 5/a\ 6
-(* We have now four open subgoals:
+(*
+\ 5h2 class="section"\ 6Focusing\ 5/h2\ 6
+After performing the previous application, we have four open subgoals:
X : STATE
Y : reachable [east,east,east,east] X
| /\ 5span class="autotactic"\ 62\ 5span class="autotrace"\ 6 trace \ 5a href="cic:/matita/tutorial/chapter1/move.con(0,1,0)"\ 6move_goat\ 5/a\ 6, \ 5a href="cic:/matita/tutorial/chapter1/opp.con(0,1,0)"\ 6east_west\ 5/a\ 6\ 5/span\ 6\ 5/span\ 6/ ]
-(* Let us perform the next step, namely moving back the boat, in a sligtly
+(*
+\ 5h2 class="section"\ 6Implicit arguments\ 5/h2\ 6
+Let us perform the next step, namely moving back the boat, in a sligtly
different way. The more operation expects as second argument the new
intermediate state, hence instead of applying more we can apply this term
already instatated on the next intermediate state. As first argument, we
projects / helm.git / commitdiff