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

1) f � x1 x 2 � x1 � x 2 � ;                      3) f � �010110 01� ;
2) f � � x ~ y �� y � z � ~ z ;                   4) f � �011010 011010 0101� .


                          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�.
        Функции x & y, x � y, x � y, x являются функциями из T0 , тогда как
x | y, x � y, x � y, x ~ y, x не принадлежат T0 .
        3. Класс T1 булевых функций, сохраняющих константу 1:
                                      T1 � � f � Б | f �1, ...,1� � 1�.
        Как легко проверить, x � y, x & y, x � y, x ~ y, x , 1 – функции из
T1 , в то время как x | y, x � y, x � y, x , 0 не принадлежат T1 .
                                                   46

Страницы