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

                                             96
Операция замыкания. Основные замкнутые классы.
__________________________________________________________________________________________
ставление
                             f (x 1 , ..., x n ) =c 0 ⊕ c 1 x 1 ⊕ ... ⊕ c n x n , (7)
где коэффициенты ci принимают значения либо 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 ∨ x z ;           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

     они отличаются только одной координатой. Доказать, что если функция
      f ( x1 , ..., x n ) на двух соседних наборах принимает противоположные
     значения, то она линейная. Верно ли обратное утверждение?