Download Preuves Constructives

Transcript
21 janvier 2005
13
Il faut noter que cette fonction pourrait également être dénie dans le système T, mais de
manière un peu plus lourde. Il s'agit donc là d'un aménagement du formalisme qui n'étend pas
l'expressivité du formalisme, mais juste son confort d'utilisation.
Dans un registre diérent, le mécanisme de récursion structurelle permet la dénition de
fonctions logiquement complexes, c'est-à-dire qui croissent très vite. L'exemple le plus connu est
la fonction due à Ackermann, dont voici la dénition ML:
let rec ack = function
O,m -> S(m)
| S(n),O -> ack(n,(S O))
| S(n),S(m) -> ack(n,ack(S(n),m));;
La terminaison de cette dénition est assurée par une décroissance de la paire d'arguments visà-vis de l'ordre lexicographique. En terme de récursion structurelle, ceci est codé par l'utilisation
de deux récursions emboîtées. En Coq, la syntaxe est alors un peu plus complexe; la commande
fix
jouant le rôle d'un
let rec...in:
Coq
Coq
Coq
Coq
Coq
Coq
Coq
Coq
Coq
Coq
< Fixpoint ack (n:nat) : nat -> nat :=
<
match n with
<
| O => fun m:nat => S m
<
| S n' =>
<
(fix aux (m:nat) : nat :=
<
match m with
<
| O => ack n' (S O)
<
| S m' => ack n' (aux m')
<
end)
<
end.
1.4.4 Calculer pour raisonner
Donnons un exemple simple (et classique) d'utilisation de la règle de conversion; il s'agit de
prouver
S (S O)
2 + 2 = 4 où + est la notation inxe de Coq pour plus
et S (S (S (S O))). Ici, cette proposition s'énonce:
et
2
et
4
les représentations de
Coq < Lemma deux_et_deux : 2 + 2 = 4.
1 subgoal
============================
2 + 2 = 4
Il sut d'observer que le terme correspondant à
la proposition est logiquement identiée à
Coq < simpl.
1 subgoal
============================
4 = 4
Coq < reflexivity.
Proof completed.
4=4:
2+2
se réduit eectivement vers
4, et donc que