Доказательство с функциями пола и потолка формально для компьютерных ученых

Question

Это действительно своего рода упражнение, которое я должен выполнить, но небольшое направление было бы замечательно. Я должен определить, должен ли я доказать или опровергнуть эти три утверждения ...

Определение пола и потолка у меня довольно простое. Я не буду размещать их здесь. Как только я определяю, нужно ли им доказательство / опровержение, я должен приступить к тому, чтобы действительно это произошло.

Я догадываюсь, что первому нужно опровергнуть, потому что дело не в том, что все X и Y пол и равный потолок меньше, чем умноженный пол. Это кажется слишком строгим.

Второе утверждение кажется менее строгим. Раз этаж выше, чем пол xy ... это очень возможно.

Третий вариант также представляется возможным, хотя большую часть времени я держу пари, что они будут равны по стоимости.

Интересно, если я на правильном пути. Извините за мои обозначения, я не хотел использовать формальные математические символы. Мне придется выписать формальное и строгое доказательство для каждого.

Answer 1

Великолепная книга, которая сделает вас чрезвычайно опытным в работе с полами и потолками, а также ряд других полезных вещей: Конкретная математика: основа компьютерных наук Грэм, Кнут и Паташник. Это очень весело, вы должны прочитать это!

Для ваших конкретных вопросов есть простые примеры / контрпримеры для каждого:

1. «Для всех x, для всех y, floor (x) * ceil (y) <= floor (xy)» - просто возьмите x = 1, а y не целое число: тогда это говорит о том, что ceil (y) ≤ floor (у), что, очевидно, не соответствует действительности. </li>
2. «Some X, Some Y, floor (x) * ceil (y)> = floor (xy)» - Опять же, возьмите x = 1 и любой y: тогда это говорит о том, что ceil (y) ≥ floor (y ), что является правдой.
3. «Для всех X, для всех Y, floor (x) * ceil (y)> ceil (xy)» - снова возьмите x = 1! Он говорит, что ceil (y)> ceil (y), что не может быть правдой. На самом деле вы можете получить строго меньше, взяв, например, x = 0,99 и y положительно: тогда левая сторона равна 0, а правая положительна.

Answer 2

1. Контрпример: x = 2,9, y = 2,9; ⎣x⎦ = 2; ⎡y⎤ = 3; ⎣xy⎦ = 8.
2. Рассмотрим x = 2.4, y = 2.4, но ∃x ∃y ⎣x⎦.⎡y⎤ ≥ ⎣xy⎦ не очень сильное утверждение.
3. Контрпример: x = 2, y = 2; ⎣x⎦ = 2, ⎡y⎤ = 2, ⎡xy⎤ = 4.

Мне не пришлось много работать, чтобы найти подходящие примеры.