theory Deterministic_AI

lemma next_sib:
  "valid_list_2 t m
    \<Longrightarrow> next_sib p (t(src := dest # t src))
        (m(dest \<mapsto> src))
     = (if p = dest then next_child src t else next_sib p t m)" apply(case_tac "next_child src t") apply(simp) apply(drule next_child_NoneD) apply(safe)[1] apply(rule_tac p=src in next_sib_NoneI) apply(simp) apply(case_tac "next_sib p t m") apply(simp) apply(drule next_sib_NoneD) apply(erule disjE) apply(rule next_sib_NoneI) apply(simp) apply(elim exE conjE) apply(rule_tac p=pa in next_sib_NoneI) apply(simp) apply(simp) apply(drule next_sibD) apply(elim exE conjE) apply(rule_tac p=pa in next_sibI) apply(simp) apply(fastforce simp: valid_list_2_def) apply(drule (1) next_childD) apply(simp, safe) apply(case_tac "next_child src t") apply(fastforce dest: next_child_NoneD) apply(simp) apply(fastforce dest: next_childD intro: next_sibI) apply(case_tac "next_sib p t m") apply(fastforce dest: next_sib_NoneD next_sibD intro: next_sib_NoneI next_sibI)+ done

(* Proof state trace *)
proof (prove)
goal (1 subgoal):
 1. valid_list_2 t m \<Longrightarrow> next_sib p (t(src := dest # t src)) (m(dest \<mapsto> src)) = (if p = dest then next_child src t else next_sib p t m) proof (prove)
goal (2 subgoals):
 1. \<lbrakk>valid_list_2 t m; next_child src t = None\<rbrakk> \<Longrightarrow> next_sib p (t(src := dest # t src)) (m(dest \<mapsto> src)) = (if p = dest then next_child src t else next_sib p t m)
 2. \<And>a. \<lbrakk>valid_list_2 t m; next_child src t = Some a\<rbrakk> \<Longrightarrow> next_sib p (t(src := dest # t src)) (m(dest \<mapsto> src)) = (if p = dest then next_child src t else next_sib p t m) proof (prove)
goal (2 subgoals):
 1. \<lbrakk>valid_list_2 t m; next_child src t = None\<rbrakk> \<Longrightarrow> (p = dest \<longrightarrow> next_sib dest (t(src := dest # t src)) (m(dest \<mapsto> src)) = None) \<and> (p \<noteq> dest \<longrightarrow> next_sib p (t(src := dest # t src)) (m(dest \<mapsto> src)) = next_sib p t m)
 2. \<And>a. \<lbrakk>valid_list_2 t m; next_child src t = Some a\<rbrakk> \<Longrightarrow> next_sib p (t(src := dest # t src)) (m(dest \<mapsto> src)) = (if p = dest then next_child src t else next_sib p t m) proof (prove)
goal (2 subgoals):
 1. \<lbrakk>valid_list_2 t m; t src = []\<rbrakk> \<Longrightarrow> (p = dest \<longrightarrow> next_sib dest (t(src := dest # t src)) (m(dest \<mapsto> src)) = None) \<and> (p \<noteq> dest \<longrightarrow> next_sib p (t(src := dest # t src)) (m(dest \<mapsto> src)) = next_sib p t m)
 2. \<And>a. \<lbrakk>valid_list_2 t m; next_child src t = Some a\<rbrakk> \<Longrightarrow> next_sib p (t(src := dest # t src)) (m(dest \<mapsto> src)) = (if p = dest then next_child src t else next_sib p t m) proof (prove)
goal (3 subgoals):
 1. \<lbrakk>valid_list_2 t m; t src = []; p = dest\<rbrakk> \<Longrightarrow> next_sib dest (t(src := dest # t src)) (m(dest \<mapsto> src)) = None
 2. \<lbrakk>valid_list_2 t m; t src = []; p \<noteq> dest\<rbrakk> \<Longrightarrow> next_sib p (t(src := dest # t src)) (m(dest \<mapsto> src)) = next_sib p t m
 3. \<And>a. \<lbrakk>valid_list_2 t m; next_child src t = Some a\<rbrakk> \<Longrightarrow> next_sib p (t(src := dest # t src)) (m(dest \<mapsto> src)) = (if p = dest then next_child src t else next_sib p t m) proof (prove)
goal (3 subgoals):
 1. \<lbrakk>valid_list_2 t m; t src = []; p = dest\<rbrakk> \<Longrightarrow> (m(dest \<mapsto> src)) dest = None \<or> (m(dest \<mapsto> src)) dest = Some src \<and> after_in_list ((t(src := dest # t src)) src) dest = None
 2. \<lbrakk>valid_list_2 t m; t src = []; p \<noteq> dest\<rbrakk> \<Longrightarrow> next_sib p (t(src := dest # t src)) (m(dest \<mapsto> src)) = next_sib p t m
 3. \<And>a. \<lbrakk>valid_list_2 t m; next_child src t = Some a\<rbrakk> \<Longrightarrow> next_sib p (t(src := dest # t src)) (m(dest \<mapsto> src)) = (if p = dest then next_child src t else next_sib p t m) proof (prove)
goal (2 subgoals):
 1. \<lbrakk>valid_list_2 t m; t src = []; p \<noteq> dest\<rbrakk> \<Longrightarrow> next_sib p (t(src := dest # t src)) (m(dest \<mapsto> src)) = next_sib p t m
 2. \<And>a. \<lbrakk>valid_list_2 t m; next_child src t = Some a\<rbrakk> \<Longrightarrow> next_sib p (t(src := dest # t src)) (m(dest \<mapsto> src)) = (if p = dest then next_child src t else next_sib p t m) proof (prove)
goal (3 subgoals):
 1. \<lbrakk>valid_list_2 t m; t src = []; p \<noteq> dest; next_sib p t m = None\<rbrakk> \<Longrightarrow> next_sib p (t(src := dest # t src)) (m(dest \<mapsto> src)) = next_sib p t m
 2. \<And>a. \<lbrakk>valid_list_2 t m; t src = []; p \<noteq> dest; next_sib p t m = Some a\<rbrakk> \<Longrightarrow> next_sib p (t(src := dest # t src)) (m(dest \<mapsto> src)) = next_sib p t m
 3. \<And>a. \<lbrakk>valid_list_2 t m; next_child src t = Some a\<rbrakk> \<Longrightarrow> next_sib p (t(src := dest # t src)) (m(dest \<mapsto> src)) = (if p = dest then next_child src t else next_sib p t m) proof (prove)
goal (3 subgoals):
 1. \<lbrakk>valid_list_2 t m; t src = []; p \<noteq> dest; next_sib p t m = None\<rbrakk> \<Longrightarrow> next_sib p (t(src := [dest])) (m(dest \<mapsto> src)) = None
 2. \<And>a. \<lbrakk>valid_list_2 t m; t src = []; p \<noteq> dest; next_sib p t m = Some a\<rbrakk> \<Longrightarrow> next_sib p (t(src := dest # t src)) (m(dest \<mapsto> src)) = next_sib p t m
 3. \<And>a. \<lbrakk>valid_list_2 t m; next_child src t = Some a\<rbrakk> \<Longrightarrow> next_sib p (t(src := dest # t src)) (m(dest \<mapsto> src)) = (if p = dest then next_child src t else next_sib p t m) proof (prove)
goal (3 subgoals):
 1. \<lbrakk>valid_list_2 t m; t src = []; p \<noteq> dest; m p = None \<or> (\<exists>pa. m p = Some pa \<and> after_in_list (t pa) p = None)\<rbrakk> \<Longrightarrow> next_sib p (t(src := [dest])) (m(dest \<mapsto> src)) = None
 2. \<And>a. \<lbrakk>valid_list_2 t m; t src = []; p \<noteq> dest; next_sib p t m = Some a\<rbrakk> \<Longrightarrow> next_sib p (t(src := dest # t src)) (m(dest \<mapsto> src)) = next_sib p t m
 3. \<And>a. \<lbrakk>valid_list_2 t m; next_child src t = Some a\<rbrakk> \<Longrightarrow> next_sib p (t(src := dest # t src)) (m(dest \<mapsto> src)) = (if p = dest then next_child src t else next_sib p t m) proof (prove)
goal (4 subgoals):
 1. \<lbrakk>valid_list_2 t m; t src = []; p \<noteq> dest; m p = None\<rbrakk> \<Longrightarrow> next_sib p (t(src := [dest])) (m(dest \<mapsto> src)) = None
 2. \<lbrakk>valid_list_2 t m; t src = []; p \<noteq> dest; \<exists>pa. m p = Some pa \<and> after_in_list (t pa) p = None\<rbrakk> \<Longrightarrow> next_sib p (t(src := [dest])) (m(dest \<mapsto> src)) = None
 3. \<And>a. \<lbrakk>valid_list_2 t m; t src = []; p \<noteq> dest; next_sib p t m = Some a\<rbrakk> \<Longrightarrow> next_sib p (t(src := dest # t src)) (m(dest \<mapsto> src)) = next_sib p t m
 4. \<And>a. \<lbrakk>valid_list_2 t m; next_child src t = Some a\<rbrakk> \<Longrightarrow> next_sib p (t(src := dest # t src)) (m(dest \<mapsto> src)) = (if p = dest then next_child src t else next_sib p t m) proof (prove)
goal (4 subgoals):
 1. \<lbrakk>valid_list_2 t m; t src = []; p \<noteq> dest; m p = None\<rbrakk> \<Longrightarrow> (m(dest \<mapsto> src)) p = None \<or> (m(dest \<mapsto> src)) p = Some ?p22 \<and> after_in_list ((t(src := [dest])) ?p22) p = None
 2. \<lbrakk>valid_list_2 t m; t src = []; p \<noteq> dest; \<exists>pa. m p = Some pa \<and> after_in_list (t pa) p = None\<rbrakk> \<Longrightarrow> next_sib p (t(src := [dest])) (m(dest \<mapsto> src)) = None
 3. \<And>a. \<lbrakk>valid_list_2 t m; t src = []; p \<noteq> dest; next_sib p t m = Some a\<rbrakk> \<Longrightarrow> next_sib p (t(src := dest # t src)) (m(dest \<mapsto> src)) = next_sib p t m
 4. \<And>a. \<lbrakk>valid_list_2 t m; next_child src t = Some a\<rbrakk> \<Longrightarrow> next_sib p (t(src := dest # t src)) (m(dest \<mapsto> src)) = (if p = dest then next_child src t else next_sib p t m) proof (prove)
goal (3 subgoals):
 1. \<lbrakk>valid_list_2 t m; t src = []; p \<noteq> dest; \<exists>pa. m p = Some pa \<and> after_in_list (t pa) p = None\<rbrakk> \<Longrightarrow> next_sib p (t(src := [dest])) (m(dest \<mapsto> src)) = None
 2. \<And>a. \<lbrakk>valid_list_2 t m; t src = []; p \<noteq> dest; next_sib p t m = Some a\<rbrakk> \<Longrightarrow> next_sib p (t(src := dest # t src)) (m(dest \<mapsto> src)) = next_sib p t m
 3. \<And>a. \<lbrakk>valid_list_2 t m; next_child src t = Some a\<rbrakk> \<Longrightarrow> next_sib p (t(src := dest # t src)) (m(dest \<mapsto> src)) = (if p = dest then next_child src t else next_sib p t m) proof (prove)
goal (3 subgoals):
 1. \<And>pa. \<lbrakk>valid_list_2 t m; t src = []; p \<noteq> dest; m p = Some pa; after_in_list (t pa) p = None\<rbrakk> \<Longrightarrow> next_sib p (t(src := [dest])) (m(dest \<mapsto> src)) = None
 2. \<And>a. \<lbrakk>valid_list_2 t m; t src = []; p \<noteq> dest; next_sib p t m = Some a\<rbrakk> \<Longrightarrow> next_sib p (t(src := dest # t src)) (m(dest \<mapsto> src)) = next_sib p t m
 3. \<And>a. \<lbrakk>valid_list_2 t m; next_child src t = Some a\<rbrakk> \<Longrightarrow> next_sib p (t(src := dest # t src)) (m(dest \<mapsto> src)) = (if p = dest then next_child src t else next_sib p t m) proof (prove)
goal (3 subgoals):
 1. \<And>pa. \<lbrakk>valid_list_2 t m; t src = []; p \<noteq> dest; m p = Some pa; after_in_list (t pa) p = None\<rbrakk> \<Longrightarrow> (m(dest \<mapsto> src)) p = None \<or> (m(dest \<mapsto> src)) p = Some pa \<and> after_in_list ((t(src := [dest])) pa) p = None
 2. \<And>a. \<lbrakk>valid_list_2 t m; t src = []; p \<noteq> dest; next_sib p t m = Some a\<rbrakk> \<Longrightarrow> next_sib p (t(src := dest # t src)) (m(dest \<mapsto> src)) = next_sib p t m
 3. \<And>a. \<lbrakk>valid_list_2 t m; next_child src t = Some a\<rbrakk> \<Longrightarrow> next_sib p (t(src := dest # t src)) (m(dest \<mapsto> src)) = (if p = dest then next_child src t else next_sib p t m) proof (prove)
goal (2 subgoals):
 1. \<And>a. \<lbrakk>valid_list_2 t m; t src = []; p \<noteq> dest; next_sib p t m = Some a\<rbrakk> \<Longrightarrow> next_sib p (t(src := dest # t src)) (m(dest \<mapsto> src)) = next_sib p t m
 2. \<And>a. \<lbrakk>valid_list_2 t m; next_child src t = Some a\<rbrakk> \<Longrightarrow> next_sib p (t(src := dest # t src)) (m(dest \<mapsto> src)) = (if p = dest then next_child src t else next_sib p t m) proof (prove)
goal (2 subgoals):
 1. \<And>a. \<lbrakk>valid_list_2 t m; t src = []; p \<noteq> dest; next_sib p t m = Some a\<rbrakk> \<Longrightarrow> next_sib p (t(src := [dest])) (m(dest \<mapsto> src)) = Some a
 2. \<And>a. \<lbrakk>valid_list_2 t m; next_child src t = Some a\<rbrakk> \<Longrightarrow> next_sib p (t(src := dest # t src)) (m(dest \<mapsto> src)) = (if p = dest then next_child src t else next_sib p t m) proof (prove)
goal (2 subgoals):
 1. \<And>a. \<lbrakk>valid_list_2 t m; t src = []; p \<noteq> dest; \<exists>pa. m p = Some pa \<and> after_in_list (t pa) p = Some a\<rbrakk> \<Longrightarrow> next_sib p (t(src := [dest])) (m(dest \<mapsto> src)) = Some a
 2. \<And>a. \<lbrakk>valid_list_2 t m; next_child src t = Some a\<rbrakk> \<Longrightarrow> next_sib p (t(src := dest # t src)) (m(dest \<mapsto> src)) = (if p = dest then next_child src t else next_sib p t m) proof (prove)
goal (2 subgoals):
 1. \<And>a pa. \<lbrakk>valid_list_2 t m; t src = []; p \<noteq> dest; m p = Some pa; after_in_list (t pa) p = Some a\<rbrakk> \<Longrightarrow> next_sib p (t(src := [dest])) (m(dest \<mapsto> src)) = Some a
 2. \<And>a. \<lbrakk>valid_list_2 t m; next_child src t = Some a\<rbrakk> \<Longrightarrow> next_sib p (t(src := dest # t src)) (m(dest \<mapsto> src)) = (if p = dest then next_child src t else next_sib p t m) proof (prove)
goal (3 subgoals):
 1. \<And>a pa. \<lbrakk>valid_list_2 t m; t src = []; p \<noteq> dest; m p = Some pa; after_in_list (t pa) p = Some a\<rbrakk> \<Longrightarrow> (m(dest \<mapsto> src)) p = Some pa
 2. \<And>a pa. \<lbrakk>valid_list_2 t m; t src = []; p \<noteq> dest; m p = Some pa; after_in_list (t pa) p = Some a\<rbrakk> \<Longrightarrow> after_in_list ((t(src := [dest])) pa) p = Some a
 3. \<And>a. \<lbrakk>valid_list_2 t m; next_child src t = Some a\<rbrakk> \<Longrightarrow> next_sib p (t(src := dest # t src)) (m(dest \<mapsto> src)) = (if p = dest then next_child src t else next_sib p t m) proof (prove)
goal (2 subgoals):
 1. \<And>a pa. \<lbrakk>valid_list_2 t m; t src = []; p \<noteq> dest; m p = Some pa; after_in_list (t pa) p = Some a\<rbrakk> \<Longrightarrow> after_in_list ((t(src := [dest])) pa) p = Some a
 2. \<And>a. \<lbrakk>valid_list_2 t m; next_child src t = Some a\<rbrakk> \<Longrightarrow> next_sib p (t(src := dest # t src)) (m(dest \<mapsto> src)) = (if p = dest then next_child src t else next_sib p t m) proof (prove)
goal (1 subgoal):
 1. \<And>a. \<lbrakk>valid_list_2 t m; next_child src t = Some a\<rbrakk> \<Longrightarrow> next_sib p (t(src := dest # t src)) (m(dest \<mapsto> src)) = (if p = dest then next_child src t else next_sib p t m) proof (prove)
goal (1 subgoal):
 1. \<And>a. \<lbrakk>valid_list_2 t m; (\<exists>xs. t src = a # xs) \<and> m a = Some src\<rbrakk> \<Longrightarrow> next_sib p (t(src := dest # t src)) (m(dest \<mapsto> src)) = (if p = dest then next_child src t else next_sib p t m) proof (prove)
goal (2 subgoals):
 1. \<And>a b xs. \<lbrakk>valid_list_2 t m; m (a, b) = Some src; t src = (a, b) # xs; p = dest\<rbrakk> \<Longrightarrow> next_sib dest (t(src := dest # t src)) (m(dest \<mapsto> src)) = next_child src t
 2. \<And>a b xs. \<lbrakk>valid_list_2 t m; m (a, b) = Some src; t src = (a, b) # xs; p \<noteq> dest\<rbrakk> \<Longrightarrow> next_sib p (t(src := dest # t src)) (m(dest \<mapsto> src)) = next_sib p t m proof (prove)
goal (3 subgoals):
 1. \<And>a b xs. \<lbrakk>valid_list_2 t m; m (a, b) = Some src; t src = (a, b) # xs; p = dest; next_child src t = None\<rbrakk> \<Longrightarrow> next_sib dest (t(src := dest # t src)) (m(dest \<mapsto> src)) = next_child src t
 2. \<And>a b xs aa. \<lbrakk>valid_list_2 t m; m (a, b) = Some src; t src = (a, b) # xs; p = dest; next_child src t = Some aa\<rbrakk> \<Longrightarrow> next_sib dest (t(src := dest # t src)) (m(dest \<mapsto> src)) = next_child src t
 3. \<And>a b xs. \<lbrakk>valid_list_2 t m; m (a, b) = Some src; t src = (a, b) # xs; p \<noteq> dest\<rbrakk> \<Longrightarrow> next_sib p (t(src := dest # t src)) (m(dest \<mapsto> src)) = next_sib p t m proof (prove)
goal (2 subgoals):
 1. \<And>a b xs aa. \<lbrakk>valid_list_2 t m; m (a, b) = Some src; t src = (a, b) # xs; p = dest; next_child src t = Some aa\<rbrakk> \<Longrightarrow> next_sib dest (t(src := dest # t src)) (m(dest \<mapsto> src)) = next_child src t
 2. \<And>a b xs. \<lbrakk>valid_list_2 t m; m (a, b) = Some src; t src = (a, b) # xs; p \<noteq> dest\<rbrakk> \<Longrightarrow> next_sib p (t(src := dest # t src)) (m(dest \<mapsto> src)) = next_sib p t m proof (prove)
goal (2 subgoals):
 1. \<And>a b xs aa. \<lbrakk>valid_list_2 t m; m (a, b) = Some src; t src = (a, b) # xs; p = dest; next_child src t = Some aa\<rbrakk> \<Longrightarrow> next_sib dest (t(src := dest # (a, b) # xs)) (m(dest \<mapsto> src)) = Some aa
 2. \<And>a b xs. \<lbrakk>valid_list_2 t m; m (a, b) = Some src; t src = (a, b) # xs; p \<noteq> dest\<rbrakk> \<Longrightarrow> next_sib p (t(src := dest # t src)) (m(dest \<mapsto> src)) = next_sib p t m proof (prove)
goal (1 subgoal):
 1. \<And>a b xs. \<lbrakk>valid_list_2 t m; m (a, b) = Some src; t src = (a, b) # xs; p \<noteq> dest\<rbrakk> \<Longrightarrow> next_sib p (t(src := dest # t src)) (m(dest \<mapsto> src)) = next_sib p t m proof (prove)
goal (2 subgoals):
 1. \<And>a b xs. \<lbrakk>valid_list_2 t m; m (a, b) = Some src; t src = (a, b) # xs; p \<noteq> dest; next_sib p t m = None\<rbrakk> \<Longrightarrow> next_sib p (t(src := dest # t src)) (m(dest \<mapsto> src)) = next_sib p t m
 2. \<And>a b xs aa. \<lbrakk>valid_list_2 t m; m (a, b) = Some src; t src = (a, b) # xs; p \<noteq> dest; next_sib p t m = Some aa\<rbrakk> \<Longrightarrow> next_sib p (t(src := dest # t src)) (m(dest \<mapsto> src)) = next_sib p t m proof (prove)
goal:
No subgoals!