42415

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

Лабораторная работа

Логика и философия

Метод математической индукции. Рассмотреть метод математической индукции. Метод математической индукции можно сравнить с прогрессом. Принцип математической индукции  это следующая теорема: Пусть мы имеем бесконечную последовательность утверждений P1 P2 .

Русский

2013-10-29

73 KB

68 чел.

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

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

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

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

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

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

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

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

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

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

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

Примеры:

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

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

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

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

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

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

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

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

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

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

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

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

Пусть мы имеем бесконечную последовательность утверждений P1, P2, ...,Pn занумерованных  натуральными  числами,  причём:  утверждение P1  истинно; если некоторое утверждение Pk  истинно, то следующее утверждение Pk+1 тоже истинно.  

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Из последнего равенства следует, что число m2 четно. Следовательно, m тоже четно и может быть представлено в виде m= 2р для какого-то целого числа р. Подставив эту информацию в равенство m2 = 2n2, мы получим, что 4р2 = 2n2, т. е. n2 = 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) Дайте обратное доказательство высказывания: n2 — четное число  n — четное.

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

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

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

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

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

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

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

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

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

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

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

  

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

PAGE  5


 

А также другие работы, которые могут Вас заинтересовать

32280. Конструктивные схемы и порядок монтажа конструкций многоэтажных гражданских зданий с неполным каркасом и бескаркасных 138 KB
  Бескаркасные здания из кирпича и мелких камней и блоков возводят обычно с продольными несущими рис. В зданиях с поперечными несущими стенами рис. Возводятся также бескаркасные здания у которых несущими являются как поперечные так и продольные стены. Конструктивные схемы бескаркасных зданий с несущими стенами:а продольными б поперечными Бескаркасные крупноблочные здания со стенами из бетонных и других блоков имеют конструктивные схемы с поперечными и продольными несущими стенами рис.
32281. Схемы монтажа конструкций жилых крупнопанельных зданий с учетом конструктивных особенностей, условий устойчивости элементов, удобств и безопасности монтажа 81 KB
  Схемы монтажа конструкций жилых крупнопанельных зданий сучетом конструктивных особенностей условий устойчивостиэлементов удобств и безопасности монтажа Основные схемы монтажа крупнопанельных зданий Последовательность монтажа здания зависит от многих факторов: конструктивных особенностей здания; последовательности установки элементов рекомендуемой технологической картой; наличия подкосов фиксаторов монтажной оснастки. Схема монтажа крупнопанельных зданий с приобъектного склада рис. Схема монтажа элементов с приобъектного склада...
32282. Роль правосознания в правотворчестве и реализации права 30 KB
  Роль правосознания в правотворчестве и реализации права. Уровень правосознания законодателя его представления о значимости тех или иных правовых институтов его отношение к отдельным правовым явлениям напрямую выражаются в нормах права создаваемых в процессе правотворческой деятельности. юристыпрактики привлеченные к разработке проектов нормативных актов помогут обеспечить реальную применимость права его соответствие общественным реалиям связь права с общественной жизнью и юридической практикой. В процессе реализации права уровень...
32283. Правовая культура и правовое воспитание. Их понятие, соотношение и значение в условиях современной России 44.5 KB
  Юридическая культура важнейший элемент правовой системы общества непременное условие нормального функционирования государства. Правовая система без правовой культуры не действует. В отечественной литературе над проблемой правовой культуры активно работают такие ученыеправоведы как Н. Под правовой культурой предлагается понимать систему овеществленных и идеальных культурных элементов относящихся к сфере действия права и их отражение в сознании и поведении людей 'А.
32284. Понятие правоотношений. Их место в правовой системе и значение. Виды и структура правоотношений 47.5 KB
  Юридическую науку естественно интересуют прежде всего юридические или правовые отношения. Регулируя те или иные отношения оно тем самым придает им правовую форму в результате чего эти отношения приобретают новое качество и особый вид становятся правовыми облекаются в юридическую оболочку. Именно с помощью такого нормативного воздействия государственная власть переводит определенные отношения под свою юрисдикцию и защиту придает им упорядоченность стабильность устойчивость желаемую направленность вводит в нужное русло. Любые...
32285. Субъекты права как элементы правоотношений. Понятие и виды субъектов права по российскому зак-ву. Индивиды как субъекты права. Граждане и иностранцы – субъекты российского права 50 KB
  Субъекты права как элементы правоотношений. Понятие и виды субъектов права по российскому закву. Индивиды как субъекты права. Граждане и иностранцы – субъекты российского права.
32286. Содержание правоотношения. Характеристика субъективных прав и юридических обязанностей как элементов правоотношения 35 KB
  Содержание правоотношения. Характеристика субъективных прав и юридических обязанностей как элементов правоотношения. Правовое отношение имеет материальное волевое и юридическое содержание. Материальное или фактическое составляют те общественные отношения которые опосредуются правом; волевое государственная воля воплощенная в правовой норме и в возникшем на ее основе правоотношении а также волевые акты его участников; юридическое содержание образуют субъективные права и обязанности сторон субъектов правоотношения.
32287. Юридические факты. Понятие, виды юридических фактов и юридических составов. Их роль в праве 39.5 KB
  Понятие виды юридических фактов и юридических составов. Жизнь непрерывная цепь разнообразных фактов явлений действий случаев событий но не все из них приобретают юридическое значение а только такие которые затрагивают наиболее существенные интересы общества входят в сферу правового регулирования и могут повлечь за собой известные юридические последствия. Среди юридических фактов выделяются также правовые состояния нахождение на воинской службе в браке в родстве в розыске в должности и т. Особую роль в динамике правоотношений...
32288. Понятие и формы реализации права 41.5 KB
  Понятие и формы реализации права Право создается для того чтобы оно практически претворялось в жизнь чтобы достигались те цели на которые рассчитывал законодатель. Под реализацией права понимается процесс воплощения юридических предписаний в правомерных действиях граждан органов организаций учреждений должностных лиц и всех иных участников общественных отношений. Вне деятельности людей реализация права немыслима. Отсюда значение целенаправленной организаторской деятельности субъектов права.