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

                                                          82
Операция замыкания. Основные замкнутые классы.
__________________________________________________________________________________________
                      f ( x1 , ..., x n ) = f (σ , ,...,
                                                   ∧σ
                                                     1     n   )=0
                                                                     (x   σ1
                                                                          1
                                                                               ∨ x σ2 ∨ ... ∨ x σn ) ,
                                                                                     2            n
                                                                                                         (2)
где конъюнктивное произведение берется по всем наборам (σ 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 z 1 , x 0 y1 z 0 , x 1 y 0 z 0 ,
которые с учетом (1) перепишем в виде:
                                                               x y z , x y z, 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 .
   1       0     0     0              1                     Для построения СКНФ заме-
   2       0     0     1              1             тим, что рассматриваемая функция
   3       0     1     0              1             принимает значение 0 на наборах
   4       0     1     1              0             (011), (101), (110) и (111).
   5       1     0     0              1
   6       1     0     1              0
   7       1     1     0              0
   8       1 Таблица
                 1    11              0