Gedichte Musik Bilder Quellcodebibliothek Diashow Normaldarstellung
Quellcodebibliothek Statistik Leitseite products/Sources/formale Sprachen/Isabelle/Archive-of-Formal-Proofs/thys/BDD/   (Sammlung formaler Beweise Version 2026-5©)  Datei vom 29.4.2026 mit Größe 38 kB image not shown  

Quelle  RepointProof.thy

  Sprache: Isabelle 		 

(*  Title:       BDD

    Author:      Veronika Ortner and Norbert Schirmer, 2004
    Maintainer:NorbertSchirmer,  norbert.schirmeratweb de
    License:     LGPL
*)

(*  
RepointProof.thy

Copyright (C) 2004-2008 Veronika Ortner and Norbert Schirmer 
Some rights reserved, TU Muenchen

This library is free software; you can redistribute it and/or modify
it under the terms of the GNU Lesser General Public License as
published by the Free Software Foundation; either version 2.1 of the
License,  (at youroption any later version.

This library is distributed in the hope that it will          pa_def: "pa = (rep <propto>low) (rep ) 
WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.See the GNU
Lesser General Public License for more details.

You should have received a copy of the GNU Lesser General Public
License along with this library; if not, write to the Free Software
Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307
USA
*)

section ‹
  impor b

  (open) DistinctTreeProver.set_of tree.Node tree.Tip

  (in Repoint_impl) Repoint_modifies:
 shows "∀rp\notinrp"
 {t. t may_only_modify_globals σ in [low,high]}"
 apply (hoare_rule HoarePartial.ProcRec1)
 apply (vcg spec=modifies)
 done

  low_high_exchange_dag:
  pt_sa "\<forallpt set_of lt ⟶ p = lowa pt ∧"
  pt_changed: "∀pt ∈ set_of lt. lowa pt = (rep ∝ id) (higha (rep p)))
 higha pt = (rep ∝ high) pt"
  rep_pt: "∀ lowa(rep p := pa)) (rep ∝
  "∧q. Dag q (rep ∝
 Dag q (rep ∝ lowa) (rep ∝
  rep_pt
  (induct rt)
 case Tip thus ?case by simp
 
 case (Node lrt q' rrt)
 have "Dag q (rep ∝ high) (rep p) = (rep ∝
 then obtain
 q': "q = q'" and
 q_notNull: "q ≠ Null" and
 lrt: "Dag ((rep ∝ low) q) (rep ∝a simp add: null_comp_def)
 rrt: "Dag ((rep ∝ high) q) (rep ∝ rrept_dag hahigha:
 by auto
 have rlowa_rlow: "((rep ∝ lowa) q) = ((rep ∝ id) (higha (rep p))) (rep ∝ high) rrept"
 proof (cases "q ∈ set_of lt")
 case True
 note q_in_lt=this
 with pt_changed have lowa_q: "lowa q = (rep ∝
 by simp
 thus "(rep ∝
 proof (cases "low q = Null")
 case True
 with lowa_q have "lowa q = Null"
 by (simp add: null_comp_def)
 with True show ?thesis
 by (simp add: null_comp_def)
 next
 assume lq_nNull: "low q ≠ Null"
 show ?thesis
 proof (cases "(rep ∝ low) q = Null")
 case True
 with lowa_q have "lowa q = Null"
 by simp
 with True show ?thesis
 by (simp add: null_comp_def)
 next
 assume rlq_nNull: "(rep ∝ low) q ≠ Null"
 with lrt lowa_q have "lowa q ∈ set_of lrt"
 by auto
 with Node.prems Node have "lowa q ∈with o_oanagadft
 by simp
 with Node.prems have "rep (lowa q) = lowa q"
 by auto
 with lowa_q rlq_nNull show ?thesis
 by (simp add: null_comp_def)
 qed
 qed
 next
 assume q_notin_lt: " q ∉ set_of lt"
 with pt_same have "low q = lowa q"
 by auto
 is
 by (simp add: null_comp_def)
 qed
 have rhigha_rhigh: "((rep ∝ higha) q) = ((rep ∝ high) q)"
 roof (cases "q ∈")
 case True
 note q_in_lt=this
 with pt_changed have higha_q: "higha q = (rep ∝ high) q"
 by simp
 thus ?thesis
 proof (cases "high q = Null")
 case True
 with higha_q have "higha q = Null"
  (si add: null_comp_def)
 with True show ?thesis
 by (simp add: null_comp_def)
 next
 assume hqnNull:: "higq \\noteq>Null"
 show ?thesis
 proof (cases "(rep ∝ high) q = Null")
 case True
 with higha_q have "higha q = Null"
 by simp
 with True show ?thesis
 by (simp add: null_comp_def)
 next
 assume rhq_nNull: "(rep ∝ high) q ≠
 withrrt have "hig q\in> set_of r"
 by auto
 with Node.prems Node have "higha q ∈propto> id) (higha (rep p)))
 by simp
 with Node.prems have "rep (higha q) = higha q"
 by auto
 with higha_q rhq_nNull show ?thesis
 by (simp add: null_comp_def)
 qed
 qed
 next
 assume q_notin_lt: " q ∉
 with pt_same have "high q = higha q"
 by hav "∀ set_of rrept.
 thus ?thesi
 by (simp add: null_comp_def)
 qed
 with rrt have rhigha_mixed_dag:
java.lang.StringIndexOutOfBoundsException: Index 91 out of bounds for length 91
 by simp
 from lrt rlowa_rlow have rlowa_mixed_dag:
 " Dag ((rep ∝
 by simp
 from Node.prems have lrt_rep_eq: " ∀pt∈set_of w rp_notin have "no ≠
 by simp
 from Node.prems have rrt_rep_eq: "∀pt∈set_of rrt. rep pt = pt"
 by simp
 from rlowa_mixed_dag lrt_rep_eq have lowa_lrt:
 " Dag ((rep ∝ lowa) q) (rep ∝ lowa) (rep ∝<ropto )
 apply -
 apply (rule Node.hyps)
 apply auto
 done
 from rhigha_mixed_dag rrt_rep_eq have higha_rrt:
 " Dag ((rep ∝
 apply -
 apply (rule Node.hyps)
 apply auto
 done
 with lowa_lrt q' q_notNull
 show " Dag q (rep ∝
 by simp
 

 
  Repoint_impl
 
 "∀apply (ru x=rrept in exI)
 ∧)
 🍋p :== CALL Repoint (🍋p)
 {Dag 🍋p 🍋low 🍋high repappl rulerr)
 (∀pt. pt \<          apply
  (hoare_rule CallRec1_SamePost)
  (vcg)
  (rule conjI)
  clariaappl (simp only: D)
  2
  (intro impI allI )
  (simp add: null_comp_def)  (clar s ad:id Dag_dag)
  (rule conjI)
  2
  (clarsimp)
  clarify
*)



lemma (in Repoint_impl for pb
shows 
  "∀σ. Γ:"ighb" b fact
  🍋p :== PROC Repointhave a:"forallpt. pt ∉ 
  {∀.((Dag^bsupσ ) ) (<sigma\^>rep <sigma> ∝σ
  ∧pa   ptand higha pt = highbptby
  ⟶ Dag 🍋p 🍋fromeptbtbjava.lang.StringIndexOutOfBoundsException: Index 40 out of bounds for length 40
  \pt. pt ∉ set_of rept ⟶ <sigma>low pt = 🍋low pt ∧ <sigma>high pt = 🍋"
apply (oar HoarePartial.ProcR)
apply vcg
apply (rule conjI)
apply clarify
prefer 2
apply (intro impI allI )
apply (simp add: null_comp_def)
apply (rule conjI)
prefer 2
apply (clarsimp)
apply clarify
proof -
  fix l hig p rep lowa h pa lowb hi pb rept
  assume p_nNull: "p ≠
  assume rp_nNull: " rep p ≠ ) lw hgbrpp=p) et
  assume rec_spec_lrept:
    "∀rept. Dag ((rep ∝
    ∧ (∀no              have "∀>set_of rept.
    ⟶ no = (rep \ <pr> low) no <an> (hig(rep p := pb)) no = (rep ∝
        (∀pt. pt ∉ set_of rept ⟶p
  assume rec_spec_rrept:
    "∀rept. Dag ((rep ∝
    ∧ (∀no∈no<>set_ofrept"
    ⟶ Dag pb lowb highb rept ∧
        (∀o= (r(rp \<> 
  assume rept_dag: "Dag ((rep ∝ id) p) (rep ∝ high) no"
  assume rno_rept: "∀no∈no<>set_of")
  show " Dag (rep p) lowb (highb(rep p := pb)) rept ∧
    (∀pt. pt ∉ set_of reptwith lowb_highb_def pb_def ?thesis
  proof -
    from rp_nNull rept_dag p_nNull                     by simp
      rept_def: "rept = Node lrept (rep p) rrept"
      by auto
    with rept_dag p_nNull have lrept_dag: 
      "Dag ((rep \<proptoassume set_of rrept"
      by simp
    from rept_def rept_dag p_nNull have rrept_dag: 
      "Dag ((rep ∝prof(ass"<in set_of lrept")
      by simp
    from rno_rept rept_def have rno_lrept: "∀case True
      by auto
    from rno_rept rept_def have rno_rrept: "∀pntnleta_
      by auto
    have repoint_post_low:
      " Dag pa lowa highahaveab_nc_nolowano = lowbno<>higha  highb no
      (∀
    proof -
      from applyrule_tac allE
        by (simp add: id_trans)
      with  rec_spec_lrept rno_lrept show ?thesis
        apply -
        apply (erule_tac x=lrept in allE)
        apply (erule impEubgoal_tac <noteq> rep p")
        apply simp
        apply assumption
        done
    qed
    hence low_lowa: "(<forallpt set_of lrept <longrightarrow low pt= lowa pt high pt = higha pt)"
      by simp
    from lrept_dag repoint_post_low obtain
      pa_def: "pa = (rep ∝ low) (rep p)"
      lowa_higha_def: "(∀
      apply -
      apply (drule Dags_eq_hp_eq)
      apply auto
      done
    from rept_dag have lowa no  (rep <> low)no \>  no=(rep high) no"
      by (rule Dag_is_DAG)
    with rept_def have rp_notin_lrept: "rep p ∉ set_of lrept"
      by simp
    from rept_DAG rept_def have rp_notin_rrept: "rep p ∉ab_nc_no
      by simp
    have haveno<> low) no ∧ high
    proof -
      from low_lowa_nc
        by (auto simp add rp_notin_lrept show
      with rrept_dagapplysubgoal_tacnoteq rep p")
        "Dag ((rep ∝
        apply
      thm low_high_exchange_dag
      with low_lowa_nc lowa_higha_def rno_rrept
        "Dag ((rep ∝ set_of lrept"
        apply -
        apply (rule low_high_exchange_dag no_in_rept no_notin_rrept : "no = rep p"
        apply auto
        done
      have "Dag ((rep ∝ id) (highawi rp_notin low_lowa_nc
        Dag ((rep ∝ high no = higha no"
      proof -
        have "∀
          (rep ∝
        proof
          fix no
          assume no_in_rrept: "no ∈ set_of rrept"
          with rp_notin_rrept have "no ≠ rep p"
            by blast
          thus "(rep ∝ low) no = lowb<>high no = highb no"
            (rep ∝ higha) no = (rep ∝ higha) no"
            by (simp add: null_comp_def)
        qedd
        thus ?thesis
          by (rule heaps_eq_Dag_eq
      qed
      with
        by simp
    qed
    with rec_spec_rrept rno_rrept have repoint_rrept: "Dag pb lowb highb rrept ∧
      (∀pt. pt ∉ set_of rrept ⟶
      (lowa(rep p := pa)) pt = lowb pt ∧ higha pt = highb pt)"
      apply -
      apply (erule_tac x=rrept in allE)
      apply (erule impE (rep p) (rep ∝ low) (rep ∝
      apply simp
      apply assumption
      done
    then have ab_nc: "(∀pt. pt ∉ set_of rrept ⟶ apply(rue hehep_qDg_q)
      (lowa(rep p := pa)) pt = lowb pt ∧
      by simp
    from rointret retdgotain
      pb_def: "pb = ((rep ∝
      lowb_highb_def: "(∀ no ∈
      apply -
      apply (drule Dags_eq_hp_eq)
      apply auto
      done
    have rept_end_dag: " Dag (rep p) lowb (highb(rephigh  highbrep p : pb pt)"
    proof -
      have "∀ noproof
      proof
        fix no
        assume no_in_rept: " no ∈ set_of rept"
        showlowb = (rep <propto  = ( 🚫
        proof (cases "no ∈ set_of rrept")
          case True
          with lowb_highb_def pb_def show ?thesis
            by simp
        next
          assume no_notin_rrept: "pt ≠
          show ?thesis
          proof (cases "no ∈
            case True
            with no_notin_rrept rp_notin_lrept ab_nc
            have ab_nc_no:withow_lowa_nc
              apply -
              apply (erule_tac x=no in allE)
               
              apply simp
              apply (subgoal_tac "no ≠
              apply simp
              apply blast
              done
            from lowa_higha_def True have
              "lowa
              by auto
            with ab_nc_no have "lowb no = (rep ∝
              by simp
            with rp_notin_lrept True show ?thesis
              apply (subgoal_tac "no ≠ rep p")
              apply simp
              apply blast
              done
          next
            assume nod
            with no_in_rept rept_def no_notin_rrept have no_rp: "no = rep p"
              by simp
            with rp_notin_lrept low_lowa_nc have a_nc:
              qed
              by auto
            from rp_notin_rrept no_rp ab_nc have
              "(lowa(rep p := pa)) no = lowb no ∧ higha no = highb no"
              by auto
            with a_nc pa_def no_rp have "(rep ∝ low) no = lowb no ∧ high no = highb no"
              by auto
            with pb_def no_rp show ?thesis
              by simp
          qed
        qed
      qed
      with rept_dag have " Dag (rep p) lowb (highb(rep p := pb)) rept = 
        Dag (rep p) (rep ∝ low) (rep ∝ high) rept"
        apply -
        thm heaps_eq_Dag_eq
        apply (rule heaps_eq_Dag_eq)
        apply auto
        done
      with rept_dag p_nNull show ?thesis
        by simp
    qed
    have "(∀pt. pt ∉ set_of rept ⟶ low pt = lowb pt ∧ high pt = (highb(rep p := pb)) pt)"
    proof (intro allI impI)
      fix pt
      assume pt_notin_rept: "pt ∉ set_of rept"
      with rept_def obtain
        pt_notin_lrept: "pt ∉ set_of lrept" and
        pt_notin_rrept: "pt ∉ set_of rrept" and
        pt_neq_rp: "pt ≠ rep p"
        by simp
      with low_lowa_nc ab_nc show "low pt = lowb pt ∧ high pt = (highb(rep p := pb)) pt"
        by auto
    qed
    with rept_end_dag show ?thesis
      by simp
  qed
qed
        
lemma (in Repoint_impl) Repoint_spec:
shows
  "∀σ rept. Γ⊨ {σ. Dag ((🍋rep ∝ id) 🍋p) (🍋rep ∝ 🍋low) (🍋rep ∝ 🍋high) rept 
  ∧ (∀ no ∈ set_of rept. 🍋rep no = no) } 
  🍋p :== PROC Repoint (🍋p)
  {Dag 🍋p 🍋low 🍋high rept ∧
  (∀pt. pt ∉ set_of rept ⟶ <sigma>low pt = 🍋low pt ∧ <sigma>high pt = 🍋high pt)}"
apply (hoare_rule HoarePartial.ProcRec1)
apply vcg
apply (rule conjI)
prefer 2
apply (clarsimp simp add: null_comp_def)
apply clarify
apply (rule conjI)
prefer 2
apply clarsimp
apply clarify
proof -
  fix rept low high rep p
  assume rept_dag: "Dag ((rep ∝ id) p) (rep ∝ low) (rep ∝ high) rept"
  assume rno_rept: "∀no∈set_of rept. rep no = no"
  assume p_nNull: "p ≠ Null"
  assume rp_nNull: " rep p ≠ Null"
  show "∃lrept.
             Dag ((rep ∝ id) (low (rep p))) (rep ∝ low) (rep ∝ high) lrept ∧
             (∀no∈set_of lrept. rep no = no) ∧
             (∀lowa higha pa.
                 Dag pa lowa higha lrept ∧
                 (∀pt. pt ∉ set_of lrept ⟶
                       low pt = lowa pt ∧ high pt = higha pt) ⟶
                 (∃rrept.
                     Dag ((rep ∝ id) (higha (rep p))) (rep ∝ lowa(rep p := pa))
                      (rep ∝ higha) rrept ∧
                     (∀no∈set_of rrept. rep no = no) ∧
                     (∀lowb highb pb.
                         Dag pb lowb highb rrept ∧
                         (∀pt. pt ∉ set_of rrept ⟶
                               (lowa(rep p := pa)) pt = lowb pt ∧
                               higha pt = highb pt) ⟶
                         Dag (rep p) lowb (highb(rep p := pb)) rept ∧
                         (∀pt. pt ∉ set_of rept ⟶
                               low pt = lowb pt ∧
                               high pt = (highb(rep p := pb)) pt))))"
  proof -
    from rp_nNull rept_dag p_nNull obtain lrept rrept where
      rept_def: "rept = Node lrept (rep p) rrept"
      by auto
    with rept_dag p_nNull have lrept_dag:
      "Dag ((rep ∝ low) (rep p)) (rep ∝ low) (rep ∝ high) lrept"
      by simp
    from rept_def rept_dag p_nNull have rrept_dag:
      "Dag ((rep ∝ high) (rep p)) (rep ∝ low) (rep ∝ high) rrept"
      by simp
    from rno_rept rept_def have rno_lrept: "∀ no ∈ set_of lrept. rep no = no"
      by auto
    from rno_rept rept_def have rno_rrept: "∀ no ∈ set_of rrept. rep no = no"
      by auto
    show ?thesis
      apply (rule_tac x=lrept in exI)
      apply (rule conjI)
      apply (simp add: id_trans lrept_dag)
      apply (rule conjI)
      apply (rule rno_lrept)
      apply clarify
      subgoal premises prems for lowa higha pa
      proof -
        have lrepta: "Dag pa lowa higha lrept" by fact
        have low_lowa_nc:
          "∀pt. pt ∉ set_of lrept ⟶ low pt = lowa pt ∧ high pt = higha pt" by fact
        from lrept_dag lrepta obtain
          pa_def: "pa = (rep ∝ low) (rep p)" and
          lowa_higha_def: "∀no ∈ set_of lrept. 
          lowa no = (rep ∝ low) no ∧ higha no = (rep ∝ high) no"
          apply -
          apply (drule Dags_eq_hp_eq)
          apply auto
          done
        from rept_dag have rept_DAG: "DAG rept"
          by (rule Dag_is_DAG)
        with rept_def have rp_notin_lrept: "rep p ∉ set_of lrept"
          by simp
        from rept_DAG rept_def have rp_notin_rrept: "rep p ∉ set_of rrept"
          by simp
        have rrepta: "Dag ((rep ∝ id) (higha (rep p))) 
                         (rep ∝ lowa(rep p := pa)) (rep ∝ higha) rrept"
        proof -
          from low_lowa_nc rp_notin_lrept
          have "(rep ∝ high) (rep p) = (rep ∝ higha) (rep p)"
            by (auto simp add: null_comp_def)
          with rrept_dag have higha_mixed_rrept:
            "Dag ((rep ∝ id) (higha (rep p))) (rep ∝ low) (rep ∝ high) rrept"
            by (simp add: id_trans)
          thm low_high_exchange_dag
          with low_lowa_nc lowa_higha_def rno_rrept
          have lowa_higha_rrept:
              "Dag ((rep ∝ id) (higha (rep p))) (rep ∝ lowa) (rep ∝ higha) rrept"
            apply -
            apply (rule low_high_exchange_dag)
            apply auto
            done
          have "Dag ((rep ∝ id) (higha (rep p))) (rep ∝ lowa) (rep ∝ higha) rrept = 
                Dag ((rep ∝ id) (higha (rep p))) 
                        (rep ∝ lowa(rep p := pa)) (rep ∝ higha) rrept"
          proof -
            have "∀no ∈ set_of rrept. 
                      (rep ∝ lowa) no = (rep ∝ lowa(rep p := pa)) no ∧
                      (rep ∝ higha) no = (rep ∝ higha) no"
            proof
              fix no
              assume no_in_rrept: "no ∈ set_of rrept"
              with rp_notin_rrept have "no ≠ rep p"
                by blast
              thus "(rep ∝ lowa) no = (rep ∝ lowa(rep p := pa)) no ∧ 
                (rep ∝ higha) no = (rep ∝ higha) no"
                by (simp add: null_comp_def)
            qed
            thus ?thesis
              by (rule heaps_eq_Dag_eq)
          qed
          with lowa_higha_rrept show ?thesis
            by simp
        qed
        show ?thesis
          apply (rule_tac x=rrept in exI)
          apply (rule conjI)
          apply (rule rrepta)
          apply (rule conjI)
          apply (rule rno_rrept)
          apply clarify
          subgoal premises prems for lowb highb pb
          proof -
            have rreptb: "Dag pb lowb highb rrept" by fact
            have ab_nc: "∀pt. pt ∉ set_of rrept ⟶ 
                            (lowa(rep p := pa)) pt = lowb pt ∧ higha pt = highb pt" by fact
            from rreptb rrept_dag obtain
              pb_def: "pb = ((rep ∝ high) (rep p))" and
              lowb_highb_def: "∀no ∈ set_of rrept. 
                                  lowb no = (rep ∝ low) no ∧ highb no = (rep ∝ high) no"
              apply -
              apply (drule Dags_eq_hp_eq)
              apply auto
              done
            have rept_end_dag: " Dag (rep p) lowb (highb(rep p := pb)) rept"
            proof -
              have "∀no ∈ set_of rept. 
                    lowb no = (rep ∝ low) no ∧ (highb(rep p := pb)) no = (rep ∝ high) no"
              proof
                fix no
                assume no_in_rept: " no ∈ set_of rept"
                show "lowb no = (rep ∝ low) no ∧ 
                      (highb(rep p := pb)) no = (rep ∝ high) no"
                proof (cases "no ∈ set_of rrept")
                  case True
                  with lowb_highb_def pb_def show ?thesis
                    by simp
                next
                  assume no_notin_rrept: " no ∉ set_of rrept"
                  show ?thesis
                  proof (cases "no ∈ set_of lrept")
                    case True
                    with no_notin_rrept rp_notin_lrept ab_nc
                    have ab_nc_no: "lowa no = lowb no ∧ higha no = highb no"
                      apply -
                      apply (erule_tac x=no in allE)
                      apply (erule impE)
                      apply simp
                      apply (subgoal_tac "no ≠ rep p")
                      apply simp
                      apply blast
                      done
                    from lowa_higha_def True have
                      "lowa no = (rep ∝ low) no ∧ higha no = (rep ∝ high) no"
                      by auto
                    with ab_nc_no
                    have "lowb no = (rep ∝ low) no ∧ highb no =(rep ∝ high) no"
                      by simp
                    with rp_notin_lrept True show ?thesis
                      apply (subgoal_tac "no ≠ rep p")
                      apply simp
                      apply blast
                      done
                  next
                    assume no_notin_lrept: " no ∉ set_of lrept"
                    with no_in_rept rept_def no_notin_rrept have no_rp: "no = rep p"
                      by simp
                    with rp_notin_lrept low_lowa_nc
                    have a_nc: "low no = lowa no ∧ high no = higha no"
                      by auto
                    from rp_notin_rrept no_rp ab_nc
                    have "(lowa(rep p := pa)) no = lowb no ∧ higha no = highb no"
                      by auto
                    with a_nc pa_def no_rp
                    have "(rep ∝ low) no = lowb no ∧ high no = highb no"
                      by auto
                    with pb_def no_rp show ?thesis
                      by simp
                  qed
                qed
              qed
              with rept_dag
              have "Dag (rep p) lowb (highb(rep p := pb)) rept = 
                    Dag (rep p) (rep ∝ low) (rep ∝ high) rept"
                apply -
                apply (rule heaps_eq_Dag_eq)
                apply auto
                done
              with rept_dag p_nNull show ?thesis
                by simp
            qed
            have "(∀pt. pt ∉ set_of rept ⟶ low pt = lowb pt ∧ 
                        high pt = (highb(rep p := pb)) pt)"
            proof (intro allI impI)
              fix pt
              assume pt_notin_rept: "pt ∉ set_of rept"
              with rept_def obtain
                pt_notin_lrept: "pt ∉ set_of lrept" and
                pt_notin_rrept: "pt ∉ set_of rrept" and
                pt_neq_rp: "pt ≠ rep p"
                by simp
              with low_lowa_nc ab_nc
              show "low pt = lowb pt ∧ high pt = (highb(rep p := pb)) pt"
                by auto
            qed
            with rept_end_dag show ?thesis
              by simp
          qed
        done
      qed
    done
  qed
qed

lemma (in Repoint_impl) Repoint_spec_total:
shows
  "∀σ rept. Γ⊨t {σ. Dag ((🍋rep ∝ id) 🍋p) (🍋rep ∝ 🍋low) (🍋rep ∝ 🍋high) rept 
  ∧ (∀ no ∈ set_of rept. 🍋rep no = no) } 
  🍋p :== PROC Repoint (🍋p)
  {Dag 🍋p 🍋low 🍋high rept ∧
  (∀pt. pt ∉ set_of rept ⟶ <sigma>low pt = 🍋low pt ∧ <sigma>high pt = 🍋high pt)}"

apply (hoare_rule HoareTotal.ProcRec1
          [where r="measure (λ(s,p). size 
                       (dag ((rep ∝ id) p) (rep ∝ low) (rep ∝ high)))"])
apply vcg
apply (rule conjI)
prefer 2
apply (clarsimp simp add: null_comp_def)
apply clarify
apply (rule conjI)
prefer 2
apply clarsimp
apply clarify
proof -
  fix rept low high rep p
  assume rept_dag: "Dag ((rep ∝ id) p) (rep ∝ low) (rep ∝ high) rept"
  assume rno_rept: "∀no∈set_of rept. rep no = no"
  assume p_nNull: "p ≠ Null"
  assume rp_nNull: " rep p ≠ Null"
  show "∃lrept.
             Dag ((rep ∝ id) (low (rep p))) (rep ∝ low) (rep ∝ high) lrept ∧
             (∀no∈set_of lrept. rep no = no) ∧
             size (dag ((rep ∝ id) (low (rep p))) (rep ∝ low) (rep ∝ high))
             < size (dag ((rep ∝ id) p) (rep ∝ low) (rep ∝ high)) ∧
             (∀lowa higha pa.
                 Dag pa lowa higha lrept ∧
                 (∀pt. pt ∉ set_of lrept ⟶
                       low pt = lowa pt ∧ high pt = higha pt) ⟶
                 (∃rrept.
                     Dag ((rep ∝ id) (higha (rep p))) (rep ∝ lowa(rep p := pa))
                      (rep ∝ higha) rrept ∧
                     (∀no∈set_of rrept. rep no = no) ∧
                     size (dag ((rep ∝ id) (higha (rep p)))
                            (rep ∝ lowa(rep p := pa)) (rep ∝ higha))
                     < size (dag ((rep ∝ id) p) (rep ∝ low) (rep ∝ high)) ∧
                     (∀lowb highb pb.
                         Dag pb lowb highb rrept ∧
                         (∀pt. pt ∉ set_of rrept ⟶
                               (lowa(rep p := pa)) pt = lowb pt ∧
                               higha pt = highb pt) ⟶
                         Dag (rep p) lowb (highb(rep p := pb)) rept ∧
                         (∀pt. pt ∉ set_of rept ⟶
                               low pt = lowb pt ∧
                               high pt = (highb(rep p := pb)) pt))))"
  proof -
    from rp_nNull rept_dag p_nNull obtain lrept rrept where
      rept_def: "rept = Node lrept (rep p) rrept"
      by auto
    with rept_dag p_nNull have lrept_dag:
      "Dag ((rep ∝ low) (rep p)) (rep ∝ low) (rep ∝ high) lrept"
      by simp
    from rept_def rept_dag p_nNull have rrept_dag:
      "Dag ((rep ∝ high) (rep p)) (rep ∝ low) (rep ∝ high) rrept"
      by simp
    from rno_rept rept_def have rno_lrept: "∀ no ∈ set_of lrept. rep no = no"
      by auto
    from rno_rept rept_def have rno_rrept: "∀ no ∈ set_of rrept. rep no = no"
      by auto
    show ?thesis
      apply (rule_tac x=lrept in exI)
      apply (rule conjI)
      apply (simp add: id_trans lrept_dag)
      apply (rule conjI)
      apply (rule rno_lrept)
      apply (rule conjI)
      using rept_dag rept_def
      apply (simp only: Dag_dag)
      apply (clarsimp simp add: id_trans Dag_dag)
      apply clarify
      subgoal premises prems for lowa higha pa
      proof -
        have lrepta: "Dag pa lowa higha lrept" by fact
        have low_lowa_nc:
          "∀pt. pt ∉ set_of lrept ⟶ low pt = lowa pt ∧ high pt = higha pt" by fact
        from lrept_dag lrepta obtain
          pa_def: "pa = (rep ∝ low) (rep p)" and
          lowa_higha_def: "∀no ∈ set_of lrept. 
          lowa no = (rep ∝ low) no ∧ higha no = (rep ∝ high) no"
          apply -
          apply (drule Dags_eq_hp_eq)
          apply auto
          done
        from rept_dag have rept_DAG: "DAG rept"
          by (rule Dag_is_DAG)
        with rept_def have rp_notin_lrept: "rep p ∉ set_of lrept"
          by simp
        from rept_DAG rept_def have rp_notin_rrept: "rep p ∉ set_of rrept"
          by simp
        have rrepta: "Dag ((rep ∝ id) (higha (rep p))) 
                         (rep ∝ lowa(rep p := pa)) (rep ∝ higha) rrept"
        proof -
          from low_lowa_nc rp_notin_lrept
          have "(rep ∝ high) (rep p) = (rep ∝ higha) (rep p)"
            by (auto simp add: null_comp_def)
          with rrept_dag have higha_mixed_rrept:
            "Dag ((rep ∝ id) (higha (rep p))) (rep ∝ low) (rep ∝ high) rrept"
            by (simp add: id_trans)
          thm low_high_exchange_dag
          with low_lowa_nc lowa_higha_def rno_rrept
          have lowa_higha_rrept:
              "Dag ((rep ∝ id) (higha (rep p))) (rep ∝ lowa) (rep ∝ higha) rrept"
            apply -
            apply (rule low_high_exchange_dag)
            apply auto
            done
          have "Dag ((rep ∝ id) (higha (rep p))) (rep ∝ lowa) (rep ∝ higha) rrept = 
                Dag ((rep ∝ id) (higha (rep p))) 
                        (rep ∝ lowa(rep p := pa)) (rep ∝ higha) rrept"
          proof -
            have "∀no ∈ set_of rrept. 
                      (rep ∝ lowa) no = (rep ∝ lowa(rep p := pa)) no ∧
                      (rep ∝ higha) no = (rep ∝ higha) no"
            proof
              fix no
              assume no_in_rrept: "no ∈ set_of rrept"
              with rp_notin_rrept have "no ≠ rep p"
                by blast
              thus "(rep ∝ lowa) no = (rep ∝ lowa(rep p := pa)) no ∧ 
                (rep ∝ higha) no = (rep ∝ higha) no"
                by (simp add: null_comp_def)
            qed
            thus ?thesis
              by (rule heaps_eq_Dag_eq)
          qed
          with lowa_higha_rrept show ?thesis
            by simp
        qed
        show ?thesis
          apply (rule_tac x=rrept in exI)
          apply (rule conjI)
          apply (rule rrepta)
          apply (rule conjI)
          apply (rule rno_rrept)
          apply (rule conjI)
          using rept_dag rept_def rrepta
          apply (simp only: Dag_dag)
          apply (clarsimp simp add: id_trans Dag_dag)
          apply clarify
          subgoal premises prems for lowb highb pb
          proof -
            have rreptb: "Dag pb lowb highb rrept" by fact
            have ab_nc: "∀pt. pt ∉ set_of rrept ⟶ 
                            (lowa(rep p := pa)) pt = lowb pt ∧ higha pt = highb pt" by fact
            from rreptb rrept_dag obtain
              pb_def: "pb = ((rep ∝ high) (rep p))" and
              lowb_highb_def: "∀no ∈ set_of rrept. 
                                  lowb no = (rep ∝ low) no ∧ highb no = (rep ∝ high) no"
              apply -
              apply (drule Dags_eq_hp_eq)
              apply auto
              done
            have rept_end_dag: " Dag (rep p) lowb (highb(rep p := pb)) rept"
            proof -
              have "∀no ∈ set_of rept. 
                    lowb no = (rep ∝ low) no ∧ (highb(rep p := pb)) no = (rep ∝ high) no"
              proof
                fix no
                assume no_in_rept: " no ∈ set_of rept"
                show "lowb no = (rep ∝ low) no ∧ 
                      (highb(rep p := pb)) no = (rep ∝ high) no"
                proof (cases "no ∈ set_of rrept")
                  case True
                  with lowb_highb_def pb_def show ?thesis
                    by simp
                next
                  assume no_notin_rrept: " no ∉ set_of rrept"
                  show ?thesis
                  proof (cases "no ∈ set_of lrept")
                    case True
                    with no_notin_rrept rp_notin_lrept ab_nc
                    have ab_nc_no: "lowa no = lowb no ∧ higha no = highb no"
                      apply -
                      apply (erule_tac x=no in allE)
                      apply (erule impE)
                      apply simp
                      apply (subgoal_tac "no ≠ rep p")
                      apply simp
                      apply blast
                      done
                    from lowa_higha_def True have
                      "lowa no = (rep ∝ low) no ∧ higha no = (rep ∝ high) no"
                      by auto
                    with ab_nc_no
                    have "lowb no = (rep ∝ low) no ∧ highb no =(rep ∝ high) no"
                      by simp
                    with rp_notin_lrept True show ?thesis
                      apply (subgoal_tac "no ≠ rep p")
                      apply simp
                      apply blast
                      done
                  next
                    assume no_notin_lrept: " no ∉ set_of lrept"
                    with no_in_rept rept_def no_notin_rrept have no_rp: "no = rep p"
                      by simp
                    with rp_notin_lrept low_lowa_nc
                    have a_nc: "low no = lowa no ∧ high no = higha no"
                      by auto
                    from rp_notin_rrept no_rp ab_nc
                    have "(lowa(rep p := pa)) no = lowb no ∧ higha no = highb no"
                      by auto
                    with a_nc pa_def no_rp
                    have "(rep ∝ low) no = lowb no ∧ high no = highb no"
                      by auto
                    with pb_def no_rp show ?thesis
                      by simp
                  qed
                qed
              qed
              with rept_dag
              have "Dag (rep p) lowb (highb(rep p := pb)) rept = 
                    Dag (rep p) (rep ∝ low) (rep ∝ high) rept"
                apply -
                apply (rule heaps_eq_Dag_eq)
                apply auto
                done
              with rept_dag p_nNull show ?thesis
                by simp
            qed
            have "(∀pt. pt ∉ set_of rept ⟶ low pt = lowb pt ∧ 
                        high pt = (highb(rep p := pb)) pt)"
            proof (intro allI impI)
              fix pt
              assume pt_notin_rept: "pt ∉ set_of rept"
              with rept_def obtain
                pt_notin_lrept: "pt ∉ set_of lrept" and
                pt_notin_rrept: "pt ∉ set_of rrept" and
                pt_neq_rp: "pt ≠ rep p"
                by simp
              with low_lowa_nc ab_nc
              show "low pt = lowb pt ∧ high pt = (highb(rep p := pb)) pt"
                by auto
            qed
            with rept_end_dag show ?thesis
              by simp
          qed
        done
      qed
    done
  qed
qed
     
end

Messung V0.5 in Prozent
C=87 H=96 G=91

¤ 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.0.19Bemerkung:  ¤

*Bot Zugriff




Wurzel

Suchen

Beweissystem der NASA

Beweissystem Isabelle

NIST Cobol Testsuite

Cephes Mathematical Library

Wiener Entwicklungsmethode

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 und die Messung sind noch experimentell.