Функции алгебры логики. Стасюк В.В. - 12 стр.

          Пример 12. Разложим функцию f ( x, y, z ) = y (z ↓ xz ) из примера 11 по всем пере-
менным.         Так        как      функция         принимает    значение    1    на   трех   наборах:
 f (0, 0, 0) = f (1, 0, 0) = f (1, 0,1) = 1 , то согласно следствию из теоремы о разложении, имеем

                                  f ( x, y , z ) = x 0 y 0 z 0 ∨ x1 y 0 z 0 ∨ x1 y 0 z1 = x y z ∨ x y z ∨ x y z .

Итак, y (z ↓ xz ) = x y z ∨ x y z ∨ x y z .
      Определение. Разложение булевой функции f ( x1 ,..., xn ) по всем переменным в виде

                                                                                 ∨
                                                                          f (σ 1 ,...,σ n ) = 1
                                                                                                  x1σ1 ∧ ... ∧ xnσ n


называется совершенной дизъюнктивной нормальной формой (СДНФ).
      Пример 13. x y z ∨ x y z ∨ x y z — СДНФ для функции f ( x, y, z ) = (1000 1100) (см.
пример 12).

         Теорема 3. Всякая булева функция (кроме 0) имеет единственную СДНФ.

Доказательство. Согласно следствию из теоремы о разложении

                 f ( x1 ,..., xn ) =                   ∨
                                                f (σ 1 ,...,σ n ) = 1
                                                                        x1σ1 ∧ ... ∧ xnσ n f (σ 1 ,..., σ n ) =                     ∨
                                                                                                                             f (σ 1 ,...,σ n ) = 1
                                                                                                                                                     x1σ1 ∧ ... ∧ xnσ n .


       Замечание. Если под дизъюнкцией одного слагаемого понимать само это слагаемое,
то дизъюнкции нуля слагаемых не существует, поэтому не существует СДНФ для функции 0.
       При построении СДНФ имеет место следующее
       Правило единицы. Рассматриваются только те наборы аргументов, на которых
функция f ( x1 ,..., xn ) принимает значение 1; для каждого такого набора в СДНФ делается за-
готовка слагаемого x1 ∧ ... ∧ xi ∧ ... ∧ xn . Если в данном наборе аргументов xi ≠ 1 , то над пере-
менной xi в заготовленном слагаемом навешивается отрицание: x1 ∧ ... ∧ xi ∧ ... ∧ xn .
      Теорема 4. Всякая булева функция может быть выражена через дизъюнкцию, конъ-
юнкцию и отрицание:
                                ∀f ∈ Pn ∃Φ ⎡⎣{∨, ∧, ¬}⎤⎦ : funcΦ = f .

Доказательство. Если f ( x1 ,..., xn ) = 0 , то f ( x1 ,..., xn ) = x1 ∧ x1 . Если f ( x1 ,..., xn ) ≠ 0 , то
f ( x1 ,..., xn ) =          ∨
                      f (σ 1 ,...,σ n ) = 1
                                              x1σ1 ∧ ... ∧ xnσ n .
      Теорема 5. Всякая булева функция (кроме 1) может быть единственным образом вы-
ражена в виде совершенной конъюнктивной нормальной формы (СКНФ):

                                                        f ( x1 ,..., xn ) =                  ∧
                                                                                     f (σ1 ,...,σ n ) = 0
                                                                                                             (x   σ1
                                                                                                                  1    ∨ ... ∨ xnσ n .)
Доказательство. Если f ( x1 ,..., xn ) ≠ 1 , то f ∗ ( x1 ,..., xn ) ≠ 0 и

                                                         f ∗ ( x1 ,..., xn ) =                    ∨
                                                                                         f ∗ (σ1 ,...,σ n ) = 1
                                                                                                                  x1σ1 ∧ ... ∧ xnσ n .
Применив к последнему тождеству принцип двойственности, находим