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

                                            95
Операция замыкания. Основные замкнутые классы.
__________________________________________________________________________________________
     Пример 2. Пусть f (x , y , z ) =( x → y )( y → z ) . Построить полином
Жегалкина, используя метод эквивалентных преобразований.
     Решение. Построим д.н.ф.
             (x → y )( y → z ) =(x ∨ y )( y ∨ z ) =x y ∨ x z ∨ yz .
Освободимся от знака дизъюнкции ∨ :
                                                (             )
                                          (1)
                           x y ∨ x z ∨ yz =� x y ∧ x z ∧ yz .
Применим формулу (2):
          (                )
        � x y ∧ x z ∧ yz =((x ⊕ 1)( y ⊕ 1)⊕ 1)((x ⊕ 1)z ⊕1)( yz ⊕ 1)⊕ 1.
Пользуясь (3), раскроем скобки в последнем выражении и приведем по-
добные, получим:
          ( xy ⊕ x ⊕ y )( xz ⊕ z ⊕1)( yz ⊕ 1) ⊕1 = yz ⊕ xy ⊕ y ⊕ x ⊕ 1.
      Описанный в пунктах а) — д) способ построения полинома Жегал-
кина применим для любой формулы. Однако в большинстве случаев суще-
ствует более краткие пути преобразования формулы в полином Жегалкина.
В предыдущем примере можно построить полином Жегалкина для каждо-
го сомножителя x → y и y → z , их произведение и дает полином Жегал-
кина для f (x , y , z ). Действительно,
                  u → v =u ∨ v =uv =u(v ⊕ 1) ⊕1 =uv ⊕ u ⊕ 1 ,
откуда следует
                    (x → y )( y → z ) =(xy ⊕ x ⊕ 1)( yz ⊕ y ⊕ 1),
поэтому
                       (x → y )( y → z ) =xy ⊕ yz ⊕ y ⊕ x ⊕1.
     Для формул, содержащих символы ~ и | при построении полинома
Жегалкина, полезно использовать эквивалентности:
                       u ~ v =u ⊕ v =u ⊕ v ⊕1 ,               (5)
                         u v =uv =uv ⊕ 1 .                    (6)

       Пример 3. Построим полином Жегалкина для функции
                       f (x , y , z ) =�((xy ~ z ) (x ∨ y )).
       Решение.
                           (5 , 6 )
      � ((xy ~ z ) (x ∨ y )) =(xy ⊕ z ⊕1)(xy ⊕ x ⊕1) =xyz ⊕ xz ⊕ x ⊕ z ⊕1 .

      Булева функция, которой соответствует полином Жегалкина первой
степени, называется линейной. Функции, задаваемые формулами
                      x ~ y , x ⊕ y, x , x, x ⊕ y⊕z,
являются линейными. Множество всех линейных булевых функций обо-
значается через L , множество линейных функций, зависящих от n пере-
менных, — через L(n ). Для каждой функции f ∈ L(n ) имеет место
представление