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

UptoLike

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

30
8. На праздник было решено пригласить гостей. В связи с этим были вы-
сказаны следующие соображения: если мы пригласим Андрея, то Воло-
дю приглашать не надо. Но Сережу можно пригласить только тогда, ко-
гда будет приглашен Володя. А если мы пригласим Андрея с Володей,
то Сережу пригласить нельзя. На следующий день было решено, что
нужно сделать противоположное, т.е. в качестве инструкции по при-
глашению гостей взять отрицание конъюнкции всего того, что было
сказано накануне. Упростить новую инструкцию и свести ее к простей-
шим условиям.
9. По случаю новоселья семья решила купить новый шкаф. Все хотели,
чтобы шкаф был либо дубовый, либо березовый; либо желтый, либо ко-
ричневый; либо светлый, либо темный. Отцу дали целый ряд рекомен-
даций.
1) Мать сказала: «Ты можешь купить светлый шкаф, если только
он будет березовым желтого цвета».
2) Бабушка сказала: «Если шкаф будет березовым, то светлый тон
должен быть достаточным признаком желтой окраски».
3) Дети сказали: «Если шкаф будет коричневым, то для того, что-
бы он был темным, необходимо, чтобы он был сделан из дуба».
Отец сообразил, что эти рекомендации сводятся к двум простейшим ус-
ловиям. Но он купил шкаф, который удовлетворял только одному из
этих условий. Он поступил так потому, что хотел, чтобы шкаф был
светлым и березовым или темным, но желтым. И это условие действи-
тельно оказалось выполненным. Какой шкаф был куплен?
Указание: решение задач 79 сводится к поиску минимальной КНФ.
5.4 Совершенные нормальные формы
Пусть
(
)
n
x...,,xf
1
произвольная булева функция, зависящая от
n
переменных.
Определение. ДНФ функции
(
)
n
x...,,xf
1
называется совершенной,
если она составлена из попарно различных элементарных конъюнкций
ранга
n
, т.е. формул вида
(
)
( )
(
)
n
n
n
,...,,f
n
x&...&x&xx...,,xf
s
ss
ss
21
1
21
1
1
=
Ú= , (1)
где дизъюнктивная сумма берется по всем наборам
(
)
n
,...,,
s
s
s
21
, для ко-
торых
(
)
1
21
=
n
,...,,f
s
s
s
.
Ясно, что эта функция
(
)
n
x...,,xf
1
отлична от тождественного нуля.