Anforderungen  |   Konzepte  |   Entwurf  |   Entwicklung  |   Qualitätssicherung  |   Lebenszyklus  |   Steuerung
 
 
 
 


Quellcode-Bibliothek

© Kompilation durch diese Firma

[Weder Korrektheit noch Funktionsfähigkeit der Software werden zugesichert.]

Datei: Relations_3_facts.v   Sprache: Coq

Original von: Coq©

(************************************************************************)
(*         *   The Coq Proof Assistant / The Coq Development Team       *)
(*  v      *   INRIA, CNRS and contributors - Copyright 1999-2018       *)
(* <O___,, *       (see CREDITS file for the list of authors)           *)
(*   \VV/  **************************************************************)
(*    //   *    This file is distributed under the terms of the         *)
(*         *     GNU Lesser General Public License Version 2.1          *)
(*         *     (see LICENSE file for the text of the license)         *)
(************************************************************************)
(****************************************************************************)
(*                                                                          *)
(*                         Naive Set Theory in Coq                          *)
(*                                                                          *)
(*                     INRIA                        INRIA                   *)
(*              Rocquencourt                        Sophia-Antipolis        *)
(*                                                                          *)
(*                                 Coq V6.1                                 *)
(*     *)
(*          Gilles Kahn      *)
(*  Gerard Huet     *)
(*     *)
(*     *)
(*                                                                          *)
(* Acknowledgments: This work was started in July 1993 by F. Prost. Thanks  *)
(* to the Newton Institute for providing an exceptional work environment    *)
(* in Summer 1995. Several developments by E. Ledinot were an inspiration.  *)
(****************************************************************************)

Require Export Relations_1.
Require Export Relations_1_facts.
Require Export Relations_2.
Require Export Relations_2_facts.
Require Export Relations_3.

Theorem Rstar_imp_coherent :
 forall (U:Type) (R:Relation U) (x y:U), Rstar U R x y -> coherent U R x y.
Proof.
intros U R x y H'; red.
exists y; auto with sets.
Qed.
Hint Resolve Rstar_imp_coherent : core.

Theorem coherent_symmetric :
 forall (U:Type) (R:Relation U), Symmetric U (coherent U R).
Proof.
unfold coherent at 1.
intros U R; red.
intros x y H'; elim H'.
intros z H'0; exists z; tauto.
Qed.

Theorem Strong_confluence :
 forall (U:Type) (R:Relation U), Strongly_confluent U R -> Confluent U R.
Proof.
intros U R H'; red.
intro x; redintros a b H'0.
unfold coherent at 1.
generalize b; clear b.
elim H'0; clear H'0.
intros x0 b H'1; exists b; auto with sets.
intros x0 y z H'1 H'2 H'3 b H'4.
  generalize (Lemma1 U R); intro h; lapply h;
    [ intro H'0; generalize (H'0 x0 b); intro h0; lapply h0;
      [ intro H'5; generalize (H'5 y); intro h1; lapply h1;
        [ intro h2; elim h2; intros z0 h3; elim h3; intros H'6 H'7;
          clear h h0 h1 h2 h3
        | clear h h0 h1 ]
      | clear h h0 ]
    | clear h ]; auto with sets.
  generalize (H'3 z0); intro h; lapply h;
    [ intro h0; elim h0; intros z1 h1; elim h1; intros H'8 H'9; clear h h0 h1
    | clear h ]; auto with sets.
  exists z1; splitauto with sets.
  apply Rstar_n with z0; auto with sets.
Qed.

Theorem Strong_confluence_direct :
 forall (U:Type) (R:Relation U), Strongly_confluent U R -> Confluent U R.
Proof.
intros U R H'; red.
intro x; redintros a b H'0.
unfold coherent at 1.
generalize b; clear b.
elim H'0; clear H'0.
intros x0 b H'1; exists b; auto with sets.
intros x0 y z H'1 H'2 H'3 b H'4.
  cut (ex (fun t:U => Rstar U R y t /\ R b t)).
  + intro h; elim h; intros t h0; elim h0; intros H'0 H'5; clear h h0.
    generalize (H'3 t); intro h; lapply h;
      [ intro h0; elim h0; intros z0 h1; elim h1; intros H'6 H'7; clear h h0 h1
      | clear h ]; auto with sets.
    exists z0; split; [ assumption | idtac ].
    apply Rstar_n with t; auto with sets.
  + generalize H'1; generalize y; clear H'1.
    elim H'4.
    * intros x1 y0 H'0; exists y0; auto with sets.
    * intros x1 y0 z0 H'0 H'1 H'5 y1 H'6.
      red in H'.
      generalize (H' x1 y0 y1); intro h; lapply h;
        [ intro H'7; lapply H'7;
          [ intro h0; elim h0; intros z1 h1; elim h1; intros H'8 H'9;
            clear h H'7 h0 h1
          | clear h ]
        | clear h ]; auto with sets.
      generalize (H'5 z1); intro h; lapply h;
        [ intro h0; elim h0; intros t h1; elim h1; intros H'7 H'10; clear h h0 h1
        | clear h ]; auto with sets.
      exists t; splitauto with sets.
      apply Rstar_n with z1; auto with sets.
Qed.

Theorem Noetherian_contains_Noetherian :
 forall (U:Type) (R R':Relation U),
   Noetherian U R -> contains U R R' -> Noetherian U R'.
Proof.
unfold Noetherian at 2.
intros U R R' H' H'0 x.
elim (H' x); auto with sets.
Qed.

Theorem Newman :
 forall (U:Type) (R:Relation U),
   Noetherian U R -> Locally_confluent U R -> Confluent U R.
Proof.
intros U R H' H'0; redintro x.
elim (H' x); unfold confluent.
intros x0 H'1 H'2 y z H'3 H'4.
generalize (Rstar_cases U R x0 y); intro h; lapply h;
 [ intro h0; elim h0;
    [ clear h h0; intro h1
    | intro h1; elim h1; intros u h2; elim h2; intros H'5 H'6;
       clear h h0 h1 h2 ]
 | clear h ]; auto with sets.
elim h1; auto with sets.
generalize (Rstar_cases U R x0 z); intro h; lapply h;
    [ intro h0; elim h0;
      [ clear h h0; intro h1
      | intro h1; elim h1; intros v h2; elim h2; intros H'7 H'8;
        clear h h0 h1 h2 ]
    | clear h ]; auto with sets.
  + elim h1; generalize coherent_symmetric; intro t; red in t; auto with sets.
  + unfold Locally_confluent, locally_confluent, coherent in H'0.
    generalize (H'0 x0 u v); intro h; lapply h;
      [ intro H'9; lapply H'9;
        [ intro h0; elim h0; intros t h1; elim h1; intros H'10 H'11;
          clear h H'9 h0 h1
        | clear h ]
      | clear h ]; auto with sets.
    clear H'0.
    unfold coherent at 1 in H'2.
    generalize (H'2 u); intro h; lapply h;
      [ intro H'0; generalize (H'0 y t); intro h0; lapply h0;
        [ intro H'9; lapply H'9;
          [ intro h1; elim h1; intros y1 h2; elim h2; intros H'12 H'13;
            clear h h0 H'9 h1 h2
          | clear h h0 ]
        | clear h h0 ]
      | clear h ]; auto with sets.
    generalize Rstar_transitive; intro T; red in T.
    generalize (H'2 v); intro h; lapply h;
      [ intro H'9; generalize (H'9 y1 z); intro h0; lapply h0;
        [ intro H'14; lapply H'14;
          [ intro h1; elim h1; intros z1 h2; elim h2; intros H'15 H'16;
            clear h h0 H'14 h1 h2
          | clear h h0 ]
        | clear h h0 ]
      | clear h ]; auto with sets.
    * red; (exists z1; split); auto with sets.
      apply T with y1; auto with sets.
    * apply T with t; auto with sets.
Qed.

¤ Dauer der Verarbeitung: 0.14 Sekunden  (vorverarbeitet)  ¤





Download des
Quellennavigators
Download des
sprechenden Kalenders

in der Quellcodebibliothek suchen




Haftungshinweis

Die Informationen auf dieser Webseite wurden nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit, noch Qualität der bereit gestellten Informationen zugesichert.


Bemerkung:

Die farbliche Syntaxdarstellung ist noch experimentell.


Bot Zugriff



                                                                                                                                                                                                                                                                                                                                                                                                     


Neuigkeiten

     Aktuelles
     Motto des Tages

Software

     Produkte
     Quellcodebibliothek

Aktivitäten

     Artikel über Sicherheit
     Anleitung zur Aktivierung von SSL

Muße

     Gedichte
     Musik
     Bilder

Jenseits des Üblichen ....
    

Besucherstatistik

Besucherstatistik