Математика в Internet |
Метод застосовують тоді, коли булева функція задана нормальною формою.
Алгоритм методу використовує наступні етапи:
1. Кожній констинуенті присвоюється індекс - число одиниць термів та номер - відповідне число в
десятковій системі числення.
Наприклад, ,
індекс - 3, номер 14.
Тут:
;
;
;
.
Отримані результати заносяться в таблицю, в першому рядку якої записують індекси, а в другому -
номери констинтуент.
2. Виконується склеювання за правилом: нехай i - індекс, j - індекс,.
Склеюються ті констинтуенти , різниця між та є степенем двійки, тобто
При склеюванні, справа вказується величина різниці. Склеювання продовжується доти, поки воно
можливо (різниці степені-двійки). Склеювати можна лише сусідні індекси.
Алгоритм методу розглянемо на прикладі.
Приклад 8. Методом Мак-Класкі мінімізувати булеву функцію, нормальна форма якої
.
Розв'язання. Запишемо всі констинтуенти через індекси та присвоєні номери (десяткове
числення).
Отримані результати занесемо в таблицю 15.
Зауважимо, що реалізація методу Мак-Краскі на ПК більш простіша, ніж реалізація інших методів. Всі розглянуті методи використовують для функцій, у яких невелика кількість змінних.
ЗМІСТ |