products/Sources/formale Sprachen/VDM/VDMPP/concfactorialPP/  image not shown  

Quellcode-Bibliothek

© Kompilation durch diese Firma

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

Datei: rewrite_hol_proof.ML   Sprache: Unknown

(*  Title:      HOL/Tools/rewrite_hol_proof.ML
    Author:     Stefan Berghofer, TU Muenchen

Rewrite rules for HOL proofs.
*)

signature REWRITE_HOL_PROOF =
sig
  val rews: (Proofterm.proof * Proofterm.proof) list
  val elim_cong: typ list -> term option list -> Proofterm.proof -> (Proofterm.proof * Proofterm.proof) option
end;

structure Rewrite_HOL_Proof : REWRITE_HOL_PROOF =
struct

val rews =
  map (apply2 (Proof_Syntax.proof_of_term \<^theory> true) o Logic.dest_equals o
    Logic.varify_global o Proof_Syntax.read_term \<^theory> true propT o Syntax.implode_input)

  (** eliminate meta-equality rules **)

  [\<open>(equal_elim \<cdot> x1 \<cdot> x2 \<bullet>
      (combination \<cdot> TYPE('T1) \ TYPE('T2) \<cdot> Trueprop \<cdot> x3 \<cdot> A \<cdot> B \<bullet>
        (axm.reflexive \<cdot> TYPE('T3) \ x4) \ prf1)) \
    (iffD1 \<cdot> A \<cdot> B \<bullet>
      (meta_eq_to_obj_eq \<cdot> TYPE(bool) \<cdot> A \<cdot> B \<bullet> arity_type_bool \<bullet> prf1))\<close>,

   \<open>(equal_elim \<cdot> x1 \<cdot> x2 \<bullet> (axm.symmetric \<cdot> TYPE('T1) \ x3 \ x4 \
      (combination \<cdot> TYPE('T2) \ TYPE('T3) \<cdot> Trueprop \<cdot> x5 \<cdot> A \<cdot> B \<bullet>
        (axm.reflexive \<cdot> TYPE('T4) \ x6) \ prf1))) \
    (iffD2 \<cdot> A \<cdot> B \<bullet>
      (meta_eq_to_obj_eq \<cdot> TYPE(bool) \<cdot> A \<cdot> B \<bullet> arity_type_bool \<bullet> prf1))\<close>,

   \<open>(meta_eq_to_obj_eq \<cdot> TYPE('U) \ x1 \ x2 \ prfU \
      (combination \<cdot> TYPE('T) \ TYPE('U) \<cdot> f \<cdot> g \<cdot> x \<cdot> y \<bullet> prf1 \<bullet> prf2)) \<equiv>
    (cong \<cdot> TYPE('T) \ TYPE('U) \<cdot> f \<cdot> g \<cdot> x \<cdot> y \<bullet>
      (Pure.PClass type_class \<cdot> TYPE('T)) \ prfU \
      (meta_eq_to_obj_eq \<cdot> TYPE('T \ 'U) \<cdot> f \<cdot> g \<bullet> (Pure.PClass type_class \<cdot> TYPE('T \ 'U)) \<bullet> prf1) \<bullet>
      (meta_eq_to_obj_eq \<cdot> TYPE('T) \ x \ y \ (Pure.PClass type_class \ TYPE('T)) \<bullet> prf2))\<close>,

   \<open>(meta_eq_to_obj_eq \<cdot> TYPE('T) \ x1 \ x2 \ prfT \
      (axm.transitive \<cdot> TYPE('T) \ x \ y \ z \ prf1 \ prf2)) \
    (HOL.trans \<cdot> TYPE('T) \ x \ y \ z \ prfT \
      (meta_eq_to_obj_eq \<cdot> TYPE('T) \ x \ y \ prfT \ prf1) \
      (meta_eq_to_obj_eq \<cdot> TYPE('T) \ y \ z \ prfT \ prf2))\,

   \<open>(meta_eq_to_obj_eq \<cdot> TYPE('T) \ x \ x \ prfT \ (axm.reflexive \ TYPE('T) \<cdot> x)) \<equiv>
    (HOL.refl \<cdot> TYPE('T) \ x \ prfT)\,

   \<open>(meta_eq_to_obj_eq \<cdot> TYPE('T) \ x \ y \ prfT \
      (axm.symmetric \<cdot> TYPE('T) \ x \ y \ prf)) \
    (sym \<cdot> TYPE('T) \ x \ y \ prfT \ (meta_eq_to_obj_eq \ TYPE('T) \<cdot> x \<cdot> y \<bullet> prfT \<bullet> prf))\<close>,

   \<open>(meta_eq_to_obj_eq \<cdot> TYPE('T \ 'U) \<cdot> x1 \<cdot> x2 \<bullet> prfTU \<bullet>
      (abstract_rule \<cdot> TYPE('T) \ TYPE('U) \<cdot> f \<cdot> g \<bullet> prf)) \<equiv>
    (ext \<cdot> TYPE('T) \ TYPE('U) \<cdot> f \<cdot> g \<bullet>
      (Pure.PClass type_class \<cdot> TYPE('T)) \ (Pure.PClass type_class \ TYPE('U)) \<bullet>
      (\<^bold>\<lambda>(x::'T). meta_eq_to_obj_eq \ TYPE('U) \<cdot> f x \<cdot> g x \<bullet>
         (Pure.PClass type_class \<cdot> TYPE('U)) \ (prf \ x)))\,

   \<open>(meta_eq_to_obj_eq \<cdot> TYPE('T) \ x \ y \ prfT \
      (eq_reflection \<cdot> TYPE('T) \ x \ y \ prfT \ prf)) \ prf\,

   \<open>(meta_eq_to_obj_eq \<cdot> TYPE('T) \ x1 \ x2 \ prfT \ (equal_elim \ x3 \ x4 \
      (combination \<cdot> TYPE('T) \ TYPE(prop) \ x7 \ x8 \ C \ D \
        (combination \<cdot> TYPE('T) \ TYPE('T3) \<cdot> (\<equiv>) \<cdot> (\<equiv>) \<cdot> A \<cdot> B \<bullet>
          (axm.reflexive \<cdot> TYPE('T4) \ (\)) \ prf1) \ prf2) \ prf3)) \
    (iffD1 \<cdot> A = C \<cdot> B = D \<bullet>
      (cong \<cdot> TYPE('T) \ TYPE(bool) \ (=) A \ (=) B \ C \ D \
        prfT \<bullet> arity_type_bool \<bullet>
        (cong \<cdot> TYPE('T) \ TYPE('T\<Rightarrow>bool) \<cdot>
          ((=) :: 'T\'T\<Rightarrow>bool) \<cdot> ((=) :: 'T\'T\<Rightarrow>bool) \<cdot> A \<cdot> B \<bullet>
          prfT \<bullet> (Pure.PClass type_class \<cdot> TYPE('T\bool)) \
          (HOL.refl \<cdot> TYPE('T\'T\<Rightarrow>bool) \<cdot> ((=) :: 'T\'T\<Rightarrow>bool) \<bullet>
             (Pure.PClass type_class \<cdot> TYPE('T\'T\<Rightarrow>bool))) \<bullet>
          (meta_eq_to_obj_eq \<cdot> TYPE('T) \ A \ B \ prfT \ prf1)) \
        (meta_eq_to_obj_eq \<cdot> TYPE('T) \ C \ D \ prfT \ prf2)) \
      (meta_eq_to_obj_eq \<cdot> TYPE('T) \ A \ C \ prfT \ prf3))\,

   \<open>(meta_eq_to_obj_eq \<cdot> TYPE('T) \ x1 \ x2 \ prfT \ (equal_elim \ x3 \ x4 \
      (axm.symmetric \<cdot> TYPE('T2) \ x5 \ x6 \
        (combination \<cdot> TYPE('T) \ TYPE(prop) \ x7 \ x8 \ C \ D \
          (combination \<cdot> TYPE('T) \ TYPE('T3) \<cdot> (\<equiv>) \<cdot> (\<equiv>) \<cdot> A \<cdot> B \<bullet>
            (axm.reflexive \<cdot> TYPE('T4) \ (\)) \ prf1) \ prf2)) \ prf3)) \
    (iffD2 \<cdot> A = C \<cdot> B = D \<bullet>
      (cong \<cdot> TYPE('T) \ TYPE(bool) \ (=) A \ (=) B \ C \ D \
        prfT \<bullet> arity_type_bool \<bullet>
        (cong \<cdot> TYPE('T) \ TYPE('T\<Rightarrow>bool) \<cdot>
          ((=) :: 'T\'T\<Rightarrow>bool) \<cdot> ((=) :: 'T\'T\<Rightarrow>bool) \<cdot> A \<cdot> B \<bullet>
          prfT \<bullet> (Pure.PClass type_class \<cdot> TYPE('T\bool)) \
          (HOL.refl \<cdot> TYPE('T\'T\<Rightarrow>bool) \<cdot> ((=) :: 'T\'T\<Rightarrow>bool) \<bullet>
             (Pure.PClass type_class \<cdot> TYPE('T\'T\<Rightarrow>bool))) \<bullet>
          (meta_eq_to_obj_eq \<cdot> TYPE('T) \ A \ B \ prfT \ prf1)) \
        (meta_eq_to_obj_eq \<cdot> TYPE('T) \ C \ D \ prfT \ prf2)) \
      (meta_eq_to_obj_eq \<cdot> TYPE('T) \ B \ D \ prfT \ prf3))\,

   (** rewriting on bool: insert proper congruence rules for logical connectives **)

   (* All *)

   \<open>(iffD1 \<cdot> All P \<cdot> All Q \<bullet> (cong \<cdot> TYPE('T1) \ TYPE('T2) \<cdot> All \<cdot> All \<cdot> P \<cdot> Q \<bullet> prfT1 \<bullet> prfT2 \<bullet>
      (HOL.refl \<cdot> TYPE('T3) \ x1 \ prfT3) \
      (ext \<cdot> TYPE('a) \ TYPE(bool) \ x2 \ x3 \ prfa \ prfb \ prf)) \ prf') \<equiv>
    (allI \<cdot> TYPE('a) \ Q \ prfa \
      (\<^bold>\<lambda>x.
          iffD1 \<cdot> P x \<cdot> Q x \<bullet> (prf \<cdot> x) \<bullet>
           (spec \<cdot> TYPE('a) \ P \ x \ prfa \ prf')))\<close>,

   \<open>(iffD2 \<cdot> All P \<cdot> All Q \<bullet> (cong \<cdot> TYPE('T1) \ TYPE('T2) \<cdot> All \<cdot> All \<cdot> P \<cdot> Q \<bullet> prfT1 \<bullet> prfT2 \<bullet>
      (HOL.refl \<cdot> TYPE('T3) \ x1 \ prfT3) \
      (ext \<cdot> TYPE('a) \ TYPE(bool) \ x2 \ x3 \ prfa \ prfb \ prf)) \ prf') \<equiv>
    (allI \<cdot> TYPE('a) \ P \ prfa \
      (\<^bold>\<lambda>x.
          iffD2 \<cdot> P x \<cdot> Q x \<bullet> (prf \<cdot> x) \<bullet>
           (spec \<cdot> TYPE('a) \ Q \ x \ prfa \ prf')))\<close>,

   (* Ex *)

   \<open>(iffD1 \<cdot> Ex P \<cdot> Ex Q \<bullet> (cong \<cdot> TYPE('T1) \ TYPE('T2) \<cdot> Ex \<cdot> Ex \<cdot> P \<cdot> Q \<bullet> prfT1 \<bullet> prfT2 \<bullet>
      (HOL.refl \<cdot> TYPE('T3) \ x1 \ prfT3) \
      (ext \<cdot> TYPE('a) \ TYPE(bool) \ x2 \ x3 \ prfa \ prfb \ prf)) \ prf') \<equiv>
    (exE \<cdot> TYPE('a) \ P \ \x. Q x \ prfa \ prf' \<bullet>
      (\<^bold>\<lambda>x H : P x.
          exI \<cdot> TYPE('a) \ Q \ x \ prfa \
           (iffD1 \<cdot> P x \<cdot> Q x \<bullet> (prf \<cdot> x) \<bullet> H)))\<close>,

   \<open>(iffD2 \<cdot> Ex P \<cdot> Ex Q \<bullet> (cong \<cdot> TYPE('T1) \ TYPE('T2) \<cdot> Ex \<cdot> Ex \<cdot> P \<cdot> Q \<bullet> prfT1 \<bullet> prfT2 \<bullet>
      (HOL.refl \<cdot> TYPE('T3) \ x1 \ prfT3) \
      (ext \<cdot> TYPE('a) \ TYPE(bool) \ x2 \ x3 \ prfa \ prfb \ prf)) \ prf') \<equiv>
    (exE \<cdot> TYPE('a) \ Q \ \x. P x \ prfa \ prf' \<bullet>
      (\<^bold>\<lambda>x H : Q x.
          exI \<cdot> TYPE('a) \ P \ x \ prfa \
           (iffD2 \<cdot> P x \<cdot> Q x \<bullet> (prf \<cdot> x) \<bullet> H)))\<close>,

   (* \<and> *)

   \<open>(iffD1 \<cdot> A \<and> C \<cdot> B \<and> D \<bullet> (cong \<cdot> TYPE('T1) \ TYPE('T2) \<cdot> x1 \<cdot> x2 \<cdot> C \<cdot> D \<bullet> prfT1 \<bullet> prfT2 \<bullet>
      (cong \<cdot> TYPE('T3) \ TYPE('T4) \<cdot> (\<and>) \<cdot> (\<and>) \<cdot> A \<cdot> B \<bullet> prfT3 \<bullet> prfT4 \<bullet>
        (HOL.refl \<cdot> TYPE('T5) \ (\) \ prfT5) \ prf1) \ prf2) \ prf3) \
    (conjI \<cdot> B \<cdot> D \<bullet>
      (iffD1 \<cdot> A \<cdot> B \<bullet> prf1 \<bullet> (conjunct1 \<cdot> A \<cdot> C \<bullet> prf3)) \<bullet>
      (iffD1 \<cdot> C \<cdot> D \<bullet> prf2 \<bullet> (conjunct2 \<cdot> A \<cdot> C \<bullet> prf3)))\<close>,

   \<open>(iffD2 \<cdot> A \<and> C \<cdot> B \<and> D \<bullet> (cong \<cdot> TYPE('T1) \ TYPE('T2) \<cdot> x1 \<cdot> x2 \<cdot> C \<cdot> D \<bullet> prfT1 \<bullet> prfT2 \<bullet>
      (cong \<cdot> TYPE('T3) \ TYPE('T4) \<cdot> (\<and>) \<cdot> (\<and>) \<cdot> A \<cdot> B \<bullet> prfT3 \<bullet> prfT4 \<bullet>
        (HOL.refl \<cdot> TYPE('T5) \ (\) \ prfT5) \ prf1) \ prf2) \ prf3) \
    (conjI \<cdot> A \<cdot> C \<bullet>
      (iffD2 \<cdot> A \<cdot> B \<bullet> prf1 \<bullet> (conjunct1 \<cdot> B \<cdot> D \<bullet> prf3)) \<bullet>
      (iffD2 \<cdot> C \<cdot> D \<bullet> prf2 \<bullet> (conjunct2 \<cdot> B \<cdot> D \<bullet> prf3)))\<close>,

   \<open>(cong \<cdot> TYPE(bool) \<cdot> TYPE(bool) \<cdot> (\<and>) A \<cdot> (\<and>) A \<cdot> B \<cdot> C \<bullet> prfb \<bullet> prfb \<bullet>
      (HOL.refl \<cdot> TYPE(bool\<Rightarrow>bool) \<cdot> (\<and>) A \<bullet> prfbb)) \<equiv>
    (cong \<cdot> TYPE(bool) \<cdot> TYPE(bool) \<cdot> (\<and>) A \<cdot> (\<and>) A \<cdot> B \<cdot> C \<bullet> prfb \<bullet> prfb \<bullet>
      (cong \<cdot> TYPE(bool) \<cdot> TYPE(bool\<Rightarrow>bool) \<cdot>
        ((\<and>) :: bool\<Rightarrow>bool\<Rightarrow>bool) \<cdot> ((\<and>) :: bool\<Rightarrow>bool\<Rightarrow>bool) \<cdot> A \<cdot> A \<bullet>
          prfb \<bullet> prfbb \<bullet>
          (HOL.refl \<cdot> TYPE(bool\<Rightarrow>bool\<Rightarrow>bool) \<cdot> ((\<and>) :: bool\<Rightarrow>bool\<Rightarrow>bool) \<bullet>
             (Pure.PClass type_class \<cdot> TYPE(bool\<Rightarrow>bool\<Rightarrow>bool))) \<bullet>
          (HOL.refl \<cdot> TYPE(bool) \<cdot> A \<bullet> prfb)))\<close>,

   (* \<or> *)

   \<open>(iffD1 \<cdot> A \<or> C \<cdot> B \<or> D \<bullet> (cong \<cdot> TYPE('T1) \ TYPE('T2) \<cdot> x1 \<cdot> x2 \<cdot> C \<cdot> D \<bullet> prfT1 \<bullet> prfT2 \<bullet>
      (cong \<cdot> TYPE('T3) \ TYPE('T4) \<cdot> (\<or>) \<cdot> (\<or>) \<cdot> A \<cdot> B \<bullet> prfT3 \<bullet> prfT4 \<bullet>
        (HOL.refl \<cdot> TYPE('T5) \ (\) \ prfT5) \ prf1) \ prf2) \ prf3) \
    (disjE \<cdot> A \<cdot> C \<cdot> B \<or> D \<bullet> prf3 \<bullet>
      (\<^bold>\<lambda>H : A. disjI1 \<cdot> B \<cdot> D \<bullet> (iffD1 \<cdot> A \<cdot> B \<bullet> prf1 \<bullet> H)) \<bullet>
      (\<^bold>\<lambda>H : C. disjI2 \<cdot> D \<cdot> B \<bullet> (iffD1 \<cdot> C \<cdot> D \<bullet> prf2 \<bullet> H)))\<close>,

   \<open>(iffD2 \<cdot> A \<or> C \<cdot> B \<or> D \<bullet> (cong \<cdot> TYPE('T1) \ TYPE('T2) \<cdot> x1 \<cdot> x2 \<cdot> C \<cdot> D \<bullet> prfT1 \<bullet> prfT2 \<bullet>
      (cong \<cdot> TYPE('T3) \ TYPE('T4) \<cdot> (\<or>) \<cdot> (\<or>) \<cdot> A \<cdot> B \<bullet> prfT3 \<bullet> prfT4 \<bullet>
        (HOL.refl \<cdot> TYPE('T5) \ (\) \ prfT5) \ prf1) \ prf2) \ prf3) \
    (disjE \<cdot> B \<cdot> D \<cdot> A \<or> C \<bullet> prf3 \<bullet>
      (\<^bold>\<lambda>H : B. disjI1 \<cdot> A \<cdot> C \<bullet> (iffD2 \<cdot> A \<cdot> B \<bullet> prf1 \<bullet> H)) \<bullet>
      (\<^bold>\<lambda>H : D. disjI2 \<cdot> C \<cdot> A \<bullet> (iffD2 \<cdot> C \<cdot> D \<bullet> prf2 \<bullet> H)))\<close>,

   \<open>(cong \<cdot> TYPE(bool) \<cdot> TYPE(bool) \<cdot> (\<or>) A \<cdot> (\<or>) A \<cdot> B \<cdot> C \<bullet> prfb \<bullet> prfb \<bullet>
      (HOL.refl \<cdot> TYPE(bool\<Rightarrow>bool) \<cdot> (\<or>) A \<bullet> prfbb)) \<equiv>
    (cong \<cdot> TYPE(bool) \<cdot> TYPE(bool) \<cdot> (\<or>) A \<cdot> (\<or>) A \<cdot> B \<cdot> C \<bullet> prfb \<bullet> prfb \<bullet>
      (cong \<cdot> TYPE(bool) \<cdot> TYPE(bool\<Rightarrow>bool) \<cdot>
        ((\<or>) :: bool\<Rightarrow>bool\<Rightarrow>bool) \<cdot> ((\<or>) :: bool\<Rightarrow>bool\<Rightarrow>bool) \<cdot> A \<cdot> A \<bullet>
          prfb \<bullet> prfbb \<bullet>
          (HOL.refl \<cdot> TYPE(bool\<Rightarrow>bool\<Rightarrow>bool) \<cdot> ((\<or>) :: bool\<Rightarrow>bool\<Rightarrow>bool) \<bullet>
             (Pure.PClass type_class \<cdot> TYPE(bool\<Rightarrow>bool\<Rightarrow>bool))) \<bullet>
          (HOL.refl \<cdot> TYPE(bool) \<cdot> A \<bullet> prfb)))\<close>,

   (* \<longrightarrow> *)

   \<open>(iffD1 \<cdot> A \<longrightarrow> C \<cdot> B \<longrightarrow> D \<bullet> (cong \<cdot> TYPE('T1) \ TYPE('T2) \<cdot> x1 \<cdot> x2 \<cdot> C \<cdot> D \<bullet> prfT1 \<bullet> prfT2 \<bullet>
      (cong \<cdot> TYPE('T3) \ TYPE('T4) \<cdot> (\<longrightarrow>) \<cdot> (\<longrightarrow>) \<cdot> A \<cdot> B \<bullet> prfT3 \<bullet> prfT4 \<bullet>
        (HOL.refl \<cdot> TYPE('T5) \ (\) \ prfT5) \ prf1) \ prf2) \ prf3) \
    (impI \<cdot> B \<cdot> D \<bullet> (\<^bold>\<lambda>H: B. iffD1 \<cdot> C \<cdot> D \<bullet> prf2 \<bullet>
      (mp \<cdot> A \<cdot> C \<bullet> prf3 \<bullet> (iffD2 \<cdot> A \<cdot> B \<bullet> prf1 \<bullet> H))))\<close>,

   \<open>(iffD2 \<cdot> A \<longrightarrow> C \<cdot> B \<longrightarrow> D \<bullet> (cong \<cdot> TYPE('T1) \ TYPE('T2) \<cdot> x1 \<cdot> x2 \<cdot> C \<cdot> D \<bullet> prfT1 \<bullet> prfT2 \<bullet>
      (cong \<cdot> TYPE('T3) \ TYPE('T4) \<cdot> (\<longrightarrow>) \<cdot> (\<longrightarrow>) \<cdot> A \<cdot> B \<bullet> prfT3 \<bullet> prfT4 \<bullet>
        (HOL.refl \<cdot> TYPE('T5) \ (\) \ prfT5) \ prf1) \ prf2) \ prf3) \
    (impI \<cdot> A \<cdot> C \<bullet> (\<^bold>\<lambda>H: A. iffD2 \<cdot> C \<cdot> D \<bullet> prf2 \<bullet>
      (mp \<cdot> B \<cdot> D \<bullet> prf3 \<bullet> (iffD1 \<cdot> A \<cdot> B \<bullet> prf1 \<bullet> H))))\<close>,

   \<open>(cong \<cdot> TYPE(bool) \<cdot> TYPE(bool) \<cdot> (\<longrightarrow>) A \<cdot> (\<longrightarrow>) A \<cdot> B \<cdot> C \<bullet> prfb \<bullet> prfb \<bullet>
      (HOL.refl \<cdot> TYPE(bool\<Rightarrow>bool) \<cdot> (\<longrightarrow>) A \<bullet> prfbb)) \<equiv>
    (cong \<cdot> TYPE(bool) \<cdot> TYPE(bool) \<cdot> (\<longrightarrow>) A \<cdot> (\<longrightarrow>) A \<cdot> B \<cdot> C \<bullet> prfb \<bullet> prfb \<bullet>
      (cong \<cdot> TYPE(bool) \<cdot> TYPE(bool\<Rightarrow>bool) \<cdot>
        ((\<longrightarrow>) :: bool\<Rightarrow>bool\<Rightarrow>bool) \<cdot> ((\<longrightarrow>) :: bool\<Rightarrow>bool\<Rightarrow>bool) \<cdot> A \<cdot> A \<bullet>
          prfb \<bullet> prfbb \<bullet>
          (HOL.refl \<cdot> TYPE(bool\<Rightarrow>bool\<Rightarrow>bool) \<cdot> ((\<longrightarrow>) :: bool\<Rightarrow>bool\<Rightarrow>bool) \<bullet>
             (Pure.PClass type_class \<cdot> TYPE(bool\<Rightarrow>bool\<Rightarrow>bool))) \<bullet>
          (HOL.refl \<cdot> TYPE(bool) \<cdot> A \<bullet> prfb)))\<close>,

   (* \<not> *)

   \<open>(iffD1 \<cdot> \<not> P \<cdot> \<not> Q \<bullet> (cong \<cdot> TYPE('T1) \ TYPE('T2) \<cdot> Not \<cdot> Not \<cdot> P \<cdot> Q \<bullet> prfT1 \<bullet> prfT2 \<bullet>
      (HOL.refl \<cdot> TYPE('T3) \ Not \ prfT3) \ prf1) \ prf2) \
    (notI \<cdot> Q \<bullet> (\<^bold>\<lambda>H: Q.
      notE \<cdot> P \<cdot> False \<bullet> prf2 \<bullet> (iffD2 \<cdot> P \<cdot> Q \<bullet> prf1 \<bullet> H)))\<close>,

   \<open>(iffD2 \<cdot> \<not> P \<cdot> \<not> Q \<bullet> (cong \<cdot> TYPE('T1) \ TYPE('T2) \<cdot> Not \<cdot> Not \<cdot> P \<cdot> Q \<bullet> prfT1 \<bullet> prfT2 \<bullet>
      (HOL.refl \<cdot> TYPE('T3) \ Not \ prfT3) \ prf1) \ prf2) \
    (notI \<cdot> P \<bullet> (\<^bold>\<lambda>H: P.
      notE \<cdot> Q \<cdot> False \<bullet> prf2 \<bullet> (iffD1 \<cdot> P \<cdot> Q \<bullet> prf1 \<bullet> H)))\<close>,

   (* = *)

   \<open>(iffD1 \<cdot> B \<cdot> D \<bullet>
      (iffD1 \<cdot> A = C \<cdot> B = D \<bullet> (cong \<cdot> TYPE(bool) \<cdot> TYPE('T1) \ x1 \ x2 \ C \ D \ prfb \ prfT1 \
        (cong \<cdot> TYPE(bool) \<cdot> TYPE('T2) \ (=) \ (=) \ A \ B \ prfb \ prfT2 \
          (HOL.refl \<cdot> TYPE('T3) \ (=) \ prfT3) \ prf1) \ prf2) \ prf3) \ prf4) \
    (iffD1 \<cdot> C \<cdot> D \<bullet> prf2 \<bullet>
      (iffD1 \<cdot> A \<cdot> C \<bullet> prf3 \<bullet> (iffD2 \<cdot> A \<cdot> B \<bullet> prf1 \<bullet> prf4)))\<close>,

   \<open>(iffD2 \<cdot> B \<cdot> D \<bullet>
      (iffD1 \<cdot> A = C \<cdot> B = D \<bullet> (cong \<cdot> TYPE(bool) \<cdot> TYPE('T1) \ x1 \ x2 \ C \ D \ prfb \ prfT1 \
        (cong \<cdot> TYPE(bool) \<cdot> TYPE('T2) \ (=) \ (=) \ A \ B \ prfb \ prfT2 \
          (HOL.refl \<cdot> TYPE('T3) \ (=) \ prfT3) \ prf1) \ prf2) \ prf3) \ prf4) \
    (iffD1 \<cdot> A \<cdot> B \<bullet> prf1 \<bullet>
      (iffD2 \<cdot> A \<cdot> C \<bullet> prf3 \<bullet> (iffD2 \<cdot> C \<cdot> D \<bullet> prf2 \<bullet> prf4)))\<close>,

   \<open>(iffD1 \<cdot> A \<cdot> C \<bullet>
      (iffD2 \<cdot> A = C \<cdot> B = D \<bullet> (cong \<cdot> TYPE(bool) \<cdot> TYPE('T1) \ x1 \ x2 \ C \ D \ prfb \ prfT1 \
        (cong \<cdot> TYPE(bool) \<cdot> TYPE('T2) \ (=) \ (=) \ A \ B \ prfb \ prfT2 \
          (HOL.refl \<cdot> TYPE('T3) \ (=) \ prfT3) \ prf1) \ prf2) \ prf3) \ prf4)\
    (iffD2 \<cdot> C \<cdot> D \<bullet> prf2 \<bullet>
      (iffD1 \<cdot> B \<cdot> D \<bullet> prf3 \<bullet> (iffD1 \<cdot> A \<cdot> B \<bullet> prf1 \<bullet> prf4)))\<close>,

   \<open>(iffD2 \<cdot> A \<cdot> C \<bullet>
      (iffD2 \<cdot> A = C \<cdot> B = D \<bullet> (cong \<cdot> TYPE(bool) \<cdot> TYPE('T1) \ x1 \ x2 \ C \ D \ prfb \ prfT1 \
        (cong \<cdot> TYPE(bool) \<cdot> TYPE('T2) \ (=) \ (=) \ A \ B \ prfb \ prfT2 \
          (HOL.refl \<cdot> TYPE('T3) \ (=) \ prfT3) \ prf1) \ prf2) \ prf3) \ prf4) \
    (iffD2 \<cdot> A \<cdot> B \<bullet> prf1 \<bullet>
      (iffD2 \<cdot> B \<cdot> D \<bullet> prf3 \<bullet> (iffD1 \<cdot> C \<cdot> D \<bullet> prf2 \<bullet> prf4)))\<close>,

   \<open>(cong \<cdot> TYPE(bool) \<cdot> TYPE(bool) \<cdot> (=) A \<cdot> (=) A \<cdot> B \<cdot> C \<bullet> prfb \<bullet> prfb \<bullet>
      (HOL.refl \<cdot> TYPE(bool\<Rightarrow>bool) \<cdot> (=) A \<bullet> prfbb)) \<equiv>
    (cong \<cdot> TYPE(bool) \<cdot> TYPE(bool) \<cdot> (=) A \<cdot> (=) A \<cdot> B \<cdot> C \<bullet> prfb \<bullet> prfb \<bullet>
      (cong \<cdot> TYPE(bool) \<cdot> TYPE(bool\<Rightarrow>bool) \<cdot>
        ((=) :: bool\<Rightarrow>bool\<Rightarrow>bool) \<cdot> ((=) :: bool\<Rightarrow>bool\<Rightarrow>bool) \<cdot> A \<cdot> A \<bullet>
          prfb \<bullet> prfbb \<bullet>
          (HOL.refl \<cdot> TYPE(bool\<Rightarrow>bool\<Rightarrow>bool) \<cdot> ((=) :: bool\<Rightarrow>bool\<Rightarrow>bool) \<bullet>
             (Pure.PClass type_class \<cdot> TYPE(bool\<Rightarrow>bool\<Rightarrow>bool))) \<bullet>
          (HOL.refl \<cdot> TYPE(bool) \<cdot> A \<bullet> prfb)))\<close>,

   (** transitivity, reflexivity, and symmetry **)

   \<open>(iffD1 \<cdot> A \<cdot> C \<bullet> (HOL.trans \<cdot> TYPE(bool) \<cdot> A \<cdot> B \<cdot> C \<bullet> prfb \<bullet> prf1 \<bullet> prf2) \<bullet> prf3) \<equiv>
    (iffD1 \<cdot> B \<cdot> C \<bullet> prf2 \<bullet> (iffD1 \<cdot> A \<cdot> B \<bullet> prf1 \<bullet> prf3))\<close>,

   \<open>(iffD2 \<cdot> A \<cdot> C \<bullet> (HOL.trans \<cdot> TYPE(bool) \<cdot> A \<cdot> B \<cdot> C \<bullet> prfb \<bullet> prf1 \<bullet> prf2) \<bullet> prf3) \<equiv>
    (iffD2 \<cdot> A \<cdot> B \<bullet> prf1 \<bullet> (iffD2 \<cdot> B \<cdot> C \<bullet> prf2 \<bullet> prf3))\<close>,

   \<open>(iffD1 \<cdot> A \<cdot> A \<bullet> (HOL.refl \<cdot> TYPE(bool) \<cdot> A \<bullet> prfb) \<bullet> prf) \<equiv> prf\<close>,

   \<open>(iffD2 \<cdot> A \<cdot> A \<bullet> (HOL.refl \<cdot> TYPE(bool) \<cdot> A \<bullet> prfb) \<bullet> prf) \<equiv> prf\<close>,

   \<open>(iffD1 \<cdot> A \<cdot> B \<bullet> (sym \<cdot> TYPE(bool) \<cdot> B \<cdot> A \<bullet> prfb \<bullet> prf)) \<equiv> (iffD2 \<cdot> B \<cdot> A \<bullet> prf)\<close>,

   \<open>(iffD2 \<cdot> A \<cdot> B \<bullet> (sym \<cdot> TYPE(bool) \<cdot> B \<cdot> A \<bullet> prfb \<bullet> prf)) \<equiv> (iffD1 \<cdot> B \<cdot> A \<bullet> prf)\<close>,

   (** normalization of HOL proofs **)

   \<open>(mp \<cdot> A \<cdot> B \<bullet> (impI \<cdot> A \<cdot> B \<bullet> prf)) \<equiv> prf\<close>,

   \<open>(impI \<cdot> A \<cdot> B \<bullet> (mp \<cdot> A \<cdot> B \<bullet> prf)) \<equiv> prf\<close>,

   \<open>(spec \<cdot> TYPE('a) \ P \ x \ prfa \ (allI \ TYPE('a) \<cdot> P \<bullet> prfa \<bullet> prf)) \<equiv> prf \<cdot> x\<close>,

   \<open>(allI \<cdot> TYPE('a) \ P \ prfa \ (\<^bold>\x::'a. spec \<cdot> TYPE('a) \ P \ x \ prfa \ prf)) \ prf\,

   \<open>(exE \<cdot> TYPE('a) \ P \ Q \ prfa \ (exI \ TYPE('a) \<cdot> P \<cdot> x \<bullet> prfa \<bullet> prf1) \<bullet> prf2) \<equiv> (prf2 \<cdot> x \<bullet> prf1)\<close>,

   \<open>(exE \<cdot> TYPE('a) \ P \ Q \ prfa \ prf \ (exI \ TYPE('a) \<cdot> P \<bullet> prfa)) \<equiv> prf\<close>,

   \<open>(disjE \<cdot> P \<cdot> Q \<cdot> R \<bullet> (disjI1 \<cdot> P \<cdot> Q \<bullet> prf1) \<bullet> prf2 \<bullet> prf3) \<equiv> (prf2 \<bullet> prf1)\<close>,

   \<open>(disjE \<cdot> P \<cdot> Q \<cdot> R \<bullet> (disjI2 \<cdot> Q \<cdot> P \<bullet> prf1) \<bullet> prf2 \<bullet> prf3) \<equiv> (prf3 \<bullet> prf1)\<close>,

   \<open>(conjunct1 \<cdot> P \<cdot> Q \<bullet> (conjI \<cdot> P \<cdot> Q \<bullet> prf1 \<bullet> prf2)) \<equiv> prf1\<close>,

   \<open>(conjunct2 \<cdot> P \<cdot> Q \<bullet> (conjI \<cdot> P \<cdot> Q \<bullet> prf1 \<bullet> prf2)) \<equiv> prf2\<close>,

   \<open>(iffD1 \<cdot> A \<cdot> B \<bullet> (iffI \<cdot> A \<cdot> B \<bullet> prf1 \<bullet> prf2)) \<equiv> prf1\<close>,

   \<open>(iffD2 \<cdot> A \<cdot> B \<bullet> (iffI \<cdot> A \<cdot> B \<bullet> prf1 \<bullet> prf2)) \<equiv> prf2\<close>];


(** Replace congruence rules by substitution rules **)

fun strip_cong ps (PThm ({name = "HOL.cong", ...}, _) % _ % _ % SOME x % SOME y %%
      prfa %% prfT %% prf1 %% prf2) = strip_cong (((x, y), (prf2, prfa)) :: ps) prf1
  | strip_cong ps (PThm ({name = "HOL.refl", ...}, _) % SOME f %% _) = SOME (f, ps)
  | strip_cong _ _ = NONE;

val subst_prf = fst (Proofterm.strip_combt (fst (Proofterm.strip_combP (Thm.proof_of @{thm subst}))));
val sym_prf = fst (Proofterm.strip_combt (fst (Proofterm.strip_combP (Thm.proof_of@{thm sym}))));

fun make_subst Ts prf xs (_, []) = prf
  | make_subst Ts prf xs (f, ((x, y), (prf', clprf)) :: ps) =
      let val T = fastype_of1 (Ts, x)
      in if x aconv y then make_subst Ts prf (xs @ [x]) (f, ps)
        else Proofterm.change_types (SOME [T]) subst_prf %> x %> y %>
          Abs ("z", T, list_comb (incr_boundvars 1 f,
            map (incr_boundvars 1) xs @ Bound 0 ::
            map (incr_boundvars 1 o snd o fst) ps)) %% clprf %% prf' %%
          make_subst Ts prf (xs @ [x]) (f, ps)
      end;

fun make_sym Ts ((x, y), (prf, clprf)) =
  ((y, x),
    (Proofterm.change_types (SOME [fastype_of1 (Ts, x)]) sym_prf %> x %> y %% clprf %% prf, clprf));

fun mk_AbsP P t = AbsP ("H", Option.map HOLogic.mk_Trueprop P, t);

fun elim_cong_aux Ts (PThm ({name = "HOL.iffD1", ...}, _) % _ % _ %% prf1 %% prf2) =
      Option.map (make_subst Ts prf2 []) (strip_cong [] prf1)
  | elim_cong_aux Ts (PThm ({name = "HOL.iffD1", ...}, _) % P % _ %% prf) =
      Option.map (mk_AbsP P o make_subst Ts (PBound 0) [])
        (strip_cong [] (Proofterm.incr_pboundvars 1 0 prf))
  | elim_cong_aux Ts (PThm ({name = "HOL.iffD2", ...}, _) % _ % _ %% prf1 %% prf2) =
      Option.map (make_subst Ts prf2 [] o
        apsnd (map (make_sym Ts))) (strip_cong [] prf1)
  | elim_cong_aux Ts (PThm ({name = "HOL.iffD2", ...}, _) % _ % P %% prf) =
      Option.map (mk_AbsP P o make_subst Ts (PBound 0) [] o
        apsnd (map (make_sym Ts))) (strip_cong [] (Proofterm.incr_pboundvars 1 0 prf))
  | elim_cong_aux _ _ = NONE;

fun elim_cong Ts hs prf = Option.map (rpair Proofterm.no_skel) (elim_cong_aux Ts prf);

end;

[ Dauer der Verarbeitung: 0.3 Sekunden  (vorverarbeitet)  ]