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

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

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



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

      Пусть f ( x 1 , ..., x n ) — произвольная булева функция, зависящая от n
переменных.
      Определение. ДНФ функции f ( x 1 , ..., 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 ) отлична от тождественного нуля.
      Определение. КНФ функции f ( x 1 , ..., x n ) называется совершенной,
если она составлена из попарно различных элементарных дизъюнкций
ранга n , т.е. формул вида