Логические задачи

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

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

Пример 1
Три друга обсуждали историю Нового года, при этом каждый сказал следующее:
Празднование Нового года с 1 января установили во Франции в 45 году до Рождества Христова (Юлием Цезарем)
Празднование Нового года с 1 января установили римляне в 1659 году указом Карла IX
Празднование Нового года с 1 января установили во 2 веке и не французы
Оказавшийся рядом знаток истории сказал, что каждый из них прав только в одном из двух высказанных предложений.
Где и в какое время было установлено празднование Нового года с 1 января?

Решение
Вводим обозначения:
Ф – французы
Р – римляне
К – Карл IX в 1659
Ц – Цезарь
В –2 век
Логическая формула:
(Ф&неЦ + неФ&Ц)&(Р&неК + неР&К)&(неВ&неФ +Ф&В)=
упростим логическую формулу
воспользуемся распределительным законом
(Ф&неЦ + неФ&Ц)&(Р&неК + неР&К)&(неВ&неФ +Ф&В)=((Ф&неЦ+неФ&Ц)&Р&неК+(Ф&неЦ+неФ&Ц)&неР&К)&(неВ&неФ+Ф&В)=(Ф&неЦ&Р&неК+неФ&Ц& Р&неК+Ф&неЦ& &неР&К+неФ&Ц&неР&К)&(неВ&неФ+Ф&В)=
Т.к. Ф&Р=0, Ц&К=0, то получаем следующую формулу
=(неФ&Ц& Р&неК+Ф&неЦ& неР&К)&(неВ&неФ+Ф&В)= (неФ&Ц& Р&неК+Ф&неЦ& неР&К)&неВ&неФ+ (неФ&Ц& Р&неК+Ф&неЦ& неР&К)&Ф&В=
Т.к. Ф&неФ=0, неФ&неФ=неФ, Ф&Ф=Ф, то получаем
=неФ&Ц&Р&неК&неВ+Ф&неЦ&неР&К&В=
т.к. К&В=0, то получаем следующую формулу:
=Ц&Р&неК&неВ&неФ
формула принимает значение истинно только при Ц=1, Р=1, К=0, В=0, Ф=0

Ответ: Празднование Нового года с 1 января установили римляне в 45 году до Рождества Христова(благодаря введению нового календаря Юлием Цезарем )
Пример 2
Три школьника Миша, Коля и Сергей, оставшиеся в классе на перемене, были вызваны к директору по поводу разбитого в это время окна в кабинете. На вопрос директора о том, кто это сделал, мальчики ответили следуещее:
Миша: «Я не бил окно, и Коля тоже..»
Коля: «Миша не разбивал окно, это Сергей разбил окно футбольным мячом!»
Сергей: «Я не делал этого, стекло разбил Миша».
Стало известно, что один из ребят сказал чистую правду, второй в одной части заявления соврал, а другое его высказываение истинно, а третий оба факта исказил. Зная это, директор смог докопаться до истины.
Кто разбил стекло в классе?
Решение
Аналогичный способ решени(больше пояснений)

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

Пример 3
На новогодний праздник три друга – Евгений, Николай, Алексей, выбрали себе костюмы трех богатырей: Ильи Муромца, Алеши Попович, Добрыни Никитича. Известно, что:
Евгений – самый высокий
Выбравший костюм Добрыни Никитича меньше ростом, чем выбравший костюм Ильи Муромца
Алексею не подошел костюм Добрыни Никитича
Ни у одного из друзей имена не совпадает с именем богатырей, выбранных костюмов
Какой костюм выбрал каждый из друзей?

Решение.
Составим таблицу и отразим в ней условия задачи, заполнив соответствующие клетки цифрами 0 и 1 в зависимости от того, ложно или истинно соответствующее высказывание.
Т.к. Евгений – самый высокий, а выбравший костюм Добрыни Никитича меньше ростом, чем выбравший костюм Ильи Муромца, значит Евгений выбрал не Добрыню(ставим 0).
Алексею не подошел костюм Добрыни Никитича, поэтому ставим 0 у Алексея.
Ни у одного из друзей имена не совпадает с именем богатырей, выбранных костюмов, значит Алексей не выбрал Алешу поповича.

Из таблицы видно, что Добрыней Никитичем может быть только Николай, а Алексей мог выбрать только Илью Муромца.

Заполнем нулями клетки у Николая и Ильи Муромца, получается, что Евгений выбрал Алешу Поповича:

Ответ: Алексей - Илья Муромец, Николай - Добрыня Никитич, а Евгений - Алеша Попович.
Пример4
Пятеро одноклассников: Ирена, Тимур, Камилла, Эльдар и Залим стали победителями олимпиад школьников по физике, математике, информатике, литературе и географии.
Известно, что:
победитель олимпиады по информатике учит Ирену и Тимура работе на компьютере;
Камилла и Эльдар тоже заинтересовались информатикой;
Тимур всегда побаивался физики;
Камилла, Тимур и победитель олимпиады по литературе занимаются плаванием;
Тимур и Камилла поздравили победителя олимпиады по математике;
Ирена cожалеет о том, что у нее остается мало времени на литературу.
Победителем какой олимпиады стал каждый из этих ребят?
Решение
(ссылка на видео)

Этим способом обычно решают несложные логические задачи.
Пример 5
В соревнованиях по плаванию участвовали Андрей, Виктор, Саша и Дима.
Их друзья высказали предположения о возможных победителях:
1) первым будет Саша, Виктор будет вторым;
2) вторым будет Саша, Дима будет третьим;
3) Андрей будет вторым, Дима будет четвёртым.
По окончании соревнований оказалось, что в каждом из предположений только одно из высказываний истинно, другое ложно. Какое место на соревнованиях занял каждый из юношей, если все они заняли разные места.
Решение задачи

== Решение задачи путём построения граф ==
Пример6
При составлении расписания на пятницу были высказаны пожелания, чтобы информатика была первым или вторым уроком, физика — первым или третьим, история — вторым или третьим.
Можно ли удовлетворить одновременно все высказанные пожелания?
Решение
В соответствии с условием задачи, при помощи графов получается следующая схема:

Теперь нужно избавиться от лишних, противоречащих самим себе или условию, вариантов, зачеркнув их

• В первом варианте первой ветки Ф1 противоречит Ин1 - вычёркиваем
  
• Во втором варианте Ис3 противоречит Ф3 - вычёркиваем
  
• В 1ом варианте второй ветки Ис3 также противоречит Ф3, а Ис2 - Ин2 - убираем
  
• Во 2ом варианте второй ветки Ис2 противоречит Ин2 - убираем
  

В этой задаче есть два варианта ответа:
1. Информатика или 1. Физика
2. История 2. Информатика
3. Физика 3. История

Пример7
Для длительной международной экспедиции на околоземной космической станции надо из восьми претендентов отобрать шесть специалистов: по аэронавтике, космонавигации, биомеханике, энергетике, медицине и астрофизике. Условия полёта не позволяют совмещать работы по разным специальностям, хотя некоторые претенденты владеют двумя специальностями. Обязанности аэронавта могут выполнять Геррети и Нам; космонавигатора — Кларк и Фриш; биомеханика — Фриш и Нам; энергетика — Депардье и Леонов; врача — Депардье и Хорхес; астрофизика — Волков и Леонов.
По особенностям психологической совместимости врачи рекомендуют совместные полеты Фриша и Кларка, а также Леонова с Хорхесом и Депардье. Напротив, нежелательно, чтобы Депардье оказался в одной экспедиции с Намом, а Волков — с Кларком.
Кого следует включить в состав экспедиции?
Решение
Г - Геррети аэ - аэронавт
Н - Нам к - космонавигатор
К - Кларк б - биомеханик
Ф - Фриш э - энергетик
Д - Депардье в - врач
Х - Хорхес ас - астрофизик
В - Волков
Л - Леонов

Ответ:
Геррети - аэронавт
Фриш - космонавигатор
Нам - биомеханник
Леонов - энергетик
Хорхес - врач
Волков - астрофизик

Задача 1 По подозрению в совершенном преступлении задержали Брауна, Джона и Смита. Один из них был уважаемым в городе стариком, другой был малоизвестным чиновником, третий – известным мошенником. В процессе следствия старик говорил правду, мошенник лгал, а третий задержанный в одном случае говорил правду, а в другом – ложь. Вот, что они утверждали:

• Браун: «Я совершил это. Джон не виноват».
  
• Джон: «Браун не виноват. Преступление совершил Смит».
  
• Смит: «Я не виноват, виновен Браун».
  

Необходимо определить имена старика, мошенника и чиновника и кто из них виноват, если известно, что преступник один.

Задача 2
Три одноклассника — Влад, Тимур и Юра, встретились спустя 10 лет после окончания школы. Выяснилось, что один из них стал врачом, другой физиком, а третий юристом. Один полюбил туризм, другой бег, страсть третьего — регби.
Юра сказал, что на туризм ему не хватает времени, хотя его сестра — единственный врач в семье, заядлый турист. Врач сказал, что он разделяет увлечение коллеги.
Забавно, но у двоих из друзей в названиях их профессий и увлечений не встречается ни одна буква их имен.
Определите, кто чем любит заниматься в свободное время и у кого какая профессия.

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

Задача 4
В поездке пятеро друзей — Антон, Борис, Вадим, Дима и Гриша, знакомились с попутчицей. Они предложили ей отгадать их фамилии, причём каждый из них высказал одно истинное и одно ложное утверждение:
Дима сказал: «Моя фамилия — Мишин, а фамилия Бориса — Хохлов». Антон сказал: «Мишин — это моя фамилия, а фамилия Вадима — Белкин». Борис сказал: «Фамилия Вадима — Тихонов, а моя фамилия — Мишин». Вадим сказал: «Моя фамилия — Белкин, а фамилия Гриши — Чехов». Гриша сказал: «Да, моя фамилия Чехов, а фамилия Антона — Тихонов».
Какую фамилию носит каждый из друзей?

Задача 5
Министры иностранных дел России, США и Китая обсудили за закрытыми дверями проекты соглашения о полном разоружении, представленные каждой из стран. Отвечая затем на вопрос журналистов: «Чей именно проект был принят?», министры дали такие ответы:
Россия — «Проект не наш, проект не США»;
США — «Проект не России, проект Китая»;
Китай — «Проект не наш, проект России».
Один из них (самый откровенный) оба раза говорил правду; второй (самый скрытный) оба раза говорил неправду, третий (осторожный) один раз сказал правду, а другой раз — неправду.
Определите, представителями каких стран являются откровенный, скрытный и осторожный министры.

Ответ на задачу 1
Решение этой задачи начинается с введения обозначений: буквами Б, Д и С обозначим высказывания: «виноват Браун», «виноват Джон» и «виноват Смит» соответственно. Тогда утверждения, высказанные задержанными, можно записать в виде конъюнкций:
Б ∧¬ Д, Б ∧ С, Б ∧¬С,
из которых, по условию задачи, две ложны, а одна истинна. Поэтому будет истинной формула
L = (Б ∧¬ Д)∨( Б ∧ С)∨( Б ∧¬С)
Таблица истинности этой формулы имеет вид:

Из таблицы видно, что формула L истинна в пяти из восьми случаев. Случай, представленный в пятой строке, следует исключить из рассмотрения, так как здесь оказываются истинными две конъюнкции, а это противоречит условию задачи. В строках 4, 6 и 7 оказываются истинными по два высказывания: Д и С, Б и С, Б и Д, соответственно, что также противоречит условию задачи. Следовательно, справедлив случай 7, то есть преступник – Смит. Он – известный мошенник, и оба его высказывания ложны: Б ∧¬С = 0. При этом высказывания Б и Д ложны. Значит, истинна пара высказываний Джона, а у Брауна первое высказывание ложно, а второе истинно. Ответ на первый вопрос задачи: Джон – уважаемый в городе старик, а Браун – Малоизвестный чиновник, а Смит - известный мошенник

Ответ на задачу 2
Решение. Здесь исходные данные разбиваются на тройки (имя — профессия — увлечение).
Из слов Юры ясно, что он не увлекается туризмом и он не врач. Из слов врача следует, что он турист.

Ответ. Влад — юрист и регбист, Тимур — врач и турист, Юра — физик и бегун.

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

Далее рассуждаем следующим образом. Так как Линда живет не в Риме, то, согласно условию 3, она не певица. В клетку, соответствующую строке «Линда» и столбцу «Пение», ставим 0.
Из таблицы сразу видно, что Линда киноактриса, а Джуди и Айрис не снимаются в кино.

Согласно условию 2, парижанка не снимается в кино, следовательно, Линда живет не в Париже. Но она живет и не в Риме. Следовательно, Линда живет в Чикаго. Так как Линда и Джуди живут не в Париже, там живет Айрис. Джуди живет в Риме и, согласно условию 3, является певицей. А так как Линда киноактриса, то Айрис балерина.
В результате постепенного заполнения получаем следующую таблицу:

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

Ответ на задачу 4
Решение. Обозначим высказывательную форму «юноша по имени А носит фамилию Б» как АБ, где буквы А и Б соответствуют начальным буквам имени и фамилии.
Зафиксируем высказывания каждого из друзей:
1. ДМ и БХ;
2. АМ и ВБ;
3. ВТ и БМ;
4. ВБ и ГЧ;
5. ГЧ и АТ.
Допустим сначала, что истинно ДМ. Но, если истинно ДМ, то у Антона и у Бориса должны быть другие фамилии, значит АМ и БМ ложно. Но если АМ и БМ ложны, то должны быть истинны ВБ и ВТ, но ВБ и ВТ одновременно истинными быть не могут.
Значит остается другой случай: истинно БХ. Этот случай приводит к цепочке умозаключений:
БХ истинно БМ ложно ВТ истинно АТ ложно ГЧ истинно ВБ ложно АМ истинно.
Ответ: Борис — Хохлов, Вадим — Тихонов, Гриша — Чехов, Антон — Мишин, Дима — Белкин.

Ответ на задачу 5
Решение. Для удобства записи пронумеруем высказывания дипломатов:
Россия — «Проект не наш» (1), «Проект не США» (2);
США — «Проект не России» (3), «Проект Китая» (4);
Китай — «Проект не наш» (5), «Проект России» (6)
Узнаем, кто из министров самый откровенный.
Если это российский министр, то из справедливости (1) и (2) следует, что победил китайский проект. Но тогда оба утверждения министра США тоже справедливы, чего не может быть по условию.
Если самый откровенный — министр США, то тогда вновь получаем, что победил китайский проект, значит оба утверждения российского министра тоже верны, чего не может быть по условию.
Получается, что наиболее откровенным был китайский министр. Действительно, из того, что (5) и (6) справедливы, cледует, что победил российский проект. А тогда получается, что из двух утверждений российского министра первое ложно, а второе верно. Оба же утверждения министра США неверны.
Ответ: Откровеннее был китайский министр, осторожнее — российский, скрытнее — министр США.

Аналогичные задачи заданию В4, части В.

1
Алеша, Илья и Добрыня нашли в земле хорошо сохранившийся стеклянный сосуд с житкостью. Рассматривая удивительную находку, каждый высказал по два предположения:
Алеша: «Это сосуд французский и имеет 5 звездочек».
Илья: «Это сосуд испанский и имеет 3 звездочки».
Добрыня: «Это сосуд не французский и имеет 4 звездочки».
Змей Горыныч доходчиво объяснил ребятам, что каждый из них рав только в одном из двух предположений.
Где изготовлен и во сколько звездочек оченивается его качество?
2
На столе лежат в ряд фигуры: треугольник, ромб, круг и квадрат.
Цвета этих фигур - зеленый, черный, синий, красный. Фигура красного цвета лежит между зеленой и синей, справа от черной фигуры лежит ромб, круг лежит правее треугольника и ромба, и, наконец, фигура синего цвета не лежит рядом с фигурой черного.
Какого цвета круг?
3
Борису, Ивану и Сергею предъявлено обвинение в соучастии в ограблении сбербанка. В ходе следствия Борис сказал, что преступники были на синем «Запорожце», Иван сказал, что это был черный «Москвич», Серргей утверждал, что это была «Ока», но не синяя. Каждый указал неправельно либо марку, либо цвет автомобил. Определите цвет и марку.
4
Перед вами 5 коробочек: белая, черная, красная, синяя и зеленая.
Так же есть по 2 шарика каждого из цветов.
В каждой коробочке лежит по 2 шарика.
Известно, что:

• ни один шарик не лежит в коробочке того же цвета, что и он сам;
  
• в красной коробочке нет синих шариков;
  
• в каробочке нейтрального(черной или белой) лежит один красный и один зеленый шарик;
  
• в черной коробочке лежат шарики холодных тонов(синий и зеленый);
  
• в одной из коробочек лежат один белый и один синий шарик;
  
• в синей коробочке находится один черный шарик
  

Вопрос: какого цвета шарики лежат в каждой из коробочек?
5
На соревнованиях по боулингу Андрей, Борис, Сергей и Володя заняли первые четыре места. Но когда девушки стали вспоминать, как эти места распределились между победителями, то мнения разошлись.
Даша сказала: «Андрей был первым, а Володя - вторым».
Галя утверждала: «Андрей был вторым, а Борис - третьим».
Лена считала: «Борис был четвертым, а Сергей - вторым».
Аня. которая была судьей на этих соревнованиях и хорошо помнила, как распределились места, сказала, что каждая из девушек сделала одно правельное и одно неправельное заявление.
Какой из юношей занял какое место?

1 Этот сосуд испанский и оценивается в 3 звезды.
2 Круг синий.
3 Преступники были на черном «Запорожце».
4 в белой коробочке - красный и зеленый шарик, в черной - синий и зеленый, в красной - белый и черный, в синей - белый и красный, в зеленой - черный и синий.
5 1 место - Андрей, 2 место - Сергей, 3 место - Борис, 4 место - Володя.

ряд логических задач
задачи на смекалку с решением
Задача Эйншейна
Логическая задача
Логические задачи
форум. Некоторые интересные пути решение задач
учебник Шауцуковой задачи, пояснения.