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

          Пример 1. Построить полином Жегалкина для функции
 f � x , y , z � � �01110 011�.
          Решение. Запишем общий вид полинома Жегалкина для функции,
зависящей от 3-х переменных:
         P � x , y , z � � a 0 � a1 x � a 2 y � a 3 z � a12 xy � a13 xz � a 23 zy � a123 xyz .
          Составим систему уравнений:
                           �a 0 � 0 ;
                           �
                           �a 0 � a1 � 0 ;
                           �a 0 � a 2 � 1;
                           �
                           �a 0 � a3 � 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)


                                             43