ВУЗ:
Составители:
Рубрика:
Операция замыкания . Основные замкнутые классы .
__________________________________________________________________________________________
85
1. Построить совершенные ДНФ и КНФ для следующих функций (для
функций, заданных формулами, предварительно построить таблицы ис-
тинности):
1)
(
)
;yzyx
→
⊕
2)
(
)
;01101100
=
f
3)
(
)
(
)
;|~ xyzzyx
→
4)
(
)
;1100100100110000
=
f
5)
(
)
(
)
(
)
(
)
.|~ xyyxyxyx
⊕
→
2. Преобразовать заданные ДНФ в совершенные :
1)
;
y
x
z
y
xy
∨
∨
2) ;
421321
xxxxxx
∨
∨
3)
;
xy
z
y
x
x
∨
∨
4)
;
y
x
y
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
2
попарно неэквивалентных элемен -
тарных дизъюнкций.
8. По СКНФ формулы U построить
85 Операция замыкания. Основные замкнутые классы. __________________________________________________________________________________________ 1. Построить совершенные ДНФ и КНФ для следующих функций (для функций, заданных формулами, предварительно построить таблицы ис- тинности): 1) ( x ⊕ y ) → yz; 2) f =(01101100); 3) (( x → y ) ~ z ) | xyz; 4) f =(0100110000110010); 5) ( x → y )( x ⊕ y )( x ~ y )( y | x ). 2. Преобразовать заданные ДНФ в совершенные: 1) xy ∨ yz ∨ x y; 2) x1 ∨ x 2 x 3 ∨ x1 x 2 x 4 ; 3) x ∨ x yz ∨ xy; 4) xy ∨ xyz ∨ y ∨ xy ; 5) x1 x 2 ∨ x 2 x 3 ∨ x 3 x1 ; 3. Преобразовать заданные КНФ в совершенные: 1) ( x ∨ y )(z ∨ y )z; 2) (u ∨ v )(u ∨ v ∨ w )(u ∨ v ); 3) ( x 1 ∨ x 2 )( x 2 ∨ x 3 )( x 3 ∨ x 4 ); 4) ( x ∨ y )( x ∨ z ) y; 5) ( x 1 ∨ x 2 )( x 1 ∨ x 3 ∨ x 4 ); 4. Построить СДНФ и СКНФ с помощью эквивалентных преобразований: 1) (( x → y ) ∨ z ) ~ ( x ∨ ( y → z )); 2) ( x 1 ∨ x 2 ) → ( x 3 ∨ x 4 ); 3) (( x ⊕ z ) → y ) ∨ (( x | y ) ∨ y ); 4) ( y ~ z )(z ~ x )( x ∨ y ); 5) ( x 1 | x 2 ) → ( x 3 | x 4 ); 5. Построить формулу функции трех переменных, которая принимает зна- чение 1 в том и только в том случае, когда ровно две переменные равны нулю. 6. Построить формулу функции трех переменных, которая принимает та- кое же значение, как большинство (или меньшинство) переменных. 7. Доказать, что функция от n переменных f ( x1 ... x n ) ≡0 тогда и только тогда, когда ее СКНФ содержит 2 n попарно неэквивалентных элемен- тарных дизъюнкций. 8. По СКНФ формулы U построить
Страницы
- « первая
- ‹ предыдущая
- …
- 37
- 38
- 39
- 40
- 41
- …
- следующая ›
- последняя »