Правило склеювання клітинок і запису мінімальної ДНФ

1. Будується карта Карно, яка відповідає даній формулі.

2. Клітинки об'єднуються в групи, що позначають операції склеювання. У об'єднанні беруть участь тільки сусідні клітинки, в яких знаходяться одиниці.

3. У групу можна об'єднати тільки кількість клітинок, яка дорівнює числу 2 n, де n = 1,2,3,... При цьому група може мати тільки прямокутну або квадратну форму.

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

5. Кожна група клітинок, отримана після склеювання, відповідає тій імпліканті формулі, реальні змінні якої мають однакове значення для всіх клітинок групи. Змінні беруться без заперечення, якщо їм відповідає одиничне значення, та із запереченням в протилежному випадку.

6. Диз'юнкція всіх отриманих простих імплікант є результатом мінімізації формули і приводить до мінімальної ДНФ.

Приклад 3.3. Побудувати мінімальну ДНФ для формули:

(для спрощення запису формули знак кон’юнкції упущений).

Карта Карно для цієї функції має вигляд:

Імпліканти для цієї формули мають вигляд:

А – ,

B – .

Отже, мінімальна ДНФ заданої функції – f= Ú .▲

Приклад 3.4. Побудувати мінімальну ДНФ для формули:

Імпліканти для цієї формули мають вигляд:

А – ;

B – ;

C – .

Отже, мінімальна ДНФ заданої функції – f= Ú Ú .▲

Приклад 3.5. Побудувати мінімальну ДНФ для формули:

Імпліканти для цієї формули мають вигляд:

А – ;

B – ;

C – .

Отже, мінімальна ДНФ заданої функції – f= Ú Ú .▲

Аналогічно, з використанням карт Карно, можна побудувати мінімальну кон’юктивну нормальну форму, але склеювання проводити не по одиницях, а по нулях.

Поиск по сайту: