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

UptoLike

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

48
ЗАДАЧИ И УПРАЖНЕНИЯ
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. Показать, что суперпозиция самодвойственных функций является само-
двойственной, т.е.
[]
S=S.
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
получить константу:
1)
(
)
00111001
=
f ;