src/HOL/Subst/Unifier.ML
changeset 5069 3ea049f7979d
parent 4719 21af5c0be0c9
child 5119 58d267fc8630
equal deleted inserted replaced
5068:fb28eaa07e01 5069:3ea049f7979d
    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