Учитывая, что булево выражение находится в конъюнктивной нормальной форме: существует ли «простой» алгоритм для его упрощения, сохраняя его в CNF?Алгоритм упрощения CNF
В частности, какое свойство следующего выражения вызывает это упрощение?
(~a+b+c)(a+~b+c)(a+~c)
упрощается ...
(~a+b+c)(a+~b)(a+~c)
Karnaugh map вашего примера:
Чтобы получить упрощенную DNF, клетки '1' сгруппированы, чтобы получить с минимальным количеством minterms.
Аналогичным образом можно группировать ячейки «0», чтобы получить обратную крышку с минимальным количеством членов.
Обратное отображение:
литералы полученных терминов инвертировать, чтобы достигнуть желаемого минимального CNF
(а + ~ б) (а + ~ c) (~ a + b + c)
Процедура использует тот факт, что инверсия minterm - maxterm (обычно называемый CNF clause) с перевернутыми литералами.