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

                                              86
Операция замыкания. Основные замкнутые классы.
__________________________________________________________________________________________
            1) СДНФ двойственной формулы U*;
            2) СКНФ формулы U ;
            3) СДНФ формулы U ;

9. По СДНФ формулы U и СДНФ формулы V построить
        1) СКНФ и СДНФ формулы U ∨V ;
        2) СКНФ и СДНФ формулы U ∧V ;
        3) СКНФ и СДНФ формулы U → V .

10.Найти длину совершенной ДНФ функции f ( x1 ,..., x n ) :
        1) f (x 1 ,..., x n ) =x 1 ⊕ x 2 ⊕ ... ⊕ x n ;
        2) f ( x1 ,..., x n ) =(x 1 ∨ x 2 ∨ ... ∨ x n )(x1 ∨ x 2 ∨ ... ∨ x n );
        3) f (x 1 ,..., x n ) =(x 1 ∨ x 2 ∨ x 3 )(x1 ∨ x 2 ∨ x 3 ) ⊕ x 4 ⊕ x 5 ⊕ ... ⊕ x n .

11.Сотрудники конструкторского бюро обсуждали вопрос о предстоящей
   командировке в Москву. Были высказаны следующие суждения:
         1) Если поедут Иванов и Петров, то надо посылать и Сидорова.
         2) Сидоров поедет только при условии, что поедет Иванов. Зна-
            чит, Петрова посылать нельзя.
         3) Надо послать или Иванова или Петрова.
      Директор сказал, что можно выполнить только одно из этих предло-
жений. Кого хотели послать в командировку сотрудники и кого решил по-
слать директор.

12.В кафе пришли три посетителя. Они узнали, что на обед можно зака-
   зать: харчо либо борщ, плов либо азу, сок либо компот. Обсуждая ме-
   ню, каждый из посетителей высказал свое мнение:
          1) Я хочу заказать сок, если мы возьмем азу либо борщ.
          2) Чтобы я согласился взять борщ и плов, достаточно заказать
             сок. А на компот я соглашусь только при условии, что будет
             заказано азу или харчо.
          3) Если мы закажем сок, то надо взять харчо и плов, но я хочу за-
             казать борщ. Значит, надо взять азу и сок.
  Официант ничего не понял и попросил посетителей изложить свои тре-

   бования в более ясной форме. Посетители подумали и свели свои требо-

   вания к трем простейшим условиям. Тогда официант сказал, что из этих

   трех простейших условий он может выполнить только одно. Кроме того,