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

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

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

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

Задача 1.

Вы – участник игры и Вам нужно получить ключ. Перед Вами два ящика, на которых написано: на первом - «В одном из ящиков находится ключ»; на втором – «Ключ – в другом ящике». Известно при этом, что обе надписи либо обе истинны, либо обе ложны. Ключ может находиться в одном из ящиков, или сразу в обоих ящиках, или ни в одном из них.

Формализуем условия задачи.

Обозначим К1 = «Ключ находится в первом ящике»; К2 = «Ключ находится во втором ящике». Тогда = «В первом ящике нет ключа», = «Во втором ящике нет ключа».

Надпись на первом ящике: X=К1К2, надпись на втором – Y=K1.

То, что обе надписи либо обе истинны, либо обе ложны, можно в формульном виде записать так: .

Решение. Подставив значения и упростив, получим:

= (по закону поглощения) = = (по закону де Моргана) = = (по закону отсутствия степеней и дистрибутивному закону) = = (по закону непротиворечия и свойствам логических констант) = .

Ответ: ключ находится в первом ящике, во втором ящике ключа нет.

Задача 2

В некотором сказочном государстве живут молодцы, которые всегда говорят правду, и лжецы, которые всегда лгут. Вы встретили двух жителей этой страны – А и В. В ответ на вопрос, кто из них есть кто, А ответил: «По крайней мере, один из нас лжец». Так есть ли среди них молодец?

Формализация условий задачи.

Обозначим А = «А есть молодец», = «А есть лжец», В = «В есть молодец», = «В есть лжец».

Суждение «Один из нас лжец» в этих обозначениях записывается так: .

Возможно следующее: А - молодец и его суждение истинно или А – лжец и его суждение ложно (но противоречащее суждение истинно). В формульном виде это запишется так:

Решение. Упростим полученную формулу:

= =

Ответ: А – молодец, В – лжец.

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

Задача 3

Школьники Аня, Борис, Дима и Света со вторника по пятницу помогают заболевшей соседке. Они хотят составить график дежурства на ближайшие 4 недели так, чтобы каждый день помощь оказывать кто-то один и чтобы каждый из ребят дежурил ровно один раз в неделю, причем в разные дни. При этом нужно учесть, что в первую неделю Света может дежурить только в четверг, на второй неделе Аня свободна только во вторник, на третьей неделе Диме дежурство нужно поставить в среду, на четвёртой неделе Борис может дежурить только в четверг. В пятницу все хотят дежурить следующим образом: на первой неделе – Дима, на второй – Света, на третьей – Борис, на четвертой – Аня.

Решение задачи.

Составим таблицу, куда занесем условия задачи.

Анализируем первую строку и первый столбец таблицы.

Аня в первую неделю не может дежурить ни в четверг, ни в пятницу, так как в эти дни дежурят Дима и Света. Не может она дежурить и во вторник, так как во вторник она дежурит во вторую неделю. Таким образом, в первую неделю Аня будет дежурить в среду. Борису остаётся дежурить во вторник.

Анализируем второй столбец и вторую строку таблицы.

Во вторую неделю Борису остаётся для дежурства только среда. Следовательно, Дима должен дежурить в четверг.

В результате анализа первого столбца и третьей строки получаем, что в третью неделю Аня будет дежурить в четверг, а Света – во вторник.

Итоговый результат:

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

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

Задача 4

В классе прошли контрольные работы по алгебре, физике и информатике. Отличные оценки получили по алгебре 11 учеников, по физике – 8 учеников, по информатике – 14 учеников. Причем 3 ученика получили пятёрки и по алгебре и по физике, 5 учеников – по физике и информатике, 7 учеников – по алгебре и информатике. 2 ученика получили отличную оценку по всем трём предметам. Сколько человек в классе не получили пятёрки ни по одному предмету?

Решение задачи.

Изобразим условно множество всех учеников класса большим кругом, а множества учеников, получивших «5» по алгебре, физике и информатике кругами А, Ф и И соответственно.

Пересечение всех трёх кругов – это множество учеников, получивших «5» по всем трём предметам. По условию оно равно 2 ученикам.

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

Дальнейшие рассуждения и вычисления приведут нас к ответу.

Ответ: 6 учеников из 26 не получили «5» ни по одному предмету.

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

Задача 5

В забеге на легкоатлетическом соревновании участвуют Алексей, Борис, Сергей и Дмитрий. Перед забегом они сделали следующие прогнозы:

Алексей предсказал победу Бориса;

Борис предположил, что Дмитрий придёт последним;

Сергей предсказал, что Алексей придёт третьим;

Дмитрий согласился с прогнозом Алексея.

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

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

Так как только победитель высказал истинное суждение, то ни Алексей, ни Дмитрий, не могут быть победителями, так как они предположили победу Бориса. Следовательно, и Борис – не победитель. Остаётся, что в забеге победил Сергей. Следовательно, согласно его прогнозу, Алексей занял третье место. Прогноз Бориса не мог сбыться, следовательно, Дмитрий занял второе место. Последнее четвертое место занял Борис.

Ответ: 1 – Сергей, 2 – Дмитрий, 3 – Алексей, 4 – Борис.

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

A1Б1  Б1Д4  C1A3  Д1Б1 = 1

Словесная запись этой формулы такова: (Алексей занял первое место и оправдалось его предположение - Борис занял первое место) или (Борис занял первое место и Дмитрий – четвёртое) или (Сергей – первое и Алексей – третье) или (Дмитрий – первое и Борис – первое).

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

Формальные записи этих условий достаточно громоздки. Вот лишь часть их по отношению к Алексею и первому месту:

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

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

5