Правила приведения к СДНФ.

Из определения СДНФ следует, что формула F является СДНФ, если она отвечает следующим условиям (иначе, если она обладает следующими свойствами, называемыми “свойствами совершенства ”):

а) в ней нет двух одинаковых слагаемых (дизъюнктивных членов);

б) ни одно слагаемое не содержит двух одинаковых множителей;

в) никакое слагаемое не содержит переменную вместе с её отрицанием;

г) в каждом слагаемом содержится в качестве множителя либо каждая из переменных , либо её отрицание , где .

Условия а) ÷г) являются, таким образом, необходимыми и достаточными для того, чтобы ДНФ являлась СДНФ. Вместе с тем, эти условия дают возможность высказать правила, позволяющие приводить с помощью равносильных преобразований любую не тождественно ложную формулу к СДНФ, которая является для неё единственной. Итак, приведем эти правила.

Пусть дана произвольная формула F Проделаем пять операций, которые приведут формулу к СДНФ.

1. Приведем её с помощью равносильных преобразований к какой-либо ДНФ.

2. Если какое-нибудь из слагаемых этой ДНФ, например, В не содержит переменную , то заменим его суммой . Эта замена представляет собой равносильное преобразование, так как . Проделав операции по п.2, мы удовлетворили требованиям п. г) свойств совершенства.

3. Если в полученном выражении окажутся одинаковые слагаемые, то, удалив все, кроме одного из них ( в силу закона идемпотентности (8)), мы получим опять равносильное выражение. Здесь мы удовлетворили п. а) свойств совершенства.

4. Если после этого в некоторых слагаемых окажется по несколько одинаковых множителей, то лишние (в силу закона идемпотентности (9)) удаляем. Таким образом, мы удовлетворяем п. б) свойств совершенства.

5. Наконец, удаляем все те слагаемые, которые содержат какую-нибудь переменную вместе со своим отрицанием , так как, в силу закона противоречия (15), они являются тождественно ложными выражениями – удовлетворили п. в) свойств совершенства.

Если бы все слагаемые оказались таковыми, то и вся ДНФ была бы тождественно ложной. А тогда это значило бы, что исходная формула F – тождественно ложная формула и не имеет СДНФ. Именно поэтому мы утверждаем: если формула F не является тождественно ложной, то в её произвольной ДНФ должны присутствовать слагаемые, удовлетворяющие условию п. в) свойств совершенства.

После удаления всех слагаемых, содержащих какую-нибудь переменную вместе с её отрицанием, мы получили ДНФ, удовлетворяющую всем свойствам совершенства, т.е. СДНФ.

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