Алгоритм Блейка — алгоритм отримання скороченої диз'юнктивної нормальної форми (ДНФ) булевої функції із довільної ДНФ.
Алгоритм оснований на теоремі Блейка:
- Якщо в довільній ДНФ булевої функції виконати всі можливі узагальнені зклеювання, а потім усунути всі елементарні поглинання, то в результаті отримаємо скорочену ДНФ функції.
Операція узагальненого зклеювання полягає в застосуванні тотожного співвідношення
- AC ∨ B¬C = AС ∨ B¬C ∨ AB,
яке не змінює значення булевої функції.
В ряді випадків алгоритм Блейка визначає мінімальну форму булевої функції:
- якщо скорочена ДНФ булевої функції не містить заперечувань змінних, то вона є одночасно мінімальною формою, при тому єдиною;
- якщо в простих імплікантах скороченої ДНФ всі змінні містяться тільки з запереченням, то вона буде і мінімальною.
Тільки монотонні булеві функції мають скорочені ДНФ, які не мітять заперечень змінних.
Алгоритм Блейка застосовують при мінімізації булевих функцій для отримання їхніх простих імплікант.
Джерела інформації
Див. також
