diff options
author | Stephane Glondu <steph@glondu.net> | 2012-01-12 16:08:29 +0100 |
---|---|---|
committer | Stephane Glondu <steph@glondu.net> | 2012-01-12 16:08:29 +0100 |
commit | 23a6061a81ffa0c214d521287b6af0a31bfa22f0 (patch) | |
tree | f1ca9ba9240b98b8695a9f1870e56602734cf97c /theories/ZArith/auxiliary.v | |
parent | de109d8c0c68f569b907e6e24271f259ba28888e (diff) | |
parent | 39efc41237ec906226a3a53d7396d51173495204 (diff) |
Merge commit 'upstream/8.4_beta+dfsg' into experimental/master
Diffstat (limited to 'theories/ZArith/auxiliary.v')
-rw-r--r-- | theories/ZArith/auxiliary.v | 87 |
1 files changed, 34 insertions, 53 deletions
diff --git a/theories/ZArith/auxiliary.v b/theories/ZArith/auxiliary.v index ade35bef..742f4bde 100644 --- a/theories/ZArith/auxiliary.v +++ b/theories/ZArith/auxiliary.v @@ -1,14 +1,12 @@ (* -*- coding: utf-8 -*- *) (************************************************************************) (* v * The Coq Proof Assistant / The Coq Development Team *) -(* <O___,, * INRIA - CNRS - LIX - LRI - PPS - Copyright 1999-2011 *) +(* <O___,, * INRIA - CNRS - LIX - LRI - PPS - Copyright 1999-2010 *) (* \VV/ **************************************************************) (* // * This file is distributed under the terms of the *) (* * GNU Lesser General Public License Version 2.1 *) (************************************************************************) -(*i $Id: auxiliary.v 14641 2011-11-06 11:59:10Z herbelin $ i*) - (** Binary Integers (Pierre Crégut, CNET, Lannion, France) *) Require Export Arith_base. @@ -18,96 +16,79 @@ Require Import Decidable. Require Import Peano_dec. Require Export Compare_dec. -Open Local Scope Z_scope. +Local Open Scope Z_scope. (***************************************************************) (** * Moving terms from one side to the other of an inequality *) -Theorem Zne_left : forall n m:Z, Zne n m -> Zne (n + - m) 0. +Theorem Zne_left n m : Zne n m -> Zne (n + - m) 0. Proof. - intros x y; unfold Zne in |- *; unfold not in |- *; intros H1 H2; apply H1; - apply Zplus_reg_l with (- y); rewrite Zplus_opp_l; - rewrite Zplus_comm; trivial with arith. + unfold Zne. now rewrite <- Z.sub_move_0_r. Qed. -Theorem Zegal_left : forall n m:Z, n = m -> n + - m = 0. +Theorem Zegal_left n m : n = m -> n + - m = 0. Proof. - intros x y H; apply (Zplus_reg_l y); rewrite Zplus_permute; - rewrite Zplus_opp_r; do 2 rewrite Zplus_0_r; assumption. + apply Z.sub_move_0_r. Qed. -Theorem Zle_left : forall n m:Z, n <= m -> 0 <= m + - n. +Theorem Zle_left n m : n <= m -> 0 <= m + - n. Proof. - intros x y H; replace 0 with (x + - x). - apply Zplus_le_compat_r; trivial. - apply Zplus_opp_r. + apply Z.le_0_sub. Qed. -Theorem Zle_left_rev : forall n m:Z, 0 <= m + - n -> n <= m. +Theorem Zle_left_rev n m : 0 <= m + - n -> n <= m. Proof. - intros x y H; apply Zplus_le_reg_r with (- x). - rewrite Zplus_opp_r; trivial. + apply Z.le_0_sub. Qed. -Theorem Zlt_left_rev : forall n m:Z, 0 < m + - n -> n < m. +Theorem Zlt_left_rev n m : 0 < m + - n -> n < m. Proof. - intros x y H; apply Zplus_lt_reg_r with (- x). - rewrite Zplus_opp_r; trivial. + apply Z.lt_0_sub. Qed. -Theorem Zlt_left : forall n m:Z, n < m -> 0 <= m + -1 + - n. +Theorem Zlt_left_lt n m : n < m -> 0 < m + - n. Proof. - intros x y H; apply Zle_left; apply Zsucc_le_reg; - change (Zsucc x <= Zsucc (Zpred y)) in |- *; rewrite <- Zsucc_pred; - apply Zlt_le_succ; assumption. + apply Z.lt_0_sub. Qed. -Theorem Zlt_left_lt : forall n m:Z, n < m -> 0 < m + - n. +Theorem Zlt_left n m : n < m -> 0 <= m + -1 + - n. Proof. - intros x y H; replace 0 with (x + - x). - apply Zplus_lt_compat_r; trivial. - apply Zplus_opp_r. + intros. rewrite Z.add_shuffle0. change (-1) with (- Z.succ 0). + now apply Z.le_0_sub, Z.le_succ_l, Z.lt_0_sub. Qed. -Theorem Zge_left : forall n m:Z, n >= m -> 0 <= n + - m. +Theorem Zge_left n m : n >= m -> 0 <= n + - m. Proof. - intros x y H; apply Zle_left; apply Zge_le; assumption. + Z.swap_greater. apply Z.le_0_sub. Qed. -Theorem Zgt_left : forall n m:Z, n > m -> 0 <= n + -1 + - m. +Theorem Zgt_left n m : n > m -> 0 <= n + -1 + - m. Proof. - intros x y H; apply Zlt_left; apply Zgt_lt; assumption. + Z.swap_greater. apply Zlt_left. Qed. -Theorem Zgt_left_gt : forall n m:Z, n > m -> n + - m > 0. +Theorem Zgt_left_gt n m : n > m -> n + - m > 0. Proof. - intros x y H; replace 0 with (y + - y). - apply Zplus_gt_compat_r; trivial. - apply Zplus_opp_r. + Z.swap_greater. apply Z.lt_0_sub. Qed. -Theorem Zgt_left_rev : forall n m:Z, n + - m > 0 -> n > m. +Theorem Zgt_left_rev n m : n + - m > 0 -> n > m. Proof. - intros x y H; apply Zplus_gt_reg_r with (- y). - rewrite Zplus_opp_r; trivial. + Z.swap_greater. apply Z.lt_0_sub. Qed. -Theorem Zle_mult_approx : - forall n m p:Z, n > 0 -> p > 0 -> 0 <= m -> 0 <= m * n + p. +Theorem Zle_mult_approx n m p : + n > 0 -> p > 0 -> 0 <= m -> 0 <= m * n + p. Proof. - intros x y z H1 H2 H3; apply Zle_trans with (m := y * x); - [ apply Zmult_gt_0_le_0_compat; assumption - | pattern (y * x) at 1 in |- *; rewrite <- Zplus_0_r; - apply Zplus_le_compat_l; apply Zlt_le_weak; apply Zgt_lt; - assumption ]. + Z.swap_greater. intros. Z.order_pos. Qed. -Theorem Zmult_le_approx : - forall n m p:Z, n > 0 -> n > p -> 0 <= m * n + p -> 0 <= m. +Theorem Zmult_le_approx n m p : + n > 0 -> n > p -> 0 <= m * n + p -> 0 <= m. Proof. - intros x y z H1 H2 H3; apply Zlt_succ_le; apply Zmult_gt_0_lt_0_reg_r with x; - [ assumption - | apply Zle_lt_trans with (1 := H3); rewrite <- Zmult_succ_l_reverse; - apply Zplus_lt_compat_l; apply Zgt_lt; assumption ]. + Z.swap_greater. intros. apply Z.lt_succ_r. + apply Z.mul_pos_cancel_r with n; trivial. Z.nzsimpl. + apply Z.le_lt_trans with (m*n+p); trivial. + now apply Z.add_lt_mono_l. Qed. |