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

5. Построить формулу функции трех переменных, которая принимает зна-
   чение 1 в том и только в том случае, когда ровно две переменные равны
   нулю.
6. Построить формулу функции трех переменных, которая принимает та-
   кое же значение, как большинство (или меньшинство) переменных.
7. Доказать, что функция от n переменных f � x 1 ... x n � � 0 тогда и только
   тогда, когда ее СКНФ содержит 2 n попарно неэквивалентных элемен-
   тарных дизъюнкций.
8. По СКНФ формулы U построить
            1) СДНФ двойственной формулы U*;
            2) СКНФ формулы U ;
            3) СДНФ формулы U .

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

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

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

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



                                                35