340 by (simp add: floor_less_iff) |
340 by (simp add: floor_less_iff) |
341 |
341 |
342 |
342 |
343 text \<open>Addition and subtraction of integers.\<close> |
343 text \<open>Addition and subtraction of integers.\<close> |
344 |
344 |
345 lemma floor_add_of_int [simp]: "\<lfloor>x + of_int z\<rfloor> = \<lfloor>x\<rfloor> + z" |
345 lemma floor_add_int: "\<lfloor>x\<rfloor> + z = \<lfloor>x + of_int z\<rfloor>" |
346 using floor_correct [of x] by (simp add: floor_unique) |
346 using floor_correct [of x] by (simp add: floor_unique[symmetric]) |
347 |
347 |
348 lemma floor_add_numeral [simp]: "\<lfloor>x + numeral v\<rfloor> = \<lfloor>x\<rfloor> + numeral v" |
348 lemma int_add_floor: "z + \<lfloor>x\<rfloor> = \<lfloor>of_int z + x\<rfloor>" |
349 using floor_add_of_int [of x "numeral v"] by simp |
349 using floor_correct [of x] by (simp add: floor_unique[symmetric]) |
350 |
350 |
351 lemma floor_add_one [simp]: "\<lfloor>x + 1\<rfloor> = \<lfloor>x\<rfloor> + 1" |
351 lemma one_add_floor: "\<lfloor>x\<rfloor> + 1 = \<lfloor>x + 1\<rfloor>" |
352 using floor_add_of_int [of x 1] by simp |
352 using floor_add_int [of x 1] by simp |
353 |
353 |
354 lemma floor_diff_of_int [simp]: "\<lfloor>x - of_int z\<rfloor> = \<lfloor>x\<rfloor> - z" |
354 lemma floor_diff_of_int [simp]: "\<lfloor>x - of_int z\<rfloor> = \<lfloor>x\<rfloor> - z" |
355 using floor_add_of_int [of x "- z"] by (simp add: algebra_simps) |
355 using floor_add_int [of x "- z"] by (simp add: algebra_simps) |
356 |
356 |
357 lemma floor_uminus_of_int [simp]: "\<lfloor>- (of_int z)\<rfloor> = - z" |
357 lemma floor_uminus_of_int [simp]: "\<lfloor>- (of_int z)\<rfloor> = - z" |
358 by (metis floor_diff_of_int [of 0] diff_0 floor_zero) |
358 by (metis floor_diff_of_int [of 0] diff_0 floor_zero) |
359 |
359 |
360 lemma floor_diff_numeral [simp]: "\<lfloor>x - numeral v\<rfloor> = \<lfloor>x\<rfloor> - numeral v" |
360 lemma floor_diff_numeral [simp]: "\<lfloor>x - numeral v\<rfloor> = \<lfloor>x\<rfloor> - numeral v" |
412 then have "\<lfloor>of_int k / of_int l :: 'a\<rfloor> = \<lfloor>of_int (k div l) + of_int (k mod l) / of_int l :: 'a\<rfloor>" |
412 then have "\<lfloor>of_int k / of_int l :: 'a\<rfloor> = \<lfloor>of_int (k div l) + of_int (k mod l) / of_int l :: 'a\<rfloor>" |
413 by simp |
413 by simp |
414 then have "\<lfloor>of_int k / of_int l :: 'a\<rfloor> = \<lfloor>of_int (k mod l) / of_int l + of_int (k div l) :: 'a\<rfloor>" |
414 then have "\<lfloor>of_int k / of_int l :: 'a\<rfloor> = \<lfloor>of_int (k mod l) / of_int l + of_int (k div l) :: 'a\<rfloor>" |
415 by (simp add: ac_simps) |
415 by (simp add: ac_simps) |
416 then have "\<lfloor>of_int k / of_int l :: 'a\<rfloor> = \<lfloor>of_int (k mod l) / of_int l :: 'a\<rfloor> + k div l" |
416 then have "\<lfloor>of_int k / of_int l :: 'a\<rfloor> = \<lfloor>of_int (k mod l) / of_int l :: 'a\<rfloor> + k div l" |
417 by simp |
417 by (simp add: floor_add_int) |
418 with * show ?thesis |
418 with * show ?thesis |
419 by simp |
419 by simp |
420 qed |
420 qed |
421 |
421 |
422 lemma floor_divide_of_nat_eq: "\<lfloor>of_nat m / of_nat n\<rfloor> = of_nat (m div n)" |
422 lemma floor_divide_of_nat_eq: "\<lfloor>of_nat m / of_nat n\<rfloor> = of_nat (m div n)" |
442 by (simp add: ac_simps) |
442 by (simp add: ac_simps) |
443 moreover have "(of_nat (m div n) :: 'a) = of_int (of_nat (m div n))" |
443 moreover have "(of_nat (m div n) :: 'a) = of_int (of_nat (m div n))" |
444 by simp |
444 by simp |
445 ultimately have "\<lfloor>of_nat m / of_nat n :: 'a\<rfloor> = |
445 ultimately have "\<lfloor>of_nat m / of_nat n :: 'a\<rfloor> = |
446 \<lfloor>of_nat (m mod n) / of_nat n :: 'a\<rfloor> + of_nat (m div n)" |
446 \<lfloor>of_nat (m mod n) / of_nat n :: 'a\<rfloor> + of_nat (m div n)" |
447 by (simp only: floor_add_of_int) |
447 by (simp only: floor_add_int) |
448 with * show ?thesis |
448 with * show ?thesis |
449 by simp |
449 by simp |
450 qed |
450 qed |
451 |
451 |
452 |
452 |
627 lemma frac_of_int [simp]: "frac (of_int z) = 0" |
627 lemma frac_of_int [simp]: "frac (of_int z) = 0" |
628 by (simp add: frac_def) |
628 by (simp add: frac_def) |
629 |
629 |
630 lemma floor_add: "\<lfloor>x + y\<rfloor> = (if frac x + frac y < 1 then \<lfloor>x\<rfloor> + \<lfloor>y\<rfloor> else (\<lfloor>x\<rfloor> + \<lfloor>y\<rfloor>) + 1)" |
630 lemma floor_add: "\<lfloor>x + y\<rfloor> = (if frac x + frac y < 1 then \<lfloor>x\<rfloor> + \<lfloor>y\<rfloor> else (\<lfloor>x\<rfloor> + \<lfloor>y\<rfloor>) + 1)" |
631 proof - |
631 proof - |
632 have "\<lfloor>x + y\<rfloor> = \<lfloor>x\<rfloor> + \<lfloor>y\<rfloor>" if "x + y < 1 + (of_int \<lfloor>x\<rfloor> + of_int \<lfloor>y\<rfloor>)" |
632 have "x + y < 1 + (of_int \<lfloor>x\<rfloor> + of_int \<lfloor>y\<rfloor>) \<Longrightarrow> \<lfloor>x + y\<rfloor> = \<lfloor>x\<rfloor> + \<lfloor>y\<rfloor>" |
633 using that by (metis add.commute floor_unique le_floor_add le_floor_iff of_int_add) |
633 by (metis add.commute floor_unique le_floor_add le_floor_iff of_int_add) |
634 moreover |
634 moreover |
635 have "\<lfloor>x + y\<rfloor> = 1 + (\<lfloor>x\<rfloor> + \<lfloor>y\<rfloor>)" if "\<not> x + y < 1 + (of_int \<lfloor>x\<rfloor> + of_int \<lfloor>y\<rfloor>)" |
635 have "\<not> x + y < 1 + (of_int \<lfloor>x\<rfloor> + of_int \<lfloor>y\<rfloor>) \<Longrightarrow> \<lfloor>x + y\<rfloor> = 1 + (\<lfloor>x\<rfloor> + \<lfloor>y\<rfloor>)" |
636 using that |
|
637 apply (simp add: floor_unique_iff) |
636 apply (simp add: floor_unique_iff) |
638 apply (auto simp add: algebra_simps) |
637 apply (auto simp add: algebra_simps) |
639 apply linarith |
638 apply linarith |
640 done |
639 done |
641 ultimately show ?thesis |
640 ultimately show ?thesis by (auto simp add: frac_def algebra_simps) |
642 by (auto simp add: frac_def algebra_simps) |
|
643 qed |
641 qed |
644 |
642 |
645 lemma floor_add2[simp]: "frac x = 0 \<or> frac y = 0 \<Longrightarrow> \<lfloor>x + y\<rfloor> = \<lfloor>x\<rfloor> + \<lfloor>y\<rfloor>" |
643 lemma floor_add2[simp]: "frac x = 0 \<or> frac y = 0 \<Longrightarrow> \<lfloor>x + y\<rfloor> = \<lfloor>x\<rfloor> + \<lfloor>y\<rfloor>" |
646 by (metis add.commute add.left_neutral frac_lt_1 floor_add) |
644 by (metis add.commute add.left_neutral frac_lt_1 floor_add) |
647 |
645 |