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

UptoLike

Операция замыкания . Основные замкнутые классы .
__________________________________________________________________________________________
98
Функции
x
y
x
y
x
y
x
,
,
,
&
являются функциями из
0
T , тогда как
xyxyxyxyx ,~,,,| →↓
не принадлежат
0
T
.
3. Класс
1
T
булевых функций , сохраняющих константу 1 :
(
)
{
}
.11
1
...,1,f|БfT
Как легко проверить,
1
,
,
~
,
,
&
,
x
y
x
y
x
y
x
y
x
функции из
1
T
, в то время как
0,,,,| xyxyxyx ⊕↓
не принадлежат
1
T
.
4. Класс
S
самодвойственных функций . Функция
(
)
n
xxf ...,,
1
называется самодвойственной, если она совпадает со своей двойственной:
(
)
(
)
{
}
....,,...,,|
nn
xxfxxfБfS
11
=∈=
Очевидно, что самодвойственными функциями будут
x
x
,
; функции
y
x
y
x
xy
y
x
|
,
,
,
не являются самодвойственными.
Пример 2. Покажем , что функция
(
)
yzxzxyzyx
,,
ϕ
является
самодвойственной. Действительно,
(
)
(
)
(
)
(
)
()
.
,,
zyxzxyzyxzzxy
yzxzxyxyzzyzxyxzyx
∨∨=∨=
==∨=
1
ϕ
Для самодвойственной функции имеет место тождество
(
)
(
)
nn
x...,,xfx...,,xf
11
= ,
так что на наборах
(
)
n
α
α
...,,
1
и
(
)
n
α
α
...,,
1
, которые мы будем называть
противоположными, самодвойственная функция принимает противопо -
ложные значения.
Пример 3. Функция
(
)
(
)
01101110
1
zyxf ,, не является самодвойст -
венной, так как на противоположных наборах (000) и (111) она принимает
одно и то же значение 0.
Функция
(
)
(
)
10110010
2
zyxf ,,
является самодвойственной, так
как на каждой паре противоположных наборов она принимает противопо -
ложные значения.
Справедливо следующее утверждение, называемое обычно леммой о
несамодвойственной функции:
Если функция
(
)
n
xxf ...,,
1
несамодвойственная, то, подставляя на
места ее переменных
x
и
x
, можно получить константу.
5. Класс
M
монотонных функций .