Основні результати

Розглянемо лише спрощення диз'юнктивних нормальних форм. Зазначимо, що за принципом двоїстості із методів спрощення ДНФ можна отримати методи спрощення КНФ.

Мінімальною ДНФ булевої функції називають ДНФ цієї функції, яка складається з найменшої можливої кількості букв.

Зауваження. Кожну букву враховують стільки разів, скільки вона зустрічається в ДНФ. Наприклад, ДНФ складається з 6 букв. ▲

Елементарну кон'юнкцію називають імплікантоюбулевої функції f (x ₁,..., х_n), якщо на довільному наборі значень змінних, на якому k перетворюється в 1, значення функції f такождорівнює 1. Іншими словами, k- імпліканта функції f, якщо функція k→ fтотожно дорівнює 1 (тобто виключено випадокk=1, f =0). Тут -- деякі змінні з множини { x ₁, x_n }.

Приклад 8.24. Елементарна кон'юнкціяk = ху є імплікантою функції , оскільки у разіk= 1 значення функції f обов'язково дорівнюватиме 1. ▲

Елементарну кон'юнкціюk називають простою імплікантою булевої функції f якщоk- імпліканта функції f, а елементарна кон'юнкція, одержана зk вилученням довільної букви, - не імпліканта

Диз'юнктивну нормальну форму, яка містить усі прості імплі­канта даної булевої функції, називають скороченою диз'юнктивною нормальною формою цієї функції (СДНФ).

Теорема 8.23. СДНФD булевої функції f задає цю функцію, тобто f = D.

Доведення. Якщо f (x ₁,..., х_n)=0 очевидно, не має жодноїпростої імпліканти. Але диз'юнкція порожньої множини членів дорівнює 0.

Нехай тепер f (x ₁,..., х_n)≠ 0. Розглянемо довільний набір такий, що =1. Елементарна кон'юнкція , яка входить у досконалу ДНФ функції f не є її імплі­кантою. Якщоk не є простою імплікантою, то можемо вилучити хоча б одну букву так, що отримана елементарна кон'юнкція k ₁буде імплікантою. Якщо імплікантаk₁ знову не проста, то вилучимо ще одну букву так, що отримана елементарна кон'юнкціяk₂ буде імплікантою функції f. Продовжуючи цей процес, через скінченну кількість кроків знайдемо просту імпліканту k '. За побудовою k ' має значення 1 на наборі , що розглядається. Оскільки D склада­ється з усіх простих імплікант функції f, то D має диз'юнктивним членом k ' і, отже, D приймає значення 1 на цьому наборі.

З іншого боку, нехай D на деякому наборі приймає значення 1. Тоді деяка проста імплікантаk₀ із D на цьому наборі дорівнює 1. Оскількиk₀ - імпліканта функції f то = 1.

Отже, значення f та й на будь-якому наборі значень змінних збігаються. ▲

Зауваження. Скорочена ДНФ булевої функції/єдина, оскільки множина всіх простих імплікант булевої функції визначена одно­значно (адже скорочена ДНФ є диз'юнкцією їх усіх). ▲

Зв'язок між мінімальною і скороченою ДНФ виражає така тео­рема.

Теорема 8.24.Мінімальну ДНФ булевої функції f отримують із скороченої ДНФ цієї функції вилученням деяких елементарних кон'юнкцій.

Доведення. Потрібно довести, що мінімальна ДНФ D_min довіль­ної булевої функції f є диз'юнкцією простих імплікант цієї функції (можливо, не всіх). Припустимо, що імпліканта k із D_min не проста. Тоді із k ₁ можна вилучити принаймні одну букву так, що отримана елементарна кон'юнкціяk₂ також буде імплікантою функції f Крім того, k ₂ приймає значення 1 на всіх наборах, на яких приймає значення 1 імплікантаk₁. Отже, в ДНФD_min. можемо замінитиk₁ наk₂ і отримати ДНФ D_*, яка також задає функцію f. За побудовою D _*, має менше букв, ніж Суперечність. ▲

Диз'юнктивну нормальну форму T, яка задає функцію(тобто f=T)називаютьтупиковою ДНФ цієї функції, якщо:

1) кожна елементарна кон'юнкція зT простою імплікантою f;

2) вилучення з T довільного диз'юнктивного члена приводить до ДНФT₁, яка не задає f, тобто f=T.

Теорема 8.25.Мінімальна ДНФ булевої функції є її тупиковою ДНФ.

Доведення цієї теореми випливає безпосередньо із означень мінімальної ДНФ і тупикової ДНФ. ▲

Зауваження. Існують тупикові ДНФ, які не є мінімальними. Одна й та сама булева функція f може мати декілька різних мінімальних ДНФ. ▲

Ізтеорем 8.24 та 8.25 випливає, що відшукання мінімальних ДНФ можна поділити на два етапи.

Перший етап полягає у побудові скороченої ДНФ.

Другий етап полягає у побудові всіх тупикових ДНФ. Після цього із отриманих тупикових ДНФ вибирають мінімальні.