3.6     Мінімізація кон’юнктивних нормальних форм

Мінімізація КНФ виконується аналогічно розглянутим методам мінімізації ДНФ булевих функцій, тому зупинимося лише на основних положеннях.

Нагадаємо, що конституентою нуля називається функція, яка набуває значення 0 на одному наборі. Вона виражається диз’юнкцією всіх змінних функції.

Наприклад, набору 0110 відповідає конституента нуля , відповідно:

0111 - ,

1000 - .

Задачею мінімізації КНФ є визначення мінімальної КНФ. Ця задача вирішується в два етапи – пошук скороченої КНФ (кон’юнкція всіх простих імплікант) і потім знаходження мінімальної КНФ. Другий етап мінімізації виконується за допомогою таблиці Квайна так само, як і при пошуку мінімальної ДНФ. Оскільки можливо тільки два варіанти: або дана проста імпліканта поглинає дану конституенту нуля, або ні – згідно зі співвідношенням поглинання

.

Перший етап мінімізації полягає у пошуку всіх простих імплікант. Практично всі методи мінімізації ДНФ мають свої аналоги для КНФ. Розглянемо це детальніше.

Співвідношення склеювання на основі метода Квайна:

.

Співвідношення склеювання на основі метода Блейка:

.

Метод Нельсона у застосуванні до задачі мінімізації КНФ полягає у розкритті дужок в довільній ДНФ функції і виконання поглинань. Такі дії приводять до появи скороченої КНФ. Передбачається використання дужок на початку і в кінці кожного елементарного добутку початкової ДНФ та використання другого дистрибутивного закону. Наприклад, функція задана мінімальною ДНФ: , її скорочена КНФ буде мати вигляд:

.

За допомогою діаграм Вейча пошук мінімальної КНФ здійснюється так само просто, як і у випадку ДНФ. Відмінність тільки в тому, що аналізуються нульові набори і змінні виписуються з інверсіями. Наприклад для функції, заданої діаграмою (табл. 3.11), мінімальною КНФ буде:

.

Для порівняння знайдемо мінімальну ДНФ: . В даному випадку ДНФ виявилася простішою. В загальному випадку про порівняльну складність мінімальних КНФ і ДНФ не можна говорити наперед, але можна відзначити таке: кількість букв мінімальної ДНФ довільної функції і мінімальної КНФ функції однакові.

Таблиця 3.11