Математическая логика и теория алгоритмов. Стенюшкина В.А. - 10 стр.

          2.2 Совершенная нормальная форма. Теорема существования и
          единственности

       Совершенной дизъюнктивной нормальной формой по переменным x1,…,
xn называется дизъюнктивная нормальная форма, у которой все элементарные
конъюнкции содержат каждую переменную ровно по одному разу (в прямом
или инверсном виде), и все конъюнкции различны.
       Совершенной конъюнктивной нормальной формой по переменным
x1,…, xn называется конъюнктивная нормальная форма, у которой все элемента-
рные дизъюнкции содержат каждую переменную ровно по одному разу (в пря-
мом или инверсном виде), и все дизъюнкции различны.
Пример - (x1 ∧ x2 ) ∨ ( x1 ∧ x2 ) - совершенная конъюнктивная нормальная форма
по x 1 , x2 .
      Теорема (существования и единственности) Для любой n-местной буле-
вой функции f(x1,…, xn)≢ 0 существует единственная совершенная дизъюнк-
тивная нормальная форма, реализующая эту функцию, и существует единст-
венная совершенная конъюнктивная нормальная форма, реализующая эту фун-
кцию.
      Доказательство Проверим выполнение следующего тождества по двоич-
ным переменным x1,…, xn:
                                                                                            δ1          δn
                   f ( x x ,..., x n ) ≡ ∨ (δ ,...,δ ) f (δ 1 ,..., δ n ) ∧ x1 ∧ ... ∧ x n ,
                                            1    n
                                                                                                                              (2.1)

       где правая часть есть дизъюнкция (по всем двоичным наборам (δ1,… ,
δn)) функций
                                                               δ            δ
                   F (δ 1 ,..., δ n ) = f (δ 1 ,..., δ n ) ∧ x1 1 ∧ ... ∧ xn n .

       Пусть (x1,…, xn)=(σ1,…, σn) ∈ ｛0,1｝n. Слева имеем f (σ1,…, σn). Заме-
тим, что для правой части будет выполняться равенство         σ 1 δ ∧ ... ∧ σ n δ = 1                         1           n



       тогда и только тогда, когда (δ1,…,δn)=(σ1,…, σn). Это означает, что дизъ-
юнктивные члены правой части, для которых (δ1,…,δn)≠(σ1,…, σn), можно опус-
тить. Правая часть становится равной f(σ1,…, σn) ∧1=f(σ1,…, σn). Итак, слева и
справа в (2.1) имеем f(σ1,…, σn). Если f(x1,…, xn) ≢ 0, то формула (2.1) эквивале-
нтна формуле
                                                                                                 δ1          δn
                            f ( x1 ,..., x n ) ≡ ∨ (δ ,...,δ
                                                       1       n ) f ( δ 1 ,...,δ n ) =1
                                                                                           ( x1 ∧ ... ∧ x n ).                  (2.2)

      Выражение справа есть совершенная дизъюнктивная нормальная форма.
Существование совершенной дизъюнктивной нормальной формы доказано.
Единственность доказывается от противного.
      Для булевой функции f(x1,…,xn) по тождеству (1) имеем:

          f(x 1,…,x n) = ∨ (δ 1,…,δ n ) (f(δ 1,…,δ n) ∧ (x 1δ 1,…,x nδ n)                                       (2.3)