equal
deleted
inserted
replaced
618 |
618 |
619 fun tac ctxt [] = |
619 fun tac ctxt [] = |
620 resolve_tac ctxt [set_singleton] 1 ORELSE |
620 resolve_tac ctxt [set_singleton] 1 ORELSE |
621 resolve_tac ctxt [inst_Collect_mem_eq] 1 |
621 resolve_tac ctxt [inst_Collect_mem_eq] 1 |
622 | tac ctxt (If :: cont) = |
622 | tac ctxt (If :: cont) = |
623 Splitter.split_tac ctxt @{thms split_if} 1 |
623 Splitter.split_tac ctxt @{thms if_split} 1 |
624 THEN resolve_tac ctxt @{thms conjI} 1 |
624 THEN resolve_tac ctxt @{thms conjI} 1 |
625 THEN resolve_tac ctxt @{thms impI} 1 |
625 THEN resolve_tac ctxt @{thms impI} 1 |
626 THEN Subgoal.FOCUS (fn {prems, context = ctxt', ...} => |
626 THEN Subgoal.FOCUS (fn {prems, context = ctxt', ...} => |
627 CONVERSION (right_hand_set_comprehension_conv (K |
627 CONVERSION (right_hand_set_comprehension_conv (K |
628 (HOLogic.conj_conv (Conv.rewr_conv (List.last prems RS @{thm Eq_TrueI})) Conv.all_conv |
628 (HOLogic.conj_conv (Conv.rewr_conv (List.last prems RS @{thm Eq_TrueI})) Conv.all_conv |
1467 "\<lbrakk> x : set xs; ~ P x \<rbrakk> \<Longrightarrow> length(filter P xs) < length xs" |
1467 "\<lbrakk> x : set xs; ~ P x \<rbrakk> \<Longrightarrow> length(filter P xs) < length xs" |
1468 proof (induct xs) |
1468 proof (induct xs) |
1469 case Nil thus ?case by simp |
1469 case Nil thus ?case by simp |
1470 next |
1470 next |
1471 case (Cons x xs) thus ?case |
1471 case (Cons x xs) thus ?case |
1472 apply (auto split:split_if_asm) |
1472 apply (auto split:if_split_asm) |
1473 using length_filter_le[of P xs] apply arith |
1473 using length_filter_le[of P xs] apply arith |
1474 done |
1474 done |
1475 qed |
1475 qed |
1476 |
1476 |
1477 lemma length_filter_conv_card: |
1477 lemma length_filter_conv_card: |
1916 lemma append_butlast_last_id [simp]: |
1916 lemma append_butlast_last_id [simp]: |
1917 "xs \<noteq> [] ==> butlast xs @ [last xs] = xs" |
1917 "xs \<noteq> [] ==> butlast xs @ [last xs] = xs" |
1918 by (induct xs) auto |
1918 by (induct xs) auto |
1919 |
1919 |
1920 lemma in_set_butlastD: "x : set (butlast xs) ==> x : set xs" |
1920 lemma in_set_butlastD: "x : set (butlast xs) ==> x : set xs" |
1921 by (induct xs) (auto split: split_if_asm) |
1921 by (induct xs) (auto split: if_split_asm) |
1922 |
1922 |
1923 lemma in_set_butlast_appendI: |
1923 lemma in_set_butlast_appendI: |
1924 "x : set (butlast xs) | x : set (butlast ys) ==> x : set (butlast (xs @ ys))" |
1924 "x : set (butlast xs) | x : set (butlast ys) ==> x : set (butlast (xs @ ys))" |
1925 by (auto dest: in_set_butlastD simp add: butlast_append) |
1925 by (auto dest: in_set_butlastD simp add: butlast_append) |
1926 |
1926 |
2259 lemma dropWhile_last: |
2259 lemma dropWhile_last: |
2260 "x \<in> set xs \<Longrightarrow> \<not> P x \<Longrightarrow> last (dropWhile P xs) = last xs" |
2260 "x \<in> set xs \<Longrightarrow> \<not> P x \<Longrightarrow> last (dropWhile P xs) = last xs" |
2261 by (auto simp add: dropWhile_append3 in_set_conv_decomp) |
2261 by (auto simp add: dropWhile_append3 in_set_conv_decomp) |
2262 |
2262 |
2263 lemma set_dropWhileD: "x \<in> set (dropWhile P xs) \<Longrightarrow> x \<in> set xs" |
2263 lemma set_dropWhileD: "x \<in> set (dropWhile P xs) \<Longrightarrow> x \<in> set xs" |
2264 by (induct xs) (auto split: split_if_asm) |
2264 by (induct xs) (auto split: if_split_asm) |
2265 |
2265 |
2266 lemma set_takeWhileD: "x : set (takeWhile P xs) ==> x : set xs \<and> P x" |
2266 lemma set_takeWhileD: "x : set (takeWhile P xs) ==> x : set xs \<and> P x" |
2267 by (induct xs) (auto split: split_if_asm) |
2267 by (induct xs) (auto split: if_split_asm) |
2268 |
2268 |
2269 lemma takeWhile_eq_all_conv[simp]: |
2269 lemma takeWhile_eq_all_conv[simp]: |
2270 "(takeWhile P xs = xs) = (\<forall>x \<in> set xs. P x)" |
2270 "(takeWhile P xs = xs) = (\<forall>x \<in> set xs. P x)" |
2271 by(induct xs, auto) |
2271 by(induct xs, auto) |
2272 |
2272 |
3320 proof (cases "x \<in> set xs") |
3320 proof (cases "x \<in> set xs") |
3321 case False with Cons show ?thesis by simp |
3321 case False with Cons show ?thesis by simp |
3322 next |
3322 next |
3323 case True with Cons.prems |
3323 case True with Cons.prems |
3324 have "card (set xs) = Suc (length xs)" |
3324 have "card (set xs) = Suc (length xs)" |
3325 by (simp add: card_insert_if split: split_if_asm) |
3325 by (simp add: card_insert_if split: if_split_asm) |
3326 moreover have "card (set xs) \<le> length xs" by (rule card_length) |
3326 moreover have "card (set xs) \<le> length xs" by (rule card_length) |
3327 ultimately have False by simp |
3327 ultimately have False by simp |
3328 thus ?thesis .. |
3328 thus ?thesis .. |
3329 qed |
3329 qed |
3330 qed |
3330 qed |
3333 by (induct xs) (auto) |
3333 by (induct xs) (auto) |
3334 |
3334 |
3335 lemma not_distinct_decomp: "~ distinct ws ==> EX xs ys zs y. ws = xs@[y]@ys@[y]@zs" |
3335 lemma not_distinct_decomp: "~ distinct ws ==> EX xs ys zs y. ws = xs@[y]@ys@[y]@zs" |
3336 apply (induct n == "length ws" arbitrary:ws) apply simp |
3336 apply (induct n == "length ws" arbitrary:ws) apply simp |
3337 apply(case_tac ws) apply simp |
3337 apply(case_tac ws) apply simp |
3338 apply (simp split:split_if_asm) |
3338 apply (simp split:if_split_asm) |
3339 apply (metis Cons_eq_appendI eq_Nil_appendI split_list) |
3339 apply (metis Cons_eq_appendI eq_Nil_appendI split_list) |
3340 done |
3340 done |
3341 |
3341 |
3342 lemma not_distinct_conv_prefix: |
3342 lemma not_distinct_conv_prefix: |
3343 defines "dec as xs y ys \<equiv> y \<in> set xs \<and> distinct xs \<and> as = xs @ y # ys" |
3343 defines "dec as xs y ys \<equiv> y \<in> set xs \<and> distinct xs \<and> as = xs @ y # ys" |
3655 "remdups_adj (xs\<^sub>1 @ x # xs\<^sub>2) = remdups_adj (xs\<^sub>1 @ [x]) @ tl (remdups_adj (x # xs\<^sub>2))" |
3655 "remdups_adj (xs\<^sub>1 @ x # xs\<^sub>2) = remdups_adj (xs\<^sub>1 @ [x]) @ tl (remdups_adj (x # xs\<^sub>2))" |
3656 by (induct xs\<^sub>1 rule: remdups_adj.induct, simp_all) |
3656 by (induct xs\<^sub>1 rule: remdups_adj.induct, simp_all) |
3657 |
3657 |
3658 lemma remdups_adj_singleton: |
3658 lemma remdups_adj_singleton: |
3659 "remdups_adj xs = [x] \<Longrightarrow> xs = replicate (length xs) x" |
3659 "remdups_adj xs = [x] \<Longrightarrow> xs = replicate (length xs) x" |
3660 by (induct xs rule: remdups_adj.induct, auto split: split_if_asm) |
3660 by (induct xs rule: remdups_adj.induct, auto split: if_split_asm) |
3661 |
3661 |
3662 lemma remdups_adj_map_injective: |
3662 lemma remdups_adj_map_injective: |
3663 assumes "inj f" |
3663 assumes "inj f" |
3664 shows "remdups_adj (map f xs) = map f (remdups_adj xs)" |
3664 shows "remdups_adj (map f xs) = map f (remdups_adj xs)" |
3665 by (induct xs rule: remdups_adj.induct) (auto simp add: injD[OF assms]) |
3665 by (induct xs rule: remdups_adj.induct) (auto simp add: injD[OF assms]) |
4812 "sorted l \<Longrightarrow> sorted (remdups l)" |
4812 "sorted l \<Longrightarrow> sorted (remdups l)" |
4813 by (induct l) (auto simp: sorted_Cons) |
4813 by (induct l) (auto simp: sorted_Cons) |
4814 |
4814 |
4815 lemma sorted_remdups_adj[simp]: |
4815 lemma sorted_remdups_adj[simp]: |
4816 "sorted xs \<Longrightarrow> sorted (remdups_adj xs)" |
4816 "sorted xs \<Longrightarrow> sorted (remdups_adj xs)" |
4817 by (induct xs rule: remdups_adj.induct, simp_all split: split_if_asm add: sorted_Cons) |
4817 by (induct xs rule: remdups_adj.induct, simp_all split: if_split_asm add: sorted_Cons) |
4818 |
4818 |
4819 lemma sorted_distinct_set_unique: |
4819 lemma sorted_distinct_set_unique: |
4820 assumes "sorted xs" "distinct xs" "sorted ys" "distinct ys" "set xs = set ys" |
4820 assumes "sorted xs" "distinct xs" "sorted ys" "distinct ys" "set xs = set ys" |
4821 shows "xs = ys" |
4821 shows "xs = ys" |
4822 proof - |
4822 proof - |
6764 "Id_on (set xs) = set [(x, x). x \<leftarrow> xs]" |
6764 "Id_on (set xs) = set [(x, x). x \<leftarrow> xs]" |
6765 by (auto simp add: Id_on_def) |
6765 by (auto simp add: Id_on_def) |
6766 |
6766 |
6767 lemma [code]: |
6767 lemma [code]: |
6768 "R `` S = List.map_project (%(x, y). if x : S then Some y else None) R" |
6768 "R `` S = List.map_project (%(x, y). if x : S then Some y else None) R" |
6769 unfolding map_project_def by (auto split: prod.split split_if_asm) |
6769 unfolding map_project_def by (auto split: prod.split if_split_asm) |
6770 |
6770 |
6771 lemma trancl_set_ntrancl [code]: |
6771 lemma trancl_set_ntrancl [code]: |
6772 "trancl (set xs) = ntrancl (card (set xs) - 1) (set xs)" |
6772 "trancl (set xs) = ntrancl (card (set xs) - 1) (set xs)" |
6773 by (simp add: finite_trancl_ntranl) |
6773 by (simp add: finite_trancl_ntranl) |
6774 |
6774 |