В лекции представим алгоритм получения минимальной дизъюнктивной нормальной формы, а также представим общий алгоритм минимизации булевой функции в классе нормальных форм. Напомним определения импликанта и простого импликанта произвольной булевой функции. Сформулируем определения тупиковой и минимальной нормальной форм. Определение. Если из дизъюнкции простых импликантов функции F нельзя отбросить ни одного слагаемого (иначе поменяется таблица истинности), то говорят, что получена тупиковая дизъюнктивная нормальная форма (ТДНФ) булевой функции F...

Определение. Булева функция (формула логики высказываний) F называется частично (не всюду) определённой, если не для всех возможных наборов значений входящих в функцию F перемен­ных указаны её значения. Алгоритм минимизации частично определенных функций в классе дизъюнктивных нормальных форм (ДНФ) включает в себя следующие шаги. Шаг 1. Доопределить булеву функцию F нулями на тех наборах значений пе­ременных, где она не определена. Полученную булеву функцию обозначить через F0. Шаг 2. Построить совершенную дизъюнктивную нормальную форму (СДНФ) булевой функции F0...