Дискретная математика. Элементы теории задачи и упражнения. Часть 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
получить константу: 
                                             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 получить константу:

Страницы