Дискретная математика. Элементы теории, задачи и упражнения. Часть 2. Булгакова И.Н. - 33 стр.

вующих этим наборам элементарных дизъюнкций является СКНФ задан-
ной функции:
                        K c � � x � y � z �� x � y � z �� x � y � z �� x � y � z �.
          Рассмотренные примеры являются иллюстрацией к первому способу
построения СКНФ и СДНФ, основанному на представлениях (1) и (2).
Применяется он, как правило, для функций, заданных таблицей истинно-
сти или набором значений. Если же функция задана аналитически, т.е. при
помощи формулы, то для нее нужно сначала построить таблицу истинно-
сти, а затем применять описанный метод.
          Второй способ построения СДНФ и СКНФ состоит в эквивалентном
преобразовании формулы, реализующей функцию, к виду (1) или (2). Как
уже отмечалось, совершенные дизъюнктивная или конъюнктивная нор-
мальные формы функции f � x1 , ..., x n � отличаются от обычных тем, что
каждое слагаемое СДНФ и каждый сомножитель СКНФ содержит все пе-
ременные x1 , ..., x n в некоторых «степенях». Это свойство дает возмож-
ность сформулировать следующие правила.
          1. Для получения СДНФ реализуемой формулой функции
 f � x1 , ..., x n � � 0 нужно построить ДНФ этой функции (см. п. 5.2). Затем,
если какая-нибудь конъюнкция ДНФ не содержит переменной x l , заме-
нить ее парой конъюнкций K j
                                           K j xl � K j xl .                        (4)
Замену производить до тех пор, пока каждое слагаемое ДНФ не будет со-
держать всех переменных x1 , ..., x n (их отрицаний или их самих).
          2. Для получения СКНФ реализуемой формулой функции
 f � x1 , ..., x n � � 1 нужно построить КНФ этой функции. Затем, если какая-
нибудь дизъюнкция D j КНФ не содержит переменной x l , заменить ее па-
рой дизъюнкций
                                           �D j � x l ��D j � x l �.                (5)
          Замены (4) и (5) являются эквивалентными, так как в силу первого
дистрибутивного закона
                             K j xl � K j xl � K j � x l � xl � � K j �1 � K j ,
а в силу второго дистрибутивного закона
                         �D j � x l ��D j � x l � � D j � x l x l � D j � 0 � D j .
    Пример 3. Для функции f � x , y , z � � x � z ~ xy построить СДНФ и
СКНФ.
    Решение. Сначала строим нормальные формы:
                 D � xy � xz � yz , K � � x � z �� x � y �.


                                          33