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

      Определение. КНФ функции f � x1 , ..., x n � называется совершенной,
если она составлена из попарно различных элементарных дизъюнкций
ранга n , т.е. формул вида
                   f � x1 , ..., x n � � � � � � x1� � x 2� � ... � x n� � ,
                                                            1       2       n
                                                                             (2)
                                 f � 1 , ,...,� n � 0

где конъюнктивное произведение берется по всем наборам �� 1 ,� 2 ,...,� n � ,
для которых f �� 1 ,� 2 ,...,� n )  0. Ясно, что f � x 1 ,..., x n � � 1 .
         Формулы, стоящие в правых частях равенств (1) и (2), соответствен-
но называются совершенной нормальной дизъюнктивной и конъюнк-
тивной формами (СДНФ и СКНФ). В отличие от обычных форм каждое
слагаемое СДНФ или каждый сомножитель СКНФ содержит все перемен-
ные x1 ,..., x n в некоторых «степенях». Рассмотрим два способа их по-
строения.
         Первым способом совершенные нормальные формы для произволь-
ной булевой функции можно строить, исходя из представлений (1)–(2).
Для этого достаточно построить таблицу истинности функции. Для по-
строения СДНФ нужно выделить те наборы �� 1 ,� 2 ,...,� n � , на которых
 f �� 1 ,� 2 ,...,� n � � 1 . Каждому такому набору ставится в соответствие эле-
ментарная конъюнкция x1� & x 2� & ... & x n� . Составленная из этих конъ-
                             1      2                           n



юнкций дизъюнктивная сумма и есть искомая СДНФ.
     Для построения СКНФ нужно выбрать наборы �� 1 ,� 2 ,...,� n � , для ко-
торых f �� 1 ,� 2 ,...,� n � � 0 . Каждому такому набору ставится в соответст-
вие элементарная дизъюнкция x1� � x 2� � ... � x n� . Объединяя такие дизъ-
                                        1               2               n



юнкции в конъюнктивное произведение, получим СКНФ.

       Пример 1. Пусть функция � � x , y , z � принимает значение 1 тогда и
только тогда, когда большинство переменных равно нулю. Построим
СДНФ и СКНФ этой функции.
       Решение. Рассмотрим таблицу истинности заданной функции (таб-
лица 1):
       Функция � � x , y , z � принимает значение 1 на наборах (000), (001),
(010), (100). Этим наборам соответствуют элементарные конъюнкции
                        x 0 y 0 z 0 , x 0 y 0 z1 , x 0 y1 z 0 , x1 y 0 z 0 ,
которые с учетом (1) перепишем в виде: x y z , x y z , x y z , x y z .
Окончательно имеем СДНФ функции � � x , y , z � :
                        Dc � x y z � x y z � x y z � x y z.
     Для построения СКНФ заметим, что рассматриваемая функция при-
нимает значение 0 на наборах (011), (101), (110) и (111).


                                             31