# HG changeset patch # User nipkow # Date 1089889894 -7200 # Node ID d59f7e2e18d3ef81128b428a721fba05a258e0fd # Parent f224d27bb1f8caff9d8ec2d057dce52870b0c5d8 Moved to new m<.. n + m - i < m" by arith from True have "coeff P (monom P \ (Suc n)) k = \" by simp also from True - have "... = (\i \ {..n(} \ {n}. coeff P (monom P \ n) i \ + have "... = (\i \ {.. {n}. coeff P (monom P \ n) i \ coeff P (monom P \ 1) (k - i))" by (simp cong: finsum_cong add: finsum_Un_disjoint Pi_def) also have "... = (\i \ {..n}. coeff P (monom P \ n) i \ coeff P (monom P \ 1) (k - i))" by (simp only: ivl_disj_un_singleton) - also from True have "... = (\i \ {..n} \ {)n..k}. coeff P (monom P \ n) i \ + also from True have "... = (\i \ {..n} \ {n<..k}. coeff P (monom P \ n) i \ coeff P (monom P \ 1) (k - i))" by (simp cong: finsum_cong add: finsum_Un_disjoint ivl_disj_int_one order_less_imp_not_eq Pi_def) @@ -668,10 +668,10 @@ from neq have "coeff P (monom P \ (Suc n)) k = \" by simp also have "... = (\i \ {..k}. ?s i)" proof - - have f1: "(\i \ {..n(}. ?s i) = \" by (simp cong: finsum_cong add: Pi_def) + have f1: "(\i \ {.." by (simp cong: finsum_cong add: Pi_def) from neq have f2: "(\i \ {n}. ?s i) = \" by (simp cong: finsum_cong add: Pi_def) arith - have f3: "n < k ==> (\i \ {)n..k}. ?s i) = \" + have f3: "n < k ==> (\i \ {n<..k}. ?s i) = \" by (simp cong: finsum_cong add: order_less_imp_not_eq Pi_def) show ?thesis proof (cases "k < n") @@ -681,7 +681,7 @@ show ?thesis proof (cases "n = k") case True - then have "\ = (\i \ {..n(} \ {n}. ?s i)" + then have "\ = (\i \ {.. {n}. ?s i)" by (simp cong: finsum_cong add: finsum_Un_disjoint ivl_disj_int_singleton Pi_def) also from True have "... = (\i \ {..k}. ?s i)" @@ -689,12 +689,12 @@ finally show ?thesis . next case False with n_le_k have n_less_k: "n < k" by arith - with neq have "\ = (\i \ {..n(} \ {n}. ?s i)" + with neq have "\ = (\i \ {.. {n}. ?s i)" by (simp add: finsum_Un_disjoint f1 f2 ivl_disj_int_singleton Pi_def del: Un_insert_right) also have "... = (\i \ {..n}. ?s i)" by (simp only: ivl_disj_un_singleton) - also from n_less_k neq have "... = (\i \ {..n} \ {)n..k}. ?s i)" + also from n_less_k neq have "... = (\i \ {..n} \ {n<..k}. ?s i)" by (simp add: finsum_Un_disjoint f3 ivl_disj_int_one Pi_def) also from n_less_k have "... = (\i \ {..k}. ?s i)" by (simp only: ivl_disj_un_one) @@ -976,12 +976,12 @@ show "deg R p + deg R q <= deg R (p \\<^sub>2 q)" proof (rule deg_belowI, simp add: R) have "finsum R ?s {.. deg R p + deg R q} - = finsum R ?s ({.. deg R p(} Un {deg R p .. deg R p + deg R q})" + = finsum R ?s ({..< deg R p} Un {deg R p .. deg R p + deg R q})" by (simp only: ivl_disj_un_one) also have "... = finsum R ?s {deg R p .. deg R p + deg R q}" by (simp cong: finsum_cong add: finsum_Un_disjoint ivl_disj_int_one deg_aboveD less_add_diff R Pi_def) - also have "...= finsum R ?s ({deg R p} Un {)deg R p .. deg R p + deg R q})" + also have "...= finsum R ?s ({deg R p} Un {deg R p <.. deg R p + deg R q})" by (simp only: ivl_disj_un_singleton) also have "... = coeff P p (deg R p) \ coeff P q (deg R q)" by (simp cong: finsum_cong add: finsum_Un_disjoint @@ -1015,14 +1015,14 @@ proof (cases "k <= deg R p") case True hence "coeff P (finsum P ?s {..deg R p}) k = - coeff P (finsum P ?s ({..k} Un {)k..deg R p})) k" + coeff P (finsum P ?s ({..k} Un {k<..deg R p})) k" by (simp only: ivl_disj_un_one) also from True have "... = coeff P (finsum P ?s {..k}) k" by (simp cong: finsum_cong add: finsum_Un_disjoint ivl_disj_int_one order_less_imp_not_eq2 coeff_finsum R RR Pi_def) also - have "... = coeff P (finsum P ?s ({..k(} Un {k})) k" + have "... = coeff P (finsum P ?s ({.. carrier P" and "deg R p <= n" - then have "finsum P ?s {..n} = finsum P ?s ({..deg R p} Un {)deg R p..n})" + then have "finsum P ?s {..n} = finsum P ?s ({..deg R p} Un {deg R p<..n})" by (simp only: ivl_disj_un_one) also have "... = finsum P ?s {..deg R p}" by (simp cong: UP_finsum_cong add: UP_finsum_Un_disjoint ivl_disj_int_one @@ -1206,12 +1206,12 @@ from f g have "(\k \ {..n + m}. \i \ {..k}. f i \ g (k - i)) = (\k \ {..n + m}. \i \ {..n + m - k}. f k \ g i)" by (simp add: diagonal_sum Pi_def) - also have "... = (\k \ {..n} \ {)n..n + m}. \i \ {..n + m - k}. f k \ g i)" + also have "... = (\k \ {..n} \ {n<..n + m}. \i \ {..n + m - k}. f k \ g i)" by (simp only: ivl_disj_un_one) also from f g have "... = (\k \ {..n}. \i \ {..n + m - k}. f k \ g i)" by (simp cong: finsum_cong add: bound.bound [OF bf] finsum_Un_disjoint ivl_disj_int_one Pi_def) - also from f g have "... = (\k \ {..n}. \i \ {..m} \ {)m..n + m - k}. f k \ g i)" + also from f g have "... = (\k \ {..n}. \i \ {..m} \ {m<..n + m - k}. f k \ g i)" by (simp cong: finsum_cong add: ivl_disj_un_one le_add_diff Pi_def) also from f g have "... = (\k \ {..n}. \i \ {..m}. f k \ g i)" by (simp cong: finsum_cong @@ -1262,7 +1262,7 @@ proof (simp only: eval_on_carrier UP_mult_closed) from RS have "(\\<^sub>2 i \ {..deg R (p \\<^sub>3 q)}. h (coeff P (p \\<^sub>3 q) i) \\<^sub>2 s (^)\<^sub>2 i) = - (\\<^sub>2 i \ {..deg R (p \\<^sub>3 q)} \ {)deg R (p \\<^sub>3 q)..deg R p + deg R q}. + (\\<^sub>2 i \ {..deg R (p \\<^sub>3 q)} \ {deg R (p \\<^sub>3 q)<..deg R p + deg R q}. h (coeff P (p \\<^sub>3 q) i) \\<^sub>2 s (^)\<^sub>2 i)" by (simp cong: finsum_cong add: deg_aboveD finsum_Un_disjoint ivl_disj_int_one Pi_def @@ -1292,7 +1292,7 @@ proof (simp only: eval_on_carrier UP_a_closed) from RS have "(\\<^sub>2i \ {..deg R (p \\<^sub>3 q)}. h (coeff P (p \\<^sub>3 q) i) \\<^sub>2 s (^)\<^sub>2 i) = - (\\<^sub>2i \ {..deg R (p \\<^sub>3 q)} \ {)deg R (p \\<^sub>3 q)..max (deg R p) (deg R q)}. + (\\<^sub>2i \ {..deg R (p \\<^sub>3 q)} \ {deg R (p \\<^sub>3 q)<..max (deg R p) (deg R q)}. h (coeff P (p \\<^sub>3 q) i) \\<^sub>2 s (^)\<^sub>2 i)" by (simp cong: finsum_cong add: deg_aboveD finsum_Un_disjoint ivl_disj_int_one Pi_def @@ -1306,9 +1306,9 @@ by (simp cong: finsum_cong add: l_distr deg_aboveD finsum_Un_disjoint ivl_disj_int_one Pi_def) also have "... = - (\\<^sub>2 i \ {..deg R p} \ {)deg R p..max (deg R p) (deg R q)}. + (\\<^sub>2 i \ {..deg R p} \ {deg R p<..max (deg R p) (deg R q)}. h (coeff P p i) \\<^sub>2 s (^)\<^sub>2 i) \\<^sub>2 - (\\<^sub>2 i \ {..deg R q} \ {)deg R q..max (deg R p) (deg R q)}. + (\\<^sub>2 i \ {..deg R q} \ {deg R q<..max (deg R p) (deg R q)}. h (coeff P q i) \\<^sub>2 s (^)\<^sub>2 i)" by (simp only: ivl_disj_un_one le_maxI1 le_maxI2) also from RS have "... = @@ -1392,7 +1392,7 @@ assume S: "s \ carrier S" then have "(\\<^sub>2 i \ {..deg R (monom P \ 1)}. h (coeff P (monom P \ 1) i) \\<^sub>2 s (^)\<^sub>2 i) = - (\\<^sub>2i\{..deg R (monom P \ 1)} \ {)deg R (monom P \ 1)..1}. + (\\<^sub>2i\{..deg R (monom P \ 1)} \ {deg R (monom P \ 1)<..1}. h (coeff P (monom P \ 1) i) \\<^sub>2 s (^)\<^sub>2 i)" by (simp cong: finsum_cong del: coeff_monom add: deg_aboveD finsum_Un_disjoint ivl_disj_int_one Pi_def) diff -r f224d27bb1f8 -r d59f7e2e18d3 src/HOL/Algebra/poly/UnivPoly2.thy --- a/src/HOL/Algebra/poly/UnivPoly2.thy Thu Jul 15 08:38:37 2004 +0200 +++ b/src/HOL/Algebra/poly/UnivPoly2.thy Thu Jul 15 13:11:34 2004 +0200 @@ -643,12 +643,12 @@ show "deg p + deg q <= deg (p * q)" proof (rule deg_belowI, simp) have "setsum ?s {.. deg p + deg q} - = setsum ?s ({.. deg p(} Un {deg p .. deg p + deg q})" + = setsum ?s ({..< deg p} Un {deg p .. deg p + deg q})" by (simp only: ivl_disj_un_one) also have "... = setsum ?s {deg p .. deg p + deg q}" by (simp add: setsum_Un_disjoint ivl_disj_int_one setsum_0 deg_aboveD less_add_diff) - also have "... = setsum ?s ({deg p} Un {)deg p .. deg p + deg q})" + also have "... = setsum ?s ({deg p} Un {deg p <.. deg p + deg q})" by (simp only: ivl_disj_un_singleton) also have "... = coeff p (deg p) * coeff q (deg q)" by (simp add: setsum_Un_disjoint ivl_disj_int_singleton @@ -686,14 +686,14 @@ proof (cases "k <= deg p") case True hence "coeff (setsum ?s {..deg p}) k = - coeff (setsum ?s ({..k} Un {)k..deg p})) k" + coeff (setsum ?s ({..k} Un {k<..deg p})) k" by (simp only: ivl_disj_un_one) also from True have "... = coeff (setsum ?s {..k}) k" by (simp add: setsum_Un_disjoint ivl_disj_int_one order_less_imp_not_eq2 setsum_0 coeff_natsum ) also - have "... = coeff (setsum ?s ({..k(} Un {k})) k" + have "... = coeff (setsum ?s ({..j \ Suc (\i::nat< n. b i)=(\i< n. (b (j := Suc 0)) i)" apply(frule_tac b="(b (j:=(Suc 0)))" in Example2_lemma2_aux) -apply(erule_tac t="setsum (b(j := (Suc 0))) {..n(}" in ssubst) +apply(erule_tac t="setsum (b(j := (Suc 0))) {..iiiij") diff -r f224d27bb1f8 -r d59f7e2e18d3 src/HOL/HoareParallel/RG_Examples.thy --- a/src/HOL/HoareParallel/RG_Examples.thy Thu Jul 15 08:38:37 2004 +0200 +++ b/src/HOL/HoareParallel/RG_Examples.thy Thu Jul 15 13:11:34 2004 +0200 @@ -212,10 +212,10 @@ lemma Example2_lemma2: "!!b. \j \ Suc (\i::nat< n. b i)=(\i< n. (b (j := Suc 0)) i)" apply(frule_tac b="(b (j:=(Suc 0)))" in Example2_lemma2_aux) -apply(erule_tac t="setsum (b(j := (Suc 0))) {..n(}" in ssubst) +apply(erule_tac t="setsum (b(j := (Suc 0))) {..iiiij") diff -r f224d27bb1f8 -r d59f7e2e18d3 src/HOL/Infinite_Set.thy --- a/src/HOL/Infinite_Set.thy Thu Jul 15 08:38:37 2004 +0200 +++ b/src/HOL/Infinite_Set.thy Thu Jul 15 13:11:34 2004 +0200 @@ -68,7 +68,7 @@ lemma finite_nat_bounded: assumes S: "finite (S::nat set)" - shows "\k. S \ {..k(}" (is "\k. ?bounded S k") + shows "\k. S \ {..k. ?bounded S k") using S proof (induct) have "?bounded {} 0" by simp @@ -89,13 +89,13 @@ qed lemma finite_nat_iff_bounded: - "finite (S::nat set) = (\k. S \ {..k(})" (is "?lhs = ?rhs") + "finite (S::nat set) = (\k. S \ {.. {..k(}" .. + then obtain k where "S \ {..k. S \ {..k})" (is "?lhs = ?rhs") proof assume ?lhs - then obtain k where "S \ {..k(}" + then obtain k where "S \ {.. {..k}" by auto thus ?rhs .. diff -r f224d27bb1f8 -r d59f7e2e18d3 src/HOL/List.thy --- a/src/HOL/List.thy Thu Jul 15 08:38:37 2004 +0200 +++ b/src/HOL/List.thy Thu Jul 15 13:11:34 2004 +0200 @@ -1526,7 +1526,7 @@ lemma sublist_singleton [simp]: "sublist [x] A = (if 0 : A then [x] else [])" by (simp add: sublist_Cons) -lemma sublist_upt_eq_take [simp]: "sublist l {..n(} = take n l" +lemma sublist_upt_eq_take [simp]: "sublist l {..stable r step ss p then {p} else {})" + "unstables r step ss = (UN p:{..stable r step ss p then {p} else {})" apply (unfold unstables_def) apply (rule equalityI) apply (rule subsetI) diff -r f224d27bb1f8 -r d59f7e2e18d3 src/HOL/SetInterval.thy --- a/src/HOL/SetInterval.thy Thu Jul 15 08:38:37 2004 +0200 +++ b/src/HOL/SetInterval.thy Thu Jul 15 13:11:34 2004 +0200 @@ -12,30 +12,44 @@ theory SetInterval = IntArith: constdefs - lessThan :: "('a::ord) => 'a set" ("(1{.._'(})") - "{..u(} == {x. x 'a set" ("(1{..<_})") + "{.. 'a set" ("(1{.._})") "{..u} == {x. x<=u}" - greaterThan :: "('a::ord) => 'a set" ("(1{')_..})") - "{)l..} == {x. l 'a set" ("(1{_<..})") + "{l<..} == {x. l 'a set" ("(1{_..})") "{l..} == {x. l<=x}" - greaterThanLessThan :: "['a::ord, 'a] => 'a set" ("(1{')_.._'(})") - "{)l..u(} == {)l..} Int {..u(}" + greaterThanLessThan :: "['a::ord, 'a] => 'a set" ("(1{_<..<_})") + "{l<.. 'a set" ("(1{_.._'(})") - "{l..u(} == {l..} Int {..u(}" + atLeastLessThan :: "['a::ord, 'a] => 'a set" ("(1{_..<_})") + "{l.. 'a set" ("(1{')_.._})") - "{)l..u} == {)l..} Int {..u}" + greaterThanAtMost :: "['a::ord, 'a] => 'a set" ("(1{_<.._})") + "{l<..u} == {l<..} Int {..u}" atLeastAtMost :: "['a::ord, 'a] => 'a set" ("(1{_.._})") "{l..u} == {l..} Int {..u}" +(* Old syntax, will disappear! *) +syntax + "_lessThan" :: "('a::ord) => 'a set" ("(1{.._'(})") + "_greaterThan" :: "('a::ord) => 'a set" ("(1{')_..})") + "_greaterThanLessThan" :: "['a::ord, 'a] => 'a set" ("(1{')_.._'(})") + "_atLeastLessThan" :: "['a::ord, 'a] => 'a set" ("(1{_.._'(})") + "_greaterThanAtMost" :: "['a::ord, 'a] => 'a set" ("(1{')_.._})") +translations + "{..m(}" => "{.. "{m<..}" + "{)m..n(}" => "{m<.. "{m.. "{m<..n}" + syntax "@UNION_le" :: "nat => nat => 'b set => 'b set" ("(3UN _<=_./ _)" 10) "@UNION_less" :: "nat => nat => 'b set => 'b set" ("(3UN _<_./ _)" 10) @@ -56,9 +70,9 @@ translations "UN i<=n. A" == "UN i:{..n}. A" - "UN i u ==> - {(0::int)..u(} = int ` {..nat u(}" + {(0::int).. u") apply (subst image_atLeastZeroLessThan_int, assumption) apply (rule finite_imageI) apply auto - apply (subgoal_tac "{0..u(} = {}") + apply (subgoal_tac "{0.. u") apply (subst image_atLeastZeroLessThan_int, assumption) apply (subst card_image) apply (auto simp add: inj_on_def) done -lemma card_atLeastLessThan_int [simp]: "card {l..u(} = nat (u - l)" - apply (subgoal_tac "card {l..u(} = card {0..u-l(}") +lemma card_atLeastLessThan_int [simp]: "card {l.. {l} Un {)l..u(} = {l..u(}" - "(l::'a::linorder) < u ==> {)l..u(} Un {u} = {)l..u}" - "(l::'a::linorder) <= u ==> {l} Un {)l..u} = {l..u}" - "(l::'a::linorder) <= u ==> {l..u(} Un {u} = {l..u}" + "{l::'a::linorder} Un {l<..} = {l..}" + "{.. {l} Un {l<.. {l<.. {l} Un {l<..u} = {l..u}" + "(l::'a::linorder) <= u ==> {l.. {..l} Un {)l..u(} = {..u(}" - "(l::'a::linorder) <= u ==> {..l(} Un {l..u(} = {..u(}" - "(l::'a::linorder) <= u ==> {..l} Un {)l..u} = {..u}" - "(l::'a::linorder) <= u ==> {..l(} Un {l..u} = {..u}" - "(l::'a::linorder) <= u ==> {)l..u} Un {)u..} = {)l..}" - "(l::'a::linorder) < u ==> {)l..u(} Un {u..} = {)l..}" - "(l::'a::linorder) <= u ==> {l..u} Un {)u..} = {l..}" - "(l::'a::linorder) <= u ==> {l..u(} Un {u..} = {l..}" + "(l::'a::linorder) < u ==> {..l} Un {l<.. {.. {..l} Un {l<..u} = {..u}" + "(l::'a::linorder) <= u ==> {.. {l<..u} Un {u<..} = {l<..}" + "(l::'a::linorder) < u ==> {l<.. {l..u} Un {u<..} = {l..}" + "(l::'a::linorder) <= u ==> {l.. {)l..m(} Un {m..u(} = {)l..u(}" - "[| (l::'a::linorder) <= m; m < u |] ==> {)l..m} Un {)m..u(} = {)l..u(}" - "[| (l::'a::linorder) <= m; m <= u |] ==> {l..m(} Un {m..u(} = {l..u(}" - "[| (l::'a::linorder) <= m; m < u |] ==> {l..m} Un {)m..u(} = {l..u(}" - "[| (l::'a::linorder) < m; m <= u |] ==> {)l..m(} Un {m..u} = {)l..u}" - "[| (l::'a::linorder) <= m; m <= u |] ==> {)l..m} Un {)m..u} = {)l..u}" - "[| (l::'a::linorder) <= m; m <= u |] ==> {l..m(} Un {m..u} = {l..u}" - "[| (l::'a::linorder) <= m; m <= u |] ==> {l..m} Un {)m..u} = {l..u}" + "[| (l::'a::linorder) < m; m <= u |] ==> {l<.. {l<..m} Un {m<.. {l.. {l..m} Un {m<.. {l<.. {l<..m} Un {m<..u} = {l<..u}" + "[| (l::'a::linorder) <= m; m <= u |] ==> {l.. {l..m} Un {m<..u} = {l..u}" by auto lemmas ivl_disj_un = ivl_disj_un_singleton ivl_disj_un_one ivl_disj_un_two @@ -444,38 +458,38 @@ text {* Singletons and open intervals *} lemma ivl_disj_int_singleton: - "{l::'a::order} Int {)l..} = {}" - "{..u(} Int {u} = {}" - "{l} Int {)l..u(} = {}" - "{)l..u(} Int {u} = {}" - "{l} Int {)l..u} = {}" - "{l..u(} Int {u} = {}" + "{l::'a::order} Int {l<..} = {}" + "{.. 'a => 'b => 'b" ("\_<_. _" [0, 51, 10] 10) translations - "\i < n. b" == "setsum (\i. b) {..n(}" + "\i < n. b" == "setsum (\i. b) {..i < Suc n. b i) = b n + (\i < n. b i)" by (simp add:lessThan_Suc) diff -r f224d27bb1f8 -r d59f7e2e18d3 src/HOL/UNITY/Comp/AllocBase.thy --- a/src/HOL/UNITY/Comp/AllocBase.thy Thu Jul 15 08:38:37 2004 +0200 +++ b/src/HOL/UNITY/Comp/AllocBase.thy Thu Jul 15 13:11:34 2004 +0200 @@ -87,8 +87,8 @@ lemma bag_of_sublist_Un_Int: "bag_of (sublist l (A Un B)) + bag_of (sublist l (A Int B)) = bag_of (sublist l A) + bag_of (sublist l B)" -apply (subgoal_tac "A Int B Int {..length l (} = - (A Int {..length l (}) Int (B Int {..length l (}) ") +apply (subgoal_tac "A Int B Int {.. (A \ f-`(lessThan m)) leadsTo B*) lemma lessThan_induct: - "[| !!m::nat. F \ (A \ f-`{m}) leadsTo ((A \ f-`{..m(}) \ B) |] + "[| !!m::nat. F \ (A \ f-`{m}) leadsTo ((A \ f-`{.. B) |] ==> F \ A leadsTo B" apply (rule wf_less_than [THEN leadsTo_wf_induct]) apply (simp (no_asm_simp)) diff -r f224d27bb1f8 -r d59f7e2e18d3 src/HOL/ex/NatSum.thy --- a/src/HOL/ex/NatSum.thy Thu Jul 15 08:38:37 2004 +0200 +++ b/src/HOL/ex/NatSum.thy Thu Jul 15 13:11:34 2004 +0200 @@ -1,4 +1,4 @@ -(* Title: HOL/ex/NatSum.ML +(* Title: HOL/ex/NatSum.ML ID: $Id$ Author: Tobias Nipkow *) @@ -26,7 +26,7 @@ squared. *} -lemma sum_of_odds: "(\i \ {..n(}. Suc (i + i)) = n * n" +lemma sum_of_odds: "(\i \ {..i \ {..n(}. Suc (2*i) * Suc (2*i)) = + "3 * (\i \ {..i \ {..n(}. Suc (2*i) * Suc (2*i) * Suc (2*i)) = + "(\i \ {..i \ {..m(}. i * i * i * i) = + "30 * int (\i \ {..i \ {..n(}. 2^i) = 2^n - (1::nat)" +lemma sum_of_2_powers: "(\i \ {..i \ {..n(}. 3^i) = 3^n - (1::nat)" +lemma sum_of_3_powers: "2 * (\i \ {.. (k - 1) * (\i \ {..n(}. k^i) = k^n - (1::nat)" +lemma sum_of_powers: "0 < k ==> (k - 1) * (\i \ {..