Инесса Раскина - Логика для всех. От пиратов до мудрецов

3) Гусеницы не отличаются красноречием. Джон красноречив.

4) Все шутки придуманы для того, чтобы смешить людей. Ни один закон не шутка.

5) Музыка, которую слышно, вызывает колебания воздуха. Музыка, которую не слышно, не стоит того, чтобы за нее платили деньги.

Задача 6.11.Придумайте свои примеры верных и неверных рассуждений про всех и некоторых.

Задача 6.12.В следующем рассуждении истинность исходных высказываний не вызывает сомнения. Верен ли вывод? Почему?

Все сочинения Пушкина нельзя прочитать за одну ночь. «Сказка о рыбаке и рыбке» – сочинение Пушкина. Следовательно, «Сказку о рыбаке и рыбке» нельзя прочитать за одну ночь.

С методом доказательства от противного каждый школьник неизбежно сталкивается (неожиданно, и поэтому, порой, жестко) на уроках геометрии. Надеемся, что ученик, разобравшийся с материалом предыдущих занятий, воспримет метод от противного как естественное продолжение знакомства с логикой и будет избавлен от неуместных формальных трудностей при изучении геометрии.

Задача 7.1 служит вводным упражнением, показывающим логическую основу метода от противного. С формальной точки зрения он состоит в замене доказательства того, что из А следует Б, на доказательство того, что из «не Б» следует «не А». Как показывает задача 7.2, иногда такой простой трюк существенно облегчает задачу.

Однако настоящая мощь метода от противного проявляется при более широком его понимании. Пусть дано А, а доказать требуется Б. Предположив противное, мы получим уже два условия: А и «не Б», а с двумя условиями работать легче, чем с одним. Из них требуется получить два любых противоречащих друг другу высказывания: В и «не В». Задачи 7.2, 7.3 и 7.4 демонстрируют, что В может как совпадать с одним из условий А или Б, так и быть новым утверждением.

Иногда метод от противного удается применить при решении задач, в формулировке которых условия А и Б явно не выделены (см. задачу 7.6 и комментарий к ней). Достаточно усвоить идею «Предположим противное и поищем противоречие».

Задача на доказательство не всегда содержит слово «докажите». Иногда решающий должен сам выбрать верный ответ на вопрос типа «Можно ли…», «Существует ли…» ит. п., а потом доказать правильность ответа. Если ответ отрицательный, часто бывает удобно предположить, что он положительный, а затем прийти к противоречию. Такое рассуждение от противного применяется в задачах 7.6 и 7.11, а также ДЗЗ и Д36.

Немного рекламы.

1) Доказательство от противного порадует любителей перебора: мы просто рассматриваем все случаи (часто их всего два, но может быть и больше), исключаем приводящие к противоречию и делаем вывод, какой из случаев выполняется.

2) «Противное» часто оказывается хорошим. От противного удобно доказывать «отрицательные» качества: неделимость, иррациональность, бесконечность. А предположив противное, мы сразу получим что-то хорошее, с дополнительными свойствами (делимость на простое число, числитель и знаменатель рациональной дроби, размер конечного множества).

3) Метод от противного не помешает даже там, где он не нужен. Пусть дано А, и из этого без всякого «противного» можно доказать Б. Но мы этого не заметили и зачем-то предположили «не Б». И только после этого из А (без использования «не Б») получили Б. Вот и хорошо! Б и «не Б» противоречат друг другу, метод от противного сработал.

А теперь антиреклама.

1) Если метод от противного сработал описанным только что образом, самое время упростить доказательство и выбросить из него «противную» оболочку.

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

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

Задача 7.1.Если рыцарь встречает дракона, то рыцарь вступает в бой.

1) Составьте к этому высказыванию обратное, противоположное и противоположное обратному.

2) Известно, что рыцарь вступил в бой. Означает ли это, что он встретил дракона?

3) Рыцарь не вступил в бой. Означает ли это, что он не встретил дракона?

Ответ. 1)Обратное: если рыцарь вступает в бой, то рыцарь встречает дракона. Противоположное: если рыцарь не встречает дракона, то рыцарь не вступает в бой. Противоположное обратному: если рыцарь не вступает в бой, то рыцарь не встречает дракона.

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

3) Означает. Ведь если бы он встретил дракона, то вступил бы в бой, что противоречит условию. То есть истинному прямому высказыванию соответствует истинное высказывание, противоположное обратному . А это значит, что их можно заменять друг на друга.

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

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

Решение.Предположим, что число является произведением двух чисел, состоящих только из единиц и нулей. Что может быть его последней цифрой? Только 1 или 0. А последней ненулевой цифрой? Только 1 (потому что произведение последних ненулевых цифр сомножителей – это произведение двух единиц). А что может быть первой цифрой? Тоже только 1. Однако по условию число не может содержать двух единиц. Значит, первая единица и является последней ненулевой цифрой. В таком случае в каждом из сомножителей только одна единица в записи. Но так как оба числа больше 1 (иначе другое равно произведению), оба они заканчиваются на 0, и в произведении найдутся два нуля.