diff options
| author | herbelin | 2005-12-26 13:59:13 +0000 |
|---|---|---|
| committer | herbelin | 2005-12-26 13:59:13 +0000 |
| commit | f6e1acbbe00aeb479fde229c3941e3a6a2d53068 (patch) | |
| tree | ce3a6476de30cbf68c7668f5ecba92f457a721e8 /theories7/Sorting/Permutation.v | |
| parent | e0f9487be5ce770117a9c9c815af8c7010ff357b (diff) | |
Suppression des fichiers .v en ancienne syntaxe
git-svn-id: svn+ssh://scm.gforge.inria.fr/svn/coq/trunk@7733 85f007b7-540e-0410-9357-904b9bb8a0f7
Diffstat (limited to 'theories7/Sorting/Permutation.v')
| -rw-r--r-- | theories7/Sorting/Permutation.v | 111 |
1 files changed, 0 insertions, 111 deletions
diff --git a/theories7/Sorting/Permutation.v b/theories7/Sorting/Permutation.v deleted file mode 100644 index b4dcf16122..0000000000 --- a/theories7/Sorting/Permutation.v +++ /dev/null @@ -1,111 +0,0 @@ -(************************************************************************) -(* v * The Coq Proof Assistant / The Coq Development Team *) -(* <O___,, * CNRS-Ecole Polytechnique-INRIA Futurs-Universite Paris Sud *) -(* \VV/ **************************************************************) -(* // * This file is distributed under the terms of the *) -(* * GNU Lesser General Public License Version 2.1 *) -(************************************************************************) - -(*i $Id$ i*) - -Require Relations. -Require PolyList. -Require Multiset. - -Set Implicit Arguments. - -Section defs. - -Variable A : Set. -Variable leA : (relation A). -Variable eqA : (relation A). - -Local gtA := [x,y:A]~(leA x y). - -Hypothesis leA_dec : (x,y:A){(leA x y)}+{~(leA x y)}. -Hypothesis eqA_dec : (x,y:A){(eqA x y)}+{~(eqA x y)}. -Hypothesis leA_refl : (x,y:A) (eqA x y) -> (leA x y). -Hypothesis leA_trans : (x,y,z:A) (leA x y) -> (leA y z) -> (leA x z). -Hypothesis leA_antisym : (x,y:A)(leA x y) -> (leA y x) -> (eqA x y). - -Hints Resolve leA_refl : default. -Hints Immediate eqA_dec leA_dec leA_antisym : default. - -Local emptyBag := (EmptyBag A). -Local singletonBag := (SingletonBag eqA_dec). - -(** contents of a list *) - -Fixpoint list_contents [l:(list A)] : (multiset A) := - Cases l of - nil => emptyBag - | (cons a l) => (munion (singletonBag a) (list_contents l)) - end. - -Lemma list_contents_app : (l,m:(list A)) - (meq (list_contents (app l m)) (munion (list_contents l) (list_contents m))). -Proof. -Induction l; Simpl; Auto with datatypes. -Intros. -Apply meq_trans with - (munion (singletonBag a) (munion (list_contents l0) (list_contents m))); Auto with datatypes. -Qed. -Hints Resolve list_contents_app. - -Definition permutation := [l,m:(list A)](meq (list_contents l) (list_contents m)). - -Lemma permut_refl : (l:(list A))(permutation l l). -Proof. -Unfold permutation; Auto with datatypes. -Qed. -Hints Resolve permut_refl. - -Lemma permut_tran : (l,m,n:(list A)) - (permutation l m) -> (permutation m n) -> (permutation l n). -Proof. -Unfold permutation; Intros. -Apply meq_trans with (list_contents m); Auto with datatypes. -Qed. - -Lemma permut_right : (l,m:(list A)) - (permutation l m) -> (a:A)(permutation (cons a l) (cons a m)). -Proof. -Unfold permutation; Simpl; Auto with datatypes. -Qed. -Hints Resolve permut_right. - -Lemma permut_app : (l,l',m,m':(list A)) - (permutation l l') -> (permutation m m') -> - (permutation (app l m) (app l' m')). -Proof. -Unfold permutation; Intros. -Apply meq_trans with (munion (list_contents l) (list_contents m)); Auto with datatypes. -Apply meq_trans with (munion (list_contents l') (list_contents m')); Auto with datatypes. -Apply meq_trans with (munion (list_contents l') (list_contents m)); Auto with datatypes. -Qed. -Hints Resolve permut_app. - -Lemma permut_cons : (l,m:(list A))(permutation l m) -> - (a:A)(permutation (cons a l) (cons a m)). -Proof. -Intros l m H a. -Change (permutation (app (cons a (nil A)) l) (app (cons a (nil A)) m)). -Apply permut_app; Auto with datatypes. -Qed. -Hints Resolve permut_cons. - -Lemma permut_middle : (l,m:(list A)) - (a:A)(permutation (cons a (app l m)) (app l (cons a m))). -Proof. -Unfold permutation. -Induction l; Simpl; Auto with datatypes. -Intros. -Apply meq_trans with (munion (singletonBag a) - (munion (singletonBag a0) (list_contents (app l0 m)))); Auto with datatypes. -Apply munion_perm_left; Auto with datatypes. -Qed. -Hints Resolve permut_middle. - -End defs. -Unset Implicit Arguments. - |
