МАЛЫЙ МЕХМАТ МГУ

Кружок 8 класса

Занятие 16. Логика (часть 2)

1.

Кого больше: котов, кроме тех котов, которые не Васьки, или Васек, кроме тех Васек, которые не являются котами?

Ответ Решение

Ответ. Тех и других поровну.

Решение. Коты, кроме тех котов, которые не Васьки, — это коты по кличке Васька. Васьки, кроме тех Васек, которые не коты, — это Васьки, являющиеся котами. Так что два указанных множества совпадают.

2.

Однажды на лестнице была найдена странная тетрадь. В ней было написано 100 следующих утверждений:
«В этой тетради ровно одно неверное утверждение».
«В этой тетради ровно два неверных утверждения».
...
«В этой тетради ровно сто неверных утверждений».
Какие из написанных утверждений верные?

Ответ Решение

Ответ. Единственное верное из написанных утверждений — предпоследнее: «В этой тетради ровно девяносто девять неверных утверждений».

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

3.

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

a)

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

b)

Некоторые студенты нашей группы — болельщики «Спартака». А некоторые болельщики «Спартака» занимаются спортом. Следовательно, некоторые студенты нашей группы занимаются спортом.

Пояснение Решение

Пояснение. Контрпример — это пример, доказывающий ошибочность какого-нибудь утверждения. Скажем, контрпримером к утверждению «Все треугольники — равносторонние» может служить любой прямоугольный треугольник: в силу неравенства треугольника или теоремы Пифагора все три его стороны не могут иметь равных длин.

Решение. Пусть, к примеру, спортом занимаются только члены клуба «Спартак», не являющиеся студентами нашей группы. Тогда утверждения обоих пунктов этой задачи будут неверны.

4.

На столе лежат четыре карточки, на которых сверху написано: «А», «Б», «4», «5». Что написано на противоположных сторонах карточек, неизвестно. Какое наименьшее число карточек надо перевернуть, чтобы проверить истинность утверждения: «Если на одной стороне карточки написано чётное число, то на другой — гласная буква»?

Ответ Решение

Ответ. Три (все, кроме первой).

Решение. Первую карточку переворачивать не надо. Ведь если даже на ее обратной стороне написано не четное число, а что-то другое (нечетное число, буква и т.д.), это не противоречит нашему утверждению! Вторую карточку надо переворачивать: если на ее обратной стороне написано четное число, наше утверждение будет неверно. Третью карточку, очевидно, тоже нужно проверить (на обороте должна быть гласная буква, а не что-то другое). Нужно проверить и послежнюю карточку: на ее обратной стороне не должно быть четного числа.

5.

Каждый туземец острова Амба — честняга или лжец.

а)

Перед вами два туземца. На вопрос «Вы — честняга?» первый буркает что-то неразборчивое. Второй приходит на помощь: «Мой друг ответил «да». Но не верьте ему — он лжец». Кто эти туземцы?

b)

Один из другой пары туземцев говорит: «Хотя бы один из нас — лжец». Ваши выводы?

c)

Что вы подумаете, услышав от одного из двух туземцев фразу «Мы оба лжецы»?

d) А услышав «Если я честняга, то мой друг лжец»?

Ответ Решение

Ответ. a) Первый лжец, а второй честняга.
b) Говорящий — честняга, а молчун — лжец.
c) Говорящий — лжец, а молчун — честняга.
d) Говорящий — честняга, а молчун — лжец.

Решение.

a) Предположим сначала, что второй честняга. Тогда из его правдивых слов заключаем, что его друг — лжец. Если же второй — лжец, то он оба раза соврал. То есть его друг ответил «нет», однако он честняга. Но честняга никогда не скажет, что он лжец, так что этого быть не могло.

b) Если говорящий — честняга, то его утверждение верно. Но сам он не лжец, значит, лжец — его друг. Если же говорящий — лжец, то его утверждение неверно. То есть оба туземца на самом деле честняги, чего быть не может по нашему предположению.

c) Если говорящий — честняга, то он сказал правду, а значит, он лжец, чего быть не может. Если же говорящий — лжец, то его утверждение неверно. Так как сам он лжец, то неверно, что его друг тоже лжец. Значит, молчун на самом деле — честняга.

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

6.

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

Ответ Решение

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

Решение.

Сначала рещим эту задачу в случае, когда нам точно известны слова «да» и «нет». Вопрос надо поставить так, чтобы ответы честняги и лжеца на вопрос об одной и той же дороге были одинковы. Можно задать, например, такой вопрос: «Если бы ты был не тем, кто ты есть на самом деле, сказал бы ты, что эта дорога ведет в деревню?» Если встречный — правдивец, а дорога ведет в деревню, он ответит на этот вопрос как лжец, то есть «нет». Если же встречный — лжец, а дорога вновь ведет в деревню, он должен ответить на этот вопрос как честняга, то есть «да». Но он соврет и при ответе, так что в итоге тоже «нет». Легко убедиться также, что если указанная дорога ведет на болото, то и честняга, и лжец на поставленный вопрос ответят «да».

Теперь путешественнику надо бороться с собственной безграмотностью. Для этого предыдущий вопрос надо переформулировать так, чтобы вместо ответа «да» всегда получать, например, ответ «таш», а вместо ответа «нет» — ответ «пиш». Проще всего попросить встречного отвечать на вопрос именно таким образом. В ответе к этой задаче приведен наименее корявый (с точки зрения русского языка) способ задать такой вопрос, который удалось придумать автору этого решения. (Правда, сам автор решения языком островитян не владеет вовсе. Может быть, на их языке этот вопрос звучит гораздо красивее? Попробуйте самостоятельно задать его на всех известных вам иностранных языках и выберите наиболее удачный, с вашей точки зрения, вариант.)

7.

a)

Перед вами трое — лжец, честняга и хитрец (говорит правду или ложь по своему усмотрению), которые знают, кто из них кто. Как и вам это узнать? Вопросы можно задавать в любом количестве любому из троих.

b)

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

Решение

Решение.

a) Зададим сначала всем троим вопросы: «Ты — честняга?», «Ты — лжец?» и «Ты — хитрец?» Вот как они ответят на них:

Вопрос	Честняга	Лжец	Хитрец
Ты — честняга?	Да	Да	?
Ты — лжец?	Нет	Нет	?
Ты — хитрец?	Нет	Да	?

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

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

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

Вопрос	Честняга	Лжец	Хитрец (притворяется лжецом)
Ты — честняга?	Да	Да	Да
Ты — лжец?	Нет	Нет	Нет
Ты — хитрец?	Нет	Да	Да

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

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