diff --git a/src/HOL/Metis_Examples/Abstraction.thy b/src/HOL/Metis_Examples/Abstraction.thy --- a/src/HOL/Metis_Examples/Abstraction.thy +++ b/src/HOL/Metis_Examples/Abstraction.thy @@ -1,174 +1,174 @@ (* Title: HOL/Metis_Examples/Abstraction.thy Author: Lawrence C. Paulson, Cambridge University Computer Laboratory Author: Jasmin Blanchette, TU Muenchen Example featuring Metis's support for lambda-abstractions. *) section \Example Featuring Metis's Support for Lambda-Abstractions\ theory Abstraction -imports "HOL-Library.FuncSet" + imports "HOL-Library.FuncSet" begin (* For Christoph Benzmüller *) lemma "x < 1 \ ((=) = (=)) \ ((=) = (=)) \ x < (2::nat)" by (metis nat_1_add_1 trans_less_add2) -lemma "((=) ) = (\x y. y = x)" +lemma "(=) = (\x y. y = x)" by metis consts monotone :: "['a => 'a, 'a set, ('a *'a)set] => bool" pset :: "'a set => 'a set" order :: "'a set => ('a * 'a) set" lemma "a \ {x. P x} \ P a" proof - assume "a \ {x. P x}" thus "P a" by (metis mem_Collect_eq) qed lemma Collect_triv: "a \ {x. P x} \ P a" by (metis mem_Collect_eq) lemma "a \ {x. P x --> Q x} \ a \ {x. P x} \ a \ {x. Q x}" by (metis Collect_imp_eq ComplD UnE) lemma "(a, b) \ Sigma A B \ a \ A \ b \ B a" proof - assume A1: "(a, b) \ Sigma A B" hence F1: "b \ B a" by (metis mem_Sigma_iff) have F2: "a \ A" by (metis A1 mem_Sigma_iff) have "b \ B a" by (metis F1) thus "a \ A \ b \ B a" by (metis F2) qed lemma Sigma_triv: "(a, b) \ Sigma A B \ a \ A & b \ B a" by (metis SigmaD1 SigmaD2) lemma "(a, b) \ (SIGMA x:A. {y. x = f y}) \ a \ A \ a = f b" by (metis (full_types, lifting) CollectD SigmaD1 SigmaD2) lemma "(a, b) \ (SIGMA x:A. {y. x = f y}) \ a \ A \ a = f b" proof - assume A1: "(a, b) \ (SIGMA x:A. {y. x = f y})" hence F1: "a \ A" by (metis mem_Sigma_iff) have "b \ {R. a = f R}" by (metis A1 mem_Sigma_iff) hence "a = f b" by (metis (full_types) mem_Collect_eq) thus "a \ A \ a = f b" by (metis F1) qed lemma "(cl, f) \ CLF \ CLF = (SIGMA cl: CL.{f. f \ pset cl}) \ f \ pset cl" by (metis Collect_mem_eq SigmaD2) lemma "(cl, f) \ CLF \ CLF = (SIGMA cl: CL.{f. f \ pset cl}) \ f \ pset cl" proof - assume A1: "(cl, f) \ CLF" assume A2: "CLF = (SIGMA cl:CL. {f. f \ pset cl})" have "\v u. (u, v) \ CLF \ v \ {R. R \ pset u}" by (metis A2 mem_Sigma_iff) hence "\v u. (u, v) \ CLF \ v \ pset u" by (metis mem_Collect_eq) thus "f \ pset cl" by (metis A1) qed lemma "(cl, f) \ (SIGMA cl: CL. {f. f \ pset cl \ pset cl}) \ f \ pset cl \ pset cl" by (metis (no_types) Collect_mem_eq Sigma_triv) lemma "(cl, f) \ (SIGMA cl: CL. {f. f \ pset cl \ pset cl}) \ f \ pset cl \ pset cl" proof - assume A1: "(cl, f) \ (SIGMA cl:CL. {f. f \ pset cl \ pset cl})" have "f \ {R. R \ pset cl \ pset cl}" using A1 by simp thus "f \ pset cl \ pset cl" by (metis mem_Collect_eq) qed lemma "(cl, f) \ (SIGMA cl: CL. {f. f \ pset cl \ cl}) \ f \ pset cl \ cl" by (metis (no_types) Collect_conj_eq Int_def Sigma_triv inf_idem) lemma "(cl, f) \ (SIGMA cl: CL. {f. f \ pset cl \ cl}) \ f \ pset cl \ cl" proof - assume A1: "(cl, f) \ (SIGMA cl:CL. {f. f \ pset cl \ cl})" have "f \ {R. R \ pset cl \ cl}" using A1 by simp hence "f \ Id_on cl `` pset cl" by (metis Int_commute Image_Id_on mem_Collect_eq) hence "f \ cl \ pset cl" by (metis Image_Id_on) thus "f \ pset cl \ cl" by (metis Int_commute) qed lemma "(cl, f) \ (SIGMA cl: CL. {f. f \ pset cl \ pset cl & monotone f (pset cl) (order cl)}) \ (f \ pset cl \ pset cl) & (monotone f (pset cl) (order cl))" by auto lemma "(cl, f) \ CLF \ CLF \ (SIGMA cl: CL. {f. f \ pset cl \ cl}) \ f \ pset cl \ cl" by (metis (lifting) CollectD Sigma_triv subsetD) lemma "(cl, f) \ CLF \ CLF = (SIGMA cl: CL. {f. f \ pset cl \ cl}) \ f \ pset cl \ cl" by (metis (lifting) CollectD Sigma_triv) lemma "(cl, f) \ CLF \ CLF \ (SIGMA cl': CL. {f. f \ pset cl' \ pset cl'}) \ f \ pset cl \ pset cl" by (metis (lifting) CollectD Sigma_triv subsetD) lemma "(cl, f) \ CLF \ CLF = (SIGMA cl: CL. {f. f \ pset cl \ pset cl}) \ f \ pset cl \ pset cl" by (metis (lifting) CollectD Sigma_triv) lemma "(cl, f) \ CLF \ CLF = (SIGMA cl: CL. {f. f \ pset cl \ pset cl & monotone f (pset cl) (order cl)}) \ (f \ pset cl \ pset cl) & (monotone f (pset cl) (order cl))" by auto lemma "map (\x. (f x, g x)) xs = zip (map f xs) (map g xs)" apply (induct xs) apply (metis list.map(1) zip_Nil) by auto lemma "map (\w. (w \ w, w \ w)) xs = zip (map (\w. w \ w) xs) (map (\w. w \ w) xs)" apply (induct xs) apply (metis list.map(1) zip_Nil) by auto lemma "(\x. Suc (f x)) ` {x. even x} \ A \ \x. even x --> Suc (f x) \ A" by (metis mem_Collect_eq image_eqI subsetD) lemma "(\x. f (f x)) ` ((\x. Suc(f x)) ` {x. even x}) \ A \ (\x. even x --> f (f (Suc(f x))) \ A)" by (metis mem_Collect_eq imageI rev_subsetD) lemma "f \ (\u v. b \ u \ v) ` A \ \u v. P (b \ u \ v) \ P(f y)" by (metis (lifting) imageE) lemma image_TimesA: "(\(x, y). (f x, g y)) ` (A \ B) = (f ` A) \ (g ` B)" by (metis map_prod_def map_prod_surj_on) lemma image_TimesB: "(\(x, y, z). (f x, g y, h z)) ` (A \ B \ C) = (f ` A) \ (g ` B) \ (h ` C)" by force lemma image_TimesC: "(\(x, y). (x \ x, y \ y)) ` (A \ B) = ((\x. x \ x) ` A) \ ((\y. y \ y) ` B)" by (metis image_TimesA) end diff --git a/src/HOL/Metis_Examples/Proxies.thy b/src/HOL/Metis_Examples/Proxies.thy --- a/src/HOL/Metis_Examples/Proxies.thy +++ b/src/HOL/Metis_Examples/Proxies.thy @@ -1,267 +1,267 @@ (* Title: HOL/Metis_Examples/Proxies.thy Author: Jasmin Blanchette, TU Muenchen Example that exercises Metis's and Sledgehammer's logical symbol proxies for rudimentary higher-order reasoning. *) section \ Example that Exercises Metis's and Sledgehammer's Logical Symbol Proxies for Rudimentary Higher-Order Reasoning. \ theory Proxies imports Type_Encodings begin -sledgehammer_params [prover = spass, fact_filter = mepo, timeout = 30, preplay_timeout = 0, - dont_minimize] +sledgehammer_params [prover = spass, fact_filter = mepo, slices = 1, timeout = 30, + preplay_timeout = 0, dont_minimize] text \Extensionality and set constants\ lemma plus_1_not_0: "n + (1::nat) \ 0" by simp definition inc :: "nat \ nat" where "inc x = x + 1" lemma "inc \ (\y. 0)" sledgehammer [expect = some] (inc_def plus_1_not_0) by (metis_exhaust inc_def plus_1_not_0) lemma "inc = (\y. y + 1)" sledgehammer [expect = some] by (metis_exhaust inc_def) definition add_swap :: "nat \ nat \ nat" where "add_swap = (\x y. y + x)" lemma "add_swap m n = n + m" sledgehammer [expect = some] (add_swap_def) by (metis_exhaust add_swap_def) definition "A = {xs::'a list. True}" lemma "xs \ A" (* The "add:" argument is unfortunate. *) sledgehammer [expect = some] (add: A_def mem_Collect_eq) by (metis_exhaust A_def mem_Collect_eq) definition "B (y::int) \ y \ 0" definition "C (y::int) \ y \ 1" lemma int_le_0_imp_le_1: "x \ (0::int) \ x \ 1" by linarith lemma "B \ C" sledgehammer [expect = some] by (metis_exhaust B_def C_def int_le_0_imp_le_1 predicate1I) text \Proxies for logical constants\ lemma "id (=) x x" sledgehammer [type_enc = erased, expect = none] (id_apply) sledgehammer [type_enc = poly_tags??, expect = some] (id_apply) sledgehammer [type_enc = poly_tags, expect = some] (id_apply) sledgehammer [type_enc = poly_guards??, expect = some] (id_apply) sledgehammer [type_enc = poly_guards, expect = some] (id_apply) sledgehammer [type_enc = mono_tags??, expect = some] (id_apply) sledgehammer [type_enc = mono_tags, expect = some] (id_apply) sledgehammer [type_enc = mono_guards??, expect = some] (id_apply) sledgehammer [type_enc = mono_guards, expect = some] (id_apply) by (metis (full_types) id_apply) lemma "id True" sledgehammer [type_enc = erased, expect = some] (id_apply) sledgehammer [type_enc = poly_tags??, expect = some] (id_apply) sledgehammer [type_enc = poly_tags, expect = some] (id_apply) sledgehammer [type_enc = poly_guards??, expect = some] (id_apply) sledgehammer [type_enc = poly_guards, expect = some] (id_apply) sledgehammer [type_enc = mono_tags??, expect = some] (id_apply) sledgehammer [type_enc = mono_tags, expect = some] (id_apply) sledgehammer [type_enc = mono_guards??, expect = some] (id_apply) sledgehammer [type_enc = mono_guards, expect = some] (id_apply) by (metis_exhaust id_apply) lemma "\ id False" sledgehammer [type_enc = erased, expect = some] (id_apply) sledgehammer [type_enc = poly_tags??, expect = some] (id_apply) sledgehammer [type_enc = poly_tags, expect = some] (id_apply) sledgehammer [type_enc = poly_guards??, expect = some] (id_apply) sledgehammer [type_enc = poly_guards, expect = some] (id_apply) sledgehammer [type_enc = mono_tags??, expect = some] (id_apply) sledgehammer [type_enc = mono_tags, expect = some] (id_apply) sledgehammer [type_enc = mono_guards??, expect = some] (id_apply) sledgehammer [type_enc = mono_guards, expect = some] (id_apply) by (metis_exhaust id_apply) lemma "x = id True \ x = id False" sledgehammer [type_enc = erased, expect = some] (id_apply) sledgehammer [type_enc = poly_tags??, expect = some] (id_apply) sledgehammer [type_enc = poly_tags, expect = some] (id_apply) sledgehammer [type_enc = poly_guards??, expect = some] (id_apply) sledgehammer [type_enc = poly_guards, expect = some] (id_apply) sledgehammer [type_enc = mono_tags??, expect = some] (id_apply) sledgehammer [type_enc = mono_tags, expect = some] (id_apply) sledgehammer [type_enc = mono_guards??, expect = some] (id_apply) sledgehammer [type_enc = mono_guards, expect = some] (id_apply) by (metis_exhaust id_apply) lemma "id x = id True \ id x = id False" sledgehammer [type_enc = erased, expect = some] (id_apply) sledgehammer [type_enc = poly_tags??, expect = some] (id_apply) sledgehammer [type_enc = poly_tags, expect = some] (id_apply) sledgehammer [type_enc = poly_guards??, expect = some] (id_apply) sledgehammer [type_enc = poly_guards, expect = some] (id_apply) sledgehammer [type_enc = mono_tags??, expect = some] (id_apply) sledgehammer [type_enc = mono_tags, expect = some] (id_apply) sledgehammer [type_enc = mono_guards??, expect = some] (id_apply) sledgehammer [type_enc = mono_guards, expect = some] (id_apply) by (metis_exhaust id_apply) lemma "P True \ P False \ P x" sledgehammer [type_enc = erased, expect = none] () sledgehammer [type_enc = poly_args, expect = none] () sledgehammer [type_enc = poly_tags??, expect = some] () sledgehammer [type_enc = poly_tags, expect = some] () sledgehammer [type_enc = poly_guards??, expect = some] (id_apply) sledgehammer [type_enc = poly_guards, expect = some] () sledgehammer [type_enc = mono_tags??, expect = some] () sledgehammer [type_enc = mono_tags, expect = some] () sledgehammer [type_enc = mono_guards??, expect = some] () sledgehammer [type_enc = mono_guards, expect = some] () by (metis (full_types)) lemma "id (\ a) \ \ id a" sledgehammer [type_enc = erased, expect = some] (id_apply) sledgehammer [type_enc = poly_tags??, expect = some] (id_apply) sledgehammer [type_enc = poly_tags, expect = some] (id_apply) sledgehammer [type_enc = poly_guards??, expect = some] (id_apply) sledgehammer [type_enc = poly_guards, expect = some] (id_apply) sledgehammer [type_enc = mono_tags??, expect = some] (id_apply) sledgehammer [type_enc = mono_tags, expect = some] (id_apply) sledgehammer [type_enc = mono_guards??, expect = some] (id_apply) sledgehammer [type_enc = mono_guards, expect = some] (id_apply) by (metis_exhaust id_apply) lemma "id (\ \ a) \ id a" sledgehammer [type_enc = erased, expect = some] (id_apply) sledgehammer [type_enc = poly_tags??, expect = some] (id_apply) sledgehammer [type_enc = poly_tags, expect = some] (id_apply) sledgehammer [type_enc = poly_guards??, expect = some] (id_apply) sledgehammer [type_enc = poly_guards, expect = some] (id_apply) sledgehammer [type_enc = mono_tags??, expect = some] (id_apply) sledgehammer [type_enc = mono_tags, expect = some] (id_apply) sledgehammer [type_enc = mono_guards??, expect = some] (id_apply) sledgehammer [type_enc = mono_guards, expect = some] (id_apply) by metis_exhaust lemma "id (\ (id (\ a))) \ id a" sledgehammer [type_enc = erased, expect = some] (id_apply) sledgehammer [type_enc = poly_tags??, expect = some] (id_apply) sledgehammer [type_enc = poly_tags, expect = some] (id_apply) sledgehammer [type_enc = poly_guards??, expect = some] (id_apply) sledgehammer [type_enc = poly_guards, expect = some] (id_apply) sledgehammer [type_enc = mono_tags??, expect = some] (id_apply) sledgehammer [type_enc = mono_tags, expect = some] (id_apply) sledgehammer [type_enc = mono_guards??, expect = some] (id_apply) sledgehammer [type_enc = mono_guards, expect = some] (id_apply) by (metis_exhaust id_apply) lemma "id (a \ b) \ id a" sledgehammer [type_enc = erased, expect = some] (id_apply) sledgehammer [type_enc = poly_tags??, expect = some] (id_apply) sledgehammer [type_enc = poly_tags, expect = some] (id_apply) sledgehammer [type_enc = poly_guards??, expect = some] (id_apply) sledgehammer [type_enc = poly_guards, expect = some] (id_apply) sledgehammer [type_enc = mono_tags??, expect = some] (id_apply) sledgehammer [type_enc = mono_tags, expect = some] (id_apply) sledgehammer [type_enc = mono_guards??, expect = some] (id_apply) sledgehammer [type_enc = mono_guards, expect = some] (id_apply) by (metis_exhaust id_apply) lemma "id (a \ b) \ id b" sledgehammer [type_enc = erased, expect = some] (id_apply) sledgehammer [type_enc = poly_tags??, expect = some] (id_apply) sledgehammer [type_enc = poly_tags, expect = some] (id_apply) sledgehammer [type_enc = poly_guards??, expect = some] (id_apply) sledgehammer [type_enc = poly_guards, expect = some] (id_apply) sledgehammer [type_enc = mono_tags??, expect = some] (id_apply) sledgehammer [type_enc = mono_tags, expect = some] (id_apply) sledgehammer [type_enc = mono_guards??, expect = some] (id_apply) sledgehammer [type_enc = mono_guards, expect = some] (id_apply) by (metis_exhaust id_apply) lemma "id a \ id b \ id (a \ b)" sledgehammer [type_enc = erased, expect = some] (id_apply) sledgehammer [type_enc = poly_tags??, expect = some] (id_apply) sledgehammer [type_enc = poly_tags, expect = some] (id_apply) sledgehammer [type_enc = poly_guards??, expect = some] (id_apply) sledgehammer [type_enc = poly_guards, expect = some] (id_apply) sledgehammer [type_enc = mono_tags??, expect = some] (id_apply) sledgehammer [type_enc = mono_tags, expect = some] (id_apply) sledgehammer [type_enc = mono_guards??, expect = some] (id_apply) sledgehammer [type_enc = mono_guards, expect = some] (id_apply) by (metis_exhaust id_apply) lemma "id a \ id (a \ b)" sledgehammer [type_enc = erased, expect = some] (id_apply) sledgehammer [type_enc = poly_tags??, expect = some] (id_apply) sledgehammer [type_enc = poly_tags, expect = some] (id_apply) sledgehammer [type_enc = poly_guards??, expect = some] (id_apply) sledgehammer [type_enc = poly_guards, expect = some] (id_apply) sledgehammer [type_enc = mono_tags??, expect = some] (id_apply) sledgehammer [type_enc = mono_tags, expect = some] (id_apply) sledgehammer [type_enc = mono_guards??, expect = some] (id_apply) sledgehammer [type_enc = mono_guards, expect = some] (id_apply) by (metis_exhaust id_apply) lemma "id b \ id (a \ b)" sledgehammer [type_enc = erased, expect = some] (id_apply) sledgehammer [type_enc = poly_tags??, expect = some] (id_apply) sledgehammer [type_enc = poly_tags, expect = some] (id_apply) sledgehammer [type_enc = poly_guards??, expect = some] (id_apply) sledgehammer [type_enc = poly_guards, expect = some] (id_apply) sledgehammer [type_enc = mono_tags??, expect = some] (id_apply) sledgehammer [type_enc = mono_tags, expect = some] (id_apply) sledgehammer [type_enc = mono_guards??, expect = some] (id_apply) sledgehammer [type_enc = mono_guards, expect = some] (id_apply) by (metis_exhaust id_apply) lemma "id (\ a) \ id (\ b) \ id (\ (a \ b))" sledgehammer [type_enc = erased, expect = some] (id_apply) sledgehammer [type_enc = poly_tags??, expect = some] (id_apply) sledgehammer [type_enc = poly_tags, expect = some] (id_apply) sledgehammer [type_enc = poly_guards??, expect = some] (id_apply) sledgehammer [type_enc = poly_guards, expect = some] (id_apply) sledgehammer [type_enc = mono_tags??, expect = some] (id_apply) sledgehammer [type_enc = mono_tags, expect = some] (id_apply) sledgehammer [type_enc = mono_guards??, expect = some] (id_apply) sledgehammer [type_enc = mono_guards, expect = some] (id_apply) by (metis_exhaust id_apply) lemma "id (\ a) \ id (a \ b)" sledgehammer [type_enc = erased, expect = some] (id_apply) sledgehammer [type_enc = poly_tags??, expect = some] (id_apply) sledgehammer [type_enc = poly_tags, expect = some] (id_apply) sledgehammer [type_enc = poly_guards??, expect = some] (id_apply) sledgehammer [type_enc = poly_guards, expect = some] (id_apply) sledgehammer [type_enc = mono_tags??, expect = some] (id_apply) sledgehammer [type_enc = mono_tags, expect = some] (id_apply) sledgehammer [type_enc = mono_guards??, expect = some] (id_apply) sledgehammer [type_enc = mono_guards, expect = some] (id_apply) by (metis_exhaust id_apply) lemma "id (a \ b) \ id (\ a \ b)" sledgehammer [type_enc = erased, expect = some] (id_apply) sledgehammer [type_enc = poly_tags??, expect = some] (id_apply) sledgehammer [type_enc = poly_tags, expect = some] (id_apply) sledgehammer [type_enc = poly_guards??, expect = some] (id_apply) sledgehammer [type_enc = poly_guards, expect = some] (id_apply) sledgehammer [type_enc = mono_tags??, expect = some] (id_apply) sledgehammer [type_enc = mono_tags, expect = some] (id_apply) sledgehammer [type_enc = mono_guards??, expect = some] (id_apply) sledgehammer [type_enc = mono_guards, expect = some] (id_apply) by (metis_exhaust id_apply) end