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

                                                                        74
Операция замыкания. Основные замкнутые классы.
__________________________________________________________________________________________
     Шаг 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 ) =          ∨          (x
                                         (σ1 ,σ 2 ,...,σ n )
                                                                   σ1
                                                                   1
                                                                        & x 2σ 2 & ... & x σn n & f (σ 1 ,...,σ n ))     (∗)
при построении ДНФ и
       f ( x1 , x 2 , ..., x n ) =           &
                                    (σ 1 ,σ 2 ,...,σ n   )
                                                          (x   σ1
                                                               1    ∨ x σ2 ∨ ... ∨ x nσ ∨ f (σ 1 ,..., σ n ))
                                                                                 2       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
построить ДНФ и КНФ.
      Решение. Применяя основные равносильности и 1-ый дистрибутив-
ный закон, строим ДНФ:
        f ( x , y , z ) =( x ⊕ y ) → yz =( x ↔ y ) ∨ yz =( x → y )( y → x ) ∨ yz =
                     =( x ∨ y )( y ∨ x ) ∨ yz = x y ∨ xx ∨ yy ∨ xy ∨ yz =
                     = xy ∨ x y ∨ yz .