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

     набор значений переменных. В дизъюнкции мы записываем
      xi , если σ i = 0 , и xi , если σ i = 1 . Дизъюнкции соединяются
     знаком ∧ .

            Всякая булева функция может быть представлена в виде
полинома Жегалкина:
 f ( x1 , x 2 ,..., x n ) = a0 ⊕ a1 x1 ⊕ ... ⊕ a n x n ⊕
⊕ a n +1 x1 x 2 ⊕ ... ⊕ a        x x ...x n ,
                            2n −1 1 2
где a 0 , a1 ,..., a n ,..., a            ∈ {0,1} , где знак ⊕ обозначает сумму по
                                 2 n −1
модулю 2.
Алгоритм построения полинома Жегалкина.
1. Построить таблицу истинности данной булевой функции.
2. Каждому единичному значению булевой функции будет
      соответствовать               конъюнкция        x1σ1 x 2σ 2 ...x nσ n , где
      (σ 1 , σ 2 ,..., σ n ) - соответствующий набор значений перемен-
      ных. Конъюнкции соединяются знаком ⊕ .
3. Заменить выражения xi по формуле: xi = xi ⊕ 1 . Раскрыть
      скобки и привести подобные слагаемые по правилу:
      x ⊕ x = 0.
Пример. Построить СДНФ, СКНФ и полином Жегалкина для
функции (11110011).
           Таблица истинности данной булевой функции приведена
на стр. 5.
           СДНФ имеет вид:
 f ( x, y, z ) = x y z ∨ x yz ∨ x yz ∨ x yz ∨ xyz ∨ xyz .
           СКНФ имеет вид:
 f ( x, y, z ) = ( x ∨ y ∨ z )( x ∨ y ∨ z ) .
           Построим полином Жегалкина:




                                                  8