如何在 Coq 中证明整数除法不等式
How to prove integer division inequality in Coq
我需要证明：256 * (x / 256) <= 256 * x / 256，或者更笼统地说 forall a b c : N, c > 0 -> a * (b / c) <= a * b / c。这是真的，因为要么 b 可以被 c 整除，要么它们相等，要么不相等，首先乘法会使数字膨胀并导致更高的精度。然而，我无法在标准库中找到任何定理来证明这一点，而且我所知道的自动策略（auto、intuition、easy、zify 和 omega）都没有起作用。如果有帮助，我也知道x < 256 * 256，但是检查所有65536个案例并不是一个很好的证明...
在我的具体情况下，我可以这样解决：
rewrite (N.mul_comm 256 x).
这会在右侧切换到 256 * (x / 256) <= x * 256 / 256。
rewrite (N.div_mul x 256).
这将右侧缩小为 256 * (x / 256) <= x。
rewrite (N.mul_div_le x 256).
以后这个自动化战术就够了
我需要证明：256 * (x / 256) <= 256 * x / 256，或者更笼统地说 forall a b c : N, c > 0 -> a * (b / c) <= a * b / c。这是真的，因为要么 b 可以被 c 整除，要么它们相等，要么不相等，首先乘法会使数字膨胀并导致更高的精度。然而，我无法在标准库中找到任何定理来证明这一点，而且我所知道的自动策略（auto、intuition、easy、zify 和 omega）都没有起作用。如果有帮助，我也知道x < 256 * 256，但是检查所有65536个案例并不是一个很好的证明...
在我的具体情况下，我可以这样解决：
rewrite (N.mul_comm 256 x).
这会在右侧切换到 256 * (x / 256) <= x * 256 / 256。
rewrite (N.div_mul x 256).
这将右侧缩小为 256 * (x / 256) <= x。
rewrite (N.mul_div_le x 256).
以后这个自动化战术就够了