Еще пример задания:
Сколько различных решений имеет уравнение
((J → K) →(M N L)) ((M N L) → (¬J K)) (M → J) = 1
где J, K, L, M, N – логические переменные? В ответе не нужно перечислять все различные наборы значений J, K, L, M и N, при которых выполнено данное равенство. В качестве ответа Вам нужно указать количество таких наборов.
Решение (вариант 1, использование свойств импликации):
-
перепишем уравнение, используя более простые обозначения операций:
-
логическое произведение трех сомножителей равно единице, поэтому каждый из них должен быть тоже равен единице
-
учитывая, что
,
и выполняя замены
и
,
получаем
.
-
рассмотрим последнюю импликацию, которая должна быть равна 1:
;
по таблице истинности импликации сразу
находим, что возможны три варианта:
-
поскольку все (в том числе и первые две) импликации должны быть равны 1, по таблице истинности импликации сразу определяем, что
,
то есть
-
в случае «а» последнее уравнение превращается в
и не имеет решений -
в случае «б» имеем
,
тогда как
и
– произвольные; поэтому есть 4 решения,
соответствующие четырем комбинациям
и
-
в случае «в» получаем
,
то есть для
есть единственное решение (
),
а для
– три решения (при
;
и
;
и
) -
проверяем, что среди решений, полученных в п. 7 и 8 нет одинаковых
-
таким образом, всего есть 4 + 1 + 3 = 8 решений
-
ответ – 8
Решение (вариант 3, декомпозиция, автор идеи – А. Сидоров, ЭПИ МИСИС):
-
перепишем уравнение, используя более простые обозначения операций:
-
идея заключается в том, что мы выбираем одну какую-нибудь переменную и отдельно рассматриваем случаи, когда она равна 0 и 1; такой подход, когда большая задача разбивается на несколько более простых, называют декомпозицией
-
логическое произведение трех сомножителей равно единице, поэтому каждый из них должен быть тоже равен единице
-
например, пусть
;
тогда требуется, чтобы
,
по таблице истинности импликации
получается, что при этом
может быть любое («из лжи следует что
угодно»);
-
выполним второй шаг декомпозиции: рассмотрим отдельно варианты
и
-
при
и
получаем
это равенство истинно, если
,
а такого не может быть, то есть в этом
случае решений нет
-
при
и
получаем
это равенство истинно только при
(иначе первая скобка равна нулю), но у
нас никак не ограничены значения
и
поэтому получается, что при
и
есть 4 решения
(при
и всех 4-х различных комбинациях
и
)
-
теперь проверяем вариант, когда
;
при этом
так как должно быть
,
по таблице истинности операции импликация
сразу получаем
и уравнение преобразуется к виду
-
выполним второй шаг декомпозиции: рассмотрим отдельно варианты
и
-
при
получаем
,
откуда сразу следует, что
(3 решения:
;
и
) -
при
получаем
,
откуда сразу следует, что
(1 решение:
) -
таким образом, уравнение всего имеет 4+3+1 = 8 решений
-
ответ – 8
Решение (вариант 4, декомпозиция, автор идеи – А. Сидоров, ЭПИ МИСИС):
-
та же декомпозиция, но в другом порядке
-
сделаем сначала декомпозицию по
-
рассмотрим вариант, когда
;
подставляя это значение в уравнение
получаем
-
учитывая, что
при любом
(«из лжи следует все, что угодно»),
находим
-
отсюда сразу следует, что
и по таблице истинности операции
импликация определяем, что
;
учитывая это, получаем
этого не может быть, потому что первая
скобка равна нулю; поэтому при
решений нет
-
теперь пусть
,
тогда
и
,
поэтому остается уравнение
-
выполним декомпозицию по переменной
-
при
получаем
,
что верно при условии
;
из всех 8-ми комбинаций значений
переменных
,
и
только одна этому условию не удовлетворяет
(
),
поэтому имеем 7
решений -
при
получаем
,
что верно при условии
;
из 8-ми комбинаций значений переменных
,
и
только одна (
)
удовлетворяет этому условию, поэтому
имеем 1 решение -
таким образом, уравнение всего имеет 7+1 = 8 решений
-
ответ – 8
-
Возможные проблемы:
-
при использовании метода декомпозиции важен порядок выбора переменных для разбиения; можно рекомендовать в первую очередь делать декомпозицию по той переменной, которая чаще всего встречается в уравнении
-
нужно помнить, что импликация равна нулю только в случае
,
часто именно это свойство позволяет
упростить решение
-