ВУЗ:
Составители:
Рубрика:
Операция замыкания . Основные замкнутые классы .
__________________________________________________________________________________________
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
получить константу:
100 Операция замыкания. Основные замкнутые классы. __________________________________________________________________________________________ ЗАДАЧИ И УПРАЖНЕНИЯ 1. Обосновать следующие свойства замыкания: 1) [ [M ] ] =[M ] ; 2) если M 1 ⊆ M 2 , то [M 1 ] ⊆ [M 2 ] ; 3) [M 1 ∪ M 2 ] ⊇ [M 1 ] ∪ [M 2 ]; 4) [∅] =∅ . 2. Всегда ли на множестве Б булевых функций: a) пересечение замкнутых классов является замкнутым классом; b) разность замкнутых классов есть замкнутый класс; c) дополнение замкнутого класса не является замкнутым клас- сом? 3. Показать, что суперпозиция линейных функций является линейной функцией, т.е. что класс L замкнут, и мощность L(n ) =2 n+1 , где n - число переменных. 4. Показать, что классы T0 и T1 функций, сохраняющих константу, замк- нуты. 5. Показать, что суперпозиция самодвойственных функций является само- двойственной, т.е. [S ] =S . 6. Доказать замкнутость класса монотонных функций. 7. Показать, что мощности множеств T0 (n ) и T1 (n ) функций от n пере- менных, сохраняющих константы, совпадают: T0 (n ) =T1 (n) =2 2 −1. n 8. Показать, что мощность множества S (n ) самодвойственных функций от n переменных вычисляется по формуле: S (n ) = 2 2 . n 9. Самодвойственна ли функция f ? 1) f =�(( x → y ) → xz ) → yz ; 2) f =( x ∨ y ∨ z )t ∨ x yz ; 3) f =( x ∨ y )( y ∨ z )(z ∨ x ) ; 4) f =(01011110 ) ; 5) f =(0001001001100111 ) . 10.Из несамодвойственной функции f с помощью подстановки на места переменных функций x и x получить константу:
Страницы
- « первая
- ‹ предыдущая
- …
- 52
- 53
- 54
- 55
- 56
- …
- следующая ›
- последняя »