diff options
Diffstat (limited to 'theories/ZArith/BinInt.v')
| -rw-r--r-- | theories/ZArith/BinInt.v | 231 |
1 files changed, 138 insertions, 93 deletions
diff --git a/theories/ZArith/BinInt.v b/theories/ZArith/BinInt.v index 5aa397f8..cf7397b5 100644 --- a/theories/ZArith/BinInt.v +++ b/theories/ZArith/BinInt.v @@ -1,10 +1,12 @@ (* -*- coding: utf-8 -*- *) (************************************************************************) -(* v * The Coq Proof Assistant / The Coq Development Team *) -(* <O___,, * INRIA - CNRS - LIX - LRI - PPS - Copyright 1999-2016 *) +(* * The Coq Proof Assistant / The Coq Development Team *) +(* v * INRIA, CNRS and contributors - Copyright 1999-2018 *) +(* <O___,, * (see CREDITS file for the list of authors) *) (* \VV/ **************************************************************) -(* // * This file is distributed under the terms of the *) -(* * GNU Lesser General Public License Version 2.1 *) +(* // * This file is distributed under the terms of the *) +(* * GNU Lesser General Public License Version 2.1 *) +(* * (see LICENSE file for the text of the license) *) (************************************************************************) Require Export BinNums BinPos Pnat. @@ -1367,7 +1369,7 @@ Lemma inj_testbit a n : 0<=n -> Z.testbit (Z.pos a) n = N.testbit (N.pos a) (Z.to_N n). Proof. apply Z.testbit_Zpos. Qed. -(** Some results concerning Z.neg *) +(** Some results concerning Z.neg and Z.pos *) Lemma inj_neg p q : Z.neg p = Z.neg q -> p = q. Proof. now injection 1. Qed. @@ -1375,18 +1377,54 @@ Proof. now injection 1. Qed. Lemma inj_neg_iff p q : Z.neg p = Z.neg q <-> p = q. Proof. split. apply inj_neg. intros; now f_equal. Qed. +Lemma inj_pos p q : Z.pos p = Z.pos q -> p = q. +Proof. now injection 1. Qed. + +Lemma inj_pos_iff p q : Z.pos p = Z.pos q <-> p = q. +Proof. split. apply inj_pos. intros; now f_equal. Qed. + Lemma neg_is_neg p : Z.neg p < 0. Proof. reflexivity. Qed. Lemma neg_is_nonpos p : Z.neg p <= 0. Proof. easy. Qed. +Lemma pos_is_pos p : 0 < Z.pos p. +Proof. reflexivity. Qed. + +Lemma pos_is_nonneg p : 0 <= Z.pos p. +Proof. easy. Qed. + +Lemma neg_le_pos p q : Zneg p <= Zpos q. +Proof. easy. Qed. + +Lemma neg_lt_pos p q : Zneg p < Zpos q. +Proof. easy. Qed. + +Lemma neg_le_neg p q : (q <= p)%positive -> Zneg p <= Zneg q. +Proof. intros; unfold Z.le; simpl. now rewrite <- Pos.compare_antisym. Qed. + +Lemma neg_lt_neg p q : (q < p)%positive -> Zneg p < Zneg q. +Proof. intros; unfold Z.lt; simpl. now rewrite <- Pos.compare_antisym. Qed. + +Lemma pos_le_pos p q : (p <= q)%positive -> Zpos p <= Zpos q. +Proof. easy. Qed. + +Lemma pos_lt_pos p q : (p < q)%positive -> Zpos p < Zpos q. +Proof. easy. Qed. + Lemma neg_xO p : Z.neg p~0 = 2 * Z.neg p. Proof. reflexivity. Qed. Lemma neg_xI p : Z.neg p~1 = 2 * Z.neg p - 1. Proof. reflexivity. Qed. +Lemma pos_xO p : Z.pos p~0 = 2 * Z.pos p. +Proof. reflexivity. Qed. + +Lemma pos_xI p : Z.pos p~1 = 2 * Z.pos p + 1. +Proof. reflexivity. Qed. + Lemma opp_neg p : - Z.neg p = Z.pos p. Proof. reflexivity. Qed. @@ -1402,6 +1440,9 @@ Proof. reflexivity. Qed. Lemma add_neg_pos p q : Z.neg p + Z.pos q = Z.pos_sub q p. Proof. reflexivity. Qed. +Lemma add_pos_pos p q : Z.pos p + Z.pos q = Z.pos (p+q). +Proof. reflexivity. Qed. + Lemma divide_pos_neg_r n p : (n|Z.pos p) <-> (n|Z.neg p). Proof. apply Z.divide_Zpos_Zneg_r. Qed. @@ -1412,6 +1453,10 @@ Lemma testbit_neg a n : 0<=n -> Z.testbit (Z.neg a) n = negb (N.testbit (Pos.pred_N a) (Z.to_N n)). Proof. apply Z.testbit_Zneg. Qed. +Lemma testbit_pos a n : 0<=n -> + Z.testbit (Z.pos a) n = N.testbit (N.pos a) (Z.to_N n). +Proof. apply Z.testbit_Zpos. Qed. + End Pos2Z. Module Z2Pos. @@ -1522,94 +1567,94 @@ End Z2Pos. (** Compatibility Notations *) -Notation Zdouble_plus_one := Z.succ_double (compat "8.3"). -Notation Zdouble_minus_one := Z.pred_double (compat "8.3"). -Notation Zdouble := Z.double (compat "8.3"). -Notation ZPminus := Z.pos_sub (compat "8.3"). -Notation Zsucc' := Z.succ (compat "8.3"). -Notation Zpred' := Z.pred (compat "8.3"). -Notation Zplus' := Z.add (compat "8.3"). -Notation Zplus := Z.add (compat "8.3"). (* Slightly incompatible *) -Notation Zopp := Z.opp (compat "8.3"). -Notation Zsucc := Z.succ (compat "8.3"). -Notation Zpred := Z.pred (compat "8.3"). -Notation Zminus := Z.sub (compat "8.3"). -Notation Zmult := Z.mul (compat "8.3"). -Notation Zcompare := Z.compare (compat "8.3"). -Notation Zsgn := Z.sgn (compat "8.3"). -Notation Zle := Z.le (compat "8.3"). -Notation Zge := Z.ge (compat "8.3"). -Notation Zlt := Z.lt (compat "8.3"). -Notation Zgt := Z.gt (compat "8.3"). -Notation Zmax := Z.max (compat "8.3"). -Notation Zmin := Z.min (compat "8.3"). -Notation Zabs := Z.abs (compat "8.3"). -Notation Zabs_nat := Z.abs_nat (compat "8.3"). -Notation Zabs_N := Z.abs_N (compat "8.3"). -Notation Z_of_nat := Z.of_nat (compat "8.3"). -Notation Z_of_N := Z.of_N (compat "8.3"). - -Notation Zind := Z.peano_ind (compat "8.3"). -Notation Zopp_0 := Z.opp_0 (compat "8.3"). -Notation Zopp_involutive := Z.opp_involutive (compat "8.3"). -Notation Zopp_inj := Z.opp_inj (compat "8.3"). -Notation Zplus_0_l := Z.add_0_l (compat "8.3"). -Notation Zplus_0_r := Z.add_0_r (compat "8.3"). -Notation Zplus_comm := Z.add_comm (compat "8.3"). -Notation Zopp_plus_distr := Z.opp_add_distr (compat "8.3"). -Notation Zopp_succ := Z.opp_succ (compat "8.3"). -Notation Zplus_opp_r := Z.add_opp_diag_r (compat "8.3"). -Notation Zplus_opp_l := Z.add_opp_diag_l (compat "8.3"). -Notation Zplus_assoc := Z.add_assoc (compat "8.3"). -Notation Zplus_permute := Z.add_shuffle3 (compat "8.3"). -Notation Zplus_reg_l := Z.add_reg_l (compat "8.3"). -Notation Zplus_succ_l := Z.add_succ_l (compat "8.3"). -Notation Zplus_succ_comm := Z.add_succ_comm (compat "8.3"). -Notation Zsucc_discr := Z.neq_succ_diag_r (compat "8.3"). -Notation Zsucc_inj := Z.succ_inj (compat "8.3"). -Notation Zsucc'_inj := Z.succ_inj (compat "8.3"). -Notation Zsucc'_pred' := Z.succ_pred (compat "8.3"). -Notation Zpred'_succ' := Z.pred_succ (compat "8.3"). -Notation Zpred'_inj := Z.pred_inj (compat "8.3"). -Notation Zsucc'_discr := Z.neq_succ_diag_r (compat "8.3"). -Notation Zminus_0_r := Z.sub_0_r (compat "8.3"). -Notation Zminus_diag := Z.sub_diag (compat "8.3"). -Notation Zminus_plus_distr := Z.sub_add_distr (compat "8.3"). -Notation Zminus_succ_r := Z.sub_succ_r (compat "8.3"). -Notation Zminus_plus := Z.add_simpl_l (compat "8.3"). -Notation Zmult_0_l := Z.mul_0_l (compat "8.3"). -Notation Zmult_0_r := Z.mul_0_r (compat "8.3"). -Notation Zmult_1_l := Z.mul_1_l (compat "8.3"). -Notation Zmult_1_r := Z.mul_1_r (compat "8.3"). -Notation Zmult_comm := Z.mul_comm (compat "8.3"). -Notation Zmult_assoc := Z.mul_assoc (compat "8.3"). -Notation Zmult_permute := Z.mul_shuffle3 (compat "8.3"). -Notation Zmult_1_inversion_l := Z.mul_eq_1 (compat "8.3"). -Notation Zdouble_mult := Z.double_spec (compat "8.3"). -Notation Zdouble_plus_one_mult := Z.succ_double_spec (compat "8.3"). -Notation Zopp_mult_distr_l_reverse := Z.mul_opp_l (compat "8.3"). -Notation Zmult_opp_opp := Z.mul_opp_opp (compat "8.3"). -Notation Zmult_opp_comm := Z.mul_opp_comm (compat "8.3"). -Notation Zopp_eq_mult_neg_1 := Z.opp_eq_mul_m1 (compat "8.3"). -Notation Zmult_plus_distr_r := Z.mul_add_distr_l (compat "8.3"). -Notation Zmult_plus_distr_l := Z.mul_add_distr_r (compat "8.3"). -Notation Zmult_minus_distr_r := Z.mul_sub_distr_r (compat "8.3"). -Notation Zmult_reg_l := Z.mul_reg_l (compat "8.3"). -Notation Zmult_reg_r := Z.mul_reg_r (compat "8.3"). -Notation Zmult_succ_l := Z.mul_succ_l (compat "8.3"). -Notation Zmult_succ_r := Z.mul_succ_r (compat "8.3"). - -Notation Zpos_xI := Pos2Z.inj_xI (compat "8.3"). -Notation Zpos_xO := Pos2Z.inj_xO (compat "8.3"). -Notation Zneg_xI := Pos2Z.neg_xI (compat "8.3"). -Notation Zneg_xO := Pos2Z.neg_xO (compat "8.3"). -Notation Zopp_neg := Pos2Z.opp_neg (compat "8.3"). -Notation Zpos_succ_morphism := Pos2Z.inj_succ (compat "8.3"). -Notation Zpos_mult_morphism := Pos2Z.inj_mul (compat "8.3"). -Notation Zpos_minus_morphism := Pos2Z.inj_sub (compat "8.3"). -Notation Zpos_eq_rev := Pos2Z.inj (compat "8.3"). -Notation Zpos_plus_distr := Pos2Z.inj_add (compat "8.3"). -Notation Zneg_plus_distr := Pos2Z.add_neg_neg (compat "8.3"). +Notation Zdouble_plus_one := Z.succ_double (only parsing). +Notation Zdouble_minus_one := Z.pred_double (only parsing). +Notation Zdouble := Z.double (compat "8.6"). +Notation ZPminus := Z.pos_sub (only parsing). +Notation Zsucc' := Z.succ (compat "8.6"). +Notation Zpred' := Z.pred (compat "8.6"). +Notation Zplus' := Z.add (compat "8.6"). +Notation Zplus := Z.add (only parsing). (* Slightly incompatible *) +Notation Zopp := Z.opp (compat "8.6"). +Notation Zsucc := Z.succ (compat "8.6"). +Notation Zpred := Z.pred (compat "8.6"). +Notation Zminus := Z.sub (only parsing). +Notation Zmult := Z.mul (only parsing). +Notation Zcompare := Z.compare (compat "8.6"). +Notation Zsgn := Z.sgn (compat "8.6"). +Notation Zle := Z.le (compat "8.6"). +Notation Zge := Z.ge (compat "8.6"). +Notation Zlt := Z.lt (compat "8.6"). +Notation Zgt := Z.gt (compat "8.6"). +Notation Zmax := Z.max (compat "8.6"). +Notation Zmin := Z.min (compat "8.6"). +Notation Zabs := Z.abs (compat "8.6"). +Notation Zabs_nat := Z.abs_nat (compat "8.6"). +Notation Zabs_N := Z.abs_N (compat "8.6"). +Notation Z_of_nat := Z.of_nat (only parsing). +Notation Z_of_N := Z.of_N (only parsing). + +Notation Zind := Z.peano_ind (only parsing). +Notation Zopp_0 := Z.opp_0 (compat "8.6"). +Notation Zopp_involutive := Z.opp_involutive (compat "8.6"). +Notation Zopp_inj := Z.opp_inj (compat "8.6"). +Notation Zplus_0_l := Z.add_0_l (only parsing). +Notation Zplus_0_r := Z.add_0_r (only parsing). +Notation Zplus_comm := Z.add_comm (only parsing). +Notation Zopp_plus_distr := Z.opp_add_distr (only parsing). +Notation Zopp_succ := Z.opp_succ (compat "8.6"). +Notation Zplus_opp_r := Z.add_opp_diag_r (only parsing). +Notation Zplus_opp_l := Z.add_opp_diag_l (only parsing). +Notation Zplus_assoc := Z.add_assoc (only parsing). +Notation Zplus_permute := Z.add_shuffle3 (only parsing). +Notation Zplus_reg_l := Z.add_reg_l (only parsing). +Notation Zplus_succ_l := Z.add_succ_l (only parsing). +Notation Zplus_succ_comm := Z.add_succ_comm (only parsing). +Notation Zsucc_discr := Z.neq_succ_diag_r (only parsing). +Notation Zsucc_inj := Z.succ_inj (compat "8.6"). +Notation Zsucc'_inj := Z.succ_inj (compat "8.6"). +Notation Zsucc'_pred' := Z.succ_pred (compat "8.6"). +Notation Zpred'_succ' := Z.pred_succ (compat "8.6"). +Notation Zpred'_inj := Z.pred_inj (compat "8.6"). +Notation Zsucc'_discr := Z.neq_succ_diag_r (only parsing). +Notation Zminus_0_r := Z.sub_0_r (only parsing). +Notation Zminus_diag := Z.sub_diag (only parsing). +Notation Zminus_plus_distr := Z.sub_add_distr (only parsing). +Notation Zminus_succ_r := Z.sub_succ_r (only parsing). +Notation Zminus_plus := Z.add_simpl_l (only parsing). +Notation Zmult_0_l := Z.mul_0_l (only parsing). +Notation Zmult_0_r := Z.mul_0_r (only parsing). +Notation Zmult_1_l := Z.mul_1_l (only parsing). +Notation Zmult_1_r := Z.mul_1_r (only parsing). +Notation Zmult_comm := Z.mul_comm (only parsing). +Notation Zmult_assoc := Z.mul_assoc (only parsing). +Notation Zmult_permute := Z.mul_shuffle3 (only parsing). +Notation Zmult_1_inversion_l := Z.mul_eq_1 (only parsing). +Notation Zdouble_mult := Z.double_spec (only parsing). +Notation Zdouble_plus_one_mult := Z.succ_double_spec (only parsing). +Notation Zopp_mult_distr_l_reverse := Z.mul_opp_l (only parsing). +Notation Zmult_opp_opp := Z.mul_opp_opp (only parsing). +Notation Zmult_opp_comm := Z.mul_opp_comm (only parsing). +Notation Zopp_eq_mult_neg_1 := Z.opp_eq_mul_m1 (only parsing). +Notation Zmult_plus_distr_r := Z.mul_add_distr_l (only parsing). +Notation Zmult_plus_distr_l := Z.mul_add_distr_r (only parsing). +Notation Zmult_minus_distr_r := Z.mul_sub_distr_r (only parsing). +Notation Zmult_reg_l := Z.mul_reg_l (only parsing). +Notation Zmult_reg_r := Z.mul_reg_r (only parsing). +Notation Zmult_succ_l := Z.mul_succ_l (only parsing). +Notation Zmult_succ_r := Z.mul_succ_r (only parsing). + +Notation Zpos_xI := Pos2Z.inj_xI (only parsing). +Notation Zpos_xO := Pos2Z.inj_xO (only parsing). +Notation Zneg_xI := Pos2Z.neg_xI (only parsing). +Notation Zneg_xO := Pos2Z.neg_xO (only parsing). +Notation Zopp_neg := Pos2Z.opp_neg (only parsing). +Notation Zpos_succ_morphism := Pos2Z.inj_succ (only parsing). +Notation Zpos_mult_morphism := Pos2Z.inj_mul (only parsing). +Notation Zpos_minus_morphism := Pos2Z.inj_sub (only parsing). +Notation Zpos_eq_rev := Pos2Z.inj (only parsing). +Notation Zpos_plus_distr := Pos2Z.inj_add (only parsing). +Notation Zneg_plus_distr := Pos2Z.add_neg_neg (only parsing). Notation Z := Z (only parsing). Notation Z_rect := Z_rect (only parsing). |