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 |