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

UptoLike

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

46
(
)
n
x...,,xf
1
на двух соседних наборах принимает противоположные
значения, то она линейная. Верно ли обратное утверждение?
7. Выяснить, является ли линейной функция
f
:
1)
(
)
2121
xxxxf
Å
=
; 3)
(
)
10011010
=
f ;
2)
(
)
(
)
z~zyy~xf
®
=
; 4)
(
)
1010010110010110
=
f .
7. ОПЕРАЦИЯ ЗАМЫКАНИЯ.
ОСНОВНЫЕ ЗАМКНУТЫЕ КЛАССЫ
Обозначим множество всех булевых функций через Б. Пусть
(
)
n
x,...,xf
1
,
(
)
m
x,...,xg
11
, ,
(
)
mn
x,...,xg
1
произвольные булевы функ-
ции. Суперпозицией этих функций называется функция
(
)
(
)
(
)
(
)
mnmm
x,...,xg,...,x,...,xgfx,...,x
1111
=
j
.
Пример 1. Пусть
(
)
(
)
321321
xx~xx,x,xf
Å
=
,
(
)
xyy,xg
=
1
,
(
)
xy,xg
=
2
,
(
)
yxy,xg
=
3
, тогда их суперпозиция
(
)
y,x
j
реализуется
формулой
(
)
(
)
yxx~xy
Å
.
Пусть М некоторое множество булевых функций:
М
Í
. Замы-
канием
[
]
М множества М называется совокупность всех тех булевых
функций, которые являются суперпозициями функций из множества М.
Операция получения множества
[
]
М из М называется операцией замыка-
ния. Множество М называется функционально замкнутым классом (ко-
роче, замкнутым классом), если
.



М = М
Таким образом, замкнутый
класс вместе с любыми его функциями содержит и все их суперпозиции.
Традиционно выделяют пять замкнутых классов булевых функций:
1. Класс
L
линейных функций.
2. Класс
0
T булевых функций, сохраняющих константу 0:
(
)
{
}
.0
0
=
Î
=
0...,0,f|БfT
Функции
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 .