Дискретная математика. Элементы теории задачи и упражнения. Часть 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 
                                                  97
Операция замыкания. Основные замкнутые классы.
__________________________________________________________________________________________
7. Выяснить, является ли линейной функция f :

1) f = x1 x 2 ( x1 ⊕ x 2 ) ;                     3) f =(01 0110 01) ;
2) f =( x ~ y )( y → z ) ~ z ;                   4) f =(011010 011010 01 01) .




                         7. ОПЕРАЦИЯ ЗАМЫКАНИЯ.
                       ОСНОВНЫЕ ЗАМКНУТЫЕ КЛАССЫ

         Обозначим множество всех булевых функций через Б. Пусть
 f ( x1 ,..., x n ) , g1 ( x1 ,..., x m ), …, g n ( x1 ,..., x m ) - произвольные булевы функ-
ции. Суперпозицией этих функций называется функция
                        ϕ ( x1 ,..., x m ) = f ( g1 ( x1 ,..., x m ),..., g n ( x1 ,..., x m )) .

          Пример 1. Пусть                  f ( x1 , x 2 , x 3 ) =( x1 ~ x 2 ) ⊕ x 3 , g1 ( x , y ) =xy ,
g 2 ( x , y ) = x , g 3 ( x , y ) = x y , тогда их суперпозиция ϕ ( x , y ) реализуется
формулой (xy ~ x ) ⊕ (x y ) .

      Пусть М - некоторое множество булевых функций: М ⊆ Б . Замы-
канием [М ] множества М называется совокупность всех тех булевых
функций, которые являются суперпозициями функций из множества М .
Операция получения множества [М ] из М называется операцией замыка-
ния. Множество М называется функционально замкнутым классом (ко-
роче, замкнутым классом), если [М ] = М . Таким образом, замкнутый
класс вместе с любыми его функциями содержит и все их суперпозиции.
      Традиционно выделяют пять замкнутых классов булевых функций:
       1.       Класс L линейных функций.
       2.       Класс T0 булевых функций, сохраняющих константу 0:
                                     T0 ={f ∈ Б | f (0, ...,0 ) =0}.

Страницы