Алгоритм Блейка

Матеріал з Вікіпедії — вільної енциклопедії.

Блейка алгоритм — алгоритм отримання скороченої диз'юнктивної нормальної форми (ДНФ) булевої функції із довільної ДНФ.

Алгоритм оснований на теоремі Блейка:

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

Операція узагальненого зклеювання полягає в застосуванні тотожного співвідношення

AC ∨ B¬C = A¬C ∨ B¬C ∨ AB,

яке не змінює значення булевої функції.

В ряді випадків алгоритм Блейка визначає мінімальну форму булевої функції:

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

Тільки монотонні булеві функції мають скорочені ДНФ, які не мітять заперечень змінних.

Алгоритм Блейка застосовують при мінімізації булевих функцій для отримання їхніх простих імплікант.