Занятие 8. Равносильность

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Задача 9. Объект охраняют пятеро часовых: А, Б, В, Г и Д. При

этом справедливы следующие утверждения:

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

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

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

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

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

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

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

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

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

Задача 1. Из чисел 1, 2, 3, 4, 5, 6, 7 Незнайка задумал два числа и сообщил Знайке их произведение. Знайка не смог отгадать задуманные числа. Какое произведение мог сообщить Незнайка?

Задача 2. Встретились как-то два математика и разговорились:

А: «У меня трое сыновей».

Б: «Сколько им лет?»

А: «Произведение их возрастов равно 36. А сумма их возрастов равна номеру твоего дома».

Б: «Я все равно не знаю, сколько лет каждому».

А: «Мой старший сын рыжий».

После этого Б смог определить, сколько лет сыновьям А. Сколько же?

Задача 3. За столом сидело несколько жителей острова рыцарей и лжецов. Путешественник спросил каждого про его ближайших соседей. Каждый ответил: «У меня оба соседа – лжецы». Путешественник сказал: «Если бы вас было на одного больше или на одного меньше, я бы смог узнать, сколько среди вас рыцарей. А так не могу». Сколько человек было за столом?

Задача 4. Два мудреца написали на семи карточках числа от 5 до 11. После этого они перемешали карточки, первый мудрец взял себе три карточки, второй взял две, а две оставшиеся карточки они не глядя спрятали в мешок. Изучив свои карточки, первый мудрец сказал второму: «Я знаю, что сумма чисел на твоих карточках четна!» Какие числа написаны на карточках первого мудреца?

Задача 5. Один из двух братьев-близнецов по имени Джон совершил преступление. Известно, что по крайней мере один из близнецов всегда лжет. Судья спросил у братьев по очереди: «Вы – Джон?» Первый ответил: «Да». Второй тоже что-то ответил. После этого судья смог определить, кто из них на самом деле Джон. Определите это и вы.

Задача 6. На острове живут два племени: рыцарей и лжецов. Путешественник встретил двух островитян и спросил одного из них: «Вы оба рыцари?» Тот ответил «да» или «нет». Путешественник не смог определить, кто перед ним, и спросил у того же человека: «Вы из одного племени?» Тот ответил «да» или «нет», и теперь путешественник понял, из какого племени каждый из островитян. Кого он встретил?

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

Задача 8. Путешественник на острове рыцарей и лжецов пришел в гости к своему знакомому рыцарю и увидел его за круглым столом с пятью гостями.

– Интересно, а сколько среди вас рыцарей? – спросил он.

– А ты задай каждому какой-нибудь вопрос и узнай сам, – посоветовал один из гостей.

– Хорошо. Пусть каждый ответит на вопрос: кто твои соседи? – спросил путешественник.

На этот вопрос все ответили одинаково.

– Данных недостаточно! – сказал путешественник.

– Но сегодня день моего рождения, не забывай об этом, – сказал один из гостей.

– Да, сегодня день его рождения! – сказал его сосед. И путешественник смог узнать, сколько за столом рыцарей.

Сколько же их?

Задача 9. Саша и Маша загадали по натуральному числу и сказали их Васе. Вася написал на одном листе бумаги сумму загаданных чисел, а на другом – их произведение, после чего один из листов спрятал, а другой (на нем оказалось написано число 2002) показал Саше и Маше. Увидев это число, Саша сказал, что не знает, какое число загадала Маша. Услышав это, Маша сказала, что не знает, какое число загадал Саша. Какое число загадала Маша?

Задача 10. Есть 9 карточек с цифрами 1, 2…, 9. Их перетасовали, отдали четыре Ивану, четыре Василисе и одну Бабе-Яге. Иван сообщил вслух, что сумма цифр на его карточках оканчивается на 7.

1) Знает ли теперь Василиса карточку Бабы-Яги?

2) Знает ли теперь Баба-Яга набор карточек Василисы?

3) Может ли случится, что про какую-то карточку, кроме своей, Баба-Яга знает, у кого она находится?

Задача 11. Пять мудрецов играют в мафию. Среди них два мафиози, два мирных жителя и комиссар. Мафиози знают друг друга, комиссар знает все, мирные жители изначально ничего не знают. Мафиози могут говорить что угодно. Остальные говорят только то, в чем сами уверены. Состоялся разговор:

А: «Д – мирный житель».

Б: «Нет, Д – мафиози».

В: «Д не знает, кто я».

Г: «Д знает, кто я».

Д: «Б – мафиози».

Определите роли тех игроков, для кого это возможно.

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

Задача 2. Двум мудрецам принесли один белый и два черных колпака. Затем им завязали глаза и надели каждому на голову по черному колпаку, а белый спрятали. Когда им развязали глаза, у первого мудреца спросили, какой колпак на голове у него самого. Что он ответил? Когда после этого тот же вопрос задали второму мудрецу, он ответил правильно. Как он догадался?

Задача 3. Изменится ли решение предыдущей задачи, если вначале принесли: а) один белый и три черных колпака; б) два белых и два черных колпака?

Задача 4. Трем мудрецам принесли два белых и три черных колпака. Затем им завязали глаза и надели каждому на голову по черному колпаку, а белые спрятали. Когда им развязали глаза, у первого мудреца спросили, знает ли он, какой колпак на голове у него самого.

а) Что он ответил?

б) Тот же вопрос задали второму мудрецу. Что ответил второй?

в) Наконец, спросили третьего мудреца, и он правильно назвал цвет своего колпака. Как он рассуждал?

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

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

Задача 6. Как можно изменить количество колпаков в задаче о трех мудрецах, чтобы решение всех пунктов в точности сохранилось?

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

Задача 8*. В купе поезда собрались 7 мудрецов. Окно было открыто. Поезд въехал в тоннель, и лица всех мудрецов оказались испачканы сажей. Каждый видел, что и другие испачканы, но себя не видел и спокойно продолжал беседу. В купе вошел проводник и сказал: «Господа, среди вас есть люди с грязными лицами. В поезде воды нет. Зато на каждой станции поезд стоит достаточно долго, так что рекомендую испачкавшимся пойти и умыться». Несколько станций никто из мудрецов не реагировал на это замечание, но на некоторой станции все одновременно встали и пошли умываться.

1) На какой по счету станции мудрецы поняли, что следует умыться?

2) Парадокс проводника. Если бы проводник промолчал, каждый бы по-прежнему считал себя чистым и умываться не пошел бы. Но ведь каждый видел, что среди них есть испачкавшиеся, так что проводник, казалось бы, ничего нового не сказал. Так что же сказал проводник?

Задача 9. Установим соответствие между задачами о колпаках и о проводнике (при одинаковом количестве мудрецов). Будем считать, что на мудреце с грязным лицом надет черный колпак, а иначе – белый. Тогда ответу «Не знаю» в задаче о колпаках соответствует нежелание умываться в задаче о проводнике. Как перевести слова проводника на язык задачи о колпаках?

Задача 10. Три дамы сидят в купе с испачканными лицами и смеются. Вдруг А думает: «Почему Б не понимает, что В смеется над ней? О Боже! Они смеются надо мной!» Что в этой задаче играет роль проводника?

Задача 11. Фразы типа «Это верно», «А знает, что это верно», «Б знает, что А знает, что это верно», «В знает, что Б знает, что А знает, что это верно» можно продолжать до бесконечности, и все они имеют разный смысл, но разницу эту с каждым «витком» улавливать все труднее. Придумайте подобные цепочки, где эта разница заметна.

Приложение к занятию 10. Продолжаем играть в мудрецов

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

Задача 13. Пяти мудрецам принесли шесть колпаков: два желтых, два красных и два зеленых. Мудрецов построили в затылок друг другу и надели каждому по колпаку. Каждый мудрец видит колпаки всех стоящих перед ним, но не видит ни своего колпака, ни колпаков стоящих сзади. Затем по очереди, начиная с последнего, стали спрашивать каждого, знает ли он цвет своего колпака.

1) На мудрецов надеты колпаки в таком порядке: красный, желтый, зеленый, красный, желтый (а второй зеленый спрятан). Что ответят мудрецы?

2) На мудрецов надеты колпаки в таком порядке: красный, красный, желтый, желтый, зеленый (а второй зеленый спрятан). Что ответят мудрецы?

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

4) Один из мудрецов верно ответил на вопрос. Обязательно ли остальные после этого тоже смогут определить цвета своих колпаков?

5) Докажите, что не менее трех мудрецов правильно определят цвет своего колпака.

6) Придумайте ситуацию, в которой верно ответить на вопрос смогут четыре из пяти мудрецов.

Задача 14. 1) Двум мудрецам написали на лбу по натуральному числу и сообщили, что эти числа последовательные. Когда мудрецы посмотрели друг на друга, между ними состоялся такой диалог:

А: «Я не знаю моего числа».

Б: «А я знаю мое число».

Какие числа были написаны?