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

Страницы