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

UptoLike

Операция замыкания . Основные замкнутые классы .
__________________________________________________________________________________________
100
ЗАДАЧИ И УПРАЖНЕНИЯ
1. Обосновать следующие свойства замыкания:
1)
[
]
[
]
[
]
MM
=
;
2) если
21
MM
, то
[
]
[
]
21
MM
;
3)
[
]
[
]
[
]
2121
MMMM
;
4)
[
]
=
.
2. Всегда ли на множестве
Б
булевых функций:
a) пересечение замкнутых классов является замкнутым классом;
b) разность замкнутых классов есть замкнутый класс;
c) дополнение замкнутого класса не является замкнутым клас-
сом?
3. Показать, что суперпозиция линейных функций является линейной
функцией, т.е. что класс
L
замкнут, и мощность
(
)
1
2
+
=
n
nL , где
n
-
число переменных.
4. Показать, что классы
0
T и
1
T функций, сохраняющих константу, замк-
нуты.
5. Показать, что суперпозиция самодвойственных функций является само-
двойственной, т.е.
[
]
SS
=
.
6. Доказать замкнутость класса монотонных функций.
7. Показать, что мощности множеств
(
)
nT
0
и
(
)
nT
1
функций от
n
пере -
менных , сохраняющих константы, совпадают:
(
)
(
)
.
12
10
2
==
n
nTnT
8. Показать, что мощность множества
(
)
nS самодвойственных функций
от
n
переменных вычисляется по формуле:
(
)
n
nS
2
2= .
9. Самодвойственна ли функция
f
?
1)
(
)
(
)
yzxzyxf = ;
2)
(
)
yzxtzyxf
=
;
3)
(
)
(
)
(
)
xzzyyxf
=
;
4)
(
)
01011110
=
f
;
5)
(
)
1001110001001001
=
f .
10. Из несамодвойственной функции
f
с помощью подстановки на места
переменных функций
x
и
x
получить константу: