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

                                           94
Операция замыкания. Основные замкнутые классы.
__________________________________________________________________________________________
                   �a 0 =0 ;
                   �
                   �a 0 ⊕ a1 =0 ;
                   �a 0 ⊕ a 2 =1;
                   �
                   �a 0 ⊕ a 3 =1;
                   �
                   �a 0 ⊕ a 2 ⊕ a 3 ⊕ a 23 =1;
                   �a 0 ⊕ a1 ⊕ a 3 ⊕ a13 =0 ;
                   �
                   �a 0 ⊕ a1 ⊕ a 2 ⊕ a12 =1;
                   �a ⊕ a ⊕ a ⊕ a ⊕ a ⊕ a ⊕ a ⊕ a =1.
                   � 0     1     2     3     12 13 23 123



       Учитывая свойства операции «сложение по модулю 2»:
                           1 ⊕ 1 =0 ; 0 ⊕ 1 =1;
                              0 ⊕ 0 =0 ; 1 ⊕ 0 =1,
находим коэффициенты полинома Жегалкина
           a 0 =a1 =a12 =0 ,             a 2 =a 3 =a 23 =a13 =a123 =1
и выписываем полином третьей степени:
                    P (x , y , z ) == y ⊕ z ⊕ yz ⊕ xz ⊕ xyz .

2.    Метод эквивалентных преобразований. Этот метод применяется в
том случае, когда функция f ( x1 , ..., x n ) задана в виде формулы алгебры ло-
гики. Суть метода состоит в том, чтобы, исходя из свойств логических
операций, построить эквивалентную заданной формулу, содержащую
только символы операций логического умножения и сложения по модулю
2.
      При этом следовать схеме:
      а) построить д.н.ф. для заданной формулы;
      б) в полученной д.н.ф. выразить дизъюнкцию через конъюнкцию и
      отрицание:
                             u ∨ v ∨ w =�(u v w );                         (1)
      в) в полученной в пункте б) формуле освободиться от отрицания, ис-
      пользуя эквивалентность:
                                   �u =u ⊕1;                               (2)
      г) раскрыть скобки в полученном выражении, пользуясь свойством
      дистрибутивности операции ⊕ относительно логического умноже-
      ния
                            u (v ⊕ w ) =uv ⊕ uw ;                          (3)
      д) привести подобные члены по правилу:
                                     u ⊕ u =0.                             (4)