src/HOL/ex/Unification.thy
changeset 24444 448978b61556
parent 23777 60b7800338d5
child 30909 bd4f255837e5
equal deleted inserted replaced
24443:ab6206ccb570 24444:448978b61556
   176 next
   176 next
   177   fix \<theta> assume th: "Var v \<triangleleft> \<theta> = t \<triangleleft> \<theta>" 
   177   fix \<theta> assume th: "Var v \<triangleleft> \<theta> = t \<triangleleft> \<theta>" 
   178   show "\<theta> =\<^sub>s [(v,t)] \<bullet> \<theta>" 
   178   show "\<theta> =\<^sub>s [(v,t)] \<bullet> \<theta>" 
   179   proof
   179   proof
   180     fix s show "s \<triangleleft> \<theta> = s \<triangleleft> [(v,t)] \<bullet> \<theta>" using th 
   180     fix s show "s \<triangleleft> \<theta> = s \<triangleleft> [(v,t)] \<bullet> \<theta>" using th 
   181       by (induct s, auto)
   181       by (induct s) auto
   182   qed
   182   qed
   183 qed
   183 qed
   184 
   184 
   185 declare MGU_Var[symmetric, intro]
   185 declare MGU_Var[symmetric, intro]
   186 
   186 
   192 
   192 
   193 lemma unify_partial_correctness:
   193 lemma unify_partial_correctness:
   194   assumes "unify_dom (M, N)"
   194   assumes "unify_dom (M, N)"
   195   assumes "unify M N = Some \<sigma>"
   195   assumes "unify M N = Some \<sigma>"
   196   shows "MGU \<sigma> M N"
   196   shows "MGU \<sigma> M N"
   197 using prems
   197 using assms
   198 proof (induct M N arbitrary: \<sigma>)
   198 proof (induct M N arbitrary: \<sigma>)
   199   case (7 M N M' N' \<sigma>) -- "The interesting case"
   199   case (7 M N M' N' \<sigma>) -- "The interesting case"
   200 
   200 
   201   then obtain \<theta>1 \<theta>2 
   201   then obtain \<theta>1 \<theta>2 
   202     where "unify M M' = Some \<theta>1"
   202     where "unify M M' = Some \<theta>1"
   355 lemma unify_vars: 
   355 lemma unify_vars: 
   356   assumes "unify_dom (M, N)"
   356   assumes "unify_dom (M, N)"
   357   assumes "unify M N = Some \<sigma>"
   357   assumes "unify M N = Some \<sigma>"
   358   shows "vars_of (t \<triangleleft> \<sigma>) \<subseteq> vars_of M \<union> vars_of N \<union> vars_of t"
   358   shows "vars_of (t \<triangleleft> \<sigma>) \<subseteq> vars_of M \<union> vars_of N \<union> vars_of t"
   359   (is "?P M N \<sigma> t")
   359   (is "?P M N \<sigma> t")
   360 using prems
   360 using assms
   361 proof (induct M N arbitrary:\<sigma> t)
   361 proof (induct M N arbitrary:\<sigma> t)
   362   case (3 c v) 
   362   case (3 c v) 
   363   hence "\<sigma> = [(v, Const c)]" by simp
   363   hence "\<sigma> = [(v, Const c)]" by simp
   364   thus ?case by (induct t, auto)
   364   thus ?case by (induct t) auto
   365 next
   365 next
   366   case (4 M N v) 
   366   case (4 M N v) 
   367   hence "\<not>occ (Var v) (M\<cdot>N)" by (cases "occ (Var v) (M\<cdot>N)", auto)
   367   hence "\<not>occ (Var v) (M\<cdot>N)" by (cases "occ (Var v) (M\<cdot>N)", auto)
   368   with prems have "\<sigma> = [(v, M\<cdot>N)]" by simp
   368   with 4 have "\<sigma> = [(v, M\<cdot>N)]" by simp
   369   thus ?case by (induct t, auto)
   369   thus ?case by (induct t) auto
   370 next
   370 next
   371   case (5 v M)
   371   case (5 v M)
   372   hence "\<not>occ (Var v) M" by (cases "occ (Var v) M", auto)
   372   hence "\<not>occ (Var v) M" by (cases "occ (Var v) M", auto)
   373   with prems have "\<sigma> = [(v, M)]" by simp
   373   with 5 have "\<sigma> = [(v, M)]" by simp
   374   thus ?case by (induct t, auto)
   374   thus ?case by (induct t) auto
   375 next
   375 next
   376   case (7 M N M' N' \<sigma>)
   376   case (7 M N M' N' \<sigma>)
   377   then obtain \<theta>1 \<theta>2 
   377   then obtain \<theta>1 \<theta>2 
   378     where "unify M M' = Some \<theta>1"
   378     where "unify M M' = Some \<theta>1"
   379     and "unify (N \<triangleleft> \<theta>1) (N' \<triangleleft> \<theta>1) = Some \<theta>2"
   379     and "unify (N \<triangleleft> \<theta>1) (N' \<triangleleft> \<theta>1) = Some \<theta>2"
   418 lemma unify_eliminates: 
   418 lemma unify_eliminates: 
   419   assumes "unify_dom (M, N)"
   419   assumes "unify_dom (M, N)"
   420   assumes "unify M N = Some \<sigma>"
   420   assumes "unify M N = Some \<sigma>"
   421   shows "(\<exists>v\<in>vars_of M \<union> vars_of N. elim \<sigma> v) \<or> \<sigma> =\<^sub>s []"
   421   shows "(\<exists>v\<in>vars_of M \<union> vars_of N. elim \<sigma> v) \<or> \<sigma> =\<^sub>s []"
   422   (is "?P M N \<sigma>")
   422   (is "?P M N \<sigma>")
   423 using prems
   423 using assms
   424 proof (induct M N arbitrary:\<sigma>)
   424 proof (induct M N arbitrary:\<sigma>)
   425   case 1 thus ?case by simp
   425   case 1 thus ?case by simp
   426 next
   426 next
   427   case 2 thus ?case by simp
   427   case 2 thus ?case by simp
   428 next
   428 next
   429   case (3 c v)
   429   case (3 c v)
   430   have no_occ: "\<not> occ (Var v) (Const c)" by simp
   430   have no_occ: "\<not> occ (Var v) (Const c)" by simp
   431   with prems have "\<sigma> = [(v, Const c)]" by simp
   431   with 3 have "\<sigma> = [(v, Const c)]" by simp
   432   with occ_elim[OF no_occ]
   432   with occ_elim[OF no_occ]
   433   show ?case by auto
   433   show ?case by auto
   434 next
   434 next
   435   case (4 M N v)
   435   case (4 M N v)
   436   hence no_occ: "\<not>occ (Var v) (M\<cdot>N)" by (cases "occ (Var v) (M\<cdot>N)", auto)
   436   hence no_occ: "\<not>occ (Var v) (M\<cdot>N)" by (cases "occ (Var v) (M\<cdot>N)", auto)
   437   with prems have "\<sigma> = [(v, M\<cdot>N)]" by simp
   437   with 4 have "\<sigma> = [(v, M\<cdot>N)]" by simp
   438   with occ_elim[OF no_occ]
   438   with occ_elim[OF no_occ]
   439   show ?case by auto 
   439   show ?case by auto 
   440 next
   440 next
   441   case (5 v M) 
   441   case (5 v M) 
   442   hence no_occ: "\<not>occ (Var v) M" by (cases "occ (Var v) M", auto)
   442   hence no_occ: "\<not>occ (Var v) M" by (cases "occ (Var v) M", auto)
   443   with prems have "\<sigma> = [(v, M)]" by simp
   443   with 5 have "\<sigma> = [(v, M)]" by simp
   444   with occ_elim[OF no_occ]
   444   with occ_elim[OF no_occ]
   445   show ?case by auto 
   445   show ?case by auto 
   446 next 
   446 next 
   447   case (6 c d) thus ?case
   447   case (6 c d) thus ?case
   448     by (cases "c = d") auto
   448     by (cases "c = d") auto