Задачи по дискретной математике для контрольных и самостоятельных работ. Булевы функции. Васильев А.В - 28 стр.

UptoLike

ВУЗ: 

КФУ | Казань

Составители: 

Рубрика: 

4.20. (x
1
∨ x
2
)(x
2
∨ x
3
) . . . (x
n−1
∨ x
n
)
4.21. (. . . ((x
1
→ x
2
) → x
3
) . . .) → x
n
4.22. ((. . . ((x
1
→ x
2
) → x
3
) . . .) → x
n
) → ((. . . ((y
1
→ y
2
) → y
3
) . . .) → y
n
)
5. Найти длину сокращенной ДНФ для функции
5.1. x
1
⊕ . . . ⊕ x
n
5.2. (x
1
∨ x
2
∨ x
3
)(x
1
∨ x
2
∨ x
3
)(x
4
⊕ . . . ⊕ x
n
)
5.3. (x
1
⊕ . . . ⊕ x
k
)(x
k+1
⊕ . . . ⊕ x
n
)
5.4. (x
1
∨ . . . ∨ x
n
)(x
1
∨ . . . ∨ x
k
∨ x
k+1
∨ . . . ∨ x
n
)
6. Доказать, что если функция самодвойственна, то в ее ДНФ любые 2 сла-
гаемых имеют общий сомножитель.
7. Доказать, что если функция самодвойственна, то в ее КНФ любые 2 со-
множителя имеют общее слагаемое.
8. Доказать, что если произведение любых двух элементарных конъюнкций
в ДНФ равно 0, то после замены ∨ на ⊕ получится формула, эквивалент-
ная исходной.
9. Доказать, что любой предполный класс замкнут.
10. Доказать, что если замкнутый класс имеет конечный базис, то всякий
его базис конечен.
11. Доказать, что всякий замкнутый класс, содержащий функцию, отличную
от константы, содержит функцию x.
Подписано в печать 28.08.2008 г.
Форм. бум. 60 х84 1/16. Гарнитура “Таймс”. Печать ризографическая.
Печ.л. 5. Т.120. З.108.
Лаборатория оперативной полиграфии Издательст ва КГУ
420045, Казань, ул.Кр.Позиция, 2а
Тел. 231-52-12
28
 4.20. (x1 ∨ x2 )(x2 ∨ x3 ) . . . (xn−1 ∨ xn )
 4.21. (. . . ((x1 → x2 ) → x3 ) . . .) → xn
 4.22. ((. . . ((x1 → x2 ) → x3 ) . . .) → xn ) → ((. . . ((y1 → y2 ) → y3 ) . . .) → yn )
5. Найти длину сокращенной ДНФ для функции
  5.1. x1 ⊕ . . . ⊕ xn
  5.2. (x1 ∨ x2 ∨ x3 )(x1 ∨ x2 ∨ x3 )(x4 ⊕ . . . ⊕ xn )
  5.3. (x1 ⊕ . . . ⊕ xk )(xk+1 ⊕ . . . ⊕ xn )
  5.4. (x1 ∨ . . . ∨ xn )(x1 ∨ . . . ∨ xk ∨ xk+1 ∨ . . . ∨ xn )
6. Доказать, что если функция самодвойственна, то в ее ДНФ любые 2 сла-
   гаемых имеют общий сомножитель.
7. Доказать, что если функция самодвойственна, то в ее КНФ любые 2 со-
   множителя имеют общее слагаемое.
8. Доказать, что если произведение любых двух элементарных конъюнкций
   в ДНФ равно 0, то после замены ∨ на ⊕ получится формула, эквивалент-
   ная исходной.
9. Доказать, что любой предполный класс замкнут.
10. Доказать, что если замкнутый класс имеет конечный базис, то всякий
    его базис конечен.
11. Доказать, что всякий замкнутый класс, содержащий функцию, отличную
    от константы, содержит функцию x.




                         Подписано в печать 28.08.2008 г.
        Форм. бум. 60х84 1/16. Гарнитура “Таймс”. Печать ризографическая.
                               Печ.л. 5. Т.120. З.108.

              Лаборатория оперативной полиграфии Издательства КГУ
                        420045, Казань, ул.Кр.Позиция, 2а
                                  Тел. 231-52-12



                                            28

Страницы