В силу теоремы 6 получение минимальной ДНФ можно разбить на два этапа
1. Нахождение сокращенной ДНФ.
2. Нахождение тупиковых ДНФ (таких, из которых нельзя удалить ни одного простого импликанта) путём удаления подмножества элементарных конъюнкций из сокращённой ДНФ. Выбор минимальной из полученных тупиковых ДНФ.
Рассмотрим первый этап получения минимальной ДНФ. Метод получения сокращённой ДНФ функции f(x1, ..., xn) из ее совершенной ДНФ состоит в применении следующих эквивалентных преобразований:
а) операции полного склеивания, которая состоит в замене выражения А х Ú А`х на А, так как
А х Ú А`х º А (х Ú`х) º A • 1 º A;
б) операции неполного склеивания, которая состоит в замене А х Ú А`х на А х Ú А`х Ú А, так как
А х Ú А`х Ú А º А (х Ú`х) Ú А º А•1Ú A = A;
в) операции поглощения, которая состоит в замене АВ Ú А на А, так как
АВ Ú А º А (В Ú 1) º А.
Здесь А и В – произвольные элементарные конъюнкции.
Теорема 7 (без доказательства). Сокращённую ДНФ функции f(x1, ..., xn) можно получить из ее совершенной ДНФ, применяя все возможные операции неполного склеивания, а затем операции поглощения.
Пример 1. Построить сокращённую ДНФ функции f(x1, x2) = x1 ® х2 из ее СДНФ:
Теперь перейдем ко второму этапу получения минимальной ДНФ.
Пусть дана сокращённая ДНФ функции f(x1, ..., xn):
N = U1 Ú U2 Ú … Ú Uk. Простой импликант называется ядерным (входящим в ядро функции f(x1, ..., xn)), если
≢ 1.
Эта запись означает, что простой импликант Ui является ядерным импликантом функции f(x1, ..., xn), если существует набор a = (a1, ..., an), на котором импликант Ui обращается в 1, а все остальные импликанты сокращённой ДНФ – в ноль.
Пример 2. Найти ядерные импликанты функции f(x1, ..., xn), заданной своей сокращённой ДНФ:
Теорема 8 (без доказательства). Простой импликант Ui входит во все тупиковые ДНФ тогда и только тогда, когда Ui входит в ядро функции f(x1, ..., xn), то есть тогда и только тогда, когда он является ядерным.
Следствие. Пусть ядро f(x1, ..., xn) состоит из импликантов Ul1, ... ,Ulm тогда импликант Ul, для которого выполнено соотношение: º 1.
То есть, импликант Ul обращается в единицу на тех же наборах, что и дизъюнкция ядерных импликантов: не входит ни в одну из тупиковых ДНФ функции f(x1, ..., xn).
Возвращаясь к примеру 2, отметим, что:
Импликант х1`х4 удовлетворяет следствию из теоремы 8:
`х1`х2 х3®`х2`х4 Ú х1 х2 ≢ 1, не удовлетворяет следствию.
Таким образом, последовательность действий при выполнении второго этапа состоит в следующем:
1) для каждого простого импликанта сокращённой ДНФ проверить, входит он в ядро или нет. Отметить неядерные импликанты;
2) проверить для отмеченных импликантов выполнение следствия из теоремы 8. Простые импликанты, для которых выполнено следствие, удалить из сокращённой ДНФ;
3) проверить возможность удаления оставшихся отмеченных конъюнкций. Из полученных тупиковых ДНФ выбрать минимальную ДНФ.
Рассмотрим эту последовательность действий на примере 2.
1) нашли ядро функции f(х1, х2, х3, х4), состоящее из простых импликантов `х2`х4 и х1 х2. Отметим курсивом в сокращённой ДНФ неядерные импликанты:
≢ 1.
º 1.