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