Мінімізація булевих функцій

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

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

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

Будь-яку елементарну кон'юнкцію А, що входить до складу елементарної кон'юнкції В і містить менше змінних, ніж кон'юнкція В, називають власною частиною кон'юнкції В, і вважають, що кон'юнкція А покриває кон'юнкцію В.

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

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