39. Неформальное определение доказательства. Использование доказательства в математике. Виды доказательств.

Доказательство

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

научным мышлением. Будем придерживаться содержательного определения доказательства, данного русским математиком Н. Н. Непейводой:

Доказательство – конструкция, синтаксическая правильность которой гарантирует семантическую.

Выделим два вида использования доказательства.

• Сведение новой задачи к уже решенным задачам.

• Выявление условий, при которых можно пользоваться данным утверждением.

Решить задачу – значит свести ее к уже решенным

• Чистые математики занимаются тем, что решают задачи. Никакое математическое доказательство не ведется с самого

начала (за исключением нескольких примитивных теорем в учебниках логики и алгебры). Оно заканчивается ссылками на уже известные теоремы, которые когда-то были математическими задачами.

• Эта привычка сводить новые задачи к уже решенным послужила даже основанием для шутки, которая на самом деле

достаточно точно отражает суть математического метода:

Математику задали вопрос:

– Как приготовить чай?

– Элементарно. Берем чайник, наливаем в него воду, зажигаем газ,

ставим чайник на огонь, ждем пока закипит, выключаем газ,

кладем заварку в соответствующий сосуд, заливаем ее

кипятком, ждем еще пять минут, и чай готов.

– А если у нас уже есть чайник с кипятком?

– Выливаем из него кипяток и сводим задачу к предыдущей.

• Именно так и действует хороший математик, решая задачу.

• Даже работая в рамках какой-нибудь формальной теории, математик пытается неформально подходить к доказательству, облегчая себе жизнь. Для этого уже доказанные теоремы используются наравне с аксиомами, кроме того, используются новые правила вывода, обоснованность применения которых следует из существующих правил вывода и аксиом.

• Например, справедливо цепное правило вывода, которое позволяет вывести новую импликацию из двух данных

импликаций. Можно записать его следующим образом:

A ⊃ B, B ⊃ C |– A ⊃ C.

• Во всей своей полноте понятие доказательства несомненно обладает и психологическими признаками. Надо обладать

красноречием и умением убеждать, чтобы слушатели (или читатели) приняли ваше доказательство. С неформальной

точки зрения, доказательство – это просто рассуждение, убеждающее нас настолько, что с его помощью мы готовы

убеждать других.

Классические методы доказательства

• Использование теоремы о дедукции.

• Доказательство импликаций с помощью контропозиции.

• Доказательство с помощью противоречия (от противного).

• Доказательство контрпримером.

• Метод математической индукции.

40. Доказательство контрпримером. Доказательство от противного. Пример доказательства.

Доказательство от противного

• Частным случаем косвенных методов доказательства является приведение к противоречию (от противного). Метод

доказательства основывается на следующем утверждении.

Если Γ, ¬S |− F, где F − любое противоречие (тождественно ложная формула), то Γ |-− S.

В этом методе используются следующие равносильности:

• A⊃B ≡ ¬ (A⊃B) ⊃ (C&¬C) ≡ (A&¬B) ⊃ (C&¬C),

• A⊃B ≡ (A&¬B) ⊃¬A,

• A⊃B ≡ (A&¬B) ⊃B.

• Например, возьмем равносильность A⊃B ≡ (A&¬B) ⊃¬A

• Для доказательства A⊃B, мы допускаем одновременно A и ¬B, т.е. предполагаем, что заключение ложно: ¬ (A⊃B) ≡ ¬ (¬A∨B) ≡ A & ¬B.

• Теперь мы можем двигаться и вперед от A, и назад от ¬B. Если B выводимо из A, то, допустив A, мы доказали бы B. Поэтому, допустив ¬B, мы получим противоречие. Если же мы выведем ¬A из ¬B, то тем самым получим противоречие с A.

• В общем случае мы можем действовать с обоих концов, выводя некоторое предложение C, двигаясь вперед, и его отрицание ¬C, двигаясь назад. В случае удачи это доказывает, что наши посылки несовместимы или противоречивы (равносильность A⊃B ≡ (A&¬B) ⊃ (C&¬C) ). Отсюда мы выводим, что дополнительная посылка A&¬B должна быть ложна, а значит, противоположное ей утверждение A⊃B истинно. Метод доказательство от противного – один из самых лучших инструментов математика. «Это гораздо более “хитроумный” гамбит, чем любой шахматный гамбит: шахматист может пожертвовать пешку или даже фигуру, но математик жертвует партию» (Г. Харди).

Пример 1. Докажем, что диагональ единичного квадрата является иррациональным числом.

Доказательство. Используя теорему Пифагора, переформулируем утверждение: «Не существуют два таких целых числа p и q, чтобы выполнялось отношение

q

2 = p

В самом деле, тогда мы приходим к равенству p2 = 2q2. Мы можем считать, что дробь p/q несократима, иначе мы с самого начала

сократили бы ее на наибольший общий делитель чисел p и q. С правой стороны имеется 2 в качестве множителя, и потому p2 есть четное число, и, значит, само p – также четное, так как квадрат нечетного числа есть нечетное число. В таком случае можно положить p = 2r. Тогда равенство принимает вид: 4r2 = 2q2, или 2r2 = q2. Так как с левой стороны теперь имеется 2 в качестве множителя, значит

q2, а следовательно, и q – четное. Итак, и p, и q – четные числа, т.е. делятся на 2, а это противоречит допущению, что дробь p/q

несократима. Итак, равенство p2 = 2q2 невозможно, и корень 2 не может быть рациональным числом.

Пример 2. Доказать, что простых чисел бесконечно много.

Доказательство. Предположим, что существует конечное множество простых чисел и p есть наибольшее из них: 2, 3, 5, 7, 11, …, p.

Определим число N=p!+1. Число N при делении на любое из чисел 2, 3, 5, 7, 11, …, p дает в остатке 1. Каждое число, которое не является простым, делится, по крайней мере, на одно простое число. Число N не делится ни на одно простое число, следовательно, N само простое число, причем N>p. Таким образом, мы пришли к противоречию, которое доказывает, что простых чисел бесконечно много.

Теорема. Единица – наибольшее натуральное число.

Доказательство. Пусть k > 1 – наибольшее натуральное число; тогда k ⋅ k = k2 > k ⋅ 1 = k.

Последнее неравенство показывает, что k не является наибольшим натуральным числом. Следовательно, никакое целое число k > 1 не может быть наибольшим натуральным числом.

Остается принять, что наибольшим натуральным числом является 1, так как только в этом случае мы

не приходим к противоречию.

Доказательство контрпримером

Многие математические гипотезы имеют в своей основе форму: «Все объекты со свойством A обладают свойством B». Мы можем записать это в виде формулы ∀x (A(x)⊃B(x)), где A(x) обозначает предикат «x обладает свойством A», B(x) –

«x обладает свойством B». Если число возможных значений х является конечным, то в принципе доказательство может быть проведено с помощью разбора случаев, то есть непосредственной проверкой выполнимости гипотезы для каждого объекта. В случае если число объектов не является конечным, то такой возможности не существует даже в принципе.

Однако для доказательства ложности гипотезы достаточно привести хотя бы один пример (называемый в этом случае

контрпример), для которого гипотеза не выполнима. Наличие контрпримера доказывает отрицание формулы ∀x (A(x)⊃B(x)).