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

                                                            Таблица 1
                  Номер         х         у        z       � �x , y , z�
                  набора

                     1          0         0        0           1
                     2          0         0        1           1
                     3          0         1        0           1
                     4          0         1        1           0
                     5          1         0        0           1
                     6          1         0        1           0
                     7          1         1        0           0
                     8          1         1        1           0

Построим соответствующие этим наборам элементарные дизъюнкции:
                         x0 � y1 � z1 , x1 � y0 � z1 ,
                         x1 � y1 � z0 , x1 � y1 � z1 ,
перепишем в стандартной форме:
                x � y � z , x � y � z , x � y � z , x � y � z.
     Конъюнктивное произведение этих дизъюнкций и есть СКНФ задан-
ной функции: K c � � x � y � z �� x � y � z �� x � y � z �� x � y � z �.

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

       Пример 2. Пусть f � x , y , z � � �011 010 01� . Найти СДНФ и СКНФ.
       Решение. Функция f принимает значение 1 на наборах с номерами
2, 3, 5, 8. Восстановим по формуле (3) эти наборы: (001), (010), (100), (111).
Объединим соответствующие этим наборам элементарные конъюнкции в
СДНФ: Dc � x y z � x y z � x y z � x y z .
       Значение 0 функция f принимает на наборах с номерами 1, 4, 6, 7.
Выпишем эти наборы: (000), (011), (110), (101). Конъюнкция соответст-

                                          32