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

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

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

     Пример 2. Построить сокращенную ДНФ для функции
                            f =( x ∨ y )( x ∨ y ∨ z ) .
     Решение. Раскрывая скобки по 1-му дистрибутивному закону, полу-
чаем ДНФ; затем применяем операцию поглощения:
          f =( x ∨ y )( x ∨ y ∨ z ) = xx ∨ x y ∨ xy ∨ yy ∨ xz ∨ yz =
             =xy ∨ ( xy ∨ y ) ∨ xz ∨ yz =( x y ∨ 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 ),
                                     f (σ 1 ,σ 2 ,...,σ n )=1
                                                                1   2   n




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


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

1. Для функции f =(0 0101111) построить несколько ДНФ. Указать крат-
   чайшую, минимальную. Среди э.к. определить, какие являются