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

                                             �1, если �� 1 ,� 2 , ...,� n � � �
                   f �� 1 ,� 2 , ...,� n � � �
                                             �0, если �� 1 ,� 2 , ...,� n � � � .
         И наоборот, булева функция f ( x1 , x 2 ,..., x n ) однозначно определяет
множество истинности E f � � f �� 1 ,� 2 , ... ,� n � f �� 1 ,� 2 , ... ,� n � � 1�.
    В случае описанного выше примера
                   E f � ��0 0 0�, �0 0 1�, �0 1 0�, �1 0 0��.
    Имеет место

Теорема. Всякая булева функция представима в виде формулы алгебры ло-
               гики через операции � , & и �, и это представление таково:
  f � x1 , ..., x n � � � � x1� & x 2� & ... & x m� & f �� 1 ,� 2 ,...,� m , x m �1 , ..., x n �� ,
                                              1     2             m

                            �� 1 ,...,� m �
                где �� 1 ,� 2 ,...,� m � – различные двоичные наборы значений пе-
                ременных         x1 , ..., x n , 1 � m � n , x i� � x i ,       i
                                                                                               если         � i � 1,
                x i� � x i , если � i � 0 , i � 1, ..., m .
                    i




         Приведенная выше в примере функция f � x1 , x 2 , x 3 � представима
формулой:
f � x1 , x 2 , x3 � � x10 x 20 x30 f �0 0 0� � x10 x 20 x31 f �0 01� � x10 x 12 x30 f �010� � x10 x 12 x31 f �011� �
                        � x11 x 20 x30 f �10 0� � x11 x 20 x31 f �101� � x11 x 12 x30 f �110� � x11 x 12 x31 f �111� �
                        � x1 x 2 x3 � x1 x 2 x3 � x1 x 2 x3 � x1 x 2 x3 .

      Такое представление называется нормальной формой, речь о которой
пойдет в следующих двух параграфах.
      Всякая формула алгебры логики есть булева функция. Тождественно
истинная и тождественно ложная формулы есть постоянные функции. Их
множества значений соответственно состоят только из единиц или только
из нулей.
      Булевы функции вида

 f1 � x ,                                     f4 � x & y,                             f7 � x � y,
 f2 � x ,              f5 � x � y ,             f8 � x � y ,
 f3 � x � y ,          f6 � x � y ,             f9 � x � y
называются элементарными.
       Булевы функции от n переменных называются равными, если они
принимают одинаковые значения на соответствующих одинаковых набо-
рах переменных, в них входящих. Равные функции реализуются равно-
сильными формулами. Например,

                                                            18