Студопедия

Главная страница Случайная страница

Разделы сайта

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






Пример 3. Доказать, что простых чисел бесконечно много.






Решение. Предположим противное, т.е. пусть различных простых чисел – конечное число. Обозначим самое большое из них через p. Образуем теперь из всех простых чисел от 2 до p число

2·3·5·7·11·...· p +1 = N.

Очевидно, что N не делится ни на одно из использованных здесь простых чисел 2, 3, 5,..., p (при таком делении в остатке всегда будет получаться 1). Значит, возможны только два варианта: либо само N будет простым числом, и притом значительно превышающим p, либо N будет разлагаться на простые множители, заведомо отличные от чисел 2, 3, 5,..., p, т.е. б о льшие чем p. И в том, и в другом случае должны существовать простые числа, б о льшие p, следовательно, обе возможности противоречат исходному предположению о конечности набора простых чисел. Полученное противоречие показывает, что исходное предположение было неверным, значит, простых чисел бесконечно много.

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

Доказательство существования

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

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

Пример. В самолете летят 380 пассажиров. Докажем, что по крайней мере двое из них родились в один и тот же день года.

Решение. Всего в году 365 или 366 дней, а пассажиров в самолете 380 – значит, их дни рождения не могут приходиться только на различные даты. Вообще, если пассажиров больше, чем 366, то хотя бы у двоих дни рождения совпадают. А вот если пассажиров 366, не исключено, что все они родились в разные дни года, но это маловероятно. (Согласно теории вероятностей, в случайно выбранной группе численностью свыше 22 человек совпадение дней рождения у некоторых из них более вероятно, нежели то, что у всех дни рождения приходятся на разные дни года.)

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

Пусть в n ящиков помещены k предметов. Если количество предметов больше количества ящиков (k > n), то существует хотя бы один ящик, в котором находятся не менее двух предметов.

В шутливой форме принцип Дирихле часто формулируют так: Пусть в n клетках сидит не меньше, чем n +1 кроликов; тогда найдется клетка, в которой сидит не меньше двух кроликов.

Рассмотрим еще примеры на применение этого принципа.

Пример. Доказать, что среди шести любых натуральных чисел найдутся два числа, разность которых делится на 5.

Решение. Рассмотрим 5 «клеток», пронумерованных цифрами 0, 1, 2, 3, 4, представляющими собой остатки от деления на 5. Распределим в эти «клетки» шесть «кроликов», т.е. шесть заданных натуральных чисел в соответствии с остатком от деления на пять. А именно, в одну «клетку» помещаем числа, имеющие одинаковые остатки от деления на 5. Поскольку «кроликов» (чисел) больше, чем «клеток», то согласно принципу Дирихле существует «клетка», содержащая не менее двух «кроликов». Значит, существуют (по крайней мере) два числа с одинаковым остатком от деления на 5. Тогда разность этих чисел делится на 5.

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

В основе всякого математического рассуждения лежат дедуктивный или индуктивный методы. Дедукция – это умозаключение от общего к частному, например, такое: известно, что если сумма цифр натурального числа делится на 3, то и само число делится на 3; так, поскольку у числа 678 сумма цифр, равная 21, делится на 3, то и само число 678 делится на 3. Индукция – это умозаключение от частного к общего, когда общие выводы получают, опираясь на ряд частных утверждений.

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

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

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

Пример. Рассмотрим трехчлен x 2 + x + 41, на который обратил внимание еще Л. Эйлер. Подставим в этот трехчлен вместо x нуль, получим простое число 41. Подставим теперь в этот же трехчлен вместо x единицу, получим опять простое число 43. Продолжая подставлять в трехчлен вместо x последовательно 2, 3, 4, 5, 6, 7, 8, 9, 10, получаем всякий раз простое число 47, 53, 61, 71, 83, 97, 113, 131, 151. На основании полученных результатов утверждаем, что при подстановке в трехчлен вместо x любого целого неотрицательного числа всегда в результате получается простое число. Однако, при более внимательном изучении трехчлена x 2 + x + 41 обнаруживается, что он равен простому числу при x = 0, 1, 2,..., 39, но при x = 40 этот трехчлен равен 412, т.е. числу составному.

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

Наверное, каждому приходилось выстраивать в ряд костяшки домино. Толкнешь первую – она повалит вторую, та – третью и так до тех пор, пока не упадут все. Заменим ряд доминошек бесконечным рядом утверждений: У 1, У 2, У 3,..., занумерованных натуральными числами. Пусть мы умеем доказывать, что:

I: первое утверждение ряда истинно;

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

Тогда нами доказаны все утверждения ряда. В самом деле, мы умеем «толкать первую доминошку» – доказывать первое утверждение, а п. II означает, что «каждая доминошка, падая, валит следующую». Какую бы «доминошку»-утверждение мы ни взяли, волна «падений»-доказательств, раз начавшись, рано или поздно дойдет до нее, т.е. утверждение будет доказано.

Общая формулировка принципа математической индукции выглядит так:

Если предложение A (n), зависящее от натурального числа n, истинно для n = 1 и из того, что оно истинно для какого-либо произвольного натурального n = k следует, что оно истинно и для следующего числа n = k +1 (кратко это записывают так: A (k)⇒ A (k +1)), то предложение A (n) истинно для любого натурального числа n.

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

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

1) Доказываемое утверждение проверяют для n = 1. Эта часть доказательства называется базисом индукции.

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

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

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

Примеры. 1. Предложение «Снег – белый» есть истинное высказывание.

2. Предложение «Волга впадает в Средиземное море» – ложное высказывание.

3. Предложение «2+2=10» – ложное высказывание.

Далеко не всякое предложение является высказыванием. В частности, вопросительные и повелительные предложения не относятся к высказываниям. Например, по поводу предложения «Который час?» не имеет смысла ставить вопрос, истинно оно или ложно; то же самое относится, скажем, к предложению «Мойте руки перед едой!». Не являются высказываниями и такие предложения, которые служат определениями чего-либо, например: «Трапецией называется четырехугольник, две стороны которого параллельны».

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

Однако, не всякое повествовательное предложение является высказыванием. Рассмотрим, например, предложение: «Остаток от деления числа n на 7 равен 3». В этом предложении не содержится никакого утверждения, и нельзя ставить вопрос о его истинности или ложности. Однако, подставив в это предложение вместо n конкретное натуральное число, мы получим высказывание.

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

В логике высказываний интересуются не содержанием, а истинностью (ложностью) высказываний. Если высказывание истинное, то ему предписывается (сопоставляется) значение «истина» (другие обозначения: «И» или «1»). Ложному высказыванию предписывается значение «ложь» (другие обозначения: «Л» или «0»). Эти значения называют значениями истинности высказываний.

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

Перейдем к точному описанию логических операций. В дальнейшем будем обозначать высказывания заглавными буквами латинского алфавита: A, B, C и т.д.

Определение 1. Отрицанием высказывания A называется новое высказывание, обозначаемое (читается: «не A» или «неверно, что A»). Высказывание A считается истинным, если высказывание A ложно, и ложным, если A истинно. (Другое обозначение отрицания высказывания A, которое встречается в литературе, – это A.)

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

A
И Л
Л И

Отрицание – одноместная (или унарная) операция. Последующие операции – двуместные (или бинарные).

Определение 2. Конъюнкцией высказываний A и B называется новое высказывание, обозначаемое AB (читается: «A и B»), которое считается истинным, если истинны оба высказывания A и B, и ложным во всех остальных случаях. (Другое обозначение для конъюнкции: A & B.)

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

Определение 3. Дизъюнкцией высказываний A и B называется новое высказывание, обозначаемое AB (читается: «A или B»), которое истинно в тех случаях, когда истинно хотя бы одно из высказываний A или B, и ложно, когда ложны оба высказывания A и B.

Приведенное определение дизъюнкции вполне отвечает обычному употреблению союза «или». Действительно, в практике рассуждений утверждение «A или B» считается верным в любом из случаев, когда верно A или B; если же оба утверждения A и B неверны, то неверно и «A или B».

Определение 4. Импликацией высказываний A и B называется высказывание, обозначаемое AB (читается: «Если A, то B», или «Из A следует B», или «A влечет за собой B»), которое ложно лишь в том случае, если A истинно, а B ложно.

Приведенное определение импликации в основном отражает тот смысл, который придается в обычных рассуждениях связке «если…, то…». Единственное возражение может вызвать случай, когда A – ложно, B – истинно, а высказывание AB – истинно. Однако стаким пониманием импликации приходится все же согласиться, поскольку принцип «Из лжи следует что угодно» представляется вполне оправданным.

Заметим, что при рассмотрении импликации A⇒ B высказывание A называют посылкой (или условием) импликации, а высказывание B – ее заключением (или следствием).

Определение 5. Эквивалентностью (равносильностью) высказываний A и B называется новое высказывание, обозначаемое A⇔ B (читается: «A эквивалентно B» или «A тогда и только тогда, когда B»), которое истинно в том и только в том случае, если A и B одновременно истинны или одновременно ложны.

Таблицы истинности рассмотренных двуместных логических операций имеют следующий вид:

A B A ∧ B A∨ B A⇒ B A⇔ B
И И И И И И
И Л Л И Л Л
Л И Л И И Л
Л Л Л Л И И





© 2023 :: MyLektsii.ru :: Мои Лекции
Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав.
Копирование текстов разрешено только с указанием индексируемой ссылки на источник.