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

                                  K 1 � x z � x � y �,
                                  K 2 � x z � x � y �� y � z �,
                                  K 3 � x z � x � y �� y � z �� x � z �.

      Рассмотрим два способа построения ДНФ и КНФ.
      Способ 1. (Метод эквивалентных преобразований). Пусть булева
функция f � x1 , x 2 , ... , x n � задана формулой. Алгоритм построения ДНФ и
КНФ состоит в следующем:
      Шаг 1. Формулу преобразовать так, чтобы в ней были только опера-
ции � , & и �.
      Шаг 2. Добиться с помощью законов де Моргана, чтобы знак отри-
цания стоял лишь над отдельными переменными.
      Шаг 3. Раскрыть скобки по 1-му дистрибутивному закону
A B  C   AB  AC при построении ДНФ и по 2-му дистрибутивному
закону A � BC � � A � B �� A � C � при построении КНФ.

         Способ 2. (С использованием таблицы истинности).
         Шаг 1. Пусть функция f � x1 , x 2 , ... , x n � задана таблицей или набором
своих значений. Воспользоваться разложением функции по переменным
x1 , x 2 , ... , x n :
             f � x1 , x 2 , ... , x n � � � � �� x1� 1 & x 2� 2 & ... & x n� n & f �� 1 ,...,� n �� (�)
                                        � 1 ,� 2 ,...,� n

при построении ДНФ и
       f � x1 , x 2 , ... , x n � �         &
                                      ��1 ,� 2 ,...,� n   �
                                                           �x   �1
                                                                1
                                                                     � x 2� 2 � ... � x n� n � f �� 1 ,..., � n ��   (��)
при построении КНФ.
     Шаг 2. Полученные формулы по возможности упростить с помощью
основных равносильностей алгебры логики высказываний.
               a � b � a � b;
               a & a � 0 , a � a � 1;
                        a � b � �a � b ��b � a � � �a � b ��b � a � � a b � ab ;
                                                            �
                        a � b � a � b � a & b � �a & b � � �a � b � a � b ;�                        �        �
                        a � b � a b � ab ;                           a � 1 � 1;
                        a � b � a � b � a b ; a�b � ab � a � b ; и т .д .

     Пример 1. Методом эквивалентных преобразований для функции
                      f � x , y , z � � � x � y � � yz
построить ДНФ и КНФ.


                                                                      23