Лекция 12. Методы решения логических задач.
3. Решение
истинностных задач Данный тип задач можно решать
тремя методами: методом рассуждений, табличным методом и с помощью логических
выражений, с помощью построения таблиц истинности и приведения задачи к системе
логических уравнений. Пример: Перед началом Турнира
«Четырех» болельщики высказали следующие предположения по поводу своих кумиров:
А)
Макс победит, Билл – второй;
В)
Билл – третий, Ник – первый;
С)
Макс – последний, а первый – Джон.
Когда соревнования
закончились, оказалось, что каждый из болельщиков был прав только в одном из
своих прогнозов. Какое место на турнире заняли Джон, Ник, Билл, Макс?
Решение (способ 1, метод
рассуждений): 1) Есть
«точная» информация, которая не подвергается сомнению: каждый из болельщиков
оказался прав в одном прогнозе. 2) Запишем
высказывания болельщиков: 1. Макс победит, Билл – второй; 2. Билл – третий, Ник – первый; 3. Макс – последний, а первый – Джон.
3) Известно, что каждый из болельщиков только в одном из прогнозов был прав (то есть, из двух высказываний одно истинно, а другое – ложно). 4) Пусть
первый болельщик угадал, что Макс победит, тогда третий болельщик ошибся в двух
предположениях, а это не соответствует «точной» информации. 5) Пусть
первый болельщик угадал, что Билл занял второе место, тогда второй болельщик
предсказал первое место Нику, следовательно, по предположению третьего, Макс
занял последнее место, а Джон – оставшееся третье место.
Отсюда имеем: Ник –
первое, Билл – второе, Джон – третье и Макс – четвертое место. Решение
(способ 2, табличный метод): Основной прием, который
используется при решении текстовых логических задач, заключается в построении
таблиц. Таблицы не только позволяют наглядно представить условие задачи или ее
ответ, но в значительной степени помогают делать правильные логические выводы в
ходе решения задачи.
1) Запишем высказывания трех болельщиков в
форме таблицы (заголовок строки обозначает место в турнирной таблице):
2) Считая, что два человека не могут
оказаться на одном месте, начнем «раскручивать» эту таблицу с той строчки, где
больше всего информации (в данном случае – с первой). 3) Предположим, что Макс действительно занял первое место, как и сказал «A»; в этом случае:
- «C» ошибся, поставив на первое место
Джона;
- учитывая, что каждый один раз угадал, а
второй ошибся, получается, что «C» угадал, что Макс будет на четвертом месте;
- но мы предположили, что Макс – на первом
месте (а не на четвертом), следовательно, получили противоречие; это значит,
что Макс все-таки не на первом месте
- таким образом, в первом прогнозе «А»
ошибся, это значит, что во втором он угадал, и Билл действительно занял второе
место:
- так
как Билл – второй, он не может быть на третьем месте, поэтому из прогноза «Б» следует,
что Ник – первый:
- если
Ник на первом месте, там не может быть Джон, поэтому из ответов «С» (среди
которых должен быть один верный, и один неверный), сразу находим, что Макс
занял четвертое место:
4) осталось только определиться с Джоном –
ему досталось единственное «свободное» третье место; окончательный список
победителей:
1.
Ник
2.
Билл
3.
Джон
4.
Макс.
Пример: В школе-новостройке в каждой из двух аудиторий может находится либо
кабинет информатики, либо кабинет физики. На дверях аудиторий повесили шутливые
таблички. На первой повесили табличку «По крайней мере, в одном из этих
аудиторий размещается кабинет информатики», а на второй аудитории – табличку с
надписью «Кабинет физики находится в другой аудитории». Проверяющему, который
пришел в школу, известно только, что надписи на табличках либо обе истины, либо
обе ложны. Помогите проверяющему найти кабинет информатики. Решение (способ 3, логические выражения): Переведем условие задачи на язык логики высказываний. Так как в каждой из
аудиторий может находиться кабинет информатики, то пусть: А = «В первой аудитории находится кабинет информатики»; В = «Во второй аудитории находится кабинет информатики».
Отрицания этих высказываний: ¬А =«В первой аудитории находится
кабинет физики»; ¬В = «Во второй аудитории находится кабинет физики». Х = А ˅ В. Высказывание на второй двери:
Утверждение о том, что надписи на табличках либо одновременно истинные,
либо одновременно ложные в соответствии с законом исключенного третьего
запишется следующим образом:
Подставим вместо X и Y соответствующие формулы:
Упростим
сначала первое слагаемое. В соответствии с законом дистрибутивности умножения
относительно сложения:
В
соответствии закона непротиворечия:
Далее
упростим второе слагаемое. В соответствии с первым законом де Моргана и законом
двойного отрицания:
В
соответствии с законом непротиворечия:
В
результате получаем:
Построим
таблицу истинности для полученного выражения:
Проанализировав
данные таблицы истинности имеем, что в первой аудитории находится кабинет
физики, а во второй – кабинет информатики.
Пример:
Следующие два высказывания истинны: (1). Неверно, что если корабль A вышел
в море, то корабль C — нет.
(2). В море вышел корабль B или
корабль C, но не оба вместе. Определить, какие корабли вышли в море. Решение (способ 4, система логических
уравнений): Обозначим
буквами высказывания:
A — «корабль
A вышел в море»,
B — «корабль
B вышел в море»,
C — «корабль
C вышел в море».
Высказывание «если корабль A вышел в море, то корабль C —
нет» можно записать в виде:
По
условию (1), это высказывание неверно, таким образом, имеем:
Кроме
того, из (2) получаем:
Таким
образом, решение задачи сводится к решению системы логических уравнений:
Нужно
найти тройку логических значений A,
B и C, при которых оба уравнения превращаются в истинные равенства.
Рассмотрим несколько способов решения этой системы. Способ 1. Сведение к одному
уравнению. Преобразуем уравнения так, чтобы правые части
были равны 1 (истинному значению). Для этого применим инверсию (операцию «НЕ»)
к первому уравнению:
Теперь
представляем импликацию и «исключающее ИЛИ» через базовые операции «И», «ИЛИ»,
«НЕ»:
Объединить
оба уравнения с помощью операции «И» в одно уравнение, равносильное исходной
системе:
Раскрываем
инверсию в первой скобке по закону де Моргана и совершаем необходимые
преобразования, после чего получим:
Последнее
уравнение, равносильное исходной системе, имеет единственное решение: A = 1, B = 0 и C = 1. Таким
образом, в море вышли корабли А и
C. Способ 2. Таблица истинности. Построим таблицу истинности для системы с тремя переменными: Полужирным
выделена строка, для которой выполняются условия задачи. Таким образом, A = 1, B = 0 и C = 1 , это значит,
что в море вышли корабли А и C. Недостаток этого метода —
трудоемкость при большом количестве переменных. Способ 3. Декомпозиция. Идея
состоит в том, чтобы зафиксировать значение одной из переменных (положить ее
равной 0 или 1) и за счет этого упростить уравнения. Затем можно зафиксировать
значение второй переменной и т.д. При A =
0 получаем: На
основе определения импликации можно сделать вывод о том, что первое уравнение
(и, следовательно, вся система) при A =
0 решений не имеет. Рассмотрим второй
случай, при A = 1: Из
первого уравнения в следует, что или С = 1, а из второго — B = 0. Таким образом, существует единственное решение системы: A = 1, B = 0 и C = 1; это значит,
что в море вышли корабли А и C.
Способ 4. Последовательное
решение уравнений. В некоторых случаях можно решать уравнения
последовательно, на каждом шаге добавляя по одной переменной в рассматриваемый
набор. Для данного способа удобнее вводить переменные в алфавитном порядке, для
этого поменяем местами уравнения в системе: Мы
видим, что первое уравнение зависит только от A и B, а в третьем
подключается переменная C. Будем
строить дерево решений. Переменная А может принимать 2 значения: Из
первого уравнения поэтому
при A = 0 получаем единственный вариант B = 1, а при A = 1 имеем B = 0. Итак, первое уравнение имеет два
решения относительно переменных A и
B: Теперь
«подключаем» второе уравнение из
которого нужно определить допустимые значения C для каждого варианта. При A = 0 импликация не
может быть ложна, то есть первая ветка дерева не дает ни одного решения системы
двух уравнений. При A = 1 получаем единственное решение, для которого C = 1: Таким
образом, существует единственное решение системы: A = 1, B = 0 и C = 1. Это значит, что в море вышли
корабли А и C.
|