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

Принцип двойственности. Если функция f реализована формулой Φ [ F ] = f (ϕ1 ,..., ϕ n ) над
системой F = { f1 ,..., f k } , то функция f ∗ реализуется формулой Φ∗ ⎡⎣ F ∗ ⎤⎦ = f ∗ (ϕ1∗ ,..., ϕn∗ ) над
системой F ∗ = { f1∗ ,..., f n∗ } , где Φ∗ ⎡⎣ F ∗ ⎤⎦ получается из Φ [ F ] заменой всех f i на fi ∗ .
Следствие. Если Φ1 = Φ 2 , то Φ1∗ = Φ ∗2 .
                                                         (                  )
        Пример 9. Пусть f ( x, y, z ) = x ∧ ( y ∨ z ) ↓ x ≡ z . Из принципа двойственности, с по-

мощью таблицы 4 получаем: f ∗                 ( x, y, z ) = x ∨ ( yz / x ⊕ z ) .
        Пример 10. В силу самодвойственности отрицания из тождества x ∧ y = x ∨ y немед-
ленно получаем тождество x ∨ y = x ∧ y .


                                                 Нормальные формы
      Понятие «нормальной формы» для формулы, реализующей некоторую функцию, под-
разумевает, прежде всего, синтаксически однозначный способ записи этой формулы. Нали-
чие у класса формул нормальной формы очень редкое, сильное и полезное свойство. Оно
обеспечивает разрешимость, то есть способность проверки равносильности формул. Для бу-
левых функций, например, нормальные формы позволяют по известным значениям функции
построить реализующую ее формулу.


                               Разложение булевых функций по переменным

        Обозначим через xσ = xσ ∨ xσ . Тогда

                                                             ⎧ x, σ = 1,
                                                        xσ = ⎨
                                                             ⎩ x , σ = 0.

В частности, xσ = 1 тогда и только тогда, когда x = σ .
      С помощью «степенной функции» xσ всякую булеву функцию f ( x1 ,..., xn ) можно
представить в виде
                       f ( x1 , x2 ,..., xn ) = x10 f (0, x2 ,..., xn ) ∨ x11 f (1, x2 ,..., xn ) =
                                    = x1 f (0, x2 ,..., xn ) ∨ x1 f (1, x2 ,..., xn ) ,

называемом разложением булевой функции f ( x1 ,..., xn ) по переменной x1 .
В самом деле, если x1 = 0 , то x10 = 1 , x11 = 0 и

       x10 f (0, x2 ,..., xn ) ∨ x11 f (1, x2 ,..., xn ) = 1⋅ f (0, x2 ,..., xn ) ∨ 0 ⋅ f (1, x2 ,..., xn ) = f (0, x2 ,..., xn ) .

Если x1 = 1 , то x10 = 0 , x11 = 1 и

       x10 f (0, x2 ,..., xn ) ∨ x11 f (1, x2 ,..., xn ) = 0 ⋅ f (0, x2 ,..., xn ) ∨ 1⋅ f (1, x2 ,..., xn ) = f (1, x2 ,..., xn ) .

      Обобщая формулу разложения булевой функции по нескольким переменным, пока-
жем, что справедлива следующая