Преобразование логических выражений.
если в выражении нет скобок, сначала выполняются все операции «НЕ», затем – «И», затем – «ИЛИ», потом – «импликация», и самая последняя – «эквиваленция»
логическое произведение A∙B∙C∙… равно 1 (выражение истинно) только тогда, когда все сомножители равны 1 (а в остальных случаях равно 0)
логическая сумма A+B+C+… равна 0 (выражение ложно) только тогда, когда все слагаемые равны 0 (а в остальных случаях равна 1)
правила преобразования логических выражений (законы алгебры логики):
Закон | Для И | Для ИЛИ |
двойного отрицания | |
исключения третьего | | |
исключения констант | A · 1 = A; A · 0 = 0 | A + 0 = A; A + 1 = 1 |
повторения | A · A = A | A + A = A |
поглощения | A · (A + B) = A | A + A · B = A |
переместительный | A · B = B · A | A + B = B + A |
сочетательный | A · (B · C) = (A · B) · C | A + (B + C) = (A + B) + C |
распределительный | A + B · C = (A + B) · (A + C) | A · (B + C) = A · B + A · C |
де Моргана | | |
Пример задания:
Сколько различных решений имеет система логических уравнений
(x1 x2) (x2 x3) = 1
x1 y1 z1 x1 y1 z1 x1 y1 z1 = 1
x2 y2 z2 x2 y2 z2 x2 y2 z2 = 1
x3 y3 z3 x3 y3 z3 x3 y3 z3 = 1
где x1, …, x3, y1, …, y3, z1, …, z3 – логические переменные? В ответе не нужно перечислять все различные наборы значений переменных, при которых выполнено данное равенство. В качестве ответа нужно указать количество таких наборов.
Решение (последовательное подключение уравнений):
перепишем уравнения с помощью более простых обозначений:
заметим, что последние 3 уравнения независимы друга от друга, и вся система связана только через первое уравнение
рассмотрим второе уравнение
оно имеет три решения, каждое из которых соответствует единичному значению одного из слагаемых:
аналогичные уравнения 3-4 тоже имеют по три решения
теперь рассмотрим множество решений системы уравнений 2-3
при ограничении, которое накладывается первым уравнением:
поскольку импликация дает ложное значение (0) только для случая 10, первое уравнение в исходной системе запрещает комбинацию .
рассмотрим решение уравнений 2 и 3:
| |
(0,1,1) (1,0,1) (1,1,0) | (0,1,1) (1,0,1) (1,1,0) |
Эти уравнения независимы, поэтому система уравнений 2-3 (без дополнительных ограничений) имеет 33=9 решений
При ограничении :
поэтому количество решений системы уравнений 2-3 при ограничении вычисляется как 1 + 3 + 3 = 7 решений
рассуждая аналогично, подключаем уравнение 4 и ограничение , получаем, что количество решений системы уравнений 2-4 при ограничении вычисляется как 1 + 7 + 7 = 15 решений
Ответ: 15.
Решение (метод отображений, решение А.Н. Носкина):
п. 1-4 совпадают с предыдущим вариантом решения
построим правило отображения троек переменных.
1 уравнение
2 уравнение
3 уравнение
x2y2z2
x3y3z3
x1y1z1
011
011
011
101
110
101
101
110
110
Если бы не было никаких ограничений, то данная система имела бы 9 решений.
так как система имеет ограничения в виде первого уравнения,
(x1x2) (x2x3) = 1
то убираем все связи где выше указанные импликации ложны, а именно:
для (x1x2): x1 = 1, x2 = 0,
(x2x3): x2 = 1, x3 = 0.
1 уравнение
2 уравнение
3 уравнение
x2y2z2
x3y3z3
x1y1z1
011
011
011
101
110
101
101
110
110
Заполняем таблицу, вычисляя количество решений при подключении каждого последующего уравнения.
xyz | 1 уравнение | 2 уравнение | 3 уравнение |
011 | 1 | 1 | 1 |
101 | 1 | 3 | 7 |
110 | 1 | 3 | 7 |
Складываем все результаты: 1 + 7 + 7 = 15.
Ответ: 15.