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

Страницы