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

    Определение 5. Сокращенной ДНФ функции f называется дизъ-
юнкция всех простых импликантов функции f .
    Сокращенная ДНФ определяется однозначно для функции f .

           Метод построения сокращенной ДНФ функции f
      Шаг 1. Построить ДНФ для функции f .
      Шаг 2. Производить операцию обобщенного склеивания
                      XK 1 � XK 2 � XK 1 � XK 2 � K 1 K 2
до тех пор, пока это возможно.
      Шаг 3. Производить операцию поглощения
                              K1 � K1 K 2 � K1 .
      В результате приходим к сокращенной ДНФ, учитывая, что K 1 K 1 � 0
и K1 � K1 � K1 .

     Пример 2. Построить сокращенную ДНФ для функции
                             f � � x � y �� x � y � z � .
     Решение. Раскрывая скобки по 1-му дистрибутивному закону, полу-
чаем ДНФ; затем применяем операцию поглощения:
          f � � x � y �� x � y � z � � xx � xy � xy � yy � xz � yz �
          � xy � � xy � y � � xz � yz � � xy � y � � yz � xz �
          � � y � yz � � xz � y � xz
 — сокращенная ДНФ.

      Определение 6. ДНФ функции f � x1 , x 2 ,..., x n � называется совершен-
ной, если она составлена из попарно различных э.к. ранга n , т.е. формула
вида:
              f � x1 , x 2 , ... , x n � � � � � � x1� & x 2� & ... & x n� � ,
                                                              1   2    n

                                     f � 1 ,� 2 ,...,� n �1

где дизъюнктивная сумма берется по всем наборам �� 1 ,� 2 ,...,� n � , на кото-
рых f �� 1 ,� 2 ,...,� n � � 1 . Ясно, что функция f � x1 , x 2 ,..., x n � отлична от тож-
дественного нуля.
      В следующем параграфе подробно рассматриваются совершенные
нормальные формы и их нахождение, имеющие важное значение в прило-
жениях.




                                                  28