Далі на отриманої карті знаходимо все максимально можливі блоки одиниць виду 2 k × 2 l; k, l ∈ N. враховуючи той факт, що карта закольцована. Блоки можуть перетинатися, але не повинні включати один одного. Далі для кожного блоку виписується вектор, в якому в разі, якщо змінна в межах цього блоку змінювала значення, знак «-», якщо ж не змінює, то її значення в межах блоку. Для позицій вектора i. в яких стоїть знак σ ∈? в ЕК додається xi σ. Диз'юнкція всіх отриманих ЕК і є скорочена ДНФ.
[Ред] Приклад
Знайдемо скорочену ДНФ для функції f = (1010 0110 0111 1101) методом карт Карно.
Рішення
Будуємо карту:
На підставі карти отримуємо наступні блоки:
[Ред] Побудова скороченою ДНФ по досконалої ДНФ за допомогою алгоритму Квайна
Алгоритм Квайна побудови скороченою ДНФ по досконалої ДНФ: 0) i: = 1 1) Поки можливо до доданком рангу n-i + 1 застосовувати неповне склеювання:
2) поки можливе поглинання 3) i ++; if (i<=n) goto 1
[Ред] Побудова ДНФ Квайна
ДНФ, яку отримують шляхом викидання всіх простих импликант, відповідних максимальним гранях, які покриваються ядром, називається ДНФ Квайна.
Алгоритм побудови ДНФ Квайна:
1. отримати скорочену ДНФ;
2. Визначити ядрові межі;
3. видалити імпліканти, що покриваються ядром.
Отримана ДНФ, є ДНФ Квайна.
[Ред] Побудова ДНФ σT (суми тупикових)
[Ред] Побудова всіх тупикових ДНФ
Нехай ми шукаємо все тупикові рішення для ФАЛ f. Випишемо таблицю M (таблицю Квайна), в якій стовпцями відповідають елементи з Nf (набори, на яких функція приймає значення 1), рядках відповідають максимальні межі. В осередку коштує 1, якщо грань, відповідна рядку містить набір, відповідний колонки.
Потім виписуємо КНФ функції покриття в такий спосіб:
Нехай кожному рядку відповідає деяка змінна yi.
Для кожного стовпця, змінні, відповідні рядках в яких в даному стовпці стоїть 1, запишемо через логічне або. Функція покриття дорівнює добутку таких сум для кожного стовпчика.
[Ред] Приклад
Розкриваючи дужки і приводячи подібні, отримуємо:
Далі, визначимо ядрові точки, тобто ті αi. у яких в стовпці тільки одна одиниця. Такими є α1. α3. α5. α7. α9. α10. Відповідно, ядровими гранями є ті межі, які відповідають кон'юнкції, яким належать ядрові вершини (дивимося на рядки, в яких хоча б для одного з обраних стовпців αi варто одиниця), тобто K1. K2. K4. K5. K7. Диз'юнкція цих кон'юнкція є перетин тупикових.
Для знаходження всіх тупикових ДНФ побудуємо КНФ, елементарниё диз'юнкції якої будуть складатися з БП, відповідних тим кон'юнкції, в які входить розглянута точка αi (тобто, всього диз'юнкцій стільки ж, скільки є точок, де функція приймає одиничне значення, причому перша диз'юнкція буде містити ті БП, які відповідають тим ЕК, яким належить α1 (в даному прикладі це K1), друга - ті, які відповідають ЕК, яким належить α2 (K1. K2. K3), і так далі):
Після розкриття і приведення подібних отримаємо ДНФ, що складаються з ЕК, які будуть відповідати тупиковим ДНФ, причому БП в ЕК будуть відповідати ЕК, що входять в тупикову ДНФ:
Матеріали до іспиту