Алгоритм преобразования логических выражений к минимальному виду может включать следующие этапы (описывается процесс минимизации СДНФ): 2
- Поиск пар минтермов, отличающихся друг от друга только знаком инверсии и лишь в одном из аргументов. 2 Такие минтермы склеиваются. 2
- Склеивание импликант, образовавшихся в результате первого этапа склеивания. 2 Процесс продолжают до тех пор, пока дальнейшее склеивание импликант становится невозможным, то есть до получения простых импликант. 2 Выражение, образованное только из простых импликант, называется сокращённой дизъюнктивной нормальной формой (ДНФ). 2
- Попытка исключить из сокращённой ДНФ избыточные простые импликанты, используя для этого прочие правила булевой алгебры, например, теоремы противоречия, «исключённого третьего», закон поглощения и др.. 2
- Выбор из тупиковых форм той, которая имеет наименьший коэффициент сложности (содержит минимальное суммарное количество букв и термов). 2 Это и будет минимальная дизъюнктивная нормальная форма (ДНФ). 2
Также для преобразования логических выражений к минимальному виду могут использоваться специальные алгоритмические методы минимизации, например, метод Квайна, метод карт Карно, метод испытания импликант, метод импликантных матриц, метод Квайна-Мак-Класки и другие. 4