В чем заключается метод Блейка для построения минимальной ДНФ?

Метод Блейка позволяет получить сокращённую дизъюнктивную нормальную форму (ДНФ) булевой функции из её произвольной ДНФ. ido.tsu.ru multiurok.ru

В основе метода лежит теорема Блейка, согласно которой, чтобы получить сокращённую ДНФ, нужно выполнить: ido.tsu.ru

1. Всевозможные обобщённые склеивания смежных конъюнкций. ido.tsu.ru
2. Всевозможные поглощения конъюнкций. ido.tsu.ru

В результате получится сокращённая ДНФ функции. multiurok.ru

Алгоритм метода Блейка-Порецкого: ido.tsu.ru

1. Построить список троичных векторов, представляющих конъюнкции ДНФ. ido.tsu.ru Удалить из списка все векторы, поглощаемые другими. ido.tsu.ru
2. Найти для вектора α очередной смежный вектор β среди векторов, расположенных в списке выше α. ido.tsu.ru
3. Если вектор γ поглощается хотя бы одним вектором из списка, то удалить γ и перейти к шагу 2. ido.tsu.ru
4. Если вектор γ не поглощается, то удалить все векторы, поглощаемые им. ido.tsu.ru
5. Если вектор α не удалён, то перейти к шагу 2. ido.tsu.ru

В конце невычеркнутые из списка векторы будут задавать сокращённую ДНФ. ido.tsu.ru