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

                                           83
Операция замыкания. Основные замкнутые классы.
__________________________________________________________________________________________
       Построим соответствующие этим наборам элементарные дизъюнк-
ции:
         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 ) =(111 010 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). Конъюнкция соответст-
вующих этим наборам элементарных дизъюнкций является СКНФ задан-
ной функции:
                K c =(x ∨ y ∨ z )( x ∨ y ∨ z )(x ∨ y ∨ z )(x ∨ y ∨ z ).
       Рассмотренные примеры являются иллюстрацией к первому способу
построения СКНФ и СДНФ, основанному на представлениях (1) и (2).
Применяется он, как правило, для функций, заданных таблицей истинно-
сти или набором значений. Если же функция задана аналитически, т.е. при
помощи формулы, то для нее нужно сначала построить таблицу истинно-
сти, а затем применять описанный метод.
       Второй способ построения СДНФ и СКНФ состоит в эквивалентном
преобразовании формулы, реализующей функцию, к виду (1) или (2). Как
уже отмечалось, совершенные дизъюнктивная или конъюнктивная нор-
мальные формы функции f ( x 1 , ..., x n ) отличаются от обычных тем, что
каждое слагаемое СДНФ и каждый сомножитель СКНФ содержит все пе-