Дискретная математика. Сергиевская И.М. - 7 стр.

Представления булевых функций разложениями по
переменным.
            Совершенная дизъюнктивная нормальная форма
(СДНФ) для булевой функции f ( x1 ,..., x n ) , не равной тождест-
венно нулю, имеет вид:
 f ( x1 ,..., x n ) = ∨ x1σ1 ...x nσ n ,
                       (σ1 ,...,σ n ):
                        f (σ1 ,...,σ n ) =1

где символ x σ определяется следующим образом:
      ⎧ x, если σ = 1,
xσ = ⎨
      ⎩ x , если σ = 0.
Алгоритм построения СДНФ.
1. Построить таблицу истинности данной булевой функции.
2. Каждому единичному значению булевой функции будет
    соответствовать элементарная конъюнкция x1σ1 x 2σ 2 ...x nσ n , где
    (σ 1 , σ 2 ,..., σ n ) – соответствующий набор значений перемен-
    ных. В конъюнкции мы записываем xi , если σ i = 1 , и xi ,
    если σ i = 0 . Конъюнкции соединяются знаком ∨ .

      Совершенная конъюнктивная нормальная форма
(СКНФ) для функции f ( x1 ,..., x n ) , отличной от тождественной
единицы, имеет вид:
f ( x1 ,..., x n ) =           ∧              ( x1σ1 ∨ ... ∨ x nσ n ) .
                       (σ1 ,...,σ n ):
                        f (σ1 ,...,σ n ) =0

Алгоритм построения СКНФ.
1. Построить таблицу истинности данной булевой функции.
2. Каждому нулевому значению булевой функции будет
   соответствовать        элементарная          дизъюнкция
     x1σ1 ∨ x 2σ 2 ∨ ... ∨ x nσ n , где (σ 1 , σ 2 ,..., σ n ) - соответствующий
                                                           7