Дизъюнктивная нормальная форма и совершенная дизъюнктивная нормальная форма

Определение 1.Элементарной конъюнкцией n переменных называется конъюнкция переменных или их отрицаний.

Элементарная конъюнкция n переменных может быть записана в виде

где

Определение 2.Дизъюнктивной нормальной формой (ДНФ) формулы А называется равносильная ей формула, представляющая собой дизъюнкцию элементарных конъюнкций.

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

Например, для формулы имеем

Среди многочисленных ДНФ А существует единственная ДНФ А, для которой выполняются перечисленные выше (п.7) четыре свойства совершенства.

Такая ДНФ А называется совершенной дизъюнктивной формулой формулы А (СДНФ А).

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

1. Путем равносильных преобразований формулы А получают одну из ДНФ А.

2. Если в полученной ДНФ А входящая в нее элементарная конъюнкция В не содержит переменную , то, используя равносильность

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

3. Если в ДНФ А входят две одинаковых элементарных конъюнкции В, то лишнюю можно отбросить, пользуясь равносильностью

4. Если некоторая элементарная конъюнкция В, входящая в ДНФ А, содержит переменную и ее отрицание , то B ~ 0, и В можно исключить из ДНФ А, как нулевой член дизъюнкции.

5. Если некоторая элементарная конъюнкция, входящая в ДНФ А, содержит переменную дважды, то одну переменную можно отбросить, пользуясь равносильностью ~ .

После выполнения описанной процедуры будет получена СДНФ А.

Пример. ДНФ .

Решение.Так как элементарная конъюнкция B ~ x, входящая в ДНФ А, не содержит переменной у, то, пользуясь равносильностью

заменим ее на две элементарных конъюнкции и . В результате получим

ДНФ

Так как теперь ДНФ А содержит две одинаковых элементарных конъюнкции , то лишнюю отбросим, пользуясь равносильностью

В результате получим

Так как элементарная конъюнкция содержит переменную y и ее отрицание , то ~ 0, и ее можно отбросить как нулевой член дизъюнкции.

Таким образом, получаем