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

Разлагая данную функцию f по формуле (**) с учетом, что D � 1 � 1 ,
D � 0 � D , имеем
                   �                       ��             ��
  f ( x, y,z ) � x0 � y0 � z0 � 1 x0 � y0 � z1 � 1 x0 � y1 � z0 � 0 �    �
    �                      ��                        ��        ��
  � x0 � y1 � z1 �1 x1 � y0 � z0 � 0 x1 � y0 � z1 � 0 x1 � y1 � z0 �1 �         �
  � �x  � y1 � z1
         1
                        � 1� � � x
                               1
                                 � y 0 � z 1 �� x 0 � y 1 � z 1 �� x 0 � y 1 � z 0 � �
 � � x � y � z �� x � y � z �� x � y � z � � КНФ1 .
      Учитывая, что �a � b ��a � b � � a � b b � a � 0 � a , получим другую
КНФ, равносильную КНФ1:
          f � � x � y � z ��� x � y � � z z � � � x � y � z �� x � y � � КНФ 2 .
      Неоднозначность нормальных форм очевидна.

     Таким образом, применяя различные равносильные преобразования,
мы можем прийти к различным нормальным формам, реализующих одну и
ту же функцию. В связи с этим возникает возможность выбора более
предпочтительной реализации.


                            ЗАДАЧИ И УПРАЖНЕНИЯ

1. По данному набору �� 1 ,..., � n � значений переменных x 1 ,..., x n постро-
ить элементарную конъюнкцию, истинную только для этого набора значе-
ний переменных.
2. По данному набору �� 1 ,....� n � значений переменных x 1 ,..., x n построить
элементарную дизъюнкцию, ложную только для этого набора значений пе-
ременных.
3. С помощью эквивалентных преобразований привести к ДНФ формулы:
        1) � x � yz �� x � z �;
        2) �� x 1 � x 2 x 3 x 4 �� x 2 � x 4 � � x1 x 3 x 4 � � � x1 � x 4 �;
             3) � x � z � ~ � y � z � � xy;
             4) � x 1 x 2 � x 3 x 4 � | � x 1 � x 3 �;
             5) � x � � x ~ y �� � x � y.
4. С помощью эквивалентных преобразований привести к КНФ формулы:
             1) x � yz;
             2) �� x 1 x 2 � x 3 � � x 4 � � x;
             3) �� x 1 | x 2 � � x 3 � ~ x 1 x 4 ;
             4) �� xyz ~ � y � z �� y � � x ;
             5) � � x ~ yz � � � x � � y � z ��.
                                                     25