БЛЕЙКА АЛГОРИТМ

— алгоритм получения сокращенной дизъюнктивной нормальной формы (ДНФ) булевой функции из произвольной ДНФ. Б. а. основан на теореме Блейка: если в произвольной ДНФ булевой ф-ции произвести все возможные обобщенные склеивания, а затем устранить все элементарные поглощения, то в результате получится сокращенная ДНФ ф-ции. Операция обобщенного склеивания состоит в применении тождественного соотношения , не изменяющего значения булевой ф-ции. В ряде случаев Б. а. определяет миним. форму булевой ф-ции: если сокращенная ДНФ булевой ф-ции не содержит отрицания переменных, то она является одновременно миним. формой, притом единственной; если в простых импли-кантах сокращенной ДНФ все переменные содержатся только с отрицаниями, то она будет и минимальной. Только монотонные булевы ф-ции имеют сокращенные ДНФ, не содержащие отрицаний переменных. Б. а. применяют при минимизации булевых ф-ций для получения их простых импликант. А. М. Богомолов.