Дискретная математика. Элементы теории, задачи и упражнения. Часть 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 ; 
                                ЗАДАЧИ И УПРАЖНЕНИЯ

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 � xyz ;
         3)   f   � � x � y �� y � z �� z � x � ;
         4)   f   � �01011110 � ;
         5)   f   � �0001001001100111 � .

10. Из несамодвойственной функции f с помощью подстановки на места
   переменных функций x и x получить константу:
         1) f � �00111001 � ;
                                              48

Страницы