Алгоритм знаходження невизначених коефіцієнтів

Алгоритм включає такі етапи:

1. Цикл за рядками – перегляд нульових рядків: вибрати рядок системи (16.3), у якій функція приймає нульове значення . Дорівняти нулю всі коефіцієнти цього рядка.

2. Якщо всі нульові рядки переглянуті, то перейти до пункту 3, інакше – повернутися до пункту 1.

3. Викреслювання рівних нулю коефіцієнтів з рядків з одиницями: із всіх рядків, де , викреслити рівні нулю коефіцієнти, визначені в пункті 1.

4. Модифікована система рівнянь: переписати систему (16.3) з урахуванням виконаних перетворень.

5. Вибір мінімального покриття: у модифікованій системі вибрати й покласти рівними одиниці мінімальну кількість коефіцієнтів з мінімальним числом індексів, щоб задовольнити дану систему.

6. Визначення мінімальної форми функції: скласти мінімальну ДНФ за обраними коефіцієнтами.

Приклад 16.1. Мінімізувати функцію від трьох змінних Y=1 на наборах {1, 2, 3, 4} методом невизначених коефіцієнтів з одержанням МДНФ.

Розв’язок. Таблицю невизначених коефіцієнтів можна зобразити у спрощеному вигляді (табл. 16.2).

Таблиця 16.2 – Спрощений вигляд таблиці функції для методу невизначених коефіцієнтів

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

Коефіцієнти рядків, де , дорівнюють нулю. З рядків, де , викреслюються коефіцієнти, що зустрічаються в рядках, де .

Виписуються коефіцієнти, що залишилися, з одержанням тим самим модифікованої системи:

(16.4)

З (16.4) мінімальний результат відповідає формі:

.

16.3 Контрольні запитання

1. На яких основних положеннях базується метод невизначених коефіцієнтів?

2. Яке узагальнене подання ДНФ функції від трьох змінних?

3. Які основні етапи алгоритму знаходження невизначених коефіцієнтів?

4. У якому базисі має бути подана функція, щоб для мінімізації можна було застосувати метод невизначених коефіцієнтів?

5. Коли диз’юнкція деякої кількості коефіцієнтів дорівнює нулю?

6. Коли диз’юнкція деякої кількості коефіцієнтів дорівнює одиниці?

7. Як вибирається розв’язок модифікованої системи рівнянь у методі невизначених коефіцієнтів?

8. Скільки рядків має вихідна система рівнянь при мінімізації функції від чотирьох змінних методом невизначених коефіцієнтів?

9. Що таке мінімальне покриття в методі невизначених коефіцієнтів?

17 МІНІМІЗАЦІЯ БУЛЕВИХ ФУНКЦІЙ: МЕТОД КАРТ КАРНО

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