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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

Операция замыкания . Основные замкнутые классы .
__________________________________________________________________________________________
97
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
=
ϕ
.
Пример 1. Пусть
(
)
(
)
321321
xx~xx,x,xf
⊕
=
,
(
)
xyy,xg
=
1
,
(
)
xy,xg
=
2
,
(
)
yxy,xg =
3
, тогда их суперпозиция
(
)
y,x
ϕ
реализуется
формулой
(
)
(
)
yxx~xy ⊕ .
Пусть М - некоторое множество булевых функций:
М
⊆
. Замы-
канием
[
]
М
множества М называется совокупность всех тех булевых
функций, которые являются суперпозициями функций из множества М .
Операция получения множества
[
]
М из М называется операцией замыка -
ния . Множество М называется функционально замкнутым классом (ко-
роче, замкнутым классом ), если
[
]
ММ
=
. Таким образом, замкнутый
класс вместе с любыми его функциями содержит и все их суперпозиции.
Традиционно выделяют пять замкнутых классов булевых функций:
1. Класс
линейных функций .
2. Класс
0
T
булевых функций , сохраняющих константу 0 :
(
)
{
}
.0
0
=
∈
=
0...,0,f|БfT

Страницы