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

UptoLike

Операция замыкания . Основные замкнутые классы .
__________________________________________________________________________________________
85
1. Построить совершенные ДНФ и КНФ для следующих функций (для
функций, заданных формулами, предварительно построить таблицы ис-
тинности):
1)
(
)
;yzyx
2)
(
)
;01101100
=
f
3)
(
)
(
)
;|~ xyzzyx
4)
(
)
;1100100100110000
=
f
5)
(
)
(
)
(
)
(
)
.|~ xyyxyxyx
2. Преобразовать заданные ДНФ в совершенные :
1)
;
x
z
xy
2) ;
421321
xxxxxx
3)
;
xy
z
x
x
4)
;
x
xyz
xy
5) ;
133221
xxxxxx
3. Преобразовать заданные КНФ в совершенные :
1)
(
)
(
)
;zyzyx
2)
(
)
(
)
(
)
;vuwvuvu
3)
(
)
(
)
(
)
;
433221
xxxxxx
4)
(
)
(
)
;yzxyx
5)
(
)
(
)
;
43121
xxxxx
4. Построить СДНФ и СКНФ с помощью эквивалентных преобразований:
1)
(
)
(
)
(
)
(
)
;~ zyxzyx
2)
(
)
(
)
;
4321
xxxx
3)
(
)
(
)
(
)
(
)
;| yyxyzx
4)
(
)
(
)
(
)
;~~ yxxzzy
5)
(
)
(
)
;||
4321
xxxx
5. Построить формулу функции трех переменных, которая принимает зна-
чение 1 в том и только в том случае, когда ровно две переменные равны
нулю .
6. Построить формулу функции трех переменных, которая принимает та-
кое же значение, как большинство (или меньшинство) переменных .
7. Доказать, что функция от
n
переменных
(
)
0
1
n
xxf ...
тогда и только
тогда, когда ее СКНФ содержит
n
попарно неэквивалентных элемен -
тарных дизъюнкций.
8. По СКНФ формулы U построить