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

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

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

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

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


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

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


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


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


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

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

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


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


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

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


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


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


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


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


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

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


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


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


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


если [math]n[/math] нечетное число, то и число [math]n^2[/math] — нечетное.

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


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


[math]\frac{A,\lnot B}{\lnot A}[/math] или [math]\frac{A,\lnot B}{B}[/math].

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


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


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


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


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


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


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


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

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


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




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


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


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


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


[math]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.[/math]

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




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


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


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


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


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




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


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


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

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