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

UptoLike

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

35
5. Построить формулу функции трех переменных, которая принимает зна-
чение 1 в том и только в том случае, когда ровно две переменные равны
нулю.
6. Построить формулу функции трех переменных, которая принимает та-
кое же значение, как большинство (или меньшинство) переменных.
7. Доказать, что функция от
n
переменных
(
)
0
1
º
n
xxf ... тогда и только
тогда, когда ее СКНФ содержит
n
2
попарно неэквивалентных элемен-
тарных дизъюнкций.
8. По СКНФ формулы U построить
1) СДНФ двойственной формулы U*;
2) СКНФ формулы U ;
3) СДНФ формулы
.
U
9. По СДНФ формулы U и СДНФ формулы V построить
1) СКНФ и СДНФ формулы
V
Ú
;
2) СКНФ и СДНФ формулы
V
Ù
;
3) СКНФ и СДНФ формулы
V
®
.
10. Найти длину совершенной ДНФ функции
(
)
n
xxf ,...,
1
:
1)
(
)
;...,...,
nn
xxxxxf
Å
Å
Å
=
211
2)
(
)
(
)
(
)
;......,...,
nnn
xxxxxxxxf
Ú
Ú
Ú
Ú
Ú
Ú
=
21211
3)
(
)
(
)
(
)
....,...,
nn
xxxxxxxxxxxf
Å
Å
Å
Å
Ú
Ú
Ú
Ú
=
543213211
11. Сотрудники конструкторского бюро обсуждали вопрос о предстоящей
командировке в Москву. Были высказаны следующие суждения:
1) Если поедут Иванов и Петров, то надо посылать и Сидорова.
2) Сидоров поедет только при условии, что поедет Иванов. Зна-
чит, Петрова посылать нельзя.
3) Надо послать или Иванова, или Петрова.
Директор сказал, что можно выполнить только одно из этих предло-
жений. Кого хотели послать в командировку сотрудники, и кого решил по-
слать директор.
12. В кафе пришли три посетителя. Они узнали, что на обед можно зака-
зать: харчо либо борщ, плов либо азу, сок либо компот. Обсуждая ме-
ню, каждый из посетителей высказал свое мнение:
1) Я хочу заказать сок, если мы возьмем азу либо борщ.