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

8. На праздник было решено пригласить гостей. В связи с этим были вы-
   сказаны следующие соображения: если мы пригласим Андрея, то Воло-
   дю приглашать не надо. Но Сережу можно пригласить только тогда, ко-
   гда будет приглашен Володя. А если мы пригласим Андрея с Володей,
   то Сережу пригласить нельзя. На следующий день было решено, что
   нужно сделать противоположное, т.е. в качестве инструкции по при-
   глашению гостей взять отрицание конъюнкции всего того, что было
   сказано накануне. Упростить новую инструкцию и свести ее к простей-
   шим условиям.
9. По случаю новоселья семья решила купить новый шкаф. Все хотели,
   чтобы шкаф был либо дубовый, либо березовый; либо желтый, либо ко-
   ричневый; либо светлый, либо темный. Отцу дали целый ряд рекомен-
   даций.
         1) Мать сказала: «Ты можешь купить светлый шкаф, если только
            он будет березовым желтого цвета».
         2) Бабушка сказала: «Если шкаф будет березовым, то светлый тон
            должен быть достаточным признаком желтой окраски».
         3) Дети сказали: «Если шкаф будет коричневым, то для того, что-
            бы он был темным, необходимо, чтобы он был сделан из дуба».
   Отец сообразил, что эти рекомендации сводятся к двум простейшим ус-
   ловиям. Но он купил шкаф, который удовлетворял только одному из
   этих условий. Он поступил так потому, что хотел, чтобы шкаф был
   светлым и березовым или темным, но желтым. И это условие действи-
   тельно оказалось выполненным. Какой шкаф был куплен?

   Указание: решение задач 7–9 сводится к поиску минимальной КНФ.


                  5.4 Совершенные нормальные формы

      Пусть f � x1 , ..., x n � – произвольная булева функция, зависящая от n
переменных.
      Определение. ДНФ функции f � x1 , ..., x n � называется совершенной,
если она составлена из попарно различных элементарных конъюнкций
ранга n , т.е. формул вида
                    f � x1 , ..., x n � � � � � � x1� & x 2� & ... & x n� �,
                                                       1   2   n
                                                                             (1)
                                 f � 1 , ,...,� n �1

где дизъюнктивная сумма берется по всем наборам �� 1 ,� 2 ,...,� n � , для ко-
торых f �� 1 ,� 2 ,...,� n � � 1 .
      Ясно, что эта функция f � x1 , ..., x n � отлична от тождественного нуля.


                                            30