Мінімізація ФАЛ
Абсолютно нормальні форми хоча й дають однозначні подання функції, але є дуже громіздкими. Реалізація СНФ програмно або Схемотехнічних є надлишкової, що веде до збільшення програмного коду, тому існують методи спрощення логічної запису - мінімізації.
Визначення : Перетворення логічних функцій з метою спрощення їх аналітичного подання називаються мінімізацією.
Існують два напрями мінімізації:
1. Найкоротша форма запису (ціль - мінімізувати ранг кожного терма). При цьому виходять найкоротші форми КДНФ, ККНФ, КПНФ.
2. Отримання мінімальної форми запису (ціль - одержання мінімального числа символів для запису всієї функції відразу).
При цьому слід врахувати, що ні один із способів мінімізації не універсальний!
Існують різні методи мінімізації:
1. Метод безпосередніх перетворень логічних функцій. (1.1)
При застосуванні даного методу:
а) Записуються ДСНФ логічних функцій
б) Форма перетвориться й спрощується з використанням аксіом алгебри логіки. При цьому, зокрема, виявляються у вихідному ДСНФ так звані сусідні min-терми, в яких є по одній не збігається змінної.
По відношенню до сусідніх min-термам застосовується закон склейки, значить ранг min-терма знижується на одиницю.
Визначення : Min-терми, утворені при склеюванні називаються импликантами.
Отримані після склейки імпліканти по можливості склеюють доти, поки склеювання стає неможливим.
Визначення : несклеивающиеся імпліканти називаються прошарками.
Визначення : Формула, що складається з простих импликант - тупикова.
Приклад:
</p>
0
0
0
1
0
0
1
1
0
1
0
1
0
1
1
1
1
0
0
0
1
0
1
0
1
1
0
0
1
1
1
0
Якщо в процесі склеювання утворюється форма R, що містить члени виду й то для неї справедливо вираз, що дозволяє додати до вихідної формі R кілька членів виду пар і і після цього продовжити мінімізацію.
Приклад:
Ми отримали мінімальну СНФ.
Метод невизначених коефіцієнтів. (1.2)
Суть методу полягає в перетворенні ДСНФ у МДНФ.
На підставі теореми Жигалкіна будь-яку ФАЛ можна представити у вигляді (розглянемо на прикладі трьох змінних):
Алгоритм визначення коефіцієнтів:
1. Вихідне рівняння розбити на систему рівнянь, рівних числу рядків у таблиці істинності.
2. Напроти кожного вираження поставити відповідне значення функції.
3. Вибрати рядок, у якій значення функції і прирівняти всі до нуля.
4. Переглянути рядки, де функція має одиничне значення, і викреслити всі коефіцієнти, що зустрічаються в нульових рядках.
5. Проаналізувати залишилися коефіцієнти в одиничних рядках.
6. Використовуючи правило, що диз'юнкція дорівнює 1 якщо хоча б один з, вибрати min-терми мінімального рангу. Причому віддавати перевагу коефіцієнтам, що зустрічаються в декількох рівняннях одночасно.
7. Записати вихідний вид функції.
Метод невизначених коефіцієнтів застосуємо для диз'юнктивної форми й непридатний для кон'юнктівной.
Приклад:
0
0
0
0
00
00
00
000
1
1
0
0
1
00
01
01
001
0
2
0
1
0
01
00
10
010
1
3
0
1
1
01
01
11
011
0
4
1
0
0
10
10
00
100
1
5
1
0
1
10
11
01
101
0
6
1
1
0
11
10
10
110
0
7
1
1
1
11
11
11
111
1
Отже, отримаємо
Метод Квайна (1.3)
Суть методу зводиться до того, щоб перетворити ДСНФ у МДНФ. Завдання мінімізації по методу Квайна полягає в попарному порівнянні импликант, що входять в ДСНФ із метою виявлення можливості склеювання по якийсь пременной так:
Таким чином, можна понизити ранг термів. Процедура проводиться до тих пір, поки не залишаєт...
