Алгоритм побудови скороченої днф

Крок 1. Поставимо у відповідність кожній елементарній кон’юнкції ДДНФ булевий вектор з 0 та 1, ставлячи на -му місці 1, якщо -та змінна входить в елементарну кон’юнкцію, 0 – якщо в елементарну кон’юнкцію входить заперечення -тої змінної, і знак - , якщо -та змінна не входить в елементарну кон’юнкцію.

Крок 2. Розіб’ємо двійкові вирази, що відповідають елементарним кон’юнкціям, на класи за числом одиниць і розташуємо класи у стовпчик за порядком зростання цього числа.

Крок 3. Застосуємо тотожність узагальненого склеювання до пар виразів, які лежать в сусідніх класах. Пари, які підходять, відшукуються простим спостереженням: елементи пари повинні відрізнятися тільки в одній позиції, і в цій позиції не повинно бути прочерків. Всі послідовності, які походять від даної пари, розміщуються в один клас. Результат записуємо в новий стовпчик справа, а двійкові вирази, які брали участь у склеюванні, помічаємо галочкою.

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

Приклад 1. Одержимо скорочену ДНФ для булевої функції

йдучи за алгоритмом.

Розв’язання.

0 000 000 00-

1 001 001 -01

5 101 101 1-1

6 110 110 11-

7 111 111

Відповідь:

2 Етап мінімізації – побудова тупикової днф

Означення. Тупиковою ДНФ (ТДНФ) функції називається така скорочена ДНФ функції , з якої не можна виключити жодного імпліканта, не змінивши при цьому функції .

Теорема. Будь-яка мінімальна ДНФ деякої функції є її тупиковою ДНФ.

Для отримання МДНФ функції необхідно побудувати всі ТДНФ функції і вибрати серед них ті, які містять мінімальне число букв.

Означення. Одиничним інтервалом або просто інтервалом називається одинична множина елементарної кон’юнкції.

Зображення у вигляді ДНФ відповідає зображенню її одиничної множини у вигляді об’єднання інтервалів, тобто для будь-якої ДНФ виконується теоретико-множинне співвідношення

В сукупності всі кон’юнкції ДНФ покривають всю множину . Справедливе і обернене: якщо всі елементи деякого інтервалу належать , то існує ДНФ функції , яка містить кон’юнкцію . Зокрема, ДДНФ функції відповідає просто переліку елементів .

Алгоритм побудови тупикової днф

1. Будуємо імплікантну таблицю, рядки якої відповідають імплікантам (тобто інтервалам), стовпці – елементам , а на перетині -го рядка і -го стовпця знаходиться 1, якщо -та кон’юнкція (-й інтервал) покриває -й елемент множини , в противному випадку на перетині знаходиться 0.

2. Шукаємо мінімальну комбінацію рядків таку, щоб в кожен стовпець входила хоча б одна 1. Диз’юнкція цих рядків дасть всі тупикові ДНФ.

3. Серед всіх тупикових ДНФ вибираємо мінімальну.

Приклад. Одержимо тупикову ДНФ для булевої функції з приклада 1, йдучи за алгоритмом.

	000	001	101	110	111
00-	1	1	0	0	0
-01	0	1	1	0	0
1-1	0	0	1	0	1
11-	0	0	0	1	1

Ця таблиця має два покриття: їх утворюють перший, другий і четвертий рядки та перший, третій і четвертий рядки.

Таким чином, знайдені всі тупикові ДНФ:

,