Олимпиадные задания по информатике

4. Решение логических задач

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

Решение логических задач дает возможность развивать внимание, память и прививать навыки правильного мышления.

Логические задачи очень разнообразны. Способов их решения тоже немало. Но наибольшее распространение получили следующие способы решения логических задач:

1. табличный;
2. средствами алгебры логики;
3. с помощью рассуждений.

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

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

Задача 1 «На конгрессе»

На конгрессе встретились четверо ученых: физик, биолог, историк и математик. Каждый ученый владел двумя языками из четырех (русским, английским, французским и итальянским), но не  было такого языка, на котором могли бы разговаривать все четверо. Есть только один язык, на котором могли вести беседу сразу трое. Никто из ученых не владеет и французским, и русским языками. Хотя физик не говорит по-английски, он может служить переводчиком, если истории и биолог захотят побеседовать. Историк говорит по-русски и может говорить с математиком, хотя тот не знает ни одного русского слова. Физик, биолог и математик не могут разговаривать на одном языке.

Каким двумя языками владеет каждый ученый?

Решение.

Эту задачу удобно решать, заполнив следующую таблицу:

Будем анализировать условия задачи и ставить «-» / «+» в соответствующих ячейках.

1. Известно, что математик не знает русского, физик – английского, историк – французского (он говорит по-русски, но никто не говорит и на русском, и на французском).
2. Физик служит переводчиком в беседах историка и биолога (он владеет такими двумя языками, про которые известно, что историк владеет только одним из них, а биолог – только другим). Так как историк и биолог не владеют общим языком, то, следовательно, биолог не знает русского языка. Значит, русский – общий язык для физика и историка; физик не владеет французским (он говорит по-русски, но никто не говорит ни на русском, ни на французском). Второй язык физика – итальянский; итальянским владеет и биолог, историк итальянским не владеет. Тогда второй язык историк – английский, а биолог английским не владеет. Значит второй язык биолога – французский.
3. Историк может беседовать с математиком, хотя тот не знает русского. Следовательно, математик владеет английским.
4. Так как только трое ученых знаю один и тот же язык, то этот язык – итальянский.

Ответ:

Математик владеет английским и итальянским;

Биолог – французским и итальянским;

Физик – русским и итальянским;

Историк – русским и английским.

Задача 2.

В городах Нальчик, Москва, Серпухов, Тольятти живут четыре супружеские пары, причем в каждом городе живет только одна супружеская пара. Имена этих супругов: Антон, Борис, Григорий, Ольга, Светлана, Мария, Екатерина. Антон живет в Нальчике, Борис и Ольга – супруги, Григорий и Светлана не живут в одном городе, Мария живет в Москве, Светлана – жительница Серпухова. Определить, кто на ком женат и кто где живет.

Решение.

Составит, исходя из условия задачи, таблицу возможностей, отмечая знаком «+» возможные, а знаком «-» невозможные ситуации:

Из этой таблицы видно, что Ольга может жить либо в Нальчике, либо в Тольятти. Но в Нальчике живет Антон, а она является женой Бориса. Значит, Борис и Ольга - супруги и живут в Тольятти.

Таблица приобретает вид:

Анализируя таблицу, получаем:

Екатерина живет в Нальчике и ее муж – Антон,

Григорий живет в Москве и его жена – Мария,

Давид и Светлана – супруги и живут в Серпухове.

Задача 3.

На одном званном вечере среди гостей оказалось пять офицеров: пехотинец, артиллерист, летчик, связист и сапер. Один из них капитан, трое – майоры и один - полковник. Дамы окружили офицеров таким внимание, что все остальные гости оказались просто забытыми. Из разговоров удалось выяснить следующее:

1. У Петра такое же звание, как и его друга сапера.
2. Офицер-связист и Николай – большие друзья.
3. Офицер-летчик вместе с Владимиром и Александром недавно были в гостях у Николая.
4. Незадолго до званного вечера у артиллериста и сапера почти одновременно вышли из строя радиоприемники. Оба обратились к Александру с просьбой зайти к ним и помочь связисту устранить неисправность, и с тех пор приемники у обоих работаю отлично.
5. Николай чуть было не стал летчиком, но потом по совету своего друга сапера избрал иной род войск.
6. Петр по званию старше Александра, а Владимир старше Николая.
7. Андрей накануне званного вечера был в гостях у Александра.

Определите звание каждого офицера и род войск, в котором он служит.

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

Решение.

Если рассмотреть условия 1-7 задачи не попорядку, а 1 и сразу 6, тогда можно сразу ответить на вопрос о звании каждого офицера. Строим таблицу:

Заметим, что условия 4, 5 содержат лишнюю информацию.

Мы видим, что задача «перегружена»: ее текст содержит больше информации, чем необходимо. Такую перегруженность в информатике принято называть избыточностью, а все «лишние» условия – избыточными.

Ответ.

Петр – майор и летчик, Николай – майор и артиллерист, Александр – капитан и пехотинец, Владимир - полковник и связист, Андрей – майор и сапер.

Способ решения средствами алгебры логики

Обычно используется следующая схема решения:

• изучить условие задачи;
• выделить простые высказывания и обозначить их буквами;
• записать условие задачи на языке алгебры логики.
• составить конечную формулу, для этого объединить логическим умножением формулы каждого утверждения, приравнять произведение к единице.
• упростить формулу.
• проанализировать полученный результат или составить таблицу истинности, найти по таблице значения переменных, для которых значение функции равно 1.
• из полученных значений истинности формулы определяются значения истинности введённых логических высказываний, на основании которых делается заключение о решении.

Задача 4.

Трое друзей, болельщиков автогонок "Формула-1", спорили о результатах предстоящего этапа гонок.

– Вот увидишь, Шумахер не придет первым, – сказал Джон. Первым будет Хилл.

– Да нет же, победителем будет, как всегда, Шумахер, – воскликнул Ник. – А об Алези и говорить нечего, ему не быть первым.

Питер, к которому обратился Ник, возмутился:

– Хиллу не видать первого места, а вот Алези пилотирует самую мощную машину.

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

Решение.

 Введем обозначения для логических высказываний: S– победит Шумахер; X – победит Хилл; А – победит Алези.

Реплика Ника "Алези пилотирует самую мощную машину" не содержит никакого утверждения о месте, которое займёт этот гонщик, поэтому в дальнейших рассуждениях не учитывается.

Зафиксируем высказывание каждого из друзей:

Джон:

Ник:

Питер:

Учитывая то, что предположения двух друзей подтвердились, а предположения третьего неверны, запишем и упростим истинное высказывание

Высказывание истинно только при S=1, A=0, X=0

Ответ.

 Победителем этапа гонок стал Шумахер

Задача 5.

Андрей, Аня и Маша решили пойти в кино. Каждый из них высказал свои пожелания по поводу выбора фильма.

Андрей сказал: “Я хочу посмотреть французский боевик”.

Маша сказала: “Я не хочу смотреть французскую комедию”.

Аня сказала: “Я хочу посмотреть американскую мелодраму”.

Каждый из них слукавил в одном из двух пожеланий. На какой фильм пошли ребята?

Решение:

1. Выделим простые высказывания и запишем их через переменные:

А - “Французский фильм”

В - “Боевик”

С - “Комедия”

2. Запишем логические функции (сложные высказывания). Учтем условие о том, что каждый из ребят оказался прав в одном предположении:

а) “Французский боевик” -

б) “Американскую мелодраму” -

в) “Не французская комедия” -

3. 3апишем произведение указанных функций:

4. Упростим формулу:

5. Приравняет результат к единице:

Составим таблицу истинности:

Найдем по таблице значения переменных, для которых выражение = 1

А)

Б)

8. Проанализируем результат: результат Б) не является решением, т.к. в ответе Маши оба утверждения оказываются неверными, что противоречит условию задачи. Результат А) полностью удовлетворяет условию задачи и поэтому является верным решением.

Ответ.

Ребята выбрали американский боевик

Задача 6 «Четыре свидетеля»

В деле об убийстве имеются два подозреваемых: Х и У

Допросили четырех свидетелей.

Показания первого свидетеля: «Х не виноват».

Показания второго свидетеля: «У не виноват».

Показания третьего свидетеля: «Из двух показаний, по крайне мере одно истинное».

Показания четвертого свидетеля: «Показания третьего свидетеля ложные».

Четвертый свидетель оказался прав. Кто же совершил убийство?

Решение.

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

Задача 7.

Пусть имеются только 2 пустых ведра емкостью 3 и 7 литров и большой запас воды. Нужно налить в большее ведро 5 л воды  за наименьшее число операций. Операциями считаются наполнение одного ведра, выливание воды из одного ведра, переливание из одного ведра в другое. Решение задачи определяется последовательностью операций:

1. наполнить 7-литровое ведро полностью;
2. перелить воду из большего ведра в меньшее – в большем будет 4 л воды;
3. опорожнить меньшее ведро;
4. перелить воду из большего ведра в меньшее – в большем останется 1 л воды;
5. опорожнить меньшее ведро;
6. перелить воду из большего ведра в меньшее – в меньшем останется 1 л воды;
7. наполнить водой большее ведро полностью;
8. долить меньшее ведро из большего – в большем останется 5 л воды, что и требовалось.

Тема:  Решение логических задач методом рассуждений.

    Построение и преобразование логических выражений.

Пример задания:

Классный руководитель пожаловался директору, что у него в классе появилась компания из 3-х учеников, один из которых всегда говорит правду, другой всегда лжет, а третий говорит через раз то ложь, то правду. Директор знает, что их зовут Коля, Саша и Миша, но не знает, кто из них правдив, а кто – нет. Однажды все трое прогуляли урок астрономии. Директор знает, что никогда раньше никто из них не прогуливал астрономию. Он вызвал всех троих в кабинет и поговорил с мальчиками. Коля сказал: «Я всегда прогуливаю астрономию. Не верьте тому, что скажет Саша». Саша сказал: «Это был мой первый прогул этого предмета». Миша сказал: «Все, что говорит Коля, – правда». Директор понял, кто из них кто. Расположите первые буквы имен мальчиков в порядке: «говорит всегда правду», «всегда лжет», «говорит правду через раз». (Пример: если бы имена мальчиков были Рома, Толя и Вася, ответ мог бы быть: РТВ)

Решение (вариант 1, метод рассуждений):

1. во-первых, есть «точная» информация, которая не подвергается сомнению:

(*) все трое прогуляли урок астрономии в первый раз

2. запишем высказывания мальчиков:

Коля:          1. Я всегда прогуливаю астрономию.

        2. Саша врет.

Саша:          1. Я в первый раз прогулял астрономию.

Миша:         1. Коля говорит правду.

3. известно, что один из них все время лжет, второй – говорит правду, а третий говорит правду через раз (то есть, из двух его высказываний одно истинно, а второе – ложно; если у нас есть только одно высказывание «полу-лжеца», оно может быть как истинным, так и ложным)
4. сопоставив первое высказывание Коли и высказывание Саши с «точной» информацией (*), сразу определяем, то тут Коля соврал, а Саша сказал правду; это значит, что второе высказывание Коли – тоже неверно, поэтому мальчик Коля всегда лжет
5. тогда один из оставшихся, Саша или Миша, говорит правду всегда, а второй – через раз
6. Мишино высказывание неверно, поскольку мы уже определили, что Коля лжет; это значит, что Миша не всегда говорит правду, он – «полу-лжец»
7. тогда получается, что Саша всегда правдив, и действительно, его высказывание верно
8. таким образом, верный ответ – СКМ  (Саша – правдив, Коля – лжец, Миша – «полу-лжец» ).

Еще пример задания:

Классный руководитель пожаловался директору, что у него в классе появилась компания из 3-х учеников, один из которых всегда говорит правду, другой всегда лжет, а третий говорит через раз то ложь, то правду. Директор знает, что их зовут Коля, Саша и Миша, но не знает, кто из них правдив, а кто – нет. Встретив однажды всех троих в коридоре, директор решил поговорить с мальчиками. Коля сказал: «Саша всегда лжет». Саша сказал: «Коля прав». Директору стало все понятно. Расположите первые буквы имен мальчиков в порядке: «говорит всегда правду», «всегда лжет», «говорит правду через раз». Например: если бы имена мальчиков были Рома, Толя и Вася, ответ мог бы быть: РТВ.

Решение (вариант 1, метод рассуждений):

1. в отличие от предыдущей задачи, здесь нет точной информации
2. у нас всего два высказывания мальчиков:

Коля:          Саша всегда лжет

Саша:          Коля прав

3. в отличие от предыдущей задачи, второе высказывание связано с первым: Сашино утверждение относится к данному конкретному высказыванию Коли, а не к честности Коли вообще
4. в такой ситуации нужно предположить, что истинно одно из высказываний и проверить, не приводит ли это к противоречию
5. предположим, что Коля сказал правду; тогда получается, что Саша (который всегда лжет) солгал и на этот раз; однако если Саша солгал, то получается, что Коля сказал неправду, то есть, мы пришли к противоречию, и Коля в самом деле солгал
6. если Коля солгал, то получается, что Саша тоже солгал, то есть, оба мальчика сказали неправду; отсюда следует, что один из них – лжец, а второй «полу-лжец», тогда как Миша (ничего не сказавший) говорит всегда правду
7. остается определить, кто из двоих (Коля или Саша) лжец, а кто – «полу-лжец»
8. с первого взгляда кажется, что это невозможно сделать, но ложные утверждения двух мальчиков разные: Коля говорит (неправду) о том, что Саша всегда лжет, а Саша говорит только о последнем (предыдущем) утверждении Коли; на этой разнице и основано решение
9. мы уже выяснили, что Коля солгал, то есть Саша не всегда лжет, он – «полу-лжец»; тогда сразу получается, что Коля – лжец
10. таким образом, верный ответ – МКС  (Миша – правдив, Коля – лжец, Саша – «полу-лжец»).

Еще пример задания: В-4 Демоверсия-2006

Перед началом Турнира Четырех болельщики высказали следующие предположения по поводу своих кумиров:

        А) Макс победит, Билл – второй;

        В) Билл – третий, Ник – первый;

        С) Макс – последний, а первый – Джон.

Когда соревнования закончились, оказалось, что каждый из болельщиков был прав только в одном из своих прогнозов. Какое место на турнире заняли Джон, Ник, Билл, Макс? (В ответе перечислите подряд без пробелов места участников в указанном порядке имен.)

Решение (вариант 1, табличный метод):

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

2. считая, что два человека не могут оказаться на одном месте, начнем «раскручивать» эту таблицу с той строчки, где больше всего информации (в данном случае – с первой)
3. предположим, что Макс действительно занял первое место, как и сказал «A»; в этом случае

• «C» ошибся, поставив на первое место Джона;
• учитывая, что каждый один раз угадал, а второй ошибся, получается, что «C» угадал, что Макс будет на четвертом месте;
• но мы предположили, что Макс – на первом месте (а не на четвертом), следовательно, получили противоречие; это значит, что Макс все-таки не на первом месте
• таким образом, в первом прогнозе «А» ошибся, это значит, что во втором он угадал, и Билл действительно занял второе место:

• так как Билл – второй, он не может быть на третьем месте, поэтому из прогноза «Б» следует, что Ник – первый:

• если Ник на первом месте, там не может быть Джон, поэтому из ответов «С» (среди которых должен быть один верный, и один неверный), сразу находим, что Макс занял четвертое место:

4. осталось только определиться с Джоном – ему досталось единственное «свободное» третье место; окончательный список победителей:

1. Ник   2. Билл   3. Джон   4. Макс

5. места победителей в порядке их перечисления в тексте вопроса: Джон – 3 , Ник – 1,
   Билл – 2, Макс - 4
6. таким образом, правильный ответ 3124.

Решение (вариант 2, преобразование логических выражений):

1. применим к этой задаче формальный аппарат математической логики
2. каждый из трех болельщиков высказал два утверждения, всего получилось 6; обозначим их так:

A:   М1 = «Макс – первый»,        Б2 = «Билл – второй»

B:   Н1 = «Ник – первый»,        Б3 = «Билл – третий»

C:   Д1 = «Джон – первый»,        М4 = «Макс – четвертый»

3. теперь как-то нужно записать, что у каждого одно высказывание верно, а второе неверно; скажем, для «A» это равносильно двум следующим условиям, которые должны выполняться одновременно:

A:           М1 + Б2 = 1,        (по крайней мере одно из двух условий истинно)

        М1 · Б2 = 0        (по крайней мере одно из двух условий ложно)

аналогично для остальных болельщиков^[1]

B:           Н1 + Б3 = 1,        Н1 · Б3 = 0

С:           Д1 + М4 = 1,        Д1 · М4 = 0

4. перемножим первые условия из каждой пары; поскольку все эти суммы равны 1, получаем

(М1 + Б2) · (Н1 + Б3) · (Д1 + М4) = 1

5. раскроем произведение первых двух скобок

(М1 · Н1 + М1 · Б3 + Б2 · Н1 + Б2 · Б3) · (Д1 + М4) = 1

6. попробуем упростить «большую» скобку»; во-первых, два человека (Макс и Ник) не могут одновременно находиться на первом месте, поэтому М1 · Н1 = 0
7. во-вторых, один человек (Билл) не может одновременно находиться и на втором, и на третьем месте, поэтому Б2 · Б3 = 0, так что

(М1 · Б3 + Б2 · Н1) · (Д1 + М4) = 1

8. снова перемножим скобки и получим

М1 · Б3 · Д1 +  М1 · Б3 · М4 + Б2 · Н1 · Д1 + Б2 · Н1 · М4 = 1

9. так же, как и в п. 6-7, находим, что М1 · Д1 = 0, М1 · М4 = 0 и Н1 · Д1 = 0, так что

        Б2 · Н1 · М4 = 1         (*)

10. из последнего уравнения следует, что Б2 = 1 (Билл на втором месте), Н1 = 1 (Ник – на первом) и М4 = 1 (Макс – на четвертом), а Джону осталось третье
11. таким образом, правильный ответ 3124
12. обратите внимание, что вторые условия (М1 · Б2 = 0, Н1 · Б3 = 0 и Д1 · М4 = 0 ) мы даже нигде не использовали, все получилось «само собой», поскольку уравнение (*) имеет единственное решение.

Еще пример задания: Демо-2005 В-4

Мама, прибежавшая на звон разбившейся вазы, застала всех трех своих сыновей в совершенно невинных позах: Саша, Ваня и Коля делали вид, что происшедшее к ним не относится. Однако футбольный мяч среди осколков явно говорил об обратном.

– Кто это сделал? –  спросила мама.

–  Коля не бил по мячу,  – сказал Саша. –  Это сделал Ваня.

Ваня ответил:   – Разбил Коля, Саша не играл в футбол дома.

– Так я и знала, что вы друг на дружку сваливать будете,   рассердилась мама.   Ну, а ты что скажешь? – спросила она Колю.

– Не сердись, мамочка! Я знаю, что Ваня не мог этого сделать. А я сегодня еще не сделал уроки, –  сказал Коля.

Оказалось, что один из мальчиков оба раза солгал, а двое в каждом из своих заявлений говорили правду. Кто разбил вазу?

Решение (вариант 1, метод рассуждений):

1. запишем высказывания трех мальчиков в краткой форме:

         Саша: 1. это не Коля                2. это Ваня

        Ваня: 1. это Коля                2. это не Саша

        Коля: 1. это не Ваня                

обратите внимание, что у Коли всего одно высказывание, которое «относится к делу»; то, что он сделал или не сделал уроки, никак не проясняет ситуацию с разбитой вазой

2. итак, двое мальчиков сказали правду;

• это не могут быть Саша и Ваня, потому что их первые высказывания противоречат одно другому
• это не могут быть Саша и Коля, поскольку высказывание Коли противоречит второму высказыванию Саши
• поэтому правду сказали Ваня и Коля, а Саша – соврал

3. таким образом, вазу разбил Коля

Решение (вариант 2, преобразование логических выражений):

1. применим к этой задаче формальный аппарат математической логики; введем высказывания:

С: вазу разбил Саша

В: вазу разбил Ваня

К: вазу разбил Коля

2. запишем с помощью этих обозначений утверждения мальчиков:

        Саша: 1.         2.

        Ваня: 1.         2.

        Коля: 1.

3. читаем условие: «один из мальчиков оба раза солгал, а двое в каждом из своих заявлений говорили правду»;
4. как записать «Саша два раза солгал»? в этом случае оба его утверждения неверны,  поэтому  и , что равносильно  
5. как записать «Саша два раза сказал правду»? в этом случае оба его утверждения верны,  поэтому  и , что равносильно
6. если Коля солгал, а Саша и Ваня сказали правду, то

 и  и

заменив «И» на умножение, получаем ; учитывая, что , получаем в левой части равенства ноль; так как в правой части – единица, этого не может быть (равенство ложно при любых значениях )

7. если Ваня солгал, а Саша и Коля сказали правду, то

 и  и

заменив «И» на умножение, получаем ; учитывая, что , получаем, что это равенство ложно при любых значениях  (этого не может быть)

8. остается последний возможный вариант: если Саша оба раза солгал, а Ваня и Коля сказали правду, то

 и  и

заменив «И» на умножение, получаем ; упростив это выражение с учетом равенств   и , получим ; то есть, при этом предположении вазу разбил Коля, а не Ваня и не Саша;

9. таким образом, вазу разбил Коля
10. при несколько измененном условии нам, возможно, пришлось бы использовать дополнительные условия  (вазу разбил только один из мальчиков, а не два и не три), но здесь они не пригодились

Еще пример задания:

На одной улице стоят в ряд 4 дома, в каждом из них живет по одному человеку. Их зовут Василий, Семен, Геннадий и Иван.  Известно, что все они имеют разные профессии: скрипач, столяр, охотник и врач. Известно, что

  (1) Столяр живет правее охотника.

  (2) Врач живет левее охотника.

  (3) Скрипач живет с краю.

  (4) Скрипач живет рядом с врачом.

  (5) Семен не скрипач и не живет рядом со скрипачом.

  (6) Иван живет рядом с охотником.

  (7) Василий живет правее врача.

  (8) Василий живет через дом от Ивана.

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

Эта задача представляет собой упрощенный вариант Задачи Эйнштейна.

Решение ( метод рассуждений с таблицами):

1. пронумеруем дома слева направо (от 1 до 4);
2. находим наиболее точное условие: это условие (3) «Скрипач живет с краю»; таким образом, скрипач может жить в доме 1 или в доме 4

3. по условию (4) скрипач живет рядом с врачом, но врач живет левее охотника (условие (2)), поэтому скрипач не может жить в доме (4), так как тогда получается врач, живущий с ним рядом, живет правее охотника, что противоречит условию (2); таким образом, скрипач живет в доме 1, а врач – рядом с ним

4. из условий (1) и (2) следует, что в домах 3 и 4 живут соответственно охотник и столяр

5. профессии жильцов определили, остается разобраться с именами
6. из условия (5) «Семен не скрипач и не живет рядом со скрипачом» следует, что Семен – охотник или столяр:

7. из условия (6) «Иван живет рядом с охотником» следует, что он – врач или столяр:

8. из условия (7) «Василий живет правее врача» определяем, что Василий – охотник или столяр

9. из условия (8) «Василий живет через дом от Ивана» находим, что Иван – врач, а Василий –столяр:

10. тогда сразу получается, что Семен – охотник, а Геннадий должен занять оставшееся свободное место, он – скрипач:

11. таким образом, ответ ГИСВ

Задачи для тренировки:

1. Когда сломался компьютер, его хозяин сказал «Память не могла выйти из строя». Его сын предположил, что сгорел процессор, а винчестер исправен. Пришедший специалист по обслуживанию сказал, что, скорее всего, с процессором все в порядке, а память неисправна. В результате оказалось, что двое из них сказали все верно, а третий – все неверно. Что же сломалось?

2. Три молодые мамы Анна, Ирина и Ольга, гуляя в парке со своими малышами, встретили свою четвертую подругу. На вопрос, как зовут малышей, желая подшутить над подружкой, они ответили:

Анна:        моего малыша зовут Денис, а Кирилл – сын Ирины.

Ирина:        моего сыночка зовут Максим, а Кирилл – сын Анны.

Ольга:        мой мальчик – Кирилл, а сына Анны зовут Максим.

Каждая из них один раз сказала правду и один раз солгала. Как зовут мальчиков Анны, Ирины и Ольги? В ответе перечислите подряд без пробелов буквы, соответствующие именам мальчиков

в указанном порядке имен их мам, например КМД.

Задание 6. (Задание В4 демоверсии 2007 г)

В школьном первенстве по настольному теннису в четверку лучших вошли девушки: Наташа, Маша, Люда и Рита. Самые горячие болельщики высказали свои предположения о распределении мест в дальнейших состязаниях.

Один считает, что первой будет Наташа, а Маша будет второй.

Другой болельщик на второе место прочит Люду, а Рита, по его мнению, займет четвертое место.

Третий любитель тенниса с ними не согласился. Он считает, что Рита займет третье место, а Наташа будет второй.

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

Какое место на чемпионате заняли Наташа, Маша, Люда, Рита?

(В ответе перечислите подряд без пробелов числа, соответствующие местам девочек в указанном порядке имен.)

Решение:

Обозначим высказывания:

Н1 = “первой будет Наташа”;

М2 = “второй будет Маша”;

Л2 = “второй будет Люда”;

Р4 = “четвертой будет Рита”;

Р3 = “третьей будет Рита”;

Н2 = “второй будет Наташа”.

Согласно условию:

из высказываний 1 болельщика следует, что Н1VМ2 истинно;

из высказываний2 болельщика следует, что Л2VР4 истинно;

из высказываний 3 болельщика следует, что Р3VН2 истинно.

Следовательно, истинна и конъюнкция

(Н1VМ2) /\ (Л2VР4) /\ (Р3VН2) = 1.

Раскрыв скобки получим:

(Н1VМ2) /\ (Л2VР4) /\ (Р3VН2) = (Н1/\Л2V Н1/\Р4 V М2/\Л2 V М2/\Р4) /\ (Р3VН2)=

Н1/\ Л2/\Р3 V Н1/\Р4/\Р3 V М2/\Л2/\Р3 V М2/\Р4/\Р3 V Н1/\Л2/\Н2 V Н1/\Р4/\Н2 V М2/\Л2/\Н2 V М2/\Р4/\Н2 = Н1/\ Л2/\Р3 V 0 V 0 V 0 V 0 V 0 V 0 V= Н1/\ Л2/\Р3

Наташа-1, Люда-2, Рита-3, а Маша-4.

Ответ: 1423