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

Фефелова Алла Николаевна

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

Скачать:

ВложениеРазмер
PDF icon olimpiada_zadaniya_inf_7-8_klas.pdf207.6 КБ
PDF icon ans-iikt-9-11-msk-sch-15-6.pdf150.98 КБ
Microsoft Office document icon logicheskie_zadachi.doc250.5 КБ

Предварительный просмотр:

Чтобы пользоваться предварительным просмотром создайте себе аккаунт (учетную запись) Google и войдите в него: https://accounts.google.com

Предварительный просмотр:

Чтобы пользоваться предварительным просмотром создайте себе аккаунт (учетную запись) Google и войдите в него: https://accounts.google.com


Предварительный просмотр:

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

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

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

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

  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. Приравняет результат к единице:

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

A

B

C

0

0

0

0

0

0

1

0

0

1

0

1

0

1

1

0

1

0

0

0

1

0

1

1

1

1

0

0

1

1

1

0

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

А)

0

1

0

1

Б)

1

0

1

1

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

Ответ.

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

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

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

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

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

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

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

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

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

Решение.

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

Задача 7.

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

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

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

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

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

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

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

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

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

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

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

        2. Саша врет.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

A

B

C

1

Макс

Ник

Джон

2

Билл

3

Билл

4

Макс

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

A

B

C

1

Макс

Ник

Джон

2

Билл

3

Билл

4

Макс

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

A

B

C

1

Макс

Ник

Джон

2

Билл

3

Билл

4

Макс

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

A

B

C

1

Макс

Ник

Джон

2

Билл

3

Билл

4

Макс

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

        Саша: 1.         2.

        Ваня: 1.         2.

        Коля: 1.

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

 и  и

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

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

 и  и

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

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

 и  и

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1

2

3

4

скрипач

врач

?

?

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

1

2

3

4

скрипач

врач

охотник

столяр

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

1

2

3

4

скрипач

врач

охотник

столяр

Семен?

Семен?

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

1

2

3

4

скрипач

врач

охотник

столяр

Семен?

Семен?

Иван?

Иван?

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

1

2

3

4

скрипач

врач

охотник

столяр

Семен?

Семен?

Иван?

Иван?

Василий?

Василий?

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

1

2

3

4

скрипач

врач

охотник

столяр

Иван

Семен?

Василий

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

1

2

3

4

скрипач

врач

охотник

столяр

Геннадий

Иван

Семен

Василий

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

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

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

  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


[1] Строго говоря, выражение «одно из двух высказываний верно, а второе – неверно» соответствует логической операции «исключающее ИЛИ». Поэтому вместо двух условий для болельщика «А» можно записать одно: . Однако при этом и так непростое решение еще больше усложнится…