Задачи по информатике

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

Логические задачи обычно формулируются на естественном языке. В первую очередь их необходимо формализовать, то есть записать на языке алгебры высказываний. Полученное логическое выражение необходимо упростить и проанализировать. Для этого иногда бывает необходимо построить таблицу истинности полученного логического выражения.

Существуют разные способы формализации, как условий задачи, так и процесс её решения:

  •  алгебраический
  •  табличный
  •  графический

Каждый из этих способов обладает своими достоинствами.

При применении алгебраического метода наиболее трудным является перевод текста задачи на язык формул.

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

Метод графов применяется тогда, когда между объектами, о которых идёт речь в задачи, существует много связей. Граф позволяет наглядно представить эти связи и определить, какие из них не противоречат условиям задачи.

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

Задача 1.

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

  • 1 комната
  • 2 комната
  • По крайней мере в одной из этих комнат находится принцесса.
  • Тигр в другой комнате

Решение:

Введем обозначения:

  •   П1 – в первой комнате находится принцесса
  •   ¬П1 – в первой комнате находится тигр
  •   П2 – во второй комнате находится принцесса
  •   ¬П2 – во второй комнате находится тигр

А=П1˅П2

В=¬П1

(А˄В)˅(¬A˄¬B)=1

(А˄В)˅(¬A˄¬B)=((П1˅П2)˄¬П1)˅(¬(П1˅П2)˄¬¬П1)=(П1˄¬П1˅П2˄¬П1)˅(¬П1˄¬П2˄П1)=(0˅П2˄¬П1)˅(П1˄¬П1˄¬П2)=(0˅П2˄¬П1)˅(0˄П1)=П2˄¬П1

(С обозначениями логических связок можно ознакомиться здесь).

Ответ:  в первой комнате находится тигр, во второй комнате находится принцесса.

***

Задача 2.

После традиционного вечера встречи с выпускниками школы в стенгазете появилась заметка о трех наших бывших учениках. В ней было сказано, что Иван, Андрей и Борис стали учителями. Теперь они преподают разные предметы: один из них – математику, второй – физику, а третий химию. Живут они также в разных городах: Минске, Витебске, Харькове. В заметке было также сказано, что их первоначальные планы осуществились не полностью:

1). Иван живет не в Минске;

2). Андрей не в Витебске;

3). Житель Минска преподает не математику;

4). Андрей преподает не физику;

5). Повезло только жителю Витебска, он преподает любимую им химию.

Можно ли по этим данным определить кто где живет и что преподает?

В данной задаче рациональнее всего использовать табличный метод решения.

По условию задачи имеем:

  • Имя
  • Город
  • Минск
  • Витебск
  • Харьков
  • Иван

Х

Андрей

¬М¬Ф

¬Ф

Борис

¬М

Х

Если Андрей не живет в Витебске, то он не может преподавать химию по условию задачи и по условию задачи он не преподает физику. Следовательно. Он преподает математику. Но математику не может преподавать житель Минска. Таким образом, Андрей житель Харькова. Но тогда ни Иван, ни Борис в Харькове не живут.

  • Имя
  • Город
  • Минск
  • Витебск
  • Харьков
  • Иван

Х

Андрей

¬М¬Ф

¬Ф¬ХМ

Борис

¬М

Х

Видно, что Иван не живет ни в Минске, ни в Харькове. Следовательно, Иван житель Витебска и преподает химию.

  • Имя
  • Город
  • Минск
  • Витебск
  • Харьков
  • Иван

Х

Андрей

¬М¬Ф

¬Ф¬ХМ

Борис

¬М

Х

Из таблицы видим, что жители Витебска и Харькова определены, преподаватели химии и математики. Борис не живет ни в Витебске, ни в Харькове и не преподает ни химию, ни математику. Значит Борис – Житель Минска и преподает физику.

  • Имя
  • Город
  • Минск
  • Витебск
  • Харьков
  • Иван

Х

Андрей

¬М¬Ф

¬Ф¬ХМ

Борис

¬МФ

Х

Ответ:

  • Андрей преподает математику и живет в Харькове;
  • Борис преподает физику и живет в Минске;
  • Иван преподает химию и живет в Витебске.

Можно решить эту задачу при помощи следующей логической цепочки:

Имя

Логические построения

Логические выводы

Андрей

 

п.2. Андрей живет в Минске или Харькове (но не в Витебске).

п.3 и п.5.  Житель Витебска преподает химию, житель Минска преподает физику (не математику), жителю Харькова «достается» математика.

п.4. Андрей преподает математику либо химию (но не физику), следовательно (п.3 и п.5), он не может жить в Минске, а по условию задачи (п.2) он не живет в Витебске, значит, Андрей может жить лишь в Харькове и преподавать только математику.

Андрей живет в Харькове и преподает математику
Иван

 

 

п.1. Иван живет в Витебске или Харькове (но не в Минске).

 Поскольку в Харькове живет Андрей, значит, Иван может жить лишь в Витебске, где преподает химию (п.3 и п.5).

Иван живет в Витебске и преподает химию
Борис

 

Поскольку Иван живет в Витебске и преподает химию, а Андрей живет в Харькове и преподает математику, то Борису остается Минск и физика. Борис живет в Минске и преподает физику

***

Задача 3.

На соревнованиях по легкой атлетике Андрей, Боря, Сережа и Володя заняли первые четыре места. Но когда девочки стали вспоминать, как распределились эти места между победителями, то мнения разделились:

  • Даша: Андрей был первым, а Володя вторым.
  • Галя: Андрей был вторым, а Борис – третьим.
  • Лена: Боря был четвертым, а Сережа – вторым.

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

В данной задаче применим метод графов.

  • Вершины графа – имена мальчиков и занятые ими места.
  • Ребра графа – высказывания девочек.
  • мнение Даши – красная линия
  • мнение Гали – синяя линияgraf
  • мнение Лены – черная линия

Ася сказала, что каждая девочка сделала только одно правильное заявление. Значит, надо оставить только по одной линии каждого цвета. Всего в графе должно остаться 3 линии разных цветов.graf2

Предположим, что истинное высказывание обозначенное В-2, тогда на следует удалить из графа А-1
(Даша права только в одном из предположения), А-2, С-2 (только кто – то один может занять второе место).

В графе осталось по одной линии каждого цвета, а именно В-2, Б-3, Б-4. graf3Но это невозможно, так как Борис не мог одновременно занять третье и четвертое место.
Значит, предположение об истинности высказывания, обозначенного ребром В-2 было неверным.

Одно предположение Даши (В-2) неверно, значит верно её другое предположение (А-1). Следовательно ребро А-2 следует удалить, а из этого следует, что высказывание, обозначенное ребром Б-3, должно быть истинным. Тогда ребро Б-4 надо удалить. Отсюда следует, что С-2 надо оставить. В результате получим граф, который и даёт ответ задачи.

Ответ:

  • Первое место – Андрей
  • Второе место – Сережа
  • Третье место – Боря
  • Четвертое место – Володя

***

Задача.

Три дочери писательницы Дорис Кей – Джуди, Айрис и Линда, тоже очень талантливы. Они приобрели известность в разных видах искусств – пении, балете и кино. Все они живут в разных городах, поэтому Дорис часто звонит им в Париж, Рим и Чикаго. Известно, что:

1). Джуди живет не в Париже, а Линда – не в Риме;

2). Парижанка не снимается в кино;

3). Та, что живет в Риме, певица;

4). Линда равнодушна к балету.

Где живет Айрис, и какова её профессия?

Решение:

Составим таблицу и отразим в ней условия 1 и 4, заполнив клетки цифрами 0 и 1 в зависимости от того, ложно или истинно соответствующее высказывание:

  • Париж
  • Рим
  • Чикаго
  • Пение
  • Балет
  • Кино

0

Джуди

Айрис

0

Линда

0

Далее рассуждаем следующим образом. Так как Линда живет не в Риме, то, согласно условию 3, она не певица.

  • Париж
  • Рим
  • Чикаго
  • Пение
  • Балет
  • Кино

0

Джуди

0

Айрис

0

0

Линда

0

0

1

Согласно условию 2, парижанка не снимается в кино, следовательно, Линда, живет не в Париже. Но она живёт и не в Риме. Следовательно, Линда живёт в Чикаго. Так как Линда и Джуди живут не Париже, там живёт Айрис.

  • Париж
  • Рим
  • Чикаго
  • Пение
  • Балет
  • Кино

0

Джуди

0

1

Айрис

0

0

0

1

Линда

0

0

1

Джуди живёт в Риме, и согласно условию 3, является певицей. А так как Линда киноактриса, то Айрис балерина.

В результате постепенного заполнения получаем следующую таблицу.

  • Париж
  • Рим
  • Чикаго
  • Пение
  • Балет
  • Кино

0

1

0

Джуди

1

0

0

1

0

0

Айрис

0

1

0

0

0

1

Линда

0

0

1

Ответ: Айрис балерина, она живет в Париже.

***

Попробуйте решить логическую задачу самостоятельно:

Условие задачи:

  • В одном дворе живут четыре друга.
  • Вадим и шофер старше Сергея;
  • Николай и слесарь занимаются боксом;
  • электрик — младший из друзей;
  • по вечерам Антон и токарь играют в домино против Сергея и электрика.

Определите профессию каждого из друзей.

***



Rambler's Top100