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

                                              98
Операция замыкания. Основные замкнутые классы.
__________________________________________________________________________________________
       Функции x & y, x ∨ y, x ⊕ y, x являются функциями из T0 , тогда как
x | y, x ↓ y, x → y, x ~ y, x не принадлежат T0 .
       3.     Класс T1 булевых функций, сохраняющих константу 1:
                                  T1 ={f ∈ Б | f (1, ...,1) =1}.
       Как легко проверить, x ∨ y , x & y , x → y , x ~ y , x, 1 – функции из
T1 , в то время как x | y, x ↓ y, x ⊕ y, x , 0 не принадлежат T1 .
     4.    Класс S самодвойственных функций. Функция f ( x 1 , ..., x n )
называется самодвойственной, если она совпадает со своей двойственной:
                         S ={f ∈ Б | f ( x 1 , ..., x n ) = f ∗( x1 , ..., x n )}.
      Очевидно, что самодвойственными функциями будут x, x ; функции
x ∨ y, xy, x → y, x | y не являются самодвойственными.
        Пример 2. Покажем, что функция ϕ ( x , y, z ) = xy ∨ xz ∨ yz является
самодвойственной. Действительно,
ϕ ∗( x, y , z ) =( x ∨ y )( x ∨ z )( y ∨ z ) = xyz ∨ xy ∨ xz ∨ yz =
            = xy (1 ∨ z ) ∨ xz ∨ zy = xy ∨ xz ∨ zy.

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

      Пример 3. Функция f 1 ( x , y , z ) =(01101110 ) не является самодвойст-
венной, так как на противоположных наборах (000) и (111) она принимает
одно и то же значение 0.
      Функция f 2 ( x , y, z ) =(10110010 ) является самодвойственной, так
как на каждой паре противоположных наборов она принимает противопо-
ложные значения.

      Справедливо следующее утверждение, называемое обычно леммой о
несамодвойственной функции:
      Если функция f ( x 1 , ..., x n ) несамодвойственная, то, подставляя на
места ее переменных x и x , можно получить константу.

       5. Класс M монотонных функций.