Дискретная математика. Элементы теории, задачи и упражнения. Часть 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
.