13 |
13 |
14 (*--------------------------------------------------------------------------- |
14 (*--------------------------------------------------------------------------- |
15 * Unifiers |
15 * Unifiers |
16 *---------------------------------------------------------------------------*) |
16 *---------------------------------------------------------------------------*) |
17 |
17 |
18 goal Unifier.thy |
18 Goal |
19 "Unifier s (Comb t u) (Comb v w) = (Unifier s t v & Unifier s u w)"; |
19 "Unifier s (Comb t u) (Comb v w) = (Unifier s t v & Unifier s u w)"; |
20 by (simp_tac (simpset() addsimps [Unifier_def]) 1); |
20 by (simp_tac (simpset() addsimps [Unifier_def]) 1); |
21 qed "Unifier_Comb"; |
21 qed "Unifier_Comb"; |
22 |
22 |
23 AddIffs [Unifier_Comb]; |
23 AddIffs [Unifier_Comb]; |
24 |
24 |
25 goal Unifier.thy |
25 Goal |
26 "!!v. [| v ~: vars_of t; v ~: vars_of u; Unifier s t u |] ==> \ |
26 "!!v. [| v ~: vars_of t; v ~: vars_of u; Unifier s t u |] ==> \ |
27 \ Unifier ((v,r)#s) t u"; |
27 \ Unifier ((v,r)#s) t u"; |
28 by (asm_full_simp_tac (simpset() addsimps [Unifier_def, repl_invariance]) 1); |
28 by (asm_full_simp_tac (simpset() addsimps [Unifier_def, repl_invariance]) 1); |
29 qed "Cons_Unifier"; |
29 qed "Cons_Unifier"; |
30 |
30 |
31 |
31 |
32 (*--------------------------------------------------------------------------- |
32 (*--------------------------------------------------------------------------- |
33 * Most General Unifiers |
33 * Most General Unifiers |
34 *---------------------------------------------------------------------------*) |
34 *---------------------------------------------------------------------------*) |
35 |
35 |
36 goalw Unifier.thy unify_defs "MGUnifier s t u = MGUnifier s u t"; |
36 Goalw unify_defs "MGUnifier s t u = MGUnifier s u t"; |
37 by (blast_tac (claset() addIs [sym]) 1); |
37 by (blast_tac (claset() addIs [sym]) 1); |
38 qed "mgu_sym"; |
38 qed "mgu_sym"; |
39 |
39 |
40 |
40 |
41 goal Unifier.thy "[] >> s"; |
41 Goal "[] >> s"; |
42 by (simp_tac (simpset() addsimps [MoreGeneral_def]) 1); |
42 by (simp_tac (simpset() addsimps [MoreGeneral_def]) 1); |
43 by (Blast_tac 1); |
43 by (Blast_tac 1); |
44 qed "MoreGen_Nil"; |
44 qed "MoreGen_Nil"; |
45 |
45 |
46 AddIffs [MoreGen_Nil]; |
46 AddIffs [MoreGen_Nil]; |
47 |
47 |
48 goalw Unifier.thy unify_defs |
48 Goalw unify_defs |
49 "MGUnifier s t u = (ALL r. Unifier r t u = s >> r)"; |
49 "MGUnifier s t u = (ALL r. Unifier r t u = s >> r)"; |
50 by (auto_tac (claset() addIs [ssubst_subst2, subst_comp_Nil], simpset())); |
50 by (auto_tac (claset() addIs [ssubst_subst2, subst_comp_Nil], simpset())); |
51 qed "MGU_iff"; |
51 qed "MGU_iff"; |
52 |
52 |
53 |
53 |
54 goal Unifier.thy |
54 Goal |
55 "!!v. ~ Var v <: t ==> MGUnifier [(v,t)] (Var v) t"; |
55 "!!v. ~ Var v <: t ==> MGUnifier [(v,t)] (Var v) t"; |
56 by (simp_tac(simpset() addsimps [MGU_iff, Unifier_def, MoreGeneral_def] |
56 by (simp_tac(simpset() addsimps [MGU_iff, Unifier_def, MoreGeneral_def] |
57 delsimps [subst_Var]) 1); |
57 delsimps [subst_Var]) 1); |
58 by Safe_tac; |
58 by Safe_tac; |
59 by (rtac exI 1); |
59 by (rtac exI 1); |
67 |
67 |
68 (*--------------------------------------------------------------------------- |
68 (*--------------------------------------------------------------------------- |
69 * Idempotence. |
69 * Idempotence. |
70 *---------------------------------------------------------------------------*) |
70 *---------------------------------------------------------------------------*) |
71 |
71 |
72 goalw Unifier.thy [Idem_def] "Idem([])"; |
72 Goalw [Idem_def] "Idem([])"; |
73 by (Simp_tac 1); |
73 by (Simp_tac 1); |
74 qed "Idem_Nil"; |
74 qed "Idem_Nil"; |
75 |
75 |
76 AddIffs [Idem_Nil]; |
76 AddIffs [Idem_Nil]; |
77 |
77 |
78 goalw Unifier.thy [Idem_def] "Idem(s) = (sdom(s) Int srange(s) = {})"; |
78 Goalw [Idem_def] "Idem(s) = (sdom(s) Int srange(s) = {})"; |
79 by (simp_tac (simpset() addsimps [subst_eq_iff, invariance, |
79 by (simp_tac (simpset() addsimps [subst_eq_iff, invariance, |
80 dom_range_disjoint]) 1); |
80 dom_range_disjoint]) 1); |
81 qed "Idem_iff"; |
81 qed "Idem_iff"; |
82 |
82 |
83 goal Unifier.thy "~ (Var(v) <: t) --> Idem([(v,t)])"; |
83 Goal "~ (Var(v) <: t) --> Idem([(v,t)])"; |
84 by (simp_tac (simpset() addsimps [vars_iff_occseq, Idem_iff, srange_iff, |
84 by (simp_tac (simpset() addsimps [vars_iff_occseq, Idem_iff, srange_iff, |
85 empty_iff_all_not]) 1); |
85 empty_iff_all_not]) 1); |
86 qed_spec_mp "Var_Idem"; |
86 qed_spec_mp "Var_Idem"; |
87 |
87 |
88 AddSIs [Var_Idem]; |
88 AddSIs [Var_Idem]; |
89 |
89 |
90 goalw Unifier.thy [Idem_def] |
90 Goalw [Idem_def] |
91 "!!r. [| Idem(r); Unifier s (t<|r) (u<|r) |] \ |
91 "!!r. [| Idem(r); Unifier s (t<|r) (u<|r) |] \ |
92 \ ==> Unifier (r <> s) (t <| r) (u <| r)"; |
92 \ ==> Unifier (r <> s) (t <| r) (u <| r)"; |
93 by (asm_full_simp_tac (simpset() addsimps [Unifier_def, comp_subst_subst]) 1); |
93 by (asm_full_simp_tac (simpset() addsimps [Unifier_def, comp_subst_subst]) 1); |
94 qed "Unifier_Idem_subst"; |
94 qed "Unifier_Idem_subst"; |
95 |
95 |