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

UptoLike

ВУЗ: 

ВГУ | Воронеж

Составители: 

Рубрика: 

47
4. Класс
S
самодвойственных функций. Функция
(
)
n
xxf ...,,
1
на-
зывается самодвойственной, если она совпадает со своей двойственной:
(
)
(
)
{
}
....,,...,,|
nn
xxfxxfБfS
11
*
=
Î
=
Очевидно, что самодвойственными функциями будут
x
x
; функции
y
x
y
x
xy
y
x
|
®
Ú
не являются самодвойственными.
Пример 2. Покажем, что функция
(
)
yzxzxyzyx
Ú
Ú
=
,,
j
является
самодвойственной. Действительно,
(
)
(
)
(
)
(
)
( )
.
,,
zyxzxyzyxzzxy
yzxzxyxyzzyzxyxzyx
ÚÚ=ÚÚÚ=
=
Ú
Ú
Ú
=
Ú
Ú
Ú
=
*
1
j
Для самодвойственной функции имеет место тождество
(
)
(
)
nn
x...,,xfx...,,xf
11
=
,
так что на наборах
(
)
n
a
a
...,,
1
и
(
)
n
a
a
...,,
1
, которые мы будем называть
противоположными, самодвойственная функция принимает противопо-
ложные значения.
Пример 3. Функция
(
)
(
)
01101110
1
=
zyxf ,, не является самодвой-
ственной, так как на противоположных наборах (000) и (111) она принима-
ет одно и то же значение 0.
Функция
(
)
(
)
10110010
2
=
zyxf ,, является самодвойственной, так как
на каждой паре противоположных наборов она принимает противополож-
ные значения.
Справедливо следующее утверждение, называемое обычно леммой о
несамодвойственной функции: если функция
(
)
n
xxf ...,,
1
несамодвойст-
венная, то, подставляя на места ее переменных
x
и
x
, можно получить
константу.
5. Класс
M
монотонных функций. Говорят, что набор
(
)
n
a
a
a
...,,
~
1
=
предшествует набору
(
)
n
bbb
...,,
~
1
= и пишут
ba
~
~
p
, если
ni
ii
,...,, 1
=
£
b
a
. Функция
(
)
Бxxf
n
Î
...,,
1
называется монотонной, если
(
)
(
)
ba
~
~
ff £ при
ba
~
~
p
.
Функции
xy
y
x
x
Ú
1
0
являются монотонными, тогда как
yxyxyxyxyxx ~,,,|,, Å®¯ не принадлежат классу
M
.
Справедливо утверждение (лемма о немонотонной функции):
Если
M
f
Ï
, то, подставляя на места ее переменных
x
1
0
, можно
получить функцию
x
. 
     4. Класс S самодвойственных функций. Функция f � x 1 , ..., x n � на-
зывается самодвойственной, если она совпадает со своей двойственной:
                        S � � f � Б | f � x1 , ..., x n � � f � � x 1 , ..., 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 монотонных функций. Говорят, что набор
                                                    ~                          ~
�~ � �� 1 , ...,� n � предшествует набору � � � � 1 , ..., � n � и пишут �~ � � , если
� i � � i , i � 1,..., n . Функция f � x1 , ..., x n � � Б называется монотонной, если
          � �   ~
 f ��~ � � f � при �~ � � .
                              ~
       Функции x, 0, 1, x � y, xy являются монотонными, тогда как
x , x � y, x | y, x � y, x � y, x ~ y не принадлежат классу M .
       Справедливо утверждение (лемма о немонотонной функции):
       Если f � M , то, подставляя на места ее переменных 0, 1, x , можно
получить функцию x .


                                               47

Страницы