Дискуссионный математический форумМатематический форум

Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 3 часа [ Летнее время ]
MathHelpPlanet.com RSS-лента Математического форума

Часовой пояс: UTC + 3 часа [ Летнее время ]


Методы доказательств теорем

Методы доказательств теорем


Доказательство математического утверждения, как правило, представляет собой цепочку правильных рассуждений, использующих аксиомы и теоремы, справедливость которых установлена ранее. Рассуждение называется правильным, если из истинности всех посылок следует истинность заключения. Пусть высказывания A_1,A_2, \ldots,A_n — посылки, а высказывание A — заключение. Рассуждение проводится по схеме \frac{A_1,A_2,\ldots, A_n}{B}, т.е. из предположений A_1,A_2,\ldots,A_n следует заключение B. Это рассуждение является правильным, если формула (A_1\And A_2\And \ldots\And A_n)\Rightarrow B тождественно-истинная, т.е. истинна для любых истинностных значений входящих в нее высказываний A_1,A_2,\ldots,A_n,B.


Правильным рассуждениям соответствуют, например, схемы:


\frac{A\Rightarrow B,A}{B} — правило вывода (modus ponens);

\frac{A\Rightarrow B,B\Rightarrow C}{A \Rightarrow C} — правило силлогизма;

\frac{A\Rightarrow B,\lnot B}{\lnot A} — правило контрапозиции.


По первой и третьей схемам построены следующие рассуждения:


– если натуральное число n делится на 4, то оно четное. Число n делится на 4. Следовательно, число п четное;

– если натуральное число n делится на 4, то оно четное. Число n нечетное. Следовательно, число n не делится на 4.


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


Рассмотрим пример рассуждения по схеме \frac{A\Rightarrow B,B}{A}:


– если натуральное число n делится на 4, то оно четное. Число n четное. Следовательно, число n делится на 4.


При n=6 и n=8 соответственно получаем:


– если натуральное число 6 делится на 4, то оно четное. Число 6 четное. Следовательно, число 6 делится на 4;

– если натуральное число 8 делится на 4, то оно четное. Число 8 четное. Следовательно, число 8 делится на 4.


Оба рассуждения неправильные, хотя заключение второго рассуждения истинно (число 8 действительно делится на 4), т.е. схема \frac{A\Rightarrow B,B}{A} не соответствует правильным рассуждениям.


Часто вместо доказательства теоремы вида A\Rightarrow B доказывают истинность некоторого другого утверждения, эквивалентного исходному. Такие формы доказательства называют косвенными. Одним из них является способ доказательства от противного. Чтобы доказать истинность высказывания A\Rightarrow B предполагаем, что это утверждение ложно. Исходя из такого предположения, приходим к противоречию, а именно доказываем, что некоторое утверждение выполняется и не выполняется одновременно. Отсюда делается вывод о том, что предположение неверно, а исходное высказывание истинно.


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


если n нечетное число, то и число n^2 — нечетное.

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


Рассмотренная схема доказательства от противного не единственная. Применяются также другие схемы доказательства от противного:


\frac{A,\lnot B}{\lnot A} или \frac{A,\lnot B}{B}.

Еще одна схема косвенного доказательства (по закону контрапозиции) основана на эквивалентности двух утверждений A\Rightarrow B и B\Rightarrow \lnot A. В самом деле, эти утверждения либо оба истинны, либо оба ложны. Например, высказывания "если идет дождь, то на небе есть тучи" и "если на небе нет туч, то не идет дождь" оба истинны, а высказывания "если на небе есть тучи, то идет дождь" и "если не идет дождь, то на небе нет туч" оба ложны.


Во многих задачах нужно доказать справедливость некоторого утверждения (формулы) для любого натурального числа n. Непосредственная проверка таких утверждений для каждого значения п невозможна, поскольку множество натуральных чисел бесконечно. Для доказательства таких утверждений (формул) применяется метод математической индукции, суть которого заключается в следующем. Пусть требуется доказать истинность высказывания A(n) для всех n\in \mathbb{N}. Для этого достаточно доказать два утверждения:


1) высказывание A(n) истинно для n=1. Эта часть доказательства называется базой индукции;


2) для любого натурального k из того, что высказывание истинно для n=k (индукционное предположение) следует, что оно истинно и для следующего числа n=k+1, т.е. A(k)\Rightarrow A(k+1). Эта часть доказательства называется индукционным шагом.


Если пункты 1, 2 доказаны, можно сделать вывод об истинности высказывания A(n) для любого натурального n.


В самом деле, если высказывание A(1) истинно (см. пункт 1), то высказывание A(2) тоже истинно (см. пункт 2 при n=1). Поскольку A(2) истинно, то A(3) тоже истинно (см. пункт 2 при n=2) и т.д. Таким образом можно дойти до любого натурального числа n, убеждаясь в справедливости A(n).


Замечание В.6. В ряде случаев бывает необходимо доказать справедливость некоторого утверждения A(n) не для всех натуральных n, а лишь для n\geqslant p, т.е. начиная с некоторого фиксированного числа p. Тогда метод математической индукции модифицируется следующим образом:


1) база индукции: доказать истинность A(p);

2) индукционный шаг: доказать A(k)\Rightarrow A(k+1) для любого фиксированного k\geqslant p.


Из пунктов 1, 2 следует, что утверждение A(n) верно для всех натуральных n\geqslant p.




Пример В.16. Доказать справедливость равенства 1+3+5+\ldots+(2n-1)=n^2 для любого натурального числа n.


Решение. Обозначим сумму первых n нечетных чисел через S_n=1+3+\ldots+(2n-1). Требуется доказать утверждение A(n): "равенство S_n=n^2 верно для любого n\in \mathbb{N}". Доказательство проведем по индукции.


1) Поскольку S_1=1=1^2, то при n=1 равенство S_n=n^2 верное, т.е. высказывание A(1) истинно. База индукции доказана.


2) Пусть k — любое натуральное число. Выполним индукционный шаг A(k)\Rightarrow A(k+1). Предположив, что утверждение A(n) истинно при n=k, т.е. S_k=k^2, докажем, что утверждение A(n) истинно для следующего натурального числа n=k+1, то есть S_{k+1}=(k+1)^2. Действительно,


S_{k+1}= \underbrace{1+3+5+\ldots+(2k-1)}_{S_k}+ \bigl[2(k+1)-1\bigr]= S_k+2k+1= k^2+2k+1= (k+1)^2.

Поэтому A(k)\Rightarrow A(k+1) и на основании метода математической индукции заключаем, что высказывание A(n) истинно для любого натурального n, то есть формула S_n=n^2 верна для любого n\in \mathbb{N}.




Пример В.17. Перестановкой из n чисел называется набор первых n натуральных чисел, взятых в некотором порядке. Доказать, что количество различных перестановок равно n!. Выражение n! (читается "n факториал") равно n!= 1\cdot2 \cdot3\cdot \ldots\cdot (n-1)\cdot n. Две перестановки (i_1,i_2,\ldots,i_n) и (j_1,j_2,\ldots,j_n) из n чисел считаются равными, если i_1=j_1, i_2=j_2,\ldots,i_n=j_n, а в случае нарушения хотя бы одного из равенств перестановки считаются различными.


Решение. Проведем доказательство методом математической индукции.


1) Для n=1 имеется всего одна перестановка (1), т.е. 1!=1 и утверждение верно.


2) Предположим, что для любого k количество перестановок равно k!. Докажем, что количество перестановок из (k+1) чисел равно (k+1)!. В самом деле, зафиксируем число (k+1) на любом месте в перестановке из (k+1) чисел, а первые k натуральных чисел разместим на оставшихся k местах. Количество таких перестановок равно количеству перестановок из k чисел, т.е. k! по индуктивному предположению. Так как число (k+1) можно было поставить на любое из (к +1) мест в перестановке, заключаем, что количество различных перестановок из (k+1) чисел равно (k+1)\cdot(k!)=(k+1)!. Таким образом, предположив, что утверждение верно для n=k, удалось доказать, что оно верно для n=k+1.


Из пунктов 1 и 2 следует, что утверждение верно для любого натурального числа n.




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

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

Часовой пояс: UTC + 3 часа [ Летнее время ]


Яндекс.Метрика

Copyright © 2010-2018 MathHelpPlanet.com. All rights reserved