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

UptoLike

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