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

       Таким                образом, область определения булевой функции
 f � x1 , x 2 , ... , x n � есть D�F � � E n , множество значений – R� f � � E , где мощ-
ность D� f � � 2 n , R� f � � 2.
          Булева функция может быть задана при помощи:
          1. описания;
          2. таблицы истинности;
          3. формулы алгебры высказываний;
          4. множества истинности E f � � f �� 1 ,� 2 , ... ,� n � f �� 1 ,� 2 , ... ,� n � � 1�;
          5. набора значений;
          6. функциональной схемы.
          Рассмотрим пример, на котором проиллюстрируем указанные спосо-
бы задания булевых функций.

     Пример. Пусть булева функция f � x1 , x 2 , x 3 � принимает значений 1
на наборах �� 1 ,� 2 ,� 3 � , в которых большинство нулей, а на остальных на-
борах ее значение равно 0.
     Описанная функция может быть задана с помощью таблицы истин-
ности (рис. 1):
     В случае n переменных булева функция f ( x1 , x 2 ,..., x n ) задается таб-
                                                        n
лицей, содержащей 2 n строк, т.к. E n � E                   � 2 n . В дальнейшем всегда бу-
дем располагать наборы в таблице истинности так, как показано на рис. 2.

  x1    x2     x3     f ( x1 , x 2 , x 3 )   x1  … x2         x n �1   xn    f ( x1 , x 2 ,..., x n )
  0     0      0              1              0 0 …             0       0        f ( 0 ,0 ,...,0 ,0 )
  0     0      1              1              0 0 …             0       1        f ( 0 ,0 ,...,0 ,1 )
  0     1      0              1              0 0 …             1       0        f ( 0 ,0 ,...,1,0 )
  0     1      1              0              0 0 …             1       1         f ( 0 ,0 ,...,1,1 )
  1     0      0              1              … … …             …      …               …
  1     0      1              0              1 1 …             0       1        f ( 1,1,...,0 ,1 )
  1     1      0              0              1 1 …             1       0        f ( 1,1,...,1,0 )
  1     1      1              0              1 1 …             1       1        f ( 1,1,...,1,1 )
               Рис. 1                                              Рис. 2

         При фиксированном порядке расположения наборов ( � 1 ,� 2 ,...,� n ) в
таблице истинности всякая булева функция однозначно задается набором
своих значений. В нашем примере этот набор имеет вид f � ( 111 010 0 0 ).
         Заметим, что множество истинности E f , задающее функцию
 f ( x1 , x 2 ,..., x n ) , представляет собой n -местное отношение � на множе-
стве E . Оно задает булеву функцию по правилу:

                                                  17