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

1. Определение верности предположений.

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

1. Изучение условия задачи;

2. Введение системы обозначений для логических высказываний;

3. Установление логических связей между всеми высказываниями, соответствующих условию задачи;

4. Конструирование логической формулы и определение значения ее истинности;

5. Упрощение логической формулы с применением законов алгебры логики;

6. Логический вывод на основе полученного высказывания

Задача 1.

Условие:

Алеша, Боря и Гриша нашли в земле старинный сосуд. Рассматривая находку, каждый высказал по два предположения.

§  Алеша: сосуд греческий и изготовлен в V веке:

§  Боря: сосуд финикийский и изготовлен в III веке:

§  Гриша: сосуд не греческий и изготовлен в IV веке.

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

Что это был за сосуд?

Решение:

Введем переменные:

a – греческий сосуд;

b – финикийский сосуд;

c – сосуд, изготовленный в  III веке;

d - сосуд, изготовленный в IV веке;

e - сосуд, изготовленный в V веке;

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

предположению Алеши соответствует формула: a + e = 1;

предположению Бори соответствует формула: b + c = 1;

предположению Гриши соответствует формула: -a + d = 1

Объединим все формулы в одну операцией конъюнкции (так как в общем истинность результата достигается при истинности всех дизъюнкций) и упростим:

(a + e) (b + c) (-a + d) = (b * (a + e) + c * (a + e)) (-a +d) = (ba + be + ac + ce)(-a +d) = ab(-a +d) + bc (-a + d)  + ac (-a + d) + ce (-a + d) = a-ab + abd + be-a + bed + a-ac + acd + -ace + cde =

0 + abd + be-a + bed + 0 + acd + -ace + cde = 1

Выражения, которые приобретают значение 0, в логической сумме не учитываются.

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

abd = 0; bed = 0; acd = 0; -ace = o; cde = 0

Остается: -abe = 1

Ответ:

Сосуд финикийский V века.

Задача 2.

Условие:

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

§  Их либо захватят гоблины, либо нападет дракон, либо они заблудятся в лесу, либо их ожидают две или сразу три из этих неприятностей;

§  Если дракон не нападет, то они утонут в реке;

§  И дракон нападет, и они заблудятся в лесу

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

Каких же опасностей стоит ожидать гномам?

Решение:

Введем логические переменные:

x – гномов захватят гоблины;

y – на гномов нападет дракон;

z – они утонут в реке;

w – они заблудятся в лесу

Первое предположение можно записать в виде формулы: x + y + w

По второму предположению: -y → z (= y + z) &

& возможность замены операции импликации операцией дизъюнкции мы рассмотрели в уроке 22

По третьему предположению: y * w

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

( x + y + w) * - (-y → z)  * -( yw) = (x + y + w) * -(y + z) * -(yw) = (x + y + w) * -y-z * (-y + -w) = (x-y-z + y-y-z + w-y-z) * (-y + -w) = (x-y-z + w-y-z) * (-y + -w) =  -y-z (x + w) (-y + -w)

В полученном выражении  -y-z (x + w) (-y + -w) = 1 без отрицания записаны переменные x и w.

Запись вида

НЕ Y И НЕ Z И (X ИЛИ W) И НЕ Y ИЛИ НЕ W = 1

Более наглядно иллюстрирует результат вычислений.

Ответ:

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

Решите следующие задачи:

Задача 3.

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

§  "Если удалят Лебедева или Константинова, то меня тоже", - сказал Хромов.

§  "Если удалят Лебедева или Константинова, то и меня "- сказал Голубев.

§  "Удалят либо меня со Светловым, либо Хромова с Голубевым", - сказал Лебедев.

Когда судья объявил о своем решении, все оказались правы и, кроме того, Константинов и Светлов не остались вместе на поле. Кто остался на поле?

Задача 4.

В забеге на ипподроме в числе прочих лошадей участвовали: Грейт, Цезарь и Молния.

Болельщики высказали свои предположения:

§  «Победит или Грейт, или Молния», - сказал один болельщик.

§  «Если Грейт будет вторым, то победит Цезарь», - сказал второй болельщик.

§  «Вторым придет или Цезарь, или Грейт», - сказал третий болельщик.

§  «Если Грейт придет третьим, то Молния не победит», - сказал четвертый болельщик

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

2. Задачи «о лгунах».

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

Задача 5.

Условие:

Брауну, Джону и Смиту предъявлено обвинение в соучастии в ограблении банка. Похитители скрылись на поджидавшем их автомобиле. На следствии

§  Браун показал, что преступники скрылись на синем «Бьюике»;

§  Джон сказал, что это был черный «Крайслер»;

§  Смит утверждает, что это был «Форд «Мустанг»» и ни в коем случае не синий.

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

Решение:

Введем переменные:

a – синяя машина;

b – «Бьюик»;

c – черная машина;

d – «Крайслер»;

e – «Форд « Мустанг»»

Показаниям Брауна соответствует выражение: a + b = 1;

Показаниям Джона соответствует формула: c + d = 1;

Показаниям Смита соответствует формула: -a + e = 1

Поскольку в указанных выражениях истинна только одна переменная, они объединяются знаком дизъюнкции.

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

(a + b) (c + d) (-a + e) = (с * (a + b) + d * (a + b)) * (-a +e) = (ca + cb + da + db) (-a + e) =

ca (-a + e) + cb (-a +e) + da (-a + e) + db (-a + e) = ca-a + cae + cb-a + cbe + da-a + dae + db-a + dbe = 0 + cae +cb-a + cbe + 0 + dae + db-a + dbe = cae + cb-a + cbe + dae + db-a + dbe = 1

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

cae = 0; cbe = 0; dae = 0; dbe = 0; db-a = 0

Остается: cb-a = 1

Ответ:

Преступники скрылись на черном «Бьюике».

Задача 6.

Условие:

Виктор, Роман, Леонид и Сергей заняли на олимпиаде по информатике 4 первых места. Когда их спросили о распределении мест, они дали такие ответы:

§  Сергей первый, Роман второй;

§  Сергей второй, Виктор третий;

§  Леонид второй, Виктор четвертый

Известно, что в каждом ответе только одно утверждение истинно.

Как распределились места?

Решение:

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

Первому утверждению соответствует: S1 + R2 = 1;

Второму утверждению соответствует: S2 + V3 = 1;

Третьему утверждению соответствует: L2 + V4 = 1

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

(S1 + R2) (S2 + V3) (L2 + V4) = 1

(S2 (S1 + R2) + V3 (S1 + R2)) (L2 + V4) = 1

(S2S1 + S2R2 + V3S1 + V3R2)(L2 + V4) = 1

Переменные S2S1 и S2R2 из выражения исключаются как заведомо ложные (S2S1 = 0, S2R2 = 0)

(V3S1 + V3R2)(L2 + V4) = 1

L2 (V3S1 + V3R2) + V4 (V3S1 + V3R2) = 1

L2V3S1 + V3R2L2 + V4V3S1 + V3V4R2 = 1

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

V4V3S1 = 0; V3R2L2 = 0; V3V4R2 = 0

Остается:

L2V3S1 = 1, →R4.

Ответ:

Сергей – первый, Леонид – второй, Виктор – третий, Роман – четвертый.

Задача 7.

Четырех инопланетянок, Ное, Энне, Валли и Орадо, прилетевших на Землю, спросили об их возрасте. Были получены следующие ответы:

1. Ное- 22 года, Энне - 21 год

2. Валли - 19 лет, Ное - 21 год

3. Орадо - 21 года, Валли - 18 лет

Стало известно, что все инопланетянки - разных возрастов, но все возраста совпадают с названными данными: 18, 19, 21 и 22. В каждом ответе истина - только одна часть, вторая - ложь.

Сколько лет каждой инопланетянке?

Задача 8.

Четыре ученицы: Катя, Аня, Инна, Вера участвовали в соревнованиях по гимнастике и заняли первые 4 места. На вопрос, кто из них какое место занял, 3 девочки ответили:

1. Инна - вторая, Вера- третья;

2. Инна - первая, Аня - вторая;

3. Катя - вторая, Вера - четвертая.

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

3. Вычисление соблюдения заявленных условий.

Задача 9.

Условие:

При составлении расписания на вторник преподаватели 11а  класса высказали просьбы завучу:

§  Учитель математики: поставить первый или второй урок;

§  Учитель физики: поставить первый или третий урок;

§  Учитель литературы: поставить второй или третий урок;

Какое расписание будет составлено?

Решение:

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

Учителя математики: М1 + М2

Учителя физики: Ф1+ Ф3

Учителя литературы: Л2 + Л3

Общая формула объединяет указанные выражения операцией конъюнкции, так как для ее истинности должны соблюдаться все условия:

(М1 + М2) * (Ф1+ Ф3) * (Л2 + Л3) = 1

(М1Ф1 + М2Ф1 + М1Ф3 + М2Ф3) (Л2 + Л3) = 1

М1Ф1 = 0 – заведомо ложное выражение;

(М2Ф1 + М1Ф3 + М2Ф3) (Л2 + Л3) = 1

М2Ф1Л2 + М1Ф3Л2 + М2Ф3Л2 + М2Ф1Л3 +  М1Ф3Л3 + М2Ф3Л3 = 1

Исключим заведомо ложные выражения: М2Ф1Л2 = 0, М2Ф3Л2 = 0, М1Ф3Л3 = 0, М2Ф3Л3 = 0.

Остается:

М1Ф3Л2 + М2Ф1Л3 = 1

Оба варианта совпадают  с заявленными условиями.

Ответ:

Расписание может быть составлено в двух вариантах:

1 – математика, 2 – литература, 3 – физика;

1 – физика, 2 – математика, 3 - литература

Задача 10.

Условие:

Менеджер банка должен установить четыре банкомата. В течение каждого дня работы должны выполняться следующие условия:

§  Если работает первый банкомат, то третий не должен работать, а второй и четвертый должны работать;

§  Если работает третий банкомат, то первый и четвертый не должны работать, а второй должен работать;

§  Должен работать, по крайней мере, один банкомат

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

Решение:

Введем переменные:

w – работает первый банкомат;

x – работает второй банкомат;

y – работает третий банкомат;

z – работает четвертый банкомат

Заменим операцию импликации операцией дизъюнкции по формуле: a → b = -a + b.

С учетом этого составляем формулы:

первое условие выражается  формулой: w → -yxz  = -w + -yxz = 1

второе условие y → -w-zx = -y + -w-zx = 1

Первые два условия должны выполняться одновременно, поэтому приведенные формулы объединяем операцией конъюнкции и упрощаем функцию:

(-w + -yxz) (-y + -w-zx) = (-w + -yxz) * -y + (-w + -yxz) * -w-zx = -w-y + -y-yxz + -w-w-zx + -yxz-w-zx = -w-y + -yxz + -w-zx

Далее в каждую часть нужно добавить (соединить методом конъюнкции) недостающие банкоматы так, чтобы выражение (формула) было эквивалентно исходному, поэтому добавленная часть должна принимать значение 1:

(xz + -x-z + -xz + x-z) = 1

(w + -w) = 1

(y + -y) = 1

При логическом умножении на приведенные выше формулы значение каждой части выражения не изменится, та как x * 1 = x, поэтому не изменится и значение всей формулы в целом.

-w-y (xz + -x-z + -xz + x-z) + -yxz (w + -w) + -w-zx (y + -y) = 1 = -w-yxz + -w-y-x-z + -w-yx-z + -w-y-xz + -yxz-w + -yxzw + -w-zx-y + -w-zxy

Из получившегося выражения исключаем две группы логического умножения, так как:

-w-yxz – повторяется (пятая группа –yxz-w эквивалентна, а по условию повторений быть не должно);

-w-y-x-z – противоречит третьему условию

Остается:

-w-yx-z + -w-y-xz + -yxz-w + -yxzw + -w-zx-y + -w-zxy

В данной формуле переменная без знака отрицания соответствует работающему банкомату, четвертая группа соответствует первому условию, последняя группа соответствует второму условию, и общее число дней равно 6.

Ответ:

Работа банкоматов должны осуществляться по следующему графику:

1)                       В первый день работает только второй банкомат;

2)                       Во второй день работает четвертый банкомат;

3)                       В третий день работают второй и четвертый банкомат;

4)                       В четвертый день работают первый, второй и четвертый банкомат;

5)                       В пятый день работает второй банкомат;

6)      В шестой день работают второй и третий банкомат