Математика в Internet

ОСНОВИ ДИСКРЕТНОГО АНАЛІЗУ.
Автори: Н.Д.Федоренко,В.В.Демченко

     3.12. МЕТОД МАК-КЛАСКІ

      Метод застосовують тоді, коли булева функція задана нормальною формою.

Алгоритм методу використовує наступні етапи:

1. Кожній констинуенті присвоюється індекс - число одиниць термів та номер - відповідне число в десятковій системі числення.

Наприклад, ,

індекс - 3, номер 14. Тут:

;

;

;

.

Отримані результати заносяться в таблицю, в першому рядку якої записують індекси, а в другому - номери констинтуент.

2. Виконується склеювання за правилом: нехай i - індекс, j - індекс,. Склеюються ті констинтуенти , різниця між та є степенем двійки, тобто



При склеюванні, справа вказується величина різниці. Склеювання продовжується доти, поки воно можливо (різниці степені-двійки). Склеювати можна лише сусідні індекси. Алгоритм методу розглянемо на прикладі.

      Приклад 8. Методом Мак-Класкі мінімізувати булеву функцію, нормальна форма якої

.

Розв'язання. Запишемо всі констинтуенти через індекси та присвоєні номери (десяткове числення).



















Отримані результати занесемо в таблицю 15. Таблиця 15.


Враховуючи, що склеювати можна лише сусідні індекси, бачимо:

1) констинтуенту з індексом 0 склеїти ні з якою не можна, бо немає констинтуент з індексом 1.

2) Процес склеювання

I

II

Знову проведемо склеювання I та II, у яких різниці однакові



Процес склеювання закінчено.

Отримані результати запишемо у виді констинтуент ліва дужка вказує на терми, які треба виключити із констинтуент, що залишилися.







Таким чином, мінімальна нормальна форма отримана за методом Мак-Класкі для функції f має вид:

      Зауважимо, що реалізація методу Мак-Краскі на ПК більш простіша, ніж реалізація інших методів. Всі розглянуті методи використовують для функцій, у яких невелика кількість змінних.




ЗМІСТ