Задачи по математической логике
Логические задачи и методы их решения
1. Типы и способы решения логических задач
1.1 Задачи типа «Кто есть кто?»
1.2 Тактические задачи
1.3 Задачи на нахождение пересечения множеств или их объединения
1.4 Буквенные ребусы и примеры со звездочками
1.5 Истинностные задачи
1.6 Задачи типа «Шляпы»
1.7 Задачи типа «Два города»
1.1 Задачи типа «Кто есть кто?»
Задачи типа «Кто есть кто?» очень разнообразны по сложности, содержанию и способности решения. Они, несомненно, представляют интерес для математического кружка.
Задача 1. Леня, Женя и Миша имеют фамилию Орлов, Соколов и Ястребов. Какую фамилию имеет каждый мальчик, если Женя, Миша и Соколов – члены математического кружка, а Миша и Ястребов занимаются музыкой?
Задача 2. Три товарища, Иван, Дмитрий и Степан преподают различные предметы в школах Москвы, Санкт-Петербурга и Киева. Известно, что Иван работает не в Москве, а Дмитрий – не в Санкт-Петербурге; москвич преподает химию. Дмитрий не биолог. Какой предмет, и в каком городе преподает каждый товарищ? Задача 3. Маша, Женя, Лида и Катя умеют играть на различных инструментах (виолончели, рояле, гитаре и скрипке). Они же владеют различными иностранными языками (английским, французским, немецким, испанским), но каждая только одним. Известно, что девушка, которая играет на гитаре, говорит по- испански, Лида не играет ни на скрипке, ни на виолончели и не знает английского языка, так же как и Маша. Девушка, которая говорит по-немецки, не умеет играть на виолончели, Женя знает французский язык, но не умеет играть на скрипке. Кто же из девушек какой язык знает и на каком инструменте играет? Задача 4. «Город мастеров». В нашем городе живут 5 друзей: Иванов, Петров, Сидорчук, Веселов и Гришин. У них разные профессии: маляр, мельник, парикмахер, почтальон, плотник. Но я точно знаю, что Петров и Гришин никогда не держали в руках малярной кисти, а Иванов и Гришин давно собираются посетить мельницу, где работает их товарищ. Петров и Веселов живут в одном доме с почтальоном. Иванов и Петров каждое воскресенье играют в городки с плотником и маляром, а Гришин и Веселов по субботам встречаются в парикмахерской, где работает их друг. Почтальон же предпочитает бриться дома. Помогите мне установить профессию каждого из друзей.
Задача 5. «Леночка и разноцветные игрушки».
- Ой, какие красивые разноцветные шарики! А какие коробочки! Дедушка, ну, пожалуйста, подари их мне! – воскликнула Леночка, едва переступив порог дедушкиной комнаты.
- Посмотрим, заслуживаешь ли ты такого подарка, - ответил дедушка, и попросил Леночку на некоторое время выйти из комнаты. Но не прошло и минуты, как как девочка услышала, что её уже зовут.
- Перед тобой пять коробочек: одна белая, одна чёрная, одна красная, одна синяя и одна зеленая, - сказал дедушка. – Шарики тех же цветов, что и коробочки, по два шарика каждого цвета: два белых, два чёрных, два красных, два синих и два зелёных. В каждую коробочку я положил по два шарика. Чтобы ты не думала, будто цвет шариков в коробочке совпадает с цветом самой коробочки, скажу сразу: шарики по коробочкам я разложил как пришлось. Если ты скажешь, какого цвета шарики лежат в каждой коробочке, то я подарю тебе все шарики вместе с коробочками.
- Но ведь это очень трудно, - печально вздохнула Леночка.
- Совсем не трудно, - утешил её дедушка. – К тому же я помогу тебе – вот послушай:
1) ни один шарик не лежит в коробочке того же цвета, что и он сам;
2) ы красной коробочке нет синих шариков;
3) в коробочке нейтрального цвета лежат один красный и один зелёный шарик. (Тут Леночка, не выдержав, спросила, что такое нейтральный цвет. Дедушка объяснил, что так принято называть белый или чёрный цвет);
4) в чёрной коробочке лежат шарики холодных тонов (Леночка уже знала, что холодными называют зеленые и синие тона);
5) в одной коробочке лежат белый и один синий шарик;
6) в синей коробочке находится один черный шарик. Помогите Леночке решить дедушкину задачу!
Знаний, полученных при решении предыдущих задач достаточно, чтобы решить эту задачу. Новое здесь, то, что каждой коробочке соответствует два шарика. А метод решения учащиеся могут предложить сами.
Задача 6. «Трамвай в часы «пик».
Один психолог решил заняться изучением того, как влияет на нервную систему человека поездка в переполненном трамвае, в часы «пик». Для этого опросил по одному пассажиру с каждого из четырех маршрутов трамвая; 55, 15, 25 и 33. среди опрошенных, которых звали Андрей (А), Петр (П), Владимир (В), Леонид (Л), оказалось по одному представителю четырех профессий :слесарь(с), электромонтер (э), маляр (м), фрезеровщик (ф). К сожалению, поездки в набитых трамваях основательно истрепали нервы самому психологу. Не удивительно, что он забыл, у кого из опрошенных какая профессия. Впрочем, такая забывчивость сама по себе достаточно красноречиво говорит о том, как влияет на нервную систему человека поездка в переполненном трамвае! В памяти нашего психолога сохранились лишь бессвязные отрывки из того, что рассказывал каждый из опрошенных о своем маршруте. Разумеется, полагаться на память было нельзя, и психолог решил проверить все самым тщательным образом. Ну и, конечно, нужно было выяснить, у кого какая профессия. Вот что удалось выяснить;
Задача 7. Решите представленную на рисунке 16 задачу.
Задача 8. «Преступление в гостинице». Когда в 11 часов утра служащие гостиницы в Пиэри Поуч открыли, наконец, дверь четвертого номера, расположенного на первом этаже (до этого они долго, но безуспешно пытались достучаться, но им никто не открывал), глазам их предстало ужасное зрелище: знаменитая кинозвезда, обворожительная мисс Вамп лежала на паркете в глубоком обмороке, все вещи были разбросаны в беспорядке, а бесценное бриллиантовое ожерелье кинозвезды исчезло. Правда, мисс Вамп вскоре пришла в себя, но ничего вспомнить так и не смогла. Пришлось обратиться за помощью к знаменитому сыщику Сэму Силли и его ловкому помощнику Джонни Вуду. Сыщик и его помощник тотчас же принялись за работу. Вскоре им удалось выяснить следующее:
Задача 9. «Укого живет сорока». На одной из улиц дачного поселка только 5 домов. Они окрашены в разные цвета, и занимают их семьи поэта, писателя, критика, журналиста и редактора. В доме каждой семьи живет любимая птичка. Глава семьи получает на завтрак любимый им напиток, после чего отправляется а город, пользуясь любимым способом передвижения. Известно, что:
1.2 Тактические задачи
Решение тактических и теоретико-множественных задач заключается в составлении учащимися плана действий, который приводит к правильному ответу. Сложность состоит в том, что выбор нужно сделать из очень большого числа вариантов, т.е. эти возможности не известны учащимся, их нужно придумать.
Задача 10. «Иванушка и коварная принцесса».
- Задаю тебе последнюю задачу, - сказала принцесса Иванушке, - найди единственно верный путь из этой комнаты в наш зимний сад и сорви для меня самую красивую розу. Из этой комнаты ты пройдешь через левую, или правую, или среднюю дверь во вторую комнату; такие же три вида дверей будут перед тобой при переходе из второй комнаты в третью и из третей – в сад. Учти мои советы, - продолжала принцесса, - первый: из этого зала пройди через правую дверь; второй: из второй комнаты – не через правую дверь, и третий совет: из третей – не через левую дверь. Иванушка знал, что обычно из трех советов принцессы ровно в двух указывают ложное направление, кроме того, служанка принцессы успела шепнуть ему, что надо пройти через дверь каждого вида по одному разу. Как и полагается сказке, принес Иванушка розу и был вознагражден. Какой же маршрут оказался верным?
Задача 11. Все звери в зоопарке находятся не в своих клетках. Служителю необходимо как можно быстрее разместить животных по их клеткам. Какое наименьшее число «переселений» должен сделать служитель зоопарка? Учтите, что зверей нельзя помещать вдвоем в одну клетку, так как звери – хишники (рис. 28).
Надпись на клетке Лев Олень Волк Крокодил Леопард
Животное Леопард Крокодил Олень Лев Волк
Вольера
Задача 12. Три рыцаря, каждый в сопровождении оруженосца, съехались на берегу реки и хотят переправиться на другой берег. Есть лодка, которая может вместить только двух человек. Могут ли переправиться рыцари и их оруженосцы на другой берег при условии, что, оказавшись отдельно от своего рыцаря, ни один оруженосец, не находился бы при этом в обществе других рыцарей?
Задача 13. По обычаю одной восточной страны, жене запрещается оставаться без мужа в обществе мужчин, однажды трем супружеским парам понадобилось перебраться на южный берег реки с северного. Единственное подручное средство – лодка, вмещающая двух человек. В какой последовательности они должны были переправиться, чтобы соблюсти строгий обычай?
Задача 14. Три сосуда, вместимостью 8, 5, 3 л. стоят на полке. Первый сосуд наполнен водой, а два других пусты. Как с помощью этих сосудов отмерить один литр воды? Как отмерить 4 л. воды?
Задача 15. Али-Баба хочет попасть в пещеру с сокровищами. Перед пещерой стоит бочка, в крышке которой имеются четыре отверстия, образующие квадрат. Под отверстиями находится по кувшину, в каждом из которых торчит селедка, хвостом вверх или вниз. Али-Баба может просунуть руки в любые два отверстия и определить расположение находящихся под ними селедок, а также повернуть одну или две по своему усмотрению. Если хвосты всех селедок окажутся направленными в одну сторону, то дверь пещеры открывается. После того, как Али-Баба вытащит руки из отверстий, бочка быстро поворачивается и останавливается, причем Али-Баба не в состоянии определить новое соотношение бочки по отношению к старому. Существует ли способ действий, позволяющий Али-Бабе за несколько попыток наверняка открыть дверь? 1.3 Задачи на нахождение пересечения или объединение множеств (круги Эйлера)
Ещё один тип задач – задачи, в которых требуется найти некоторое пересечение множеств или их объединение, соблюдая условия задачи.
Задача 16. В шахматном турнире участвовало 7 человек . каждый с каждым сыграл по одной партии. Сколько партий они сыграли?
Задача 17. Каждые два из двадцати городов соединены линией воздушного беспересадочного сообщения. Сколько всего воздушных сообщений?
Задача 18. В учительской комнате в одну из перемен завязался разговор о журналах. В ходе его выяснилось, что каждый из учителей выписывает два журнала. На каждый из выписываемых журналов подписывается трое. Любая комбинация из двух таких журналов выписывается одним учителем сколько было учителей? Сколько было журналов выписано? Сколько номеров журналов они получили за год, если все журналы были ежемесячными?
Задача 19. В школе зимой работали 3 секции (лыжная, хоккейная, конькобежная). Всего в секциях занималось 38 учеников. В лыжной - 21 человек, среди которых трое еще занимались коньками, шестеро - еще в хоккейной секции, а один - сразу в трех секциях. В конькобежной секции было 13 человек, среди которых пятеро занимались сразу в двух секциях. Сколько человек занималось в хоккейной секции? Задача 20. Одна швейцарская община насчитывает 50 членов. Родной язык всех 50 членов общины – немецкий, но 20 из них говорят еще по-итальянски, 35 из них владеют французским и еще 10 не знают ни итальянского, ни французского. Сколько членов общины говорят и по-французски, и по-итальянски? 1.4 Буквенные ребусы и задачи со звездочками
Методом подбора и рассмотрения различных вариантов решаются буквенные ребусы и примеры со звездочками.
Такие задачи различны по сложности и схеме решения. Рассмотрим один такой пример.
Задача 22. Перед началом бегов на ипподроме четыре знатока из числа зрителей обсуждали шансы фаворитов А, В или С.
Первый: Заезд выиграет А или С.
Второй: Если А придет третьим, то С не выиграет.
Третий: Если А будет вторым, то выиграет В.
Четвертый: Вторым придет А или В.
После заезда выяснилось, что три фаворита А, В, С действительно заняли первые три места и что все четыре утверждения знатоков оказались истинными. Как фавориты поделили между собой три первых места?
1.5 Истинностные задачи
Задачи, в которых требуется установить истинность или ложность высказываний назовем истинностными задачами.
Задача 23. В одном старинном задачнике суд Париса описан следующим образом: богини Гера, Афродита и Афина пришли к юному Парису, чтобы тот решил, кто из них прекраснее. Представ перед Парисом, богинивысказали следующие утверждения:
1. Афродита: Я самая прекрасная.
2. Афина: Афродита не самая прекрасная.
3. Гера: Я самая прекрасная.
4. Афродита: Гера не самая прекрасная.
5. Афина: Я самая прекрасная.
Парис, прилегший отдохнуть на обочине дороги, не счел нужным даже снять платок, которым прикрыл глаза от яркого солнца. Но богини были настойчивы, и ему во что бы то ни стало, нужно было решить, кто из них самая прекрасная. Парис предположил, что все утверждения прекраснейшей из богинь истинны, а все остальные утверждения двух остальных богинь ложны. Мог ли Парис,исходя из такого предположения, выпести то решение, которое ожидали от него богини, и если мог, то кто из богинь самая прекрасная?
Задача 24. До царя Гороха дошла молва, что наконец-то убили Змея Горыныча. Царь знал, что это мог сделать Илья Муромец, Алеша Попович или Добрыня Никитич. Вызвал царь к себе богатырей. И вот они, запыленные, явились ко двору. Стал спрашивать их царь. Трижды каждый богатырь ответ держал.
Добрыня Никитич:
- Я не убивал Змея.
- Я выезжал в заморские страны.
- Змея убил Алеша Попович.
Илья Муромец:
- Змея убил Алеша Попович.
- Если бы я убил его, то не сказал бы.
- Много еще на земле нечистой силы осталось.
Алеша Попович:
- Не убивал я Змея Горыныча.
- Я не ищу, какой бы подвиг совершить.
- И взаправду Добрыня Никитич в заморские страны уезжал.
Царь узнал также, что дважды говорил правду каждый богатырь, а один раз луковал. Кто же убил Змея Горыныча?
1.6 Задачи типа «Шляпы»
Наиболее известна задача про мудрецов, которым нужно определить цвет шляпы на своей голове. Чтобы решить такую задачу, нужно восстановить цепочку логических рассуждений.
Задача 25. «Какого цвета береты?». Три подруги, Аня, Шура и Соня, сидели в амфитеатре одна за другой без биретов. Соне и Шуре нельзя оглядываться назад. Шура видит только голову сидящей ниже ее Сони, а Аня видит головы обеих подруг. Из коробки, в которой находятся 2 белых и 3 черных берета (об этом все три подруги знают), вынули три и надели их на головы, не говоря о том, какого цвета берет; два берета остались в коробке. Когда спросили Аню о цвете берета, который ей надели, она не сумела ответить. Шура слышала ответ Ани и сказала, что она также не может определить цвет своего берета. Может ли Соня на основании ответов своих подруг определить цвет своего берета?
Задача 26. «Бумажные рыбки». Три учительницы увлеченно беседовали, сидя на скамейке во время перемены. Они даже не заметили, как расшалившиеся дети прикрепили им на спины бумажных рыбок. Поднявшись со скамьи, все три начали смеяться. Каждая из них думала, что ее коллеги смеются друг над другом, а сама она не стала жертвой шалунов. Внезапно одна из учительниц перестала смеяться: она поняла, что у нее самой – рыбка на спине. Как она пришла к этому выводу? 1.7 Задачи типа «Два города»
в задачах типа «Два города» рассуждения еще усложняются. Эти задачи требуют постановки вопроса учащимися, т.е. анализа исходных данных и информации, которую необходимо получить. Рассмотрим пример.
Задача 27. «Марсиане». Наблюдения показали, что планета Марс почти пустынна, за исключением двух больших городов: Марс-Полиса и Марс-Сити. Жители Марс-Полиса никогда не лгут, а жители Марс-Сити не говорят правду. Марсиане свободно перемещаются из одного города в другой, поэтому некоторые жители Марс-Полиса могут находится в Марс-Сити, и наоборот. Однажды два американских аэронавта оказались в одном из этих городов. Увы, они не знали, в каком именно. Когда один марсианин приблизился к ракете, первый аэронавт спросил у него (на языке, который должен был понимать марсианин), находятся ли они в Марс-Сити.
- Нет, - ответил марсианин, который, может быть, и солгал (мы забыли сказать, что неразговорчивые марсиане на все вопросы отвечали только «да» или «нет»). Тогда второй аэронавт задал марсианину очень хитрый вопрос, который позволил аэронавтам определить, в каком городе они оказались. Что это был за вопрос?
Задача 28. «Рыцари, плуты и нормальные люди». На одном острове, где живут рыцари, плуты и нормальные люди, рыцари всегда говорят только правду, плуты всегда лгут, а люди, которых принято называть нормальными, в одних случаях лгут, а в других высказывают правду. Однажды я посетил этот остров и встретил двух его обитателей. А и В. еще раньше мне было известно, что один из них рыцарь, а другой – нормальный человек, однако я не знал, кто же именно. Я спросил А, является ли В нормальным человеком, на что А ответил мне вполне определенно. Тут я сразу понял, кем являются аА и В. Итак, кто же из этих обитателей острова нормальный человек?
