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

       В первом слагаемом ДНФ недостает переменной z , во втором – пе-
ременной y , в третьем – x . В соответствии с (4) запишем:
                    D � xyz � xyz � xyz � x yz � xyz � x yz .
Убрав лишние слагаемые, находим СДНФ:
                           Dc � xyz � xyz � xyz � x yz .
       В первом сомножителе КНФ не достает переменной y , во втором –
z ; поэтому в соответствии с (5) имеем СКНФ:
               K c � � x � y � z �� x � y � z �� x � y � z �� x � y � z �.


                       ЗАДАЧИ И УПРАЖНЕНИЯ
   1. Построить совершенные ДНФ и КНФ для следующих функций (для
      функций, заданных формулами, предварительно построить таблицы
      истинности):
         1) � x � y � � yz;
         2) f � �01101100 �;
         3) �� x � y � ~ z � | xyz;
         4) f � �0100110000 110010 �;
         5) � x � y �� x � y �� x ~ y �� y | x �.

2. Преобразовать заданные ДНФ в совершенные:
        1. xy � yz � xy;
        2. x 1 � x 2 x 3 � x 1 x 2 x 4 ;
        3. x � xyz � xy;
        4. xy � xyz � y � xy;
        5. x1 x2 � x 2 x3 � x3 x1 .

3. Преобразовать заданные КНФ в совершенные:
   1) � x � y �� z � y �z;                     2) �u � v ��u � v � w ��u � v �;
   3) � x 1 � x 2 �� x 2 � x 3 �� x 3 � x 4 �; 4) ( x ∨ y )( z ∨ y ) y;
   5)  x1  x2  x1  x3  x4 .

4. Построить СДНФ и СКНФ с помощью эквивалентных преобразований:
        1) �� x � y � � z � ~ � x � � y � z ��;
        2) � x 1 � x 2 � � � x 3 � x 4 �;
        3) �� x � z � � y � � �� x | y � � y �;
        4) � y ~ z �� z ~ x �� x � y �;
          5) (x1 | x2 ) → (x3 | x4 ).
                                          34