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

      Булева функция, которой соответствует полином Жегалкина первой
степени, называется линейной. Функции, задаваемые формулами
                             x ~ y , x � y, x , x, x � y � z,
являются линейными. Множество всех линейных булевых функций обо-
значается через L , множество линейных функций, зависящих от n пере-
менных, — через L�n � . Для каждой функции f � L�n � имеет место пред-
ставление
                             f � x1 , ..., x n � � c 0 � c1 x1 � ... � c n x n , (7)
где коэффициенты c i принимают значения либо 0, либо 1.
      Из представления (7) следует, что число всех линейных функций от
n переменных равно 2 n �1 . Другими словами, мощность множества L�n �
равна 2 n �1 .
      Если функция f � L , то она называется нелинейной. Степень поли-
нома Жегалкина нелинейной функции не меньше 2. Элементарные функ-
ции xy , x � y , x � y , x y являются нелинейными.
      Справедливо утверждение (лемма о нелинейной функции):
      Если f � x1 , ..., x n � нелинейная функция, то, подставляя на места ее
переменных 0, 1, x , y , x , y , можно получить либо xy , либо xy .


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

1. Найти число монотонных элементарных конъюнкций ранга r , состав-
   ленных из переменных x1 , ..., x n .
2. Найти число полиномов Жегалкина степени r над множеством пере-
   менных x1 , ..., x n .
3. Методом неопределенных коэффициентов построить полином Жегал-
   кина для следующих функций:
1) f � �10 01� ;                        4) � x ~ y � � � x � y �;
2) f � �011010 0 0 � ;                  5) xyz � � x � y � ;
3) f � �01110 010 � ;                   6) � x y � � � y � z �.
4. Построить полиномы Жегалкина для элементарных булевых функций.
5. При помощи эквивалентных преобразований построить полиномы Же-
   галкина для следующих функций:
1) D � xy � yz � xz ;             4) D � x z � xyz ;
2) D � x1 x 2 � x 2 x 4 � x 3 ;   5) D � x1 x 2 � x1 x 2 x 3 � x 3 ;
3) D � xyz � x � z                6) D � xyz � x .
                                   ~ ~
                                      �         �~
6. Наборы �~ � ��~1 , ...,�~n � и � � � 1 , ..., � n называются соседними, если
   они отличаются только одной координатой. Доказать, что если функция
                                          45