Помощь по Теле2, тарифы, вопросы

Говоря «математическое доказательство», мы имеем в виду доказательство математического предложения. Доказательства, по способу ведения, подразделяются на прямые и косвенные.

Прямым доказательством теоремы Т называется конечная последовательность предложений j 1 , j 2 , ..., j n данной теории, удовлетворяющая следующим требованиям:

1) предложение j 1 – какое-либо несомненное начало;

2) каждое предложение j i последовательности или аксиома, или получается из предшествующих предложений по какому-либо из правил вывода математической логики;

3) последнее предложение последовательности j n есть Т .

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

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

Косвенное доказательство некоторой теоремы Т состоит в том, что исходят из отрицания Т и выводят из него ложное заключение. Это выведение называют «приведением к нелепости», или «приведением к абсурду». Основная форма косвенного доказательства начинается с и оканчивается предложением типа . В завершение такого доказательства обычно говорят: «полученное противоречие доказывает теорему».

Среди косвенных доказательств встречаются разделительные, в которых есть разделительное суждение вида «S есть Р 1 , Р 2 », где число всевозможных случаев n ³ 2 и конечно.

По форме умозаключения, в которой совершаются доказательства, различают индуктивные и дедуктивные. Индуктивные доказательства получаются в результате применения методов полной индукции и математической индукции.

Метод математической индукции – специальный метод доказательства, применяющийся к предложениям типа ("n Î N ) P (n ), т.е. к предложениям, выражающим некоторое свойство Р , присущее любому натуральному числу n . Многие утверждения содержат целочисленную переменную n , и если надо доказать, что утверждение верно для любого числа n ³ n 0 , то это можно осуществить в два этапа:

1) Утверждение проверяют для n = n 0 .

2) Предположив, что утверждение справедливо для некоторого n = k ³ n 0 , доказывают его справедливость для n = k + 1.

Если это осуществлено, то утверждение оказывается (этап 1) верным для n = n 0 и следовательно (этап 2), для n = n 0 + 1. Тогда (этап 2) оно верно для n = n 0 + 2 и т.д.

Эти этапы составляют основу метода математической индукции.

П р и м е р. Докажем методом математической индукции, что для всех n ³ 1 верное равенство

.

Для упрощения выкладок введем обозначение S (n ) = 1 + 2 + … + n ; требуется доказать, что для всех n ³ 1 верно равенство .

1) Для n = 1 оно очевидно.

2) Допустим, что для n = k оно выполнено, т.е. . Докажем, что тогда исходное равенство верно и для n = k + 1, т.е. . Действительно, S (k + 1) = 1 + 2 + … + k + (k + 1) =
= .

Ввиду того, что непосредственная проверка наличия этого свойства у любого натурального числа невозможна из-за бесконечности множества N , поступают так: устанавливают наличие этого свойства для n = 1 и доказывают, что из допущения о наличии его для n = k , где k – произвольное натуральное число, следует наличие этого свойства и для n = k + 1, т.е. для числа, «непосредственно следующего за k ».

После этого заключают об истинности предложения ("n Î N ) P (n ), т.е. о том, что свойством Р обладает любое натуральное число.

Нестрогое гипотетическое обоснование суждений, основанное на применении одних только умозаключений правдоподобия (вероятности), например, неполной индукции или аналогии, не является доказательством. Подавляющее большинство математических предложений доказывается на основе дедуктивных умозаключений – умозаключений достоверности. Математические доказательства – это в основном чисто дедуктивные доказательства. Они представляют собой цепочки дедуктивных силлогизмов.

Правильные умозаключения

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

Форма записи умозаключения такова: . Над чертой записаны Р 1 , Р 2 , ..., Р n – исходные высказывания, они называются посылками. Под чертой записано высказывание Р , которое логически следует из исходных и называется заключением или выводом.

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

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

Схема такого рассуждения записывается так:

и называется правилом заключения .

П р и м е р. Если четырехугольник – параллелограмм, то его диагонали пересекаясь делятся пополам. АВСD – параллелограмм. Следовательно, его диагонали пересекаясь, делятся пополам.

Существуют еще два вида дедуктивных умозаключений. Приведем их схемы.

1) – правило отрицания .

П р и м е р. В любом прямоугольнике противоположные стороны попарно равны. В четырехугольнике АВСD противоположные стороны попарно не равны, значит, АВСD – не прямоугольник.

2) – правило силлогизма .

П р и м е р. Если числитель меньше знаменателя, то дробь правильная. Если дробь правильная, то она меньше 1. Следовательно, если числитель дроби меньше знаменателя, то дробь меньше 1.

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

Его схема выглядит следующим образом:

П р и м е р. При умножении любого натурального числа на 5 последняя цифра в записи произведения 0 или 5.

Если натуральное число оканчивается на 0, то произведение оканчивается нулем. Если натуральное число оканчивается на 1, то произведение оканчивается на 5 и т.д. до 9. Переберем все возможные случаи. Значит, при умножении любого натурального числа на 5 последняя цифра в записи произведения 0 или 5.

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

1. Установите способы определения следующих понятий из начального курса математики: математическое выражение, однозначное число, двузначное число, нечетное число, деление, произведение, сантиметр.

2. Докажите с помощью таблицы истинности равносильности:

(A Ú B ) Ù C Û (A Ù C ) Ú (B Ù C );

По способу связи аргументов от условия к заключению доказательства подразделяются на прямые и косвенные .

Прямое доказательство основано на каком-нибудь несомненном начале, из которого непосредственно устанавливается истинность теоремы.

Методы прямого доказательства:

– синтетический,

– аналитический,

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

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

В учебниках приводятся преимущественно синтетические доказательства. Их преимущества – полнота, сжатость, краткость. Недостатки – отсутствие мотивации шагов, обоснования дополнительных построений; они носят значительно более формальный характер, чем аналитические доказательства.

Пример

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

Дано: АВ и СД – хорды окружности, Е – точка их пересечения.

Доказать: АЕ×ВЕ = СЕ×ДЕ. (1)

Доказательство (синтетическое)

Рассмотрим треугольники АДЕ и СВЕ. В этих треугольниках углы 1 и 2 равны, так как они вписанные и опираются на одну и ту же дугу ВМД, а углы 3 и 4 равны как вертикальные. По первому признаку подобия треугольников DАДЕ ~ DСВЕ. Отсюда следует, что , или АЕ×ВЕ = СЕ×ДЕ. Теорема доказана .

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

Пример . Теорема о хордах окружности.

Доказательство (аналитическое)

Чтобы доказать равенство (1), достаточно показать, что (2).

Для того, чтобы найти пропорцию (2), достаточно доказать подобие треугольников, стороны которых являются членами этой пропорции. Для получения таких треугольников соединяем точки С и В, А и Д.

Чтобы обосновать верность пропорции (2), достаточно доказать, что DАДЕ ~ DСВЕ. Эти треугольники подобны по первому признаку подобия треугольников: Ð1 = Ð2 как вписанные углы, опирающиеся на одну и ту же дугу ВМД, а Ð3 = Ð4 как вертикальные. Следовательно, теорема верна .

Любое аналитическое доказательство обратимо в синтетическое и наоборот. Это широко используется в учебном процессе. Технологии могут быть таковы:

1) синтетическое доказательство предваряется аналитическими поисками его плана;

2) синтетическое доказательство заменяется аналитическим, в качестве домашнего задания – изучение синтетического доказательства по учебнику;

3) при использовании лекционного метода (преимущественно за пределами курса основной школы) часто используется чисто синтетический метод доказательства.

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

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

Наиболее распространенный и единственно применимый в курсе планиметрии метод косвенного доказательства – доказательство от противного .

Логико-математическая сущность метода от противного: вместо прямой (р Þ q) доказывается обратная противоположной теорема ().

Поэтому доказательство методом от противного строится по следующей схеме:

1) пусть неверно q, то есть истинно ;

2) докажем, что ложно р, то есть истинно ;

3) убедились, что из ;

4) следовательно, р Þ q (в силу равносильности импликаций р Þ q и ), что и требовалось доказать.

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

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

1. Допускаем, что заключение теоремы ложно. Тогда будет верно противоречащее ему утверждение.

2. Вычленяем возможные случаи.

3. Убеждаемся, что в каждом случае приходим к следствию, которое противоречит:

– условию теоремы,

– ранее установленным математическим фактам.

4. Наличие противоречия заставляет отказаться от принятого заключения.

5. Признаем справедливость заключения доказываемой теоремы.

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

Можно говорить об основных математических методах доказательства теорем. В геометрии к ним можно отнести следующие базовые методы:

1) метод геометрических преобразований : эффективен, соответствует современной концепции обучения геометрии в школе, но требует развитого абстрактного и пространственного мышления; методика его использования в школе недостаточно отработана;

2) метод равенства и подобия треугольников – соответствует классической концепции обучения геометрии в школе, известен со времен Евклида, поэтому методика его хорошо разработана; навыки его применения формируются постепенно, в процессе решения задач и доказательства теорем.

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

Методы доказательства, используемые в курсе геометрии основной школы, можно обобщить в виде схемы I.

Лекция 10. Способы математического доказательства

1. Способы математического доказательства

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

3. Основные выводы

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

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

Чтобы доказать данное утверждение, рассмотрим произвольный четырехугольник, в котором три угла прямые. Так как в любом выпуклом четырехугольнике сумма углов 360⁰, то и в данном она составляет 360⁰. Сумма трех прямых углов равна 270⁰ (90⁰ 3 = 270⁰), и, значит, четвертый имеет величину 90⁰ (360⁰ - 270⁰). Если все углы четырехугольника прямые, то он – прямоугольник Следовательно, данный четырехугольник будет прямоугольником. Что и требовалось доказать.

Заметим, что сущность проведенного доказательства состоит в построении такой последовательности истинных утверждений (теорем, аксиом, определений), из которых логически следует утверждение, которое нужно доказать.

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

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

Таким образом, основой математического доказательства является дедуктивный вывод. А само доказательство – это цепочка умозаключений, причем заключение каждого из них (кроме последнего) является посылкой в одном из последующих умозаключений.

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

1. В любом выпуклом четырехугольнике сумма углов равна 360⁰; данная фигура – выпуклый четырехугольник, следовательно, сумма углов в нем 360⁰.

2. Если известна сумма всех углов четырехугольника и сумма трех из них, то вычитанием можно найти величину четвертого; сумма всех углов данного четырехугольника равна 360⁰, сумма трех 270⁰ (90⁰ 3 = 270⁰), то величина четвертого 360⁰ - 270⁰ = 90⁰.

3. Если в четырехугольнике все углы прямые, то этот четырехугольник – прямоугольник; в данном четырехугольнике все углы прямые, следовательно, он прямоугольник.

Все приведенные умозаключения выполнены по правилу заключения и, следовательно, являются дедуктивными.

Самое простое доказательство состоит из одного умозаключения. Таким, например, является доказательство утверждения о том, что 6 < 8.

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

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

По способу ведения (по форме) различают прямые и косвенные доказательства. Рассмотренное ранее доказательство было прямым – в нем, основываясь на некотором истинном предложении и с учетом условия теоремы, строилась цепочка дедуктивных умозаключений, которая приводила к истинному заключению.

Примером косвенного доказательства является доказательство методом от противного . Сущность его состоит в следующем. Пусть требуется доказать теорему

А ⇒ В. При доказательстве методом от противного допускают, что заключение теоремы (В) ложно, а, следовательно, его отрицание истинно. Присоединив предложение «не В» к совокупности истинных посылок, используемых в процессе доказательства (среди которых находится и условие А), строят цепочку дедуктивных умозаключений до тех пор, пока не получится утверждение, противоречащее одной из посылок и, в частности, условию А. Как только такое противоречие устанавливают, процесс доказательства заканчивают и говорят, что полученное противоречие доказывает истинность теоремы

Задача 1. Доказать, что если а + 3 > 10, то а ≠ 7. Метод от противного.

Задача 2. Доказать, что если х² - четное число, то х – четно. Метод от противного.

Задача 3. Даны четыре последовательных натуральных числа. Верно ли, что произведение средних чисел этой последовательности больше произведения крайних на 2? Метод неполной индукции.

Полная индукция – это такой метод доказательства, при котором истинность утверждения следует из истинности его во всех частных случаях.

Задача 4. Доказать, что каждое составное натуральное число, большее 4, но меньшее 20, представимо в виде суммы двух простых чисел.

Задача 5. Верно ли, что если натуральное число n не кратно 3, то значение выражения n² + 2 кратно 3? Метод полной индукции.

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

Метод перебора – один из простейших методов доказательства. Например, чтобы установить, что заданное число, скажем 103, простое, достаточно проверить, что оно не делится ни на одно простое число, не превосходящее корня из данного числа, в нашем случае, что оно не делится на 2, 3, 5, 7.

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

Один из методов доказательства – принцип Дирихле (см. Дирихле принцип).

Доказательство – единственный способ установления истины в классической математике. Оно далеко не сразу заняло в математике такую исключительную роль. Например, в египетской и вавилонской математике вычислительные формулы, т.е. «рецепты» решения задач, так или иначе угадывались, они подвергались экспериментальной проверке, а затем сообщались в виде немотивированных утверждений.

Доказательства не сразу появились и в греческой геометрии. Архимед (III в. до н.э.) говорил о результатах, ранее «найденных, но не доказанных». С V в. до н.э. философы, начиная с Парменида и его ученика Зенона, во многом учась у ораторов, вычленяют различные приемы перехода от одних истинных утверждений к другим. Парменид формулирует закон «исключенного третьего» (из двух противоположных утверждений одно, и только одно, истинно), а Зенон использует метод приведения к абсурду (противоречию).

Но в математику эти приемы проникают не сразу: по-видимому, еще Демокрит, живший в V-IV вв. до н. э., обходился без доказательств. В IV в. до н.э. логика завоевывает математику. Несомненно, на первых порах доказательство – это логическое сведение неочевидных утверждений к очевидным или уже известным.

Наши современники не могут точно воссоздать картину, как появилась идея максимально ограничить число очевидных утверждений (аксиом), об истинности которых заключается соглашение и из которых остальные утверждения выводятся чисто логически (см. Аксиоматика и аксиоматический метод). В «Началах» Евклида (III в. до н.э.) грандиозная программа аксиоматизации геометрии уже полностью решена. По правилам Евклида доказательства должны быть чисто логическими выводами из аксиом. Окончательные геометрические тексты тщательно оберегались от дополнительных апелляций к очевидности. Прокл Диадох (V в.), первый комментатор Евклида, писал: «...мы научились от самих пионеров этой науки совсем не принимать в расчет правдоподобные заключения, когда дело касается рассуждений, которые должны войти в науку геометрии». Тем временем Аристотель проводит формализацию и каталогизацию правил умозаключений. Его утверждение об их конечности и обозримости не менее поразительно, чем утверждение о конечности множества аксиом. Полнота этих двух каталогов не оспаривалась до XIX в.

Правила, которыми мы пользуемся при логических рассуждениях (доказательствах), не выходят за пределы простых логических операций. Утверждение, справедливое для некоторого множества (скажем, всех параллелограммов), справедливо и для его подмножества (например, прямоугольников). Если справедливы утверждения и из следует , то справедливо . При доказательстве теоремы, имеющей вид «из следует » ( - то, что дано, - то, что требуется доказать), при помощи уже известных нам теорем выводятся разные следствия, которые затем комбинируются, и из их комбинаций делаются новые выводы, пока в результате не получится .

При доказательстве методом от противного теоремы «из следует » из справедливости утверждения и отрицания утверждения выводится справедливость пары противоположных утверждений, например, достаточно доказать отрицание утверждения или утверждения . Вспомним одно из классических доказательств от противного – доказательство Евклида бесконечности множества простых чисел. Если предположить, что множество простых чисел конечно и - их полный набор, то число не может быть составным, так как оно не делится ни на одно из простых чисел , но оно не может быть и простым, так как оно больше каждого .

Существуют и другие способы установления справедливости математических утверждений. Так, у Архимеда большинство его замечательных утверждений о площадях криволинейных фигур и объемах тел было получено первоначально при помощи чисто механических рассуждений с центрами тяжести, равновесием рычагов и т.д. В дальнейшем появилось большое число «механических» доказательств геометрических утверждений. Вот одно из самых изящных. Из внутренней точки многогранника на его грани опускаются перпендикуляры. Надо доказать, что хотя бы для одной грани перпендикуляр придется на саму грань, а не на ее продолжение. «Механическое» рассуждение состоит в следующем. Изготовляется массивный многогранник с неравномерной плотностью, у которого центр тяжести находится в заданной точке. Если все перпендикуляры попадут на продолжения граней, то многогранник не сможет стоять ни на одной грани, и мы получим вечный двигатель. Можно ли считать это рассуждение доказательством? С точки зрения, принятой в геометрии, разумеется, нет. Более того, нет никаких формальных способов преобразовывать «механические» доказательства в геометрические. Архимед справился с этой задачей, он дал геометрические доказательства к найденным им фактам.

Доказательство теоремы, как правило, не несет никакой информации о том, как к этой теореме можно на самом деле прийти. Одним из немногих великих математиков, допускавших посторонних в свою творческую лабораторию, был Л. Эйлер. Тексты Эйлера дают нам возможность проследить за ходом его мысли. Например, он рассматривает бесконечный ряд

.

.

Раскрывая скобки и вычисляя коэффициент при , получаем . Разумеется, Эйлер понимал, что его смелое рассуждение доказательством не является. Он ищет косвенные подтверждения: вычисляет с большим числом знаков левую и правую части полученного соотношения, получает другие аналогичные соотношения и в их числе уже доказанное Лейбницем: . У него появляется уверенность в правильности своего рассуждения, хотя он еще не в состоянии проводить эквивалентные строгие доказательства. Эйлер энергично использует свой прием для открытия новых фактов. Умение открывать новые факты в виде гипотез, умение исследовать гипотезы на правдоподобность, как и умение проводить строгие доказательства, важнейшие компоненты математического творчества.

С XVII в. математики начинают осознавать, что, в отличие от представителей других наук, они имеют надежный способ установления истины – доказательство. С этим связаны многочисленные попытки перенести доказательства за пределы математики. И. Ньютон строит механику на аксиомах по образцу «Начал» Евклида. Нидерландский философ-материалист XVII в. Б. Спиноза аксиоматизирует этику. Начиная с французского математика и физика П. С. Лапласа (1749-1827) многие пытались внедрить математические рассуждения в юридическую практику. Делались бесконечные попытки решить проблемы человеческих отношений при помощи математики. Но, конечно же, в самой математике доказательства стали играть важнейшую роль.

К началу нашего века аксиоматический метод выходит за пределы геометрии. Большинство фактов о числах, известных со времен Пифагора, носило характер частных наблюдений над конкретными числами, а не обобщающих теорем. В XVI в. теоремы появились в алгебре (у Дж. Кардано), в XVII в. – в теории чисел (у П. Ферма). Однако здесь математики не имели дело с аксиоматическими теориями и понимание доказательства находилось на доевклидовом уровне, когда набор исходных утверждений не фиксируется. В XIX в. начинается аксиоматизация всей математики. На новом уровне формализуются и перечисляются правила вывода – перехода от одних утверждений к другим. Это позволило доказать, что некоторые утверждения невыводимы из аксиом. Всеобщее удивление вызвало рассуждение немецкого математика К. Геделя о том, что в арифметике и вообще во всякой содержащей ее аксиоматической теории существует такая теорема, что ни она сама, ни ее отрицание невыводимы из аксиом.

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

• 1. Тезис, т.е. то, что предполагается доказать.
• 2. Аргументы, т.е. совокупность фактов, общепринятых понятий, законов и т.п. соответствующей науки.
• 3. Демонстрация, т.е. сама процедура развертывания доказательства; последовательная цепь умозаключений, когда /7-е умозаключение становится одной из посылок (я + 1)-го умозаключения. Выделяются правила доказательства, указаны возможные логические ошибки.

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

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

Как правило, в математике выделяют следующие понятия:

• теоремы как доказуемые утверждения;
• гипотезы, если ни утверждение, ни его отрицание еще не доказаны;
• леммы как менее сложные утверждения, которые доказываются.

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

В зависимости от контекста может иметься в виду формальное доказательство (построенная по специальным правилам последовательность утверждений, записанная на формальном языке) или текст на естественном языке, по которому при желании можно восстановить формальное доказательство. Формальными доказательствами занимается специальная ветвь математики - теория доказательств.

Сами формальные доказательства математики почти никогда не используют, поскольку для человеческого восприятия они очень сложны и часто занимают очень много места. Обычно доказательство имеет вид текста, в котором автор, опираясь на аксиомы и доказанные ранее теоремы, с помощью логических средств показывает истинность некоторого утверждения. В отличие от других наук в математике недопустимы эмпирические доказательства: все утверждения доказываются исключительно логическими способами.

В математике важную роль играют математическая интуиция и аналогии между разными объектами и теоремами; тем не менее все эти средства используются учеными только при поиске доказательств, сами доказательства не могут основываться на таких средствах. Доказательства, написанные на естественных языках, могут быть не очень подробными в расчете на то, что подготовленный читатель сам сможет восстановить детали. Строгость доказательства гарантируется тем, что его можно представить в виде записи на формальном языке (это и происходит при компьютерной проверке доказательств).

Ошибочным доказательством называется текст, содержащий логические ошибки, т.е. такой, по которому нельзя восстановить формальное доказательство. Ошибочным может быть только признание «доказательства» на естественном или формальном языке доказательством; формальное доказательство ошибочным не может быть по определению.

При характеристике математического доказательства выделяют две особенности.

• 1. Математическое доказательство исключает какие-либо ссылки на эмпирию. Вся процедура обоснования истинности вывода осуществляется в рамках принимаемой аксиоматики.
• 2. Наивысшая абстрактность математического доказательства, которой оно отличается от процедур доказательства в остальных науках.

В этом случае речь идет не просто о степени абстракции, а о ее природе. Дело в том, что высокого уровня абстрагирования доказательство достигает и в ряде других наук, например в физике, космологи и, конечно, в философии, поскольку предметом последней становятся предельные проблемы бытия и мышления.

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

Сама процедура доказательства, определяемая в логике как демонстрация, протекает на основе правил вывода, опираясь на которые осуществляется переход от одних доказанных утверждений к другим, образуя последовательную цепь умозаключений. Таким образом, мы устанавливаем истинность высказывания А -> В.

К наиболее часто используемым приемам относятся два правила (подстановки и вывода заключений) и теорема о дедукции, которые мы рассматривали на примере исчисления высказываний.

Правило подстановки. В математике подстановка определяется как замена каждого из элементов а данного множества каким-либо другим элементом Р(а) из того же множества. В математической логике правило подстановки формулируется следующим образом: «Если истинная формула М в исчислении высказываний содержит букву, скажем А, то, заменив ее повсюду, где она встречается, произвольной буквой /), мы получим формулу, так же истинную, как и исходная».

Это возможно и допустимо именно потому, что в исчислении высказываний отвлекаются от смысла высказываний (формул). Учитываются только значения «истина» или «ложь». Например, в формуле Я:А^(В V А)) на место Л подставляем выражение (В V А), в результате получаем новую формулу Я: (Ач В)^(В V (А V В)).

Правило вывода заключений (иногда называют правилом отделения) соответствует структуре условно-категорического силлогизма modus ponens (модус утверждающий) в формальной логике. Он имеет следующий вид:

а, а -> b b

Дано высказывание а и еще дано а -> Ь. Из этого следует Ь. Например: «Если идет дождь, то мостовая мокрая , дождь идет (а), следовательно, мостовая мокрая (b )». В математической логике это высказывание записывается таким образом :

((а -> Ь) & а) -> Ь.

Умозаключение определяется как правило отделения для импликации. Если дана импликация {а -> Ь) и ее посылка (а), то мы вправе присоединить к рассуждению (доказательству) также и следствие данной импликации (b ). Силлогизм носит принудительный характер, составляя арсенал дедуктивных средств доказательства, т.е. абсолютно отвечая требованиям математических рассуждений.

Большую роль в математическом доказательстве играет теорема дедукции - общее название для ряда теорем, процедура которых обеспечивает возможность установить доказуемость импликации: А -> В, когда налицо логический вывод формулы В из формулы А. В наиболее распространенном варианте исчисления высказываний (в классической, интуиционистской и других видах математики) теорема о дедукции утверждает следующее: «Если дана система посылок G и посылка А, из которых согласно правилам выводимо В (G, Ah В, где I- - знак выводимости), то следует, что только из посылок G можно получить предложение А -э В».

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

При прямом доказательстве доказывается тезис, а при косвенном используется антитезис.

Наиболее используемые виды прямых доказательств:

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

Прямой логический вывод. При прямом логическом выводе, устанавливая истинность А -» В, мы предполагаем, что А - истинно, и показываем истинность В. Такой способ доказательства исключает ситуацию (согласно таблице истинности импликации), когда А - истинно, а В - ложно.

Задача 4.9. Прямой вывод.

Доказать общезначимость формулы VxR(x) -> 3xR(x).

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

• 1. Предположим, что формула общезначима.
• 2. Тогда, используя равносильности для двойственности исчисления предикатов, получим тождественно истинную формулу

/xR{x) -> 3xR{x) = /xR(x) v 3xR(x) = /xR(x) v 3xR(x) =

• - 3xR(x) v 3xR(x) = 3x(R(x) v R(x)) = 3x1 = 1.
• 3. Раз формула тождественно истинна, так она общезначима.

Ч.т.д.

Доказательство через обратное рассуждение. Доказывая истинность Л -> В, мы предполагаем, что В - ложно, и на основе аргументированных предположений доказываем ошибочность Л. То есть фактически прямым способом проверяем истинность импликации

A^B = ?vB = Bv?=B^?.

Задача 4.10. Обратное рассуждение.

Доказать общезначимость формулы R = (/хР(х) -> ЗхР(х)) через обратное рассуждение.

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

Давайте определим, какое высказывание А -» В мы здесь должны доказать: «Из формулы R следует, что она общезначима». Таким образом, высказывание А - «формула R», высказывание В - «общезначимость R».

Отрицанием высказывания, что формула общезначима, является: «Формула R тождественно ложна». Отрицанием от формулы R является формула R.

Таким образом, мы должны доказать следующее высказывание:

«Из того, что формула R тождественно ложна, следует, что R равна нулю».

• 1. Предположим, что это так.
• 2. Тогда, используя равносильность для двойственности и равносильность для импликации, получаем

R = (/хР(х) -> ЗхР(х)) = /хР(х) v ЗхР(х) = ЗхР(х) v ЗхР(х).

3. Внесем квантор существования под скобку и получим, что R = 0:

R = Зх(Р(х) V Р(х)) = Id = Т = 0.

4. т.д.

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

Задача 4.11. Прямое доказательство по индукции.

Пусть Р(п) - предикат, определенный для всех натуральных п. Требуется установить справедливость бесконечной последовательности утверждений, занумерованных натуральными числами : Р(1), Р(2), ..., Р(п), ... .

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

Допустим, что:

• 1. Установлено, что Р( 1) верно. (Это утверждение называется базой индукции.)
• 2. Для любого п доказано, что если верно Р(п), то верно Р(п + 1), т.е. /k > 1 импликация Р(п) -> Р(п + 1) верна. (Это утверждение называется индукционным переходом.)
• 3. Тогда все утверждения нашей последовательности верны, т.е. Р(п) = 1 для любого натурального п. Ч.т.д.

Задача 4.12. Доказательство по индукции.

Доказать, что бинарное отношение T(N) = {res(Z> + 1, а) = 1}, заданное на множестве натуральных чисел N > 1, обладает свойством рефлексивности.

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

• 1. База индукции. Пусть а = 2, b = 2. Тогда res(2 + 1, 2) = 1 и пара (2, 2) принадлежит бинарному отношению Т.
• 2. Индукционный переход. Рассмотрим Ь- а - /". Тогда res(/ + 1, /) = = (/ + 1) - / = 1 и пара (/, /) принадлежит бинарному отношению Т. Возьмем Ь- а - / + 1, res(/ + 1 + 1, / + 1) = (/ + 1 + 1) - (/ + 1) = 1 и пара (/+ 1, /+ 1) принадлежит бинарному отношению Гдля любого /.
• 3. Тогда наша последовательность верна и все рефлексивные пары на натуральных числах N > 1 принадлежат нашему бинарному отношению Т. Ч.т.д.

Трансфинитная индукция - метод доказательства, обобщающий математическую индукцию на случай несчетного числа значений параметра.

Трансфинитная индукция основана на следующем утверждении.

Пусть М - упорядоченное множество, Р(х ) при х е М - некоторое утверждение. Пусть для любого X Е М из того, что Р(у) истинно для всех у ос, следует, что верно Р(х), и пусть верно утверждение Р(х), если х - минимальный элемент М, тогда утверждение Р(х) верно для любого X.

Косвенные доказательства. Не имея в силу ряда причин (недоступность объекта исследования, утрата реальности его существования и т.п.) возможности провести прямое доказательство истинности какого-либо утверждения, тезиса, строят антитезис. Убеждаются, что антитезис ведет к противоречиям и, стало быть, является ложным. Тогда из факта ложности антитезиса делают - на основании закона исключенного третьего (?v?)- вывод об истинности тезиса.

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

Известны следующие схемы косвенных доказательств:

• доказательство от противного;
• доказательство через контрпример.

Доказательство от противного в математике - один из самых часто используемых методов доказательства утверждений. Дана последовательность формул G и отрицание А (G, А). Если из этого следует В

и его отрицание (G , А, В , В, не-В), то можно сделать вывод, что из последовательности формул G вытекает истинность А. Иначе говоря, из ложности антитезиса следует истинность тезиса.

То есть, доказывая истинность А -> В, мы предполагаем, что И - истинно, В - ложно, и на основе аргументированных предположений получаем противоречие.

Этот способ доказательства основывается на истинности формулы ((А -> В) & В) -> А в классической логике и законе двойного отрицания А - А.

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

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

Задача 4.13. Доказательство от противного.

Доказать равносильность формул

/хР(х) & /xQ(x) = /х(Р(х) & Q(x)).

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

• 1. Предположим, что это не так, что формулы неравносильны, т.е. УхР(х) & /xQ(x) Ф /х(Р(х) & Q(x)).
• 2. Тогда должны найтись Р(х) и Q(x) такие, что равносильность не выполняется. В этом случае возможно три варианта:
  • Р(х) и Q(x) оба тождественно истинные;
  • один предикат тождественно истинен, другой - нет, например Р(х) тождественно истинен, а Q(x) - нет;
  • Р(х) и Q(x) оба не тождественно истинные.
• 3. Рассмотрим случай, когда Р(х) и Q(x) оба тождественно истинные (табл. 4.6).

Таблица 4.6

Таблица для задачи 4.3 (шаг 3)

• 4. Рассмотрим случай, когда Р(х) тождественно истинен, а Q(x) - нет (табл. 4.7).
• 5. Рассмотрим случай, когда Р(х) и Q(x) оба не тождественно истинные (табл. 4.8).

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

6. Следовательно, указанные формулы равносильны. Ч.т.д.

Таблица для задачи 4.3 (шаг 4)

Таблица 4.8

Таблица для задачи 4.3 (шаг 5)

Задача 4.14. Доказательство от противного. Доказать общезначимость формулы

Vx(/?(x) v Pix)) -> (Зх/?(х) v ЗхР(х)).

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

• 1. Предположим, что это не так, что формула не общезначима, т.е. должны найтись Р(х) и Q(x) такие, на которых формула равна нулю.
• 2. Тогда

Vx(/?(x) v Pix)) -> (3xR(x) v ЗхР(х)) =

Vx(/?(x) v Р(х)) v 3xR(x) v ЗхР(х) =

= 3x(R(x) & Р(х)) v 3xR(x) v Зх/ > (х) =

3x(R(x) & Р(х) v R(x) v Р(х) = Зх(1) = 1.

Таким образом, мы получили тождественно истинное высказывание для любых R(x) и Q(x).

3. Следовательно, наше предположение об отсутствии общезначимости было неверным и наша формула - общезначима. Ч.т.д.

Доказательство через контрпример строится по другой схеме.

• 1. Сначала принимается предположение, что утверждение А верно, а затем рассматривается особый случай - контрпример , при котором данное утверждение А неверно.
• 2. Полученное противоречие показывает, что исходное предположение было неверным, и поэтому верно утверждение А.

Задача 4.15. Использование контрпримера.

Исследовать , является ли формула

УхР(х) v VxQ(x) = Vx(P(x) v Q(x))

общезначимой.

Решение.

• 1. Предположим, что формула общезначима. Тогда она тождественно истинная для любой области.
• 2. Приведем контрпример. Положим, 0(х) = Р(х), оба не тождественно истинные. Тогда:

/х(Р(х) v Р(х)) = /х = 1 - тождественно истинное высказывание;

/хР(х) v /хР(х) = 0 v 0 = 0 - тождественно ложное высказывание.

• 3. Правая и левая части формулы не равны между собой. Это означает, что мы получили противоречие и на данном контрпримере рассматриваемая формула ложна.
• 4. Следовательно, наше предположение об общезначимости было неверным.
• 5. Значит, рассматриваемая формула не является общезначимой.

Рассмотрим несколько задач на построение доказательств для

свойства делимости.

Задача 4.16

Доказать методом математической индукции , что число п 3 - п делится на 3 для всех натуральных п.

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

• 1. База индукции. Пусть п = 1, тогда I 3 - 1 =0. Число 0 делится нацело на любое натуральное число, в том числе и на 3.
• 2. Индукционный переход. Предположим, что п 3 - п делится на 3 при каком-то натуральном к. Тогда
• (к + I) 3 ~(к +) = (к + 1 )((к + I) 2 - 1) =

= (к + 1 )(к + 1 + )(к + !-!) = (* + 2 )(к +1 )к.

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

3. Следовательно, наше выражение кратно трем для любого натурального п. Р(п) для любого п. Ч.т.д.

Задача 4.17

Доказать методом математической индукции, что число 7" - 1 делится на 6 для всех натуральных п.

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

Вспомним несколько утверждений, которые касаются делимости целых чисел друг на друга:

• целое число а делится на целое число b тогда и только тогда, когда а = kb при каком-то целом числе к;
• сумма чисел, делящихся на Ь, также делится на Ь.
• 1. База индукции. Пусть п = 1, тогда 7 1 - 1 = 6. Число нацело делится на 6.
• 2. Индукционный переход. Предположим, что 7" - 1 делится на 6 при каком-то натуральном к. Тогда
• 7* +| -1 = 7- 1 к -1 + 6- 6 = 7(7* - 1) + 6.

Число 7* - 1 делится на 6 в соответствии с нашим предположением. Делится на 6 и 7(7* - 1). Сумма чисел, кратных шести, также кратна шести.

3. Следовательно, наше выражение кратно шести для любого натурального п. Индуктивным рассуждением мы доказали истинность предиката Р(п ) для любого п. Ч.т.д.