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