Как доказать неравенство целочисленного деления в Coq - PullRequest
4 голосов
/ 19 июня 2019

Мне нужно доказать: 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 случаев не является хорошим доказательством ...

1 Ответ

4 голосов
/ 20 июня 2019

В моем конкретном случае я смог решить это так:

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).

После этого достаточно автоматизированной тактики.

...