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

Задача 8.1.1) Известно, что высказывание А ⇔ Б истинно. Что можно сказать об истинности высказываний А ⇒ Б и Б ⇒ А?

2) Известно, что высказывание А ⇒ Б истинно. Можно ли что-то сказать об истинности высказывания А ⇔ Б?

3) Известно, что высказывание А ⇒ Б ложно. Можно ли что-то сказать об истинности высказывания А ⇔ Б?

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

Ответ. 1) Оба высказывания истинны; 2) нет, высказывание А ⇔ Б может быть как истинным (в случаях, если А и Б одновременно истинны или одновременно ложны), так и ложным (в случае, если А ложно, а Б истинно); 3) да, высказывание А Б ложно, поскольку А истинно, а Б ложно.

Решение. Ответить на все три вопроса можно разными способами.

Первый способ: посмотрим на таблицы истинности для А ⇒ Б, Б^Аи А<^Б. Для удобства приведем общую таблицу. 1) А⇔ Б истинно для первой и четвертой строк, для этих строк и А ⇒ Б и Б ⇒ А оба истинны. 2) и 3) решаются аналогично.

Второй способ: посмотрим на иллюстрации высказываний А ⇒ Б, Б ⇒ АиА⇔Бс помощью кругов Эйлера.

1) Область истинности высказывания А⇔Б входит целиком в области истинности высказываний А ⇒ Б и Б ⇒ А.

2) Область истинности высказывания А ⇒ Б частично входит в область истинности высказывания А ⇔ Б, а частично находится за ее пределами. 3) В той области, где высказывание А ⇒ Б ложно, высказывание А ⇔ Б тоже ложно.

Третий способ пригоден только для пункта 2 и опирается на приведение конкретных примеров высказываний (например, из задач 5.2 (п. 1) и 5.2 (п. 2)). А вот то, что мы не можем подобрать всевозможных подходящих примеров в пунктах 1 и 3, еще не доказывает, что таких примеров и вовсе нет.

Задача 8.2. Бабушка печет пирог в те и только те дни, когда ждет гостей.

1) Бабушка печет пирог. Можно ли утверждать, что она сегодня ждет гостей?

2) Бабушка не печет пирог. Можно ли утверждать, что сегодня она не ждет гостей?

Ответ. 1) Да; 2) да.

Решение. Рассмотрим два высказывания. А: «Бабушка сегодня печет пирог», Б: «Бабушка сегодня ждет гостей». Тогда условие означает А⇔Б. В предыдущей задаче получено, что тогда истинно и А ⇒ Б, откуда ясен ответ в пункте 1. Кроме того, истинно и Б ⇒ А. А значит, и «не А» ⇒ «не Б», что мы и используем для доказательства от противного в пункте 2.

Задача 8.3. Равносильны ли высказывания А и Б? Если нет, то следует ли хотя бы одно из них из другого?

1) А: «Некоторые принцессы – красавицы»; Б: «Некоторые красавицы – принцессы».

2) А: «Все принцессы – красавицы»; Б: «Все красавицы – принцессы».

3) А: «Число N кратно 11»; Б: «Сумма цифр числа А, стоящих на четных местах, равна сумме цифр, стоящих на нечетных местах».

4) А: «Число N является квадратом натурального числа»; Б: «У числа N нечетное число делителей».

5) А: «У любой девочки из 6 „А“ больше друзей среди одноклассников, чем у любого мальчика из 6 „А“ среди одноклассниц»; Б: «В 6 „А“ мальчиков больше, чем девочек».

Ответ. 1) Равносильны; 2) нет; 3) нет, но Б ⇒ А; 4) равносильны; 5) нет, но А ⇒ Б.

Решение. Пункты 1 и 2 уже обсуждались в задачах 2.3 и 2.11.

3) Утверждение А ⇒ Б следует из признака делимости на 11; обратное неверно, например, 803 кратно 11, но суммы цифр на четных и нечетных местах не равны друг другу.

4) Объединим делители числа N в пары так, чтобы произведение двух чисел в паре равнялось N. Ясно, что N = n2 равносильно существованию числа п, которое является парным самому себе, при этом число делителей нечетно.

5) Поставим в соответствие каждому шестикласснику количество его друзей противоположного пола. Сумма этих чисел у всех девочек такая же, как и у всех мальчиков, и равна количеству дружб между мальчиком и девочкой. Так как все слагаемые для девочек больше, чем для мальчиков, у мальчиков должно быть больше слагаемых. Поэтому А ⇒ Б. Обратное неверно, для доказательства достаточно любого контрпримера. Например, в классе одна девочка и два мальчика, и никто из них ни с кем не дружит.

Задача 8.4. Чтобы доказать равносильность двух утверждений А и Б, необходимо доказать две теоремы: А ⇒ Б и Б ⇒ А. А какое наименьшее число теорем надо доказать, чтобы убедиться в равносильности: а) трех утверждений;

б) десяти утверждений?

Ответ, а) Три; б) десять.

Решение. Чтобы доказать, что из любого утверждения следует любое другое, достаточно получить их друг из друга по кругу (для трех утверждений А ⇒ Б ⇒ В ⇒ А, для десяти аналогично), при этом число теорем равно числу утверждений.

С другой стороны, теорем не может получиться меньше, чем утверждений. Действительно, для каждого утверждения должна быть теорема, где оно стоит справа от знака «⇒», иначе оно ни из чего не следует.

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

Задача 8.5*. В лифте многоэтажного дома работают только две кнопки: одна поднимает лифт на х этажей, вторая опускает на у этажей (если это возможно при данном положении лифта), где натуральные числа х и у меньше количества этажей в доме. Рассмотрим три утверждения:

(1) С любого этажа можно попасть на любой другой.

(2) С любого этажа, кроме последнего, можно подняться на следующий.

(3) С любого этажа, кроме первого, можно спуститься на предыдущий.

1) Покажите, что в зависимости от значений х и у каждое утверждение может быть как верным, так и неверным.

2) Между какими из этих утверждений можно поставить знак следствия и получить верное высказывание? Есть ли среди данных трех утверждений равносильные?

Решение. 1) При х = у = 1 все утверждения верны, при х = у = 2 неверны, так как нельзя поменять четность этажа.

2) Очевидно, что (1) ⇒ (2), (1) ⇒ (3). Кроме того, из одновременной истинности (2) и (3) следует (1). Докажем, что (2) ⇒ (3). Пусть лифт находится на n-м этаже. Если n – у > 0, то сначала опустимся на у этажей, а потом у — 1 раз поднимемся на 1 этаж и окажемся на (n — 1) – м этаже. Если n – у ≤ 0, то n < у + 1, поэтому можно, прибавляя по этажу, постепенно подняться до (у + 1) – го этажа, затем спуститься на у этажей до первого, а потом постепенно подняться на (n — 1) – й этаж. Аналогично доказывается и (3) ⇒ (2), что завершает доказательство равносильности всех трех утверждений.

Ответ. Все утверждения равносильны.

Задачи для самостоятельного решения

Задача 8.6. Иа-Иа считает, что у Винни-Пуха хорошее настроение бывает тогда и только тогда, когда Винни-Пух хорошенько подкрепился. Съев всё, что было у Кролика,

Винни-Пух застрял в норе, и его настроение сразу испортилось. Прав ли Иа-Иа?

Задача 8.7. Будем считать, что трава зеленая, а небо голубое. Определите, какие из данных высказываний истинны, а какие ложны:

1) Если трава зеленая, то небо голубое.

2) Если трава зеленая, то небо оранжевое.

3) Если трава оранжевая, то небо зеленое.

4) Если трава оранжевая, то небо голубое.

5) Трава зеленая тогда и только тогда, когда небо голубое.

6) Трава зеленая тогда и только тогда, когда небо оранжевое.

7) Трава оранжевая тогда и только тогда, когда небо зеленое.

8) Трава оранжевая тогда и только тогда, когда небо голубое.

Задача 8.8. В лесу живут только ляпусики и мордасики. Равносильны ли для обитателей леса три утверждения:

(1) все ляпусики кузявые;

(2) если кто-то некузяв, то он мордасик;

(3) никто, кроме мордасиков, не может быть некузявым?

Задача 8.9. Объект охраняют пятеро часовых: А, Б, В, Г и Д. При этом справедливы следующие утверждения:

1) Если А спит, то и Б спит.

2) Хотя бы один из Г и Д спит.

3) Ровно один из Б и В спит.

4) В спит тогда и только тогда, когда спит Г.

5) Если Д спит, то А и Г тоже спят.

Перечислите всех спящих часовых.

Задача 8.10! Трех братьев пригласили на день рождения. Всего ожидалось 17 человек. «Вот бы мальчиков было больше, чем девочек», – захотел первый. «Вот бы при любой рассадке по кругу нашлось два мальчика рядом», – захотел второй. «Вот бы при любой рассадке по кругу нашелся гость, сидящий между двумя мальчиками», – захотел третий. Докажите, что все трое хотят одного и того же.

Указание. Докажите равносильность трех утверждений по кругу: 1 ⇒ 2 ⇒ 3 ⇒ 1.

Задача 8.11*. У профессора есть n утверждений А2,…, Аn. О том, что все эти утверждения равносильны, знает только он. Профессор по очереди дает ученикам для доказательства такие теоремы: Ai ⇒ Aj. Нельзя давать теорему, если она следует из ранее доказанных. Какое наибольшее число теорем могут доказать ученики, если: 1) n = 3; 2) n = 4; 3) в общем случае?