Построение сокращенной ДНФ

Один из методов построения сокращенной ДНФ – геометрический, ранее уже был изложен. Он нагляден, однако его применимость ограничена функциями трех аргументов. Для функций с большим числом аргументов необходимы аналитические способы.

Существует целый ряд методов синтеза сокращенной ДНФ. Суть всех этих методов – в последовательном упрощении логического выражения, обычно заданного в виде СДНФ. В процессе упрощения используются следующие преобразования:

1) склеивание –

2) поглощение –

3) неполное склеивание –

4) обобщенное склеивание –

Рассмотрим один из методов получения сокращенной ДНФ из СДНФ, известный как метод Блейка–Порецкого [ ], который заключается в неполном попарном склеивании всех элементарных конъюнкций СДНФ между собой, и затем – использовании правила поглощения. Эта процедура повторяется для элементарных конъюнкций меньшего числа переменных до тех пор, пока склеивание станет невозможным. Не вдаваясь глубоко в теорию, рассмотрим пример.

Пример. Получить сокращенную ДНФ функции, заданной в виде совершенной дизъюнктивной нормальной формы .

С целью формализации процесса пронумеруем все конъюнкции СДНФ:

Выполним все возможные неполные попарные склеивания конъюнкций четырех переменных, нумеруя получающиеся конъюнкции трех переменных парой индексов, относящихся к исходным конъюнкциям. Получим:

Теперь проведем процедуру поглощение конъюнкций. Легко видеть, что все конъюнкции четырех переменных поглощены коньюнкциями трех переменных. В результате получим:

Аналогичным образом выполним все возможные неполные попарные склеивания полученных элементарных конъюнкций трех переменных и проведем процедуру поглощения. В итоге имеем:

.

Дальнейшее склеивание невозможно, следовательно, сокращенная дизъюнктивная нормальная форма получена.