4.6. Локальные упрощения днф

Дизъюнктивная нормальная форма безызбыточна, если из нее нельзя удалить ни одной элементарной конъюнкции и ни одного литерала из какой-либо конъюнкции. Это равносильно тому, что из представляемой данную ДНФ троичной матрицы нельзя удалить ни одну из строк и ни одно из значений 0 или 1 нельзя заменить на «–». Локальные упрощения ДНФ сводятся к поиску и последовательному удалению таких элементарных конъюнкций и литералов до тех пор, пока данная ДНФ не станет безызбыточной. Простейшие случаи подобного сокращения определяются, например, формулами:

А х  А = А; Ах  х = А  х; А х  Вх  АВ = А х  Вх.

Более сложный случай представляет ДНФ х₁х₂ х₃  х₁х₂ х₄  х₁ х₂ х₃  х₁ х₂ х₄  х₃ х₄, где конъюнкция х₃ х₄ является избыточной. Действительно, если ее заменить на х₃ х₄ 1 = х₃ х₄ (х₁ х₂  х₁х₂ х₁ х₂ х₁х₂), а затем раскрыть скобки, то каждая из конъюнкций ранга 4 окажется поглощаемой некоторой из конъюнкций ранга 3, присутствующей в исходной ДНФ.

Исходя из выше сказанного, отметим два вида избыточности:

D = k  D = D и D = хk  D = k  D,

где k – элементарная конъюнкция, х – литерал, входящий в элементарную конъюнкцию хk, D – некоторая ДНФ, D – ДНФ, получаемая из D удалением конъюнкции k.