(* 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.7 Sekunden
(vorverarbeitet)
¤
|
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.
|
