Объем усеченной призмы онлайн. Онлайн-калькулятор для расчета площади поверхности усеченной пирамиды. и ее объем

Практическое занятие № 2

Тема: Логика и доказательство. Доказательство: прямое, обратное, от противного. Метод математической индукции.

Занятие рассчитано на 2 академ. часа.

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

Теоретический материал

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

При доказательстве теорем применяется логическая аргументация. Доказательства в информатике  неотъемлемая часть проверки корректности алгоритмов. Необходимость доказательства возникает, когда нам нужно установить истинность высказывания вида (А  В). Существует несколько стандартных типов доказательств, включающих следующие:

1. Прямое рассуждение (доказательство).

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

Таким образом, прямое доказательство идет от рассмотрения аргументов к доказательству тезиса, т. е. истинность тезиса непосредственно обосновывается аргументами. Схема этого доказательства такая: из данных аргументов (а, b, с, ...) необходимо следует доказываемый тезис q.

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

Примеры:

1. Учитель на уроке при прямом доказательстве тезиса “Народ  творец истории”, показывает; во-первых , что народ является создателем материальных благ, во-вторых , обосновывает огромную роль народных масс в политике, разъясняет, как в современную эпоху народ ведет активную борьбу за мир и демократию, в-третьих , раскрывает его большую роль в создании духовной культуры.

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

В современном журнале мод “Бурда” тезис “Зависть - корень всех зол” обосновывается с помощью прямого доказательства следующими аргументами: “Зависть не только отравляет людям повседневную жизнь, но может привести и к более серьезным последствиям, поэтому наряду с ревностью, злобой и ненавистью, несомненно, относится к самым плохим чертам характера. Подкравшись незаметно, зависть ранит больно и глубоко. Человек завидует благополучию других, мучается от сознания того, что кому-то больше повезло”".

2. Обратное рассуждение (доказательство ) . Предполагаем, что высказывание В ложно и показываем ошибочность А. То есть, фактически, прямым способом проверяем истинность импликации ((не В)  (не А)), что согласно таблицы, логически эквивалентно истинности исходного утверждения (А  В).

3. Метод «от противного».

Этот метод часто используется в математике. Пусть а - тезис или теорема, которую надо доказать. Предполагаем от противного, что а ложно, т. е. истинно не-а (или). Из допущения выводим следствия, которые противоречат действительности или ранее доказанным теоремам. Имеем, при этом - ложно, значит, истинно его отрицание, т.е. , которое по закону двузначной классической логики (→ а ) дает а. Значит, истинно а , что и требовалось доказать.

Примеров доказательства “от противного” очень много в школьном курсе математики. Так, пример, доказывается теорема о том, что из точки, лежащей вне прямой, на эту прямую можно опустить лишь один перпендикуляр. Методом “от противного” доказывается и следующая теорема: “Если две прямые перпендикулярны к одной и той же плоскости, то они параллельны”. Доказательство этой теоремы пpямо начинается словами: “Предположим противное, т. е. что прямые АВ и CD не параллельны”.

Математическая индукция

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

Проверка корректности алгоритма, содержащего циклы, нуждается в довольно мощном методе доказательства, который называется «математическая индукция».

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

Принцип математической индукции  это следующая теорема:

Пусть мы имеем бесконечную последовательность утверждений P 1 , P 2 , ..., P n занумерованных натуральными числами, причём: утверждение P 1  истинно; если некоторое утверждение P k  истинно, то следующее утверждение P k +1 тоже истинно.

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

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

Способ рассуждений, основанный на принципе математической индукции называется методом математической индукции. Для решения задач методом математической индукции необходимо:

1) сформулировать утверждение задачи в виде последовательности утверждений P 1 , P 2 , ..., P n , ... ;

2) доказать, что утверждение P 1 истинно (этот этап называется базой индукции); 3) доказать, что если утверждение P n истинно при некотором n= k, то оно истинно и при n = k + 1 (этот этап называется шагом индукции).

Ввиду недостоверности заключения индукция не может служить методом доказательства. Но она является мощным эвристическим методом , т. е. методом открытия новых истин.

Индукция может привести к ложному заключению. Так, например, вычисляя значения выражения n 2 +n+17 при n = 1,2,3, ..., 15, мы получаем неизменно простые числа, и это наводит на мысль, что значение этого выражения при любом натуральном n есть простое число. Иначе говоря, на основании пятнадцати частных посылок получено общее заключение, относящееся к бесконечному множеству частных случаев, и это заключение оказывается ложным, так как уже при n = 16 получаем составное число 16 2 +16+17=172.

В истории математики были случаи, когда известные математики ошибались в своих индуктивных выводах. Например, П. Ферма предположил, что все числа вида 22 n + 1 простые, исходя из того, что при n = 1,2,3,4 они являются таковыми, но Л. Эйлер нашел, что уже при n = 5 число 232+ 1 не является простым (оно делится на 641). Однако возможность получения с помощью индукции ложного заключения не является основанием для отрицания роли индукции в школьном обучении математике.

Методические указания

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

Решение. Любое нечетное число, и в частности х, можно записать в виде х = 2 m + 1, где m  Z . Аналогично, у = 2 n + 1, n  Z .

Значит, произведение ху = (2 m + 1)(2 n + 1) = 4mn + 2m + 2n + 1 = 2(2 mn + m + n ) + 1 тоже является нечетным числом.

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

Решение. Отрицанием высказывания о нечетности числа n 2 служит утверждение « n 2 четно», а высказывание о четности n является отрицанием утверждения «число n нечетно». Таким образом, нужно показать прямым способом рассуждений, что четность числа n влечет четность его квадрата n 2 .

Так как n четно, то n =2 m для какого-то целого числа m . Следовательно, n 2 = 4 m 2 = 2(2 m 2 ) — четное число.

Пример 3: Методом «от противного» покажите, что решение уравнения х 2 = 2 является иррациональным числом, т. е. не может быть записано в виде дроби с целыми числителем и знаменателем.

Решение. Здесь нам следует допустить, что решение х уравнения х 2 = 2 рационально, т. е. записывается в виде дроби х = с целыми m и n , причем n  0. Предположив это, нам необходимо получить противоречие либо с предположением, либо с каким-то ранее доказанным фактом.

Как известно, рациональное число неоднозначно записывается

в виде дроби. Например, х = == и т.д. Однако можно считать, что m и n не имеют общих делителей. В этом случае неоднозначность записи пропадает.

Итак, предполагаем дополнительно, что дробь х = несократима ( m и n не имеют общих делителей). По условию число х удовлетворяет уравнению х 2 = 2. Значит, () 2 = 2, откуда m 2 = 2 n 2 .

Из последнего равенства следует, что число m 2 четно. Следовательно, m тоже четно и может быть представлено в виде m = 2р для какого-то целого числа р. Подставив эту информацию в равенство m 2 = 2 n 2 , мы получим, что 4р 2 = 2 n 2 , т. е. n 2 = 2р 2 .

Но тогда n тоже является четным числом. Таким образом, мы показали, что как m , так и n  четные числа. Поэтому они обладают общим делителем 2. Если же теперь вспомнить, что мы предполагали отсутствие общего делителя у числителя и знаменателя дроби, то увидим явное противоречие.

Найденное противоречие приводит нас к однозначному выводу: решение уравнения х 2 = 2 не может быть рациональным числом, т. е. оно иррационально.

Пример 4: Докажем по индукции следующее равенство (которое, конечно, допускает и другие доказательства):

1 + 2 + 3 + ... + n = n(n + 1)/2.

База. При n = 1 равенство превращается в тождество 1 = 1·(1 + 1)/2.

Шаг. Пусть равенство выполнено при n = k: 1 + 2 + 3 + ... + k = k(k + 1)/2.

Прибавим к обеим частям этого равенства k + 1. В левой части мы получим сумму 1+2+3+...+k+(k+1), а в правой - k(k+1)/2+(k+1)=(k(k+1)+2(k+1))/2=((k+2)(k+1))/2.

Итак, 1 + 2 + 3 + ... + k + (k + 1) = (k + 1)(k + 2)/2, а это и есть требуемое равенство при n = k + 1, где n означает произвольное натуральное число.

Контрольные вопросы

1. В чем разница между доказательством прямым рассуждением, обратным, от противного?
2. Что означает математическая индукция? Объясните принцип математической индукции.

Индивидуальные задания

1. Используя методы доказательства:

1) Прямым рассуждением докажите истинность высказывания: n и m — четные числа  n + m — число четное.

2) Дайте обратное доказательство высказывания: n 2 — четное число  n — четное.

3) Методом «от противного» докажите, что n + m — нечетное число  одно из слагаемых является четным, а другое — нечетным.

2. Докажите каждое из высказываний методом математической индукции.

1) 1 + 5 + 9 +…+(4 n - 3) = n (2 n  1) для всех натуральных чисел n .

2) 1 2 +2 2 +…+ n 2 = n (n +1)(2 n +1)/6 для всех натуральных чисел n .

3) д ля всех натуральных чисел n .

4) Число n 3  n делится на 3 при всех натуральных значениях числа n .

5) 1*1! + 2* 2!+…+- n * n ! = (n + 1)!  1 для всех натуральных чисел n .

(Символ n ! читается как « n факториал» и обозначает произведение всех натуральных чисел от 1 до n включительно: n ! = l *2*3*** (n  l )* n .)

Дополнительные задания:

1. Найдите ошибку в следующем «доказательстве» того, что все лошади одной масти.

Будем доказывать индукцией по n следующее утверждение: «В любом табуне из n это лошадей, все они одной масти». База (n = 1) очевидна: в этом случае все лошади - одна лошадь, она очевидно одной масти. Ш: пусть в любом табуне из k лошадей все лошади имеют одну масть. Рассмотрим табун из k + 1 лошади. Выберем в нём двух лошадей a и b и рассмотрим оставшиеся k – 1 лошадь. Составим табун из этих оставшихся лошадей, добавив к ним a. В нём k лошадей, поэтому, по предположению индукции, все они одной масти. Значит, лошадь a имеет ту же масть, что и оставшиеся лошади. Аналогично доказывается, что ту же масть имеет лошадь b. Значит, все k + 1 лошадь имеют одинаковую масть. Утверждение доказано.

2. На бесконечном клетчатом листе бумаги 100 клеток закрашены в чёрный цвет, а все остальные — в белый. За один ход разрешается перекрашивать в противоположный цвет любые четыре клетки, образующие квадрат 2x2. Докажите, что за несколько ходов можно добиться того, что все клетки окажутся белыми тогда и только тогда, когда любая горизонталь и любая вертикаль содержит чётное число чёрных клеток.

лат. reductio ad absurdum) - вид доказательства, при котором справедливость некоторого суждения (тезиса доказательства) осуществляется через опровержение противоречащего ему суждения - антитезиса. Опровержение антитезиса достигается путем установления его несовместимости с заведомо истинным суждением. Часто доказательство от противного опирается на двузначности принцип.

Отличное определение

Неполное определение ↓

ДОКАЗАТЕЛЬСТВО ОТ ПРОТИВНОГО

обоснование суждения путем опровержения методом "приведения к нелепости" (reductio ad absurdum) нек-рого другого суждения, – именно того, к-рое является отрицанием обосновываемого (Д. от п. 1-го вида) или того, отрицанием к-рого является обосновываемое (Д. от п. 2-го вида); "приведение к нелепости" состоит в том, что из опровергаемого суждения выводится к.-л. явно ложное заключение (напр., формальнологическое противоречие), что и свидетельствует о ложности этого суждения. Необходимость различения двух видов Д. от п. вытекает из того, что в одном из них (именно, в Д. от п. 1-го вида) имеет место логический переход от двойного отрицания суждения к утверждению этого суждения (т.е. применяется т.н. правило снятия двойного отрицания, разрешающее переход от A к А, см. Двойного отрицания законы), в то время как в другом такого перехода нет. Ход рассуждения в Д. от п. 1-го вида: требуется доказать суждение А; в целях доказательства предполагаем, что суждение А неверно, т.е. что верно его отрицание: ? (не-А), и, опираясь на это предположение, логически выводим к.-л. ложное суждение, напр. противоречие, – осуществляем "приведение к нелепости" суждения А; это свидетельствует о ложности нашего предположения, т.е. доказывает, истинность двойного отрицания: A; применение к A правила снятия двойного отрицания завершает доказательство суждения А. Ход рассуждения в Д. от п. 2-го вида: требуется доказать суждение?; в целях доказательства предполагаем верным суждение А и приводим это предположение к нелепости; на этом основании заключаем, что А ложно, т.е. что верно?. Различение двух видов Д. от п. важно потому, что в так называемой интуиционистской (конструктивной) логике закон снятия двойного отрицания не имеет места, в силу чего не допускаются и Д. от п., существенно связанные с применением этого логического закона. См. также Косвенное доказательство. Лит.: Тарский?., Введение в логику и методологию дедуктивных наук, пер. с англ., М., 1948; Асмус В. Ф., Учение логики о доказательстве и опровержении, [М.], 1954; Клини С. К., Введение в метаматематику, пер. с англ., М., 1957; Черч?., Введение в математич. логику, пер. с англ., [т.] 1, М., 1960.