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

                                                     75
Операция замыкания. Основные замкнутые классы.
__________________________________________________________________________________________
    Применяя 2-ой дистрибутивный закон в полученной ДНФ, построим
КНФ для данной функции.
           f ( x, y, z ) =( xy ∨ x y ) ∨ yz =(xy ∨ x )( xy ∨ y ) ∨ yz =
                =( x ∨ x )( y ∨ x )( x ∨ y )( y ∨ y ) ∨ yz =
                =( y ∨ x )( x ∨ y ) ∨ yz =( y ∨ x ∨ yz )( x ∨ y ∨ yz ) =
           =( y ∨ x )( x ∨ z ∨ y )( x ∨ y ∨ z )( x ∨ y ∨ y ).
     Учитывая, что x ∨ y ∨ y = x ∨1 =1 , получим другую КНФ, равно-
сильную построенной:
                     f (x, y , z ) =(x ∨ y )( x ∨ y ∨ z )(x ∨ y ∨ z ) .

      Пример 2. Построить ДНФ и КНФ для функции f =(11 0 10 0 11) .
      Решение. Строим таблицу истинности для функции, зависящей от
трех переменных, т.к. длина ее двоичного набора равна 8 =2 3 (n =3).
      По формуле (∗) с учетом, что K& 1 = K , K& 0 =0 ,имеем
                 f (x , y , z ) = x 0 y 0 z 0 & 1 ∨ x 0 y 0 z 1 & 1 ∨ x 0 y 1 z 0 & 0 ∨
                 ∨ x 0 y 1z 1 & 1 ∨ x 1 y 0 z 0 & 0 ∨ x 1 y 0 z1 & 0 ∨ x 1 y 1z 0 & 1 ∨
                 ∨ x1 y 1 z 1 & 1 = x y z ∨ x y z ∨ x y z ∨ xy z ∨ x y z −ÄÍÔ 1 .
     Учитывая, что a b ∨ a c =a (b ∨ c ), можно получить другие ДНФ для
данной функции:
                f =( x y z ∨ x y z ) ∨ x yz ∨ ( x y z ∨ x y z ) =
                          = x y (z ∨ z ) ∨ x y z ∨ xy (z ∨ z ) =
                          = x y ∨ x y z ∨ x y −ДНФ 2 .

                                                         f =( x y ∨ x y z ) ∨ x y =
                                                           = x ( y ∨ y z ) ∨ xy =
                                                           = x ( y ∨ y )( y ∨ z ) ∨ x y
                                                            =x (y ∨ z )∨ x y
                                                           = x y ∨ x z ∨ x y −ÄÍÔ 3 .
     x      y      z       f
     0      0      0       1
                                        Разлагая данную функцию f по формуле (**)
     0      0      1       1
     0      1      0       0            с учетом, что D ∨1 =1, D ∨ 0 = D , имеем
     0      1      1       1                                 (                            )(                  )(
                                         f ( x , y , z ) = x 0 ∨ y 0 ∨ z 0 ∨1 x 0 ∨ y 0 ∨ z 1 ∨1 x 0 ∨ y 1 ∨ z 0 ∨
     1      0      0       0              (                         )(                           )(
                                        ∧ x 0 ∨ y 1 ∨ z 1 ∨1 x 1 ∨ y 0 ∨ z 0 ∨ 0 x 1 ∨ y 0 ∨ z 1 ∨ 0 x 1 ∨ y            )(
                                        ∧ (x                      ∨1) =(x          ∨ y 0 ∨ z 1 )(x 0 ∨ y 1 ∨ z 1 )(x 0 ∨ y 1 ∨ z 0
     1      0      1       0                   1
                                                   ∨ y1 ∨z1                    1
     1      1      0       1
     1      1      1       1            =( x ∨ y ∨ z )( x ∨ y ∨ z )( x ∨ y ∨ z ) −КНФ1 .