Главная » Java, Структуры данных и алгоритмы » Простые приемы доказательства[1]

0

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

Прием «Пример»

Иногда утверждения записываются в обобщенной форме: «Множество <5* содержит элемент х, обладающий свойством Р». Для доказательства данного утверждения достаточно привести пример х е S, который обладает свойством Р. В подобной обобщенной форме записываются, как правило, и маловероятные утверждения, например: «Каждый элемент х множества S обладает свойством Р». Чтобы доказать ошибочность данного утверждения, достаточно просто привести пример: х е S, который не обладает свойством Р. В данном случае элемент х будет выступать в качестве контрпримера.

Пример 3.2. Профессор Амонгус утверждает, что любое число вида 2′ – 1 является простым, если / — целое число, большее 1. Утверждение профессора Амонгуса ошибочно.

Доказательство: чтобы доказать неправоту профессора Амонгуса, необходимо найти контрпример. К счастью, для этого не потребуется много времени: 24 — 1 = 15 = 3-5.

Прием «Контратака»

Существует и другой способ, основанный на доказательстве от противного (использовании отрицания). Основными методами в данном случае являются контрапозиция и контрадикция. Использование метода противопоставления подобно зеркальному отражению. Чтобы доказать, что «если р — истинно, то и q — истинно», будем утверждать обратное «если q — ложно, то и р — ложно». С точки зрения логики, данные утверждения идентичны, однако второе выражение, которое является контра- позицией первого, более удобно.

Пример 3.3. Если ab — нечетное число, то а — нечетное или b — четное.

Доказательство: для доказательства данного утверждения рассмотрим контрапозицию: «Если а — четное число, а Ъ — нечетное, то ab — четное». Пусть а = 2/ для некоторого целого числа /. Тогда ab = (2i)b = lib, то есть ab — четное число.

Кроме метода контрапозиции, в примере используется закон де Моргана. Этот закон применяется при доказательстве от противного, в нем говорится, что отрицанием утверждения вида «р или q» является «не р и не q». А отрицанием утверждения вида «р и q» является «не р или не q».

Еще одним методом доказательства от противного является контрадикция,, часто используемая совместно с законом де Моргана. При использовании метода контрадикции для доказательства того, что утверждение q — верно, вначале предполагается, что q — ложно, а затем показывается, что такое предположение приводит к противоречию (например, 2 * 2’или 1 > 3). Придя к подобному противоречию, можно утверждать, что ситуации, при которой q — ложно, не существует, и, следовательно, q — истинно. Безусловно, чтобы сделать подобный вывод, условия должны быть непротиворечивыми до высказывания предположения, что q — ложно.

Пример 3.4. Если ab — нечетное число, то а — нечетное или b — четное.

Доказательство: пусть ab -г четное число. Необходимо доказать, что а — нечетное или b — четное. Предположим обратное, а именно, что а — четное, a b — нечетное. Тогда а = 2/ для некоторого целого числа i, и ab = (2i)b = 2(ib), то есть ab — четное число. Однако в этом случае появляется противоречие: ab не может быть одновременно четным и нечетным числом. В силу этого а — нечетное или b — четное число.

Источник: Гудрич М.Т. Г93 Структуры данных и алгоритмы в Java / М.Т. Гудрич, Р. Тамассия; Пер. с англ. A.M. Чернухо. — Мн.: Новое знание, 2003. — 671 е.: ил.

По теме:

  • Комментарии